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

61–70 of 128 posts

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

#61

Post by marshray »

mistercow wrote: post #51
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.

Yep. Plus, MT uses a huge amount of memory. I don't see any reason to use it any more now that modern stream ciphers have gotten so fast.

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

#62

Post by magikarp »

dakimov wrote: post #60
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 so…

I feel this is something that many a [insert security software in which critical bug was recently found here] has gone through. We've been following full disclosure principles and fixing bugs as they come for the past couple of years. It's really unfortunate that the comments tend to be so dismissive and personal — a quick look at our codebase or blog shows a serious and professional effort. That said, we definitely mess up.

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

#63

Post by aortega »

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.

Just remember that your software is not you. Have a tick skin, learn and start again. Probably a name-change will help too...

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

#64

Post by marshray »

mistercow wrote: post #59
jlgreco wrote: post #55

Earlier quoted context omitted.

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.

Or use an array of integers 0 <= n < 2^x. Some of the Javascript libraries involved are even using such a format.

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

#65

Post by caf »

yk wrote: post #40
JunkDNA wrote: post #28

Seems like at a minimum, if you are doing your own random number generator, you should have a test harness that runs the chi squared test and compare against a known good random number source. I wonder how many other automated tests one could stack up against a crypto codebase to do that kind of basic checking.

You are running the chi-square against the claimed distribution of the RNG, not against another RNG. Which is just about enough to use the RNG for simulating dice rolls ( sometimes, if the players are not too passionate). RNG can have a lot more subtile flaws, for example the RNGs from the ANSI C rand() with the suggested parameters lie in just a few thousand planes, if you construct points in some vector space out o…

The ANSI C rand() doesn't actually specify any particular algorithm. The complete set of requirements for rand() is just that: rand() computes a sequence of pseudo-random integers in the range 0 to RAND_MAX; RAND_MAX must be at least 32767; if srand() is called with the same seed value, the same sequence of values will be produced; calling rand() before calling srand() acts as if srand() had been called with a seed of 1; and no library function can peturb the pseudo-random sequence.

Historical C standard library implementations did tend to use the same or similar LCRNGs, but that was never a requirement, and is no longer the case.

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

#66

Post by aortega »

magikarp wrote: post #62
dakimov wrote: post #60

Earlier quoted context omitted.

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 so…

I feel this is something that many a [insert security software in which critical bug was recently found here] has gone through. We've been following full disclosure principles and fixing bugs as they come for the past couple of years. It's really unfortunate that the comments tend to be so dismissive and personal — a quick look at our codebase or blog shows a serious and professional effort. That said, we definitely…

>I feel this is something that many a [insert security software in which critical bug was recently found here] has gone through.

No, not really. No this kind...

Alright I quit.

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

#67

Post by marshray »

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!

If it's random, then the probability that the same case of output will occur forever is zero. Here the probability of hitting the terminating case occurs with p=(1 - 250/256). You aren't going to randomly roll 6/256 enough times in a row to notice within the age of the universe.

This is the standard method for selecting a uniform range from a source that is not an exact multiple. The worst-case probability of having to draw again can always be kept under 0.5. For example, I want a number in the range of (0 <= n < 129).

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

#68

Post by thetwiceler »

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…

If you take this sort-of-stretched case where encryption can be broken, I can explain why this is a problem.

Suppose you are using the PRNG to make a stream cipher. Basically, your random key is a seed for the PRNG. You then generate lots of pseudo-random characters from that seed, and XOR them together (character-by-character) with your message to encrypt it.

Now, the fact that XOR is linear (it's just addition mod 2) means when you XOR two probability distributions against a constant (i.e., an atomic distribution), you'll get a shifted distribution. Let's say your PRNG disproportionately outputs "0" at each character. Then the distribution of each character of the ciphertext will be centered at p XOR 0, where p is the corresponding character of the plaintext!

So by the law of large numbers, if we see the same message encrypted many times, we can determine with high probability exactly what each character of the plaintext is, and completely break encryption!

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

#69

Post by marshray »

zaroth wrote: post #54

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); Ap…

Maddening isn't it?

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

#70

Post by marshray »

mistercow wrote: post #46

>The code above is certainly an inelegant solution, since it is, in theory, at least, a potentially infinite loop. As far as I know, it is the only solution for generating unbiased random numbers in a range that does not divide the native range of the PRNG you're using. What I don't understand is why they're working in decimal in the first place. The obvious solution is to generate a random integer in the range [0, 2…

You could accumulate numbers until you reached the least common multiple of the source and desired ranges.
Post reply on HN