Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG • Hacker News Board

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

#101

Post by tptacek » Tue, Jul 09, 2013, 1:05 PM UTC

marshray wrote: post #61

mistercow wrote: post #51

Earlier quoted context omitted.

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

It is the unfortunate de facto standard for built-in noncryptographic RNGs in high-level languages. PHP, Python, and Ruby all rely on MT generators (all 3 have real CSPRNGs too).

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

#102

Post by tptacek » Tue, Jul 09, 2013, 1:08 PM UTC

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.

The problem is having to build your own random number generator at all, and it's a consequence of doing cryptography in browser Javascript.

Designing a robust CSPRNG is as hard a problem as designing a block cipher mode or a MAC; it's "systemsier" than designing your own block cipher core, but about on par with coming up with a simple authenticated encryption mode. By way of example, CSPRNG design gets extensive treatment in its own chapter in Schneier and Furgusen's _Practical Cryptography_, and it's one of the few chapters that highlights the authors own work.

Cryptocat uses JS inside of a Chrome extension to avoid the chicken/egg secure load problem (I'm ambivalent about this approach). But Chrome extension JS doesn't avoid the other problems of browser Javascript crypto, and here's an example of why: it forced Cryptocat to attempt the design of a custom CSPRNG.

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

#103

Post by jdiez17 » Tue, Jul 09, 2013, 1:36 PM UTC

davidw wrote: post #84

aortega wrote: post #22

Earlier quoted context omitted.

You are dangerously fooling yourself by minimizing the importance of those bugs. Cryptography software is not like regular software. It is critical software, like the kind used to run planes or nuclear power plants: People's lives depends on it. People with no programming experience should be literally banned by law from writing critical software. You should take those bugs way more seriously. PS: I have seen a progr…

> People with no programming experience should be literally banned by law from writing critical software. Getting the government involved in who gets to write crypto software... What could possibly go wrong?

I don't think he meant to "involve the government." I do agree with his sentiment though, an inexperienced programmer should not be allowed to write critical software.

This is, of course, very difficult to implement in practice.

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

#104

Post by jdiez17 » Tue, Jul 09, 2013, 1:38 PM UTC

z-factor wrote: post #91

IsThisObvious wrote: post #49

Earlier quoted context omitted.

I know people who write crypto software that must conform to formal verification of the algorithm, requires detailed design documentation before a single line of code, etc.

Funny thing is that code is then compiled with a compiler was not formally verified, so it's still a 'fingers crossed' situation.

Right, but it's much less of a leap of faith, IMHO. Besides, if you turn off optimisations you can be reasonably sure the compiler didn't do something unintended.

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

#105

Post by yawgmoth » Tue, Jul 09, 2013, 1:57 PM UTC

aortega wrote: post #63

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

I don't understand this. Why would anyone have to change their alias just because they wrote buggy software? Mistakes happen, people move forward, but they don't have to recreate themselves just because they mess up. That seems radically unhealthy.

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

#106

Post by davidw » Tue, Jul 09, 2013, 1:59 PM UTC

jdiez17 wrote: post #103

davidw wrote: post #84

Earlier quoted context omitted.

> People with no programming experience should be literally banned by law from writing critical software. Getting the government involved in who gets to write crypto software... What could possibly go wrong?

I don't think he meant to "involve the government." I do agree with his sentiment though, an inexperienced programmer should not be allowed to write critical software. This is, of course, very difficult to implement in practice.

I don't know much about writing "critical software" - because it's not something I've ever done.

However, my guess would be that with proper processes, you should be able to let a junior programmer write the code, because bugs and errors and mistakes will come out in the wash. It's not like experienced programmers don't make mistakes! Perhaps it simple doesn't make sense to turn a junior guy loose, but my thinking is that where people's lives are at stake, depending on someone being a 'good coder' is a bad idea.

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

#107

Post by DanBC » Tue, Jul 09, 2013, 2:04 PM UTC

ChuckMcM wrote: post #21

Nice article, I can certainly vouch for creating a visualization to clue you in that there may be a problem. One of the things I built out of Java when I was hanging out on the cypherpunks list was a 'Noise Sphere' applet. Basically this is a way of testing a PRNG visually. It was fun to put various ideas through it to see how they panned out (most really sucked) One of the cool things was using the alpha emitter RNG…

H-Online have a nice article about an external enclosure that offered "hardware data encryption with 128-bit AES, access control via an RFID chip".

The visualization (of the encrypted data, not of any PRNG used) showed that the encrypted data had strong patterns. The data wasn't encrypted using RSA, it used XOR with a non-changing cipher block. (This is trivially easy to crack. Even I could do it.)

The error arose because the manufacturer of the controller chip was using confusing terminology.

> The IM7206 merely uses AES encryption when saving the RFID chip's ID in the controller's flash memory. The company explained that actual data encryption is based on a proprietary algorithm.

(http://www.h-online.com/security/features/Enclosed-but-not-e...)

Other people interested in testing PRNGs might be interested in the DIEHARD tests (http://en.wikipedia.org/wiki/Diehard_tests), but read all the cautions too.

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

#108

Post by DanBC » Tue, Jul 09, 2013, 2:20 PM UTC

IsThisObvious wrote: post #52

jlgreco wrote: post #36

Earlier quoted context omitted.

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.

A blog post about the process would be fascinating, and probably something that many on HN would be interested in.

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

#109

Post by baq » Tue, Jul 09, 2013, 2:23 PM UTC

kunil wrote: post #99

baq wrote: post #83

Earlier quoted context omitted.

this is crypto. there were 'less serious' bugs like initializing arrays to zeros (see debian) that led to catastrophic results, which is what the explanation is about.

I am not saying if bug is critical or not. It is just pages of explanations, charts and stuff. I was expecting a video explanation by the end. If they are targeting non-crypto people (which includes me), explaining how a bad random algorithm affects cryptology would be better instead of showing that algorithm is bad in 5 different ways. Also any link to articles about that Debian bug?

excuse me for inaccuracy - it wasn't a zero-initialization, it was a maintainer who thought he was fixing a bug because he made a compiler warning disappear, which resulted in a whole lot of zeros where there should be some random data.

http://www.schneier.com/blog/archives/2008/05/random_number_... http://research.swtch.com/openssl

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

#110

Post by rheide » Tue, Jul 09, 2013, 2:24 PM UTC

This should be possible to test automatically. And if that's not possible/easy to do, it should be standard procedure to generate colour maps that can be checked by humans.