Cryptocat DERP

[-0-]

http://tobtu.com/decryptocat.php

DecryptoCat

TLDR: If you used 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.

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 BPKDF2, 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. 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. They generating a random floating point number by getting 16 random bytes of data with values less than 250 and converting each of them to a single decimal digit. This is basically wasting 15 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. 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 from Cryptocat.random().

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

Date introduced Days in Git Difficulty rating
Jul 9, 2011 58 Passwords so probably broken
Sep 5, 2011 6 *** Medium
Sep 11, 2011 36 **** Hard
Oct 15, 2011 2 ***** "Impossible"
Oct 17, 2011 12 *** Medium
Oct 29, 2011 191 ** Easy
May 7, 2012 347 * Encraption
Apr 19, 2013 45 *** Medium
Jun 3, 2013 30+ ***** "Impossible"
Encraption
Easy
Medium
Hard
"Impossible" A bored individual could break it
Hard for an individual with a shoestring budget
Governments would have enough resources to break it
Governments would might have enough resources to break it
Secure unless/until there are quantum computers, around a century of Moore's law, or better algorithms.
Here's the long version that describes each change:

Date introduced Days in Git Description
Jul 9, 2011 49 Passwords: BPKDF2-HMAC-SHA1 with 1000 iterations
Aug 27, 2011 9 Passwords: BPKDF2-HMAC-SHA1 with 600 iterations
Sep 5, 2011 1 768 bit RSA (largest publicly factored key size)
Sep 6, 2011 2 512 bit RSA
Sep 8, 2011 3 600 bit RSA (640 bit takes 5 months on 80 2.2 GHz AMD Opteron CPUs)
Sep 11, 2011 0 1280 bit RSA
Sep 11, 2011 1 1024 bit RSA
Sep 12, 2011 19 1048 bit RSA
Oct 1, 2011 9 1536/1152 bit RSA (Chrome/other)
Oct 10, 2011 5 1536/1024 bit RSA (Chrome/other)
Oct 15, 2011 2 "3072 bit" D-H ( 10^64 = 2^212.6 [106.3 bits of security])
Oct 17, 2011 0 "3072 bit" D-H (9*10^31 = 2^106.1 [ 53.1 bits of security])
Oct 17, 2011 12 "4096 bit" D-H ( 10^32 = 2^106.3 [ 53.2 bits of security])
Oct 29, 2011 63 "4096 bit" D-H (9*10^25 = 2^ 86.2 [ 43.1 bits of security])
Dec 31, 2011 128 "4096 bit" D-H (9*10^23 = 2^ 79.6 [ 39.8 bits of security])
May 7, 2012 347 ECC Curve25519 (2*10^16 = 2^ 54.2 [ 27.1 bits of security])
Sep 22, 2012 (I think) Plug-in is now mandatory. Everything before now could have been compromised by Cryptocat injecting JS.
Apr 19, 2013 45 ECC Curve25519 ( 10^32/8 = 2^103.3 [ 51.7 bits of security])
Jun 3, 2013 0 ECC Curve25519 ( 16^64/32 = 2^251.0 [125.5 bits of security])
Jun 3, 2013 30+ ECC Curve25519 ( 10^64/8 = 2^209.6 [104.8 bits of security])
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.

The current public key is (valid 11/9/2012 through 1/12/2015):
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*
* Depending on your browser you might get these two lines of extra data.

Thumbprint/Fingerprint (SHA1):
‎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.

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.

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.

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".

Copyright © 2013 Steve Thomas - EULA

Fairly hilarious and should be a lesson to anyone using someone else's software -- review the code if you have the capability.

Khannie

Ouch. They just got ripped a new one.

syklops

Lastly I think everyone involved with Cryptocat are incompetent.... 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.

Bit harsh. Cryptocat is an open source application. Not enough eyes looking at their code. Yeah because finding people who are willing to spend hours trawling through source code, for free, looking for bugs is sooo easy.

[-0-]

syklops wrote: »

Bit harsh. Cryptocat is an open source application. Not enough eyes looking at their code. Yeah because finding people who are willing to spend hours trawling through source code, for free, looking for bugs is sooo easy.

They claimed it was peer reviewed.

syklops

[-0-] wrote: »

They claimed it was peer reviewed.

Claimed it was peer reviewed? Or it was peer reviewed and the peers missed something? Peers are people too after all.

To be honest the guy sounds bitter that he didn't get anything from their bug hunting program. In a blog post on their site from yesterday, he gets credit, and his name on their wall, presumably his sticker and T-shirt are in the post.

I'm not defending cryptocat by the way. With the prism controversy its a very bad time for people to discover they were using bad crypto, but calling everyone involved with the project incompetent, is uncalled for.

Khannie

syklops wrote: »

calling everyone involved with the project incompetent, is uncalled for.

Agreed. I generally dislike stuff like that.