Tarsnap had a CTR nonce collision. It's a bad bug that's fairly common and easy to explain.
CTR mode turns AES into a stream cipher, meaning it can encrypt a byte at a time instead of 16 bytes at a time. It does this by using the block cipher core to encrypt counters, which produces a "keystream" that you can XOR against plaintext to use as a stream cipher.
For this to be secure, as with any stream cipher, it is crucial that the keystream never repeat. If you encrypt two plaintexts under the same keystream, you can XOR them together to cryptanalyze them; even easier, if you know the contents of one of the plaintexts, you can XOR the known plaintext against the ciphertext to recover the keystream!
To avoid repeating keystreams, CTR mode uses a nonce, which is a long cryptographically secure random number concatented to the counter before encrypting.
To avoid that catastrophic security bug, CTR mode users have to make sure the nonce never repeats (and also that the counter never repeats, e.g. by wrapping). We have found both bugs multiple times in shipping products, and now Colin found it in his product.
And so I come to the moral of my story: Colin is clearly a gifted crypto dev. He can talk lucidly and at length about the best ways to design crypto-secured protocols. He has found crypto flaws in major systems before. He is as expert as you could expect anyone to be on any product.
And Colin didn't get it right; what's more, the manner in which he got it wrong was devastating (in cryptographic terms).
Colin handled this well, largely due to the fact that he's an expert and knows how to handle it.
How likely is it that anyone less capable than Colin could have handled it so well? Moreover, if Colin can make a devastating mistake with his crypto code, how many worse mistakes would a non-expert make?
You should avoid writing crypto code if at all possible. Nate Lawson is fond of saying, "you should budget 10 times as much to verification as you do for construction of cryptosystems"; I would amend that only to add a price floor to it, because you cannot get real validation of a cryptosystem for less than many tens of thousands of dollars --- if your system is simple.
What should you do if you can't avoid writing crypto code?
I found myself in this situation when I tried to find a bcrypt implementation for Common Lisp. There wasn't one. Folks in #lisp suggested I adapt the blowfish implementation in Ironclad, since 'bcrypt is just blowfish anyway'.
1) Both the current C implementations are designed to be integrated into libc. The Openwall implementation does have the code factored out into its own file, but there is no support structure for building a shared library. (Python's bcrypt bundles a modified version of the Openwall C source directly with it, for example.) Common Lisp's FFI is intended for working with installed shared libraries
2) There appears to be a bias in the Lisp community towards pure-Lisp implementations, for (hopefully obvious) reasons, so an implementation as hacky as what I came up with is unlikely to see much use.
If I do go back to trying to write a webapp in Common Lisp, I think I will find myself having to reimplement bcrypt in Common Lisp. First, I'll have to find a sufficiently portable method of getting cryptographically secure random numbers; as of the writing of that blog post, there wasn't one that I could find anyone recommending. The more difficult part will be to convert the C code into Lisp code without missing any places where operations on the C types don't precisely correspond to the same operations on the Lisp types (due to, say, overflow).
I'm worried I might get something wrong, but I can't just use the crypto code written by wiser folks than I, because, at least in the Common Lisp community, that code doesn't seem to exist.
First, don't obsess too much about your password digest. I know this is head-explodey considering the source, but all I'm trying to do by ranting about it is to get people to stop using SHA1 (or SHA256 or Whirlpool or whatever) hashes. The risk to your users for doing that bit wrong is not very high.
Second, my advice about how to do crypto security is very simple:
* Use PGP for data at rest.
* Use TLS for data in motion.
Do not trust your own judgement (say, by using OTR because it "feels" like most of what you need, or trusting that you'll use Keyczar safely) on anything else without a formal external review. In practice, you will almost never need anything more than TLS or PGP.
Okay, but in the more general case, where something literally does not exist for a particular platform/language and my choices are "write it myself" or "don't use that platform/language", is there any way to feel confident that a choice to write it myself will not be a hideously wrong decision?
I'm not Thomas Ptacek, but I think his answer would be something to the effect of "to be really confident, get tens of thousands of dollars worth of code review before shipping." You may be prominent enough in the CL/hypothetical crypto-less platform community to get most of that for free, but that's the value of the validation needed.
If you're trying to make something in pure Lisp, your odds of failure are less if you take an existing hashing algorithm (e.g. SHA-256) and just iterate it a bunch of times. Ironclad has SHA-256, so this is really easy:
(defun slow-hash (password salt &key (iterations 10000))
"Produces a 256-bit hashed value of password and salt, slowly. Uses
a tweakable number of iterations, which should not be less than
1000, and which defaults to 10000."
(let ((hash (ironclad:make-digest :sha256)))
;; First, hash the salt and password
(ironclad:update-digest hash
(ironclad:ascii-string-to-byte-array salt))
(ironclad:update-digest hash
(ironclad:ascii-string-to-byte-array password))
;; Repeatedly hash the hash, to slow things down
(dotimes (x iterations)
(ironclad:update-digest hash (ironclad:produce-digest hash)))
(ironclad:produce-digest hash)))
Even after one round, repeating that knocks down your plaintext-space to 256 bit strings (or however long the output is of the hash function that you are using). Tom/Colin, is this actually a problem?
That's the case for every hash function. If it's a good hash function, the outputs will be evenly distributed across the entire 256 bit space, which comes out to 2^256 possible outputs. I don't think this is a problem; bcrypt has a much smaller output space.
1. It should be fairly trivial to test that your implementation is giving exactly the same output as the c libs (once you have chosen a particular random number that feeds into the algorithm). It seems like the trickiest part of testing will be ensuring that you are using the same character set everywhere.
2. Why is it important to have a "cryptographically strong" PRNG? Doesn't this just turn into a salt? Does a salt generator really need to be cryptographically strong?
Someone please correct me if I am being naive here.
1. I worry I might have a bug that returns the proper output for some inputs, but improper output for other inputs.
2. Cryptographically strong random numbers isn't strictly required for a bcrypt salt, I guess. But if I'm building something which I plan to share with other people, I'd rather err on the side of too strong.
In cryptography you should always use a "cryptographically strong" PRNG, even (especially) if in doubt. There have been to many mistakes with lousy random number generators undermining what would otherwise have been a strong security mechanism.
But we're talking about generating a salt here. As I understand it, the reason you use a salt is to make it much harder to brute-force a dictionary of passwords ahead of time. I don't see how the use of a cryptographically strong PRNG is going to provide any additional security here.
Nonces aren't cryptographically secure random numbers. They merely have to be different for each encryption, which is why even a counter suffices. The problem was, the counter was being incorrectly reset to zero.
It's just as secure to concatenate a string that is a function of the time of day with the counter. Another scheme would be to start out with a cryptographically hard number that is incremented each time.
The problem was, the counter was being incorrectly reset to zero.
The counter was being correctly reset to zero. The nonce was being incorrectly not set to non-zero. (In CTR mode, there is a 64-bit nonce which is different for each message and a 64-bit counter which starts at zero for each message and increments as you move through the message.)
The mistake he made is not specifically a "crypto code" problem, it was merely forgetting to increment the new variable, and that kind of thing happens in a lot of non-crypto contexts. I think that the reason people should use tested and well-known crypto code is because the stakes are high and not necessarily because cryptography is super complex; a mistake like this can have serious consequences since most encrypted data is serious by nature. As such, the maxim "don't write your own crypto" could also be applied to any high stakes programmatic endeavor; if you can't tolerate any downtime on your server, "don't write your own server", etc.
The great thing about widely used open-source utilities is the extensive vetting they receive. I was a bit uncomfortable using tarsnap's custom client and now I'm happy I went with duplicity, which is a Python script combining rsync, tar, and gpg to create encrypted archives of your data and only send the differences.
Also, perhaps Colin could look into writing a test suite for tarsnap that would automatically test for mistakes like this. It doesn't sound like the particular applicable exploit is too hard to automate.
This is a head-explodey subthread. Sure, Colin, O.K., it wasn't a "crypto mistake", it was a "refactoring mistake that happened to basically turn off your crypto". The fact that perfectly innocent and benign seeming refactoring changes can do that to crypto is exactly why generalist developers should not be writing crypto code.
I've seen major security vulnerabilities result from losing a single '=' (turning "if (uid == 0)" into "if (uid = 0)") or adding a single '=' (turning "for (...; i < N; ...)" into "for (...; i <= N; ...)"). That's half the typo size of a missing '++'.
Sure, writing crypto code is dangerous. And writing user-authentication code is dangerous. But are you seriously going to say that writing loops is dangerous and generalist developers shouldn't do it?
If the underhanded C contest taught us anything, it's that perfectly innocent and benign seeming changes can introduce security vulnerabilities anywhere.
If you ask me, "should developers avoid writing web applications in C because it's virtually always unnecessary and practically guarantees memory corruption vulnerabilities", what do you think my answer is going to be?
Are we to understand that "crypto developers" never forget to increment something or never have copy-paste errors? It seems most of the difference between a "generalist developer" and a "crypto developer" is the amount of money his employer puts into QA.
You are right. I use duplicity for remote backups too, I can really recommend it :)
However, in crypto the 'NIH' syndrome is especially prevalent because of the inherent secrecy and paranoia. Especially as there are still a lot of people on the obscurity side of security versus obscurity. A good recent example of this would be Sony...
CTR mode turns AES into a stream cipher, meaning it can encrypt a byte at a time instead of 16 bytes at a time. It does this by using the block cipher core to encrypt counters, which produces a "keystream" that you can XOR against plaintext to use as a stream cipher.
For this to be secure, as with any stream cipher, it is crucial that the keystream never repeat. If you encrypt two plaintexts under the same keystream, you can XOR them together to cryptanalyze them; even easier, if you know the contents of one of the plaintexts, you can XOR the known plaintext against the ciphertext to recover the keystream!
To avoid repeating keystreams, CTR mode uses a nonce, which is a long cryptographically secure random number concatented to the counter before encrypting.
To avoid that catastrophic security bug, CTR mode users have to make sure the nonce never repeats (and also that the counter never repeats, e.g. by wrapping). We have found both bugs multiple times in shipping products, and now Colin found it in his product.
And so I come to the moral of my story: Colin is clearly a gifted crypto dev. He can talk lucidly and at length about the best ways to design crypto-secured protocols. He has found crypto flaws in major systems before. He is as expert as you could expect anyone to be on any product.
And Colin didn't get it right; what's more, the manner in which he got it wrong was devastating (in cryptographic terms).
Colin handled this well, largely due to the fact that he's an expert and knows how to handle it.
How likely is it that anyone less capable than Colin could have handled it so well? Moreover, if Colin can make a devastating mistake with his crypto code, how many worse mistakes would a non-expert make?
You should avoid writing crypto code if at all possible. Nate Lawson is fond of saying, "you should budget 10 times as much to verification as you do for construction of cryptosystems"; I would amend that only to add a price floor to it, because you cannot get real validation of a cryptosystem for less than many tens of thousands of dollars --- if your system is simple.