Tarsnap critical security bug

Tarsnap versions 1.0.22 through 1.0.27 have a critical security bug. It may be possible for me, Amazon, or US government agencies with access to Amazon's datacenters to decrypt data stored with those versions of Tarsnap. This is an absolutely unacceptable compromise of Tarsnap's security principles, and I sincerely apologize to everyone affected.

There's a lot to say about this, and it's entirely possible that I'll miss covering some important points in this post; if I've missed something, please email me or post a comment below and I'll do my best to add the necessary information.

The bug

Tarsnap archives data by first converting it into a series of "chunks" of average size 64 kB; next compressing and encrypting each chunk; and finally uploading those chunks. The encryption is performed using a per-session AES-256 key in CTR mode.

In versions 1.0.22 through 1.0.27 of Tarsnap, the CTR nonce value is not incremented after each chunk is encrypted. (The CTR counter is correctly incremented after each 16 bytes of data was processed, but this counter is reset to zero for each new chunk.)

How the bug happened

Up to version 1.0.21 of Tarsnap, AES-CTR was used in two places: First, to encrypt each chunk of data; and second, in the Tarsnap client-server protocol. In version 1.0.22 of Tarsnap, I introduced passphrase-protected key files, which used AES-CTR encryption (with a key computed using scrypt).

In order to simplify the Tarsnap code — and in the hopes of reducing the potential for bugs — I took this opportunity to "refactor" the AES-CTR code into a new file (lib/crypto/crypto_aesctr.c in the Tarsnap source code) and modified the existing places where AES-CTR was used to take advantage of these routines.

It is at this point where the bug slipped into the chunk-encryption code (crypto_file_enc in lib/crypto/crypto_file.c):

        /* Encrypt the data. */
-       aes_ctr(&encr_aes->key, encr_aes->nonce++, buf, len,
-           filebuf + CRYPTO_FILE_HLEN);
+       if ((stream =
+           crypto_aesctr_init(&encr_aes->key, encr_aes->nonce)) == NULL)
+               goto err0;
+       crypto_aesctr_stream(stream, buf, filebuf + CRYPTO_FILE_HLEN, len);
+       crypto_aesctr_free(stream);
The encr_aes->nonce++ turned into encr_aes->nonce, and as a result the same nonce value was used repeatedly. (The other places where Tarsnap uses AES-CTR — in the client-server protocol and in the handling of passphrase-protected key files — are not affected by this bug.)

Impact of the bug

As stated above: It may be possible for me, Amazon, or US government agencies with access to Amazon's datacenters to decrypt data stored with affected versions of Tarsnap. Other individuals/agencies are unlikely to be able to decrypt data for the simple reason of being unable to access the encrypted data: Amazon Web Services is considered to be sufficiently secure to handle medical records and credit cards, and while I often remind people that regulatory compliance is not at all the same thing as security, in this case I think they align fairly accurately. (Note that since the Tarsnap client-server protocol is encrypted, being able to intercept Tarsnap client-server traffic does not provide an attacker with access to the data.)

There are two ways of decrypting AES-CTR data when the nonce is reused: By comparing two ciphertexts, or by using a known plaintext. In the first case, the ciphertexts A xor C and B xor C are compared to yield the exclusive OR of the two plaintexts, A xor B. If the plaintexts are English text or otherwise have a small amount entropy, this usually enough to allow both plaintexts to be extracted — in fact, this is one of the methods which was used by British codebreakers in the second world war. However, the blocks which Tarsnap encrypts do not have low entropy: Tarsnap compresses its chunks of data before encrypting them. While the compression is not perfect (there are, for instance, some predictable header bits), I do not believe that enough information is leaked to make such a ciphertext-only attack feasible.

Given a known plaintext, however — that is, if the attacker knows any block of data which was encrypted — then the attack is trivial: They need only compare the plaintext against corresponding ciphertext block to recover the AES-CTR keystream, which can then be used to decrypt other blocks of data. If Tarsnap is used to perform complete system backups, there will be many such plaintexts — files belonging to the operating system and the Tarsnap binary itself are obvious examples — but if Tarsnap is used selectively then it is possible that the attacker will have no such plaintext at his disposal.

Because Tarsnap uses per-session AES keys for encrypting blocks of data, this bug affects only data uploaded using affected versions of Tarsnap, and the known-plaintext attack will only endanger data uploaded during the same archive when the known plaintext is uploaded; so it is possible that an attacker would be able to decrypt some data but not all.

What Tarsnap users should do

Tarsnap users should immediately upgrade to version 1.0.28.

Tarsnap users who wish to re-encrypt their stored data should register a new machine using tarsnap-keygen, upload their data using the newly generated keys, and then delete the old data by running tarsnap --nuke with the old keys. (Note that creating a new archive with the same set of keys will not cause data to be re-encrypted and uploaded, since Tarsnap's de-duplication will recognize the duplicated data.) Anyone wishing to do this should contact me via email so that I can provide a Tarsnap account credit to cover the bandwidth fees which would otherwise be charged. (Of course, if the US government wants your data, re-encrypting it and deleting the old version from Tarsnap won't force them to delete any copies they have made — but it might help you if the US government doesn't realize that it wants your data yet.)

Tarsnap users who wish to stop using Tarsnap should delete their stored data by running tarsnap --nuke and contact me via email for a refund.

Tarsnap users with any other questions or concerns should contact me via email, twitter, IRC, or any other convenient form of communication.

What I'm doing about this

After being contacted on Friday afternoon and confirming the bug, I immediately re-checked all of the Tarsnap crytographic code; I found no other bugs. Of course, this can't guarantee that there are no subtle issues lurking; but at least it makes very unlikely the possibility that other similarly obvious problems exist.

I've also added "double-check all changes to critical security code, even if they are 'cosmetic' or 'refactoring' changes" to my pre-release checklist. When I wrote the original chunk-encryption code, I reviewed my work very carefully to make sure that I got it right — and it was right for two years, until I accidentally introduced this bug while making what I thought was an insignificant change. This is an important lesson to learn: Mistakes can happen any time a piece of code is modified.

Finally, I am instituting a Tarsnap bug bounty (complete details to follow in a later blog post). This bug was found and reported to me by someone who was reading the Tarsnap source code purely out of curiosity — I'm a great fan of curiosity, but I've also learned that money can help to encourage curiosity. While I hope that I this is the last time I have to pay out a bounty for a security bug, if there are other bugs I hope this bounty will result in them being found sooner rather than later.

Final remarks

I will not attempt to decrypt and read your data. Amazon claims that it does not inspect Amazon Web Services users' data. And the US government is theoretically bound by a constitution which prohibits unreasonable searches. This is all, however, entirely irrelevant: The entire point of Tarsnap's security is to remove the need for such guarantees. You shouldn't need to trust me; you shouldn't need to trust Amazon; and you most certainly shouldn't need to trust the US government.

This was a very easy mistake to make. Anyone could have made it. It was also a very easy mistake to find. I should have found it, 19 months ago, before releasing version 1.0.22 of Tarsnap. I didn't, and I'm sorry.

I'd like to thank Taylor R Campbell for bringing this bug to my attention.


Some questions I've been hearing, aggregated here so that people can stop asking them:

Posted at 2011-01-18 21:05 | Permanent link | Comments

Inequality in Equalland

Life in the nation of Equalland (population 80 million) is idyllic. Boring, but idyllic. By all measures, it is a wonderful place to live: Zero infant mortality; 100% high school graduation; 100% college graduation; zero unemployment; zero income inequality; a steadily rising stock market; no poverty; etc. There is one measure which raises some eyebrows, however: The wealthiest 20% of households own well over 50% of the nation's wealth.

Every resident of Equalland has the same life story. From birth until age 18, they live with their parents, earning nothing and spending nothing — their parents cover all their needs. At age 18, they graduate from high school, become independent of their parents, and go to college. The government of Equalland funds the post-secondary system well enough that it can provide free tuition to students, but the college students of Equalland want to study full-time, so they take out student loans to cover their living expenses. At age 22 they graduate from college, get married, and have children (in Equalland, women always give birth to pairs of twins, one male and one female, in order to keep the gender ratio fixed at 1:1). They immediately find jobs, and work until age 65, all earning the same constant (inflation-indexed) salary, gradually saving up enough money (which they invest in the stock market) to pay for their retirement. At age 65 they retire, and they gradually spend their retirement savings until age 80, when they die peacefully in their sleep and their few dollars of remaining retirement savings are spent on funeral costs.

To provide a more concrete picture of the household economics of Equalland, here's some more numbers (dollar values are inflation-adjusted, i.e., expressed in constant "2011 dollars"):

From these numbers, we can obtain a complete picture of the wealth of Equalland:

The most indebted households in Equalland — $130,133 in debt, to be precise — are those formed by 22 year olds; not only have they spent 4 years taking student loans while studying at college, but they have also just married, thus doubling their per-household debt. The average household, in contrast, has a comfortable $206,080 in retirement savings.

But what of the wealthiest? Out of the 33 million households in Equalland, the wealthiest 20% — 6.6 million households — are aged between 58 years 5 months and 71 years 8 months: In short, those who are either about to retire or recently retired. Their average wealth is $693,182 — over triple the average wealth — and between them, they hold 4.58 trillion dollars out of Equalland's total 7.13 trillion dollars of household wealth... or slightly over 64%. So much for equality.

Obviously no such country exists, and most countries have significantly higher wealth inequality — in the US, for example, the top 20% of households own 84% of the wealth. But consider this: Equalland is an idealized scenario. If the stock market didn't rise consistently, or some people lived beyond age 80, or some people had significant medical costs in their final years — or, god forbid, there was any variability in how much individuals earned — then the top 20% of the population would need to hold more than 64% of the country's wealth just to maintain their standard of living after retiring.

Is there too much inequality in the world? Sure. Is all inequality bad? Not if you hope to retire some day.

Posted at 2011-01-10 03:00 | Permanent link | Comments

Recent posts

Monthly Archives

Yearly Archives