DecryptoCat

Update: added text and removed text.

TLDR: If you used group chat in Cryptocat from October 17th, 2011 to June 15th, 2013 assume your messages were compromised. Also if you or the person you are talking to has a version from that time span, then assume your messages are being compromised. Lastly I think everyone involved with Cryptocat are incompetent. I feel bad about calling them incompetent, but it is true. If you mess up in all the places I cared to check... that's incompetence. Wow this apology is really not helping.

DecryptoCat v0.1 cracks the ECC public keys generated by Cryptocat versions 1.1.147 through 2.0.41. Cryptocat version 2.0.42 was released Feb 19, 2013 which increased the key space from 2^54.15 to 2^106.3. Decryptocat takes advantage of a meet-in-the-middle attack called baby-step giant-step you can effectively square root the key space. So 2^54.15 turns into 2^27.08 and 2^106.3 to 2^53.15. For Cryptocat versions before 2.0.42, doing a split of 2*10^9 and 10^7 it takes about a day to calculate data needed to crack any key in few minutes. This only requires tens of gigabytes to store. Doing a 2*10^8 and 10^8 split it will take an hour to generate and half an hour to crack any private key with that data. I suggest doing a 2*10^8 and 10^8 split unless you actually have a bunch of captured conversations or you want to test if the people you are talking to have upgraded. For Cryptocat version 2.0.42 this will take 1000 computer-years to generate, 500 computer-years on average to use, and 40 petabytes to store. So the only ones capable of doing this are large companies and governments. If there is a next version I'll probably "steal" some code from curve25519-donna and add support for GPUs.

What is wrong with Cryptocat?

Cryptocat is run by people that don't know crypto, make stupid mistakes, and not enough eyes are looking at their code to find the bugs. Cryptographers know the minimums or at least know you should look them up. Cryptocat tried PBKDF2, RSA, Diffie-Hellman, and ECC and managed to mess them all up because they used iterations or key sizes less than the minimums. There was a bug in the generation of ECC private keys that went unchecked for 347 days. They seem to not understand simple programming concepts such as a byte vs a decimal digit character: "Fix inaccurate comment". Both comments are wrong since "Cryptocat.randomString(64, 0, 0, 1, 0)" generates a string that is 64 decimal digits which is 212.6 bits or 26.6 bytes.

The bug that lasted 347 days was the confusion between a string and an array of integers. This made the ECC private keys ridiculously small because they passed a string of decimal digits into a function expecting an array of 17, 15 bit integers. Each character was considered an element in the array. So each of those "15 bit integers" were only the values 0 to 9 (3.32 bits). Also the least significant 3 bits are zeroed giving you a key space of 2*10^16 (2^54.15).

When they fixed that bug the commit message was: "Fix private key format to match curve25518-donna. THIS BREAKS COMPATIBILITY WITH PREVIOUS CRYPTOCAT VERSIONS." Even though this does not break compatibility at all. I don't know if they knew what they fixed and just wanted to slide this under the radar or they legitimately believe that. Both are scary one is violating their principles "Cryptocat is developed under a principle of radical transparency" and the other is just incompetence. There is a blog post by them saying this is inaccurate. Apparently they have too many serious bugs to keep straight. That they don't know which one breaks compatibility. The other error in the change log for version 2.0.42 is a bug where the counter in AES-CTR is reused. This means the first 32 bytes of your messages are easy to decipher with no effort at all. Which breaks compatibility, but everywhere they mention compatibility they say key generation.

Since that fix still wasn't good enough to be considered safe, 1500 computer-years and 40 petabytes of disk space to break, I gave them a simple patch but for some reason they decided to modify it. Private keys were 16^64/32, 251 bits, but they changed it to 10^64/8, 209.6 bits, this is still safe but this answers the previous question. They are completely incompetent.

Lastly, they generate random data by first generating a random floating point number instead of random bits or bytes. I don't know of any legitimate crypto software that does this. The following has been updated to reflect changes they made since they read this. They generating a random floating point number by getting 16 7 random bytes of data with values less than 250 and converting each of them to a single decimal digit. This is basically wasting 15 5 or 6 random bytes every time they generate a random floating point number because they then use it to generate a character from a small list of characters or a 15 bit integer. They generate one of three types of strings: decimal digits, hex digits, and base 62. I just searched their code for "Cryptocat.random()" just to make sure they weren't using that anywhere dumb... "var cnonce = MD5.hexdigest("" + (Cryptocat.random() * 1234567890));" I give up... well at least they didn't floor that so you get the full 10^16 2^53 from Cryptocat.random(). Ohh oops that wasn't even written by them or was used in anything that needed to be secure. Well I did say I give up... at least that was true :).

Here's the short version with basic changes to the hardness to crack:

Here's the long version that describes each change:

Yes this is scary but I believe everything is/was over https. So this just means that it was host based security. Meaning we have to trust that Cryptocat didn't store/transfer encrypted messages or leak their SSL private key. They should generate a new private key, to prevent someone from breaking into their server and stealing it. Which might let them decrypt old captured messages.

30 82 02 0a 02 82 02 01 00*
a8 0c 84 72 5f bf 5d 79 32 ac f4 d5 2e e6 01 b1
24 c2 1a 87 90 1f 46 cb 65 2c ad aa e3 70 ed 58
2e d6 25 39 5f 0e 8a 7d 9a d0 06 2f 50 5d 57 61
23 d9 7d cc b6 a7 37 a7 15 3b 17 47 95 68 8a ef
38 2c 8a c9 1e 4a 0a 4a 89 33 5c 3e 6b 15 0b 53
b3 ab 75 35 ec ab 10 e6 37 0c 7e a4 cf d6 cc 88
4c cc 03 cb ae 65 21 c7 bc 77 5e 30 3a 54 ac 29
92 48 61 aa 6b 59 f6 e1 9e 88 f5 18 17 57 56 41
ca dd 90 bd cc 2f 2b 95 84 6b e8 06 9d ed bb ac
aa b0 40 61 08 26 0c d8 46 ae 22 1c ab 05 c2 11
7c 37 c7 3f 02 8a 0a 8a de 4d 6e c7 ad dc b6 46
c4 17 6a a8 4d 9c b0 31 d8 ad b0 94 ae eb 61 fe
a9 f3 76 3c 68 ff 73 60 b2 6e f7 58 20 c5 0a 99
31 8c 5d 3f ec e9 22 2a d5 8f f1 6b c2 1f 20 bc
bf bb 87 f7 fb dd 51 65 42 53 8c 56 b9 85 5a 6e
3a f4 58 d5 29 7e 17 df 48 24 a0 6f a1 3e 9b c3
5b 9b 30 f4 af 99 4b 5d c4 2f 52 54 42 65 cb 47
76 a7 52 9d a2 cd 6c 01 5b 63 07 8e 85 71 3f 23
73 95 1c 7c 5f aa ec c6 ff 27 a4 60 a0 3d c6 1f
d5 83 3f fe 68 69 47 c0 50 1c 37 1f 4a be 89 9c
e0 85 37 eb 5c 1a c2 bb b2 51 30 3b 2b ee 50 c5
20 9c f1 85 31 71 b9 5a 5d 89 68 da e6 54 c3 66
4e df be 5f eb e1 17 60 5e 4e 8a d5 28 1d 02 91
0f 53 43 ed f6 20 8f ec bd 64 b8 9f e2 81 a7 b9
d4 fb 17 ac c7 8a 76 1b 69 8f 88 e2 d4 1c 15 77
a0 b5 64 e9 73 26 b5 83 0d 86 21 94 9d 02 95 c5
a7 b7 6e 3b d5 91 39 5d 16 c3 1d 7a d3 cd 98 3d
eb f6 62 4b 0d d0 9b d4 e7 d7 48 04 fd be f8 bf
6d 58 9a 42 75 32 de f9 48 5a 2b c4 48 1c ab de
21 80 9b ba dc 85 2e f4 5f ae 03 a6 2e c2 ea bd
b4 17 d7 33 f3 39 f9 c8 f4 79 ae 03 e1 f7 5b 9d
0a 95 11 e2 82 34 39 3d ec 34 83 b8 55 4b 90 db
02 03 01 00 01*

d1 aa 1c 10 37 20 2e 35 9f 22 4e 40 7d 7f 84 a0 e8 a9 4d d7

This is rather good as it should be a very long time (90 years) before it's even possible to crack a 4096 bit RSA public key. Assuming Moore's law holds and there are no advances in factoring or quantum computers.

I should mention that two party chat is unaffected by DecryptoCat. This is probably secure because it wasn't written by Cryptocat, but it uses random from BigInt. Which has a bug in it that generates 14 bits/element instead of 15 bits. This doesn't hurt security since it only shrinks the private key from 1536 bits to 1434 bits. Oh BigInt isn't written by Cryptocat. Oops I posted that bug in the wrong place.

What do I think of Cryptocat?

Cryptocat's public key scheme is now good after being bad since pretty much the beginning. I would suggest not using Cryptocat as there's no telling how long it will be until they break their public key encryption. Good news is if they read this they'll make a better effort not to change public key algorithms or the way they generate private keys. I'm sure there are plenty of bugs and other bad crypto in other parts because I only looked at random generation and found a bug, at public key algorithm and found a bug, and quickly looked where random is used and found something scary, and random (BigInt.randBigInt) used in two party messaging and found a bug.

What did I get out of this?

Even though I qualified for their bug bounty I never got anything. My guess is my bug is too big. Since it means that all messages after May 7th, 2012 are crackable. In a comment I was ask for my name, but I have not been added to their bug hunt page. I guess should have "t-shirt, sticker, money, and a mention on our Wall of Unquestionable Greatness!" coming sometime, but haven't heard anything about it. I got paid :).

Well I had fun writing DecryptoCat. Also I learned a new word "encraption". Thanks for that one azonenberg from irc.freenode.net. Also I learned that it means nothing when I hear "it is open source and peer reviewed".