Wow, someone used <= instead of < and they wrote 5 page report with all those images and charts. The bug is obvious and simple, what is with all those explanations?
Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG
71–80 of 128 posts
Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG
#72Earlier 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…
While I admire the effort and overall mission, the problem is that when an application promotes 'secure communications', there are people who actually may use it as such.
Mistakes are understandable, however I think in-depth code review and auditing in any environment involving cryptography is an absolute must. Potentially, peoples lives could be jeopardized (either legally or physically) if they believed their communications were secure, when in fact they were not.
Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG
#73>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.
How is that any different, am I missing something?
Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG
#74I 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…
MT is not suitable for crypto because after observing 637 values you can predict all further values. 637 is the size of MTs internal state vector and the output of MT are basically just values from that state vector run through a tempering function. That tempering function is invertible, thus by looking at 637 values you get the full state vector, at which point you can generate the next values as usual.
Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG
#75Earlier 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.
Perhaps grab 5 bytes instead?
Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG
#76I 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…
MT is not suitable for crypto because after observing 637 values you can predict all further values. 637 is the size of MTs internal state vector and the output of MT are basically just values from that state vector run through a tempering function. That tempering function is invertible, thus by looking at 637 values you get the full state vector, at which point you can generate the next values as usual.
That's a great answer, thanks for that!
Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG
#77I'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…
Yes, the fact that 0 is returned ~1% more often than other digits is very significant. E.g. if the generated random number stream were used for XOR encryption, then you could just collect a large number of encryptions of the same text, for each character look which one occurs most often and then that would be the encrypted character (because 0 has a bias and occurs most often and c XOR 0 == c).
Using other encryption methods the advantage is often not so obvious, but it exists. Also it should be noted that 1/250 is a pretty large bias and would probably not even need particularly many ciphertexts.
Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG
#78Earlier 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?
It's not the most elegant code I've ever seen - but I don't otherwise see a red flag. What's your problem with it ? I don't think the worry that a semi-infinite string of legitimate values >250 is going to come out of randomSalsaByte() is a real, practical problem. You may as well worry that the complete works of Shakespeare asciified might come out of the PRNG. In theory it could happen. In practice, it won't happen…
The issue isn't the potentially infinite loop, it's the fact it creates an uneven distribution of values, giving 0 a 1/250 greater chance of being selected, and thus makes the results of the PRNG more predictable. The article makes this pretty clear...
Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG
#79Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG
#80I thought cryptocat was independently audited. Who audited it and why didn't they find these problems?
It was probably "audited" by the NSA, or whatever other three-letter agency paid for this trainwreck of an ECMAScript to be shat out upon the world.