Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

nakedsecurity.sophos.com

Post reply on HN
Print view View original

51–60 of 128 posts

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#51

Post by mistercow »

speeder wrote: post #47

I don't understand much of crypto... But I am game developer, and game developers (specially RPG fans) love random numbers. Some games of mine, I suspected something was off with the PRNG, and did something like they did on the ending, I used the random number generator to draw pictures. Biased generators were quite obvious, because they made obvious patterns (one of the worst offenders was C default random function…

> its author claim it is bad for crypto, Mersenne Twister, I don't remember why

Because after observing a certain number of outputs, you can completely predict its subsequent outputs.

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#52

Post by IsThisObvious »

jlgreco wrote: post #36
IsThisObvious wrote: post #27

Earlier quoted context omitted.

I help write microcontroller code for pressure equipment management. If something goes sufficiently wrong in heating/fails to properly vent, an explosion can occur, endangering everyone in the area. Even unrelated code is heavily audited to make sure that it can't somehow impact the main control loop and cause an invalid state. Cryptography software should be much the same.

With normal software you can load up on the unit and integration tests to make yourself more confident with your software. When the concern is with the integrity of a cryptographic system, things are not quite so simple. You can write tests, sure, but your overall confidence afterwards is going to be much different.

We go beyond unit tests to verify that the algorithms can't create certain states by any execution path, etc.

Formal verification of software properties is an interesting field.

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#53

Post by q3k »

cobbal wrote: post #11

I think the criticism of the loop is a bit unfair. If your random number generator returns >250 a thousand times in a row, you have bigger problems than slowness.

Purely mathematically, you cannot assert that a certain value will appear in a certain timeframe - it's random!

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#54

Post by zaroth »

First, this is a great article showing the bias in Cryptocat's very awkward PRNG code.

However, the off-by-one bias was actually the least of the problems with Cryptocat's random numbers...

From reading Steve's write-up, the problem was that their keys were ridiculous undersized, because they called their own function wrong:

May 7, 2012 (switched from DH to ECC):

  myPrivateKey = Cryptocat.randomString(32, 0, 0, 1);
April 19, 2013:

  rand = Cryptocat.randomString(32, 0, 0, 1);
  myPrivateKey = BigInt.str2bigInt(rand, 10);
June 3, 2013:

  rand = Cryptocat.randomString(64, 0, 0, 1, 0);
  myPrivateKey = BigInt.str2bigInt(rand, 16);
> 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). -- http://tobtu.com/decryptocat.php

See for yourself here: https://github.com/cryptocat/cryptocat/commit/a17bb1599463e0...

Even now looking at this code, for me it just doesn't pass the 'WTFs per minute' test... It still looks fucking wrong to me... Cryptocat.randomString(64, 0, 0, 1, 0) returns a 64 character string of 0-9, why are they calling str2bigInt with a hex radix? Did they add the last '0' in the wrong place? Or maybe I'm looking at the wrong check in...

EDIT: Ok, it WAS still wrong as of June 4th... It wasn't until July 4th until it finally became:

  var rand = Cryptocat.randomString(64, 0, 0, 0, 1)
See: https://github.com/cryptocat/cryptocat/commit/8fb7f4b8e59c76...

EDIT EDIT: So just to be clear... v2.1.11 which was supposed to fix this problem has this 'incorrect radix' bug in it? Please tell me I'm wrong, or do we need another CVE and another release?

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#55

Post by jlgreco »

mistercow wrote: post #48
jlgreco wrote: post #39

Earlier quoted context omitted.

It's not just the errors that were made though. I mean, ignoring the off-by-one error: repeat byte250 = randomSalsaByte() until byte250 I am not sure what sort of code-review process they had in place if someone saw that and thought "Yup, brilliant. Ship it." I am sure we have all written code like that at one point in our lives, but code that is shipping to the general public?

How else do you generate an unbiased random number between 0 and 250? As far as I know, that's the standard algorithm.

My concern is with why they are doing that in the first place. It is possible that I am missing something here, I haven't looked at their actual code, but it seems to me that this concern would have been entirely avoided if they went with 0-F instead of 0-9.

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#56

Post by cobbal »

q3k wrote: post #53
cobbal wrote: post #11

I think the criticism of the loop is a bit unfair. If your random number generator returns >250 a thousand times in a row, you have bigger problems than slowness.

Purely mathematically, you cannot assert that a certain value will appear in a certain timeframe - it's random!

True, but purely mathematically every cipher is vulnerable to the "get lucky and guess the key right the first time" attack (OTP excepted of course).

Almost all crypto operates in the realm of absurdly close to certain.

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#57

Post by marshray »

txttran wrote: post #7

I'm a complete noob when it comes to cryptography. I understand that having a PRNG that doesn't return numbers with even distribution across a range is bad. Extreme example would be something like http://xkcd.com/221/ . But could someone explain how an attacker can take advantage of the fact that 0 is returned ~1% more often than other digits? It this flaw alone sufficient to break cryptocat? Or does it simply make b…

The small bias described in the article is a pointless and embarrassing flaw, but it's not the bug that made messages decryptable (this most recent time).

The recent work on biases in RC4 contains a good example of how small biases can end up being exploitable. http://www.isg.rhul.ac.uk/tls/

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#58

Post by marshray »

oinksoft wrote: post #30

Cryptocat's hacktivist credibility was cemented in 2012 when its Canadian developer, Nadim Kobeissi, was stopped at the US border and interviewed about his Cryptocat-related programming activities. s/was/claimed to be/. This software clearly is not Ft. Knox, and its becoming less and less believable that US intelligence would ever feel the need to interrogate the author of an open source project, and with such brittl…

I believe Nadim is being truthful in that someone at the border asked him about Cryptocat.

I think they probably saw his tweets "I'M CROSSING THE BORDER NOW OMG I HOPE THEY DON'T GIVE ME TROUBLE FOR BEING A BIGTIME HACKER ACTIVIST", they Googled him, and asked him about his website.

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#59

Post by mistercow »

jlgreco wrote: post #55
mistercow wrote: post #48

Earlier quoted context omitted.

How else do you generate an unbiased random number between 0 and 250? As far as I know, that's the standard algorithm.

My concern is with why they are doing that in the first place. It is possible that I am missing something here, I haven't looked at their actual code, but it seems to me that this concern would have been entirely avoided if they went with 0-F instead of 0-9.

Yes, I definitely agree with that, and I don't understand why they did it that way. Generating a float in the [0,1) range by producing decimal digits seems utterly perverse. The sane, naive, and correct way to do it is to generate an integer between 0 and 2^53 and then divide by 2^53.

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#60

Post by dakimov »

magikarp wrote: post #6

As the lead developer for Cryptocat, I must say this is really a great example of how to write a post-mortem for a security bug. Sophos bloggers are always worth reading.

My condolences to you. Now your product has become a target of mockery.

Also I love cats and feel sorry that the name of those lovely animals is used in a discredited entity.

The problem is that your product did not have just a security vulnerability, but had a number of blatantly unprofessional mistakes showing off ignorance and carelessness of its authors.

This is the worst that can happen with an author of open source and especially security software.

I hope at least you the poor cat's devs realize what has happened.

Post reply on HN