Sunday, October 20, 2013

A quick audit of CryptoCat's elliptic curve crypto

A few days ago I saw CryptoCat was featured on the New York Times. That reminded me of a quick audit of the chat software that I did several weeks ago. I thought I'd share my notes, since I have no plan in continuing the audit. Hopefully somebody would pick up what I found, and do something useful with them. Note that I just read the code and take notes, but haven't actually verified if the bugs work or their impacts. A copy of this blog post has been sent to CryptoCat.

First off, CryptoCat's engineering practices look bad to me. It seems that the CryptoCat team just throws together things until it works then move on [1]. They have, let me count, exactly 4 tests for the whole program. They mix Curve25519 with P-256, e.g., they call a function Curve25519.ecdsaVerify, but it actually implements (insecurely) ECDSA's signature verification over P-256. Last but not least although I like reading crypto code theirs is so clumsy that I gave up after a few minutes.

The fact that Javascript rarely complains about typing or out-of-bound access issues makes it both hard and interesting to write secure crypto code in this language. The only ways I know to catch these bugs are: writing more tests, using pseudo typing system provided by Javascript compilers such as Google Closure, and using a single data type such as Uint8Array for all inputs and outputs. Failure to do any of these will result in serious bugs. I've seen a Javascript implementation of AES that leaks secret keys because it forgets to check that some input is indeed an array of bytes. CryptoCat doesn't do any of these, which made me very doubtful of its crypto. So I took a look, and here's a few problems that I found in CryptoCat's elliptic curve crypto library [2]:

1/ Curve25519.ecdsaGenPrivateKey (line 187) generates private keys that aren't in the correct range. I don't think this is a vulnerability, but it's still a mistake that should be avoided.

2/ Curve25519.ecdsaSign calculates the hash of the to-be-signed message as follows (line 347):

m = BigInt.mod(CryptoJS.SHA512(JSON.stringify(message)).toString(CryptoJS.enc.Hex).substring(0,32), n256)

I could see there are two "type confusion" bugs here:

2.1/ A 512-bit hash is converted to hex of which a substring of 32 byte is returned. That means the hash is reduced to only 128-bit. Thus, the security level of this implementation of ECDSA would be only 64-bit.

2.2/ A string is used as a BigInt. I haven't reviewed BigInt so I don't know how large the impact could be. If there's a way to make m equal to zero bug #3 would be exploitable.

A few days after I looked at this function somebody reported a vulnerability in it [3]. It seemed that CryptoCat's lead developer didn't know what this function does - he had to consult an anonymous cryptographer that contributed this code. He decided to comment out the function, and added a warning, which is amusing because it's mostly fine, as there's no modular reduction in the way it generates the nonces (line 352). The nonces may not be in the correct range, but that's a non-security issue. which is cool. Although it isn't apparent, the nonce will always be modular reduced by the order of the group so they'll be biased.

3/ Curve25519.ecdsaVerify incorrectly verifies the signature: a pair of (n256, n256) or negative numbers would pass all the range checks (line 394). This is bad, and it's only sheer luck that makes the bug seem unexploitable. The call to BigInt.inverseMod (line 398) returns null if s is divisible by n256. That makes the next line throw an exception. Otherwise (n256, n256) would have been accepted as a valid signature for all messages.

Update: CryptoCat's response.

[1] I'm quoting Rasmus Lerdorf, the creator of PHP. The full quotation is: "I'm not a real programmer. I throw together things until it works then I move on. The real programmers will say "Yeah it works but you're leaking memory everywhere. Perhaps we should fix that." I’ll just restart Apache every 10 requests.".

[2] I chose this library because I've worked on ECC recently. Originally I wanted to look at the BigInt library, but it seems that CryptoCat just copies it from somewhere else.

[3] If you implement DSA/ECDSA be aware of this attack. Bleichenbacher once said that he only needed a fraction of a bit of each nonce to calculate the private key, given enough signatures.

No comments: