Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.


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 of the random numbers. ( That is bad, if you want to run Monte Carlo integration, because your error estimate improves, but not the accuracy of the result.)

So even for simulation you can have rather subtle effects, even though there you get bitten just by bad luck. The task for cryptographically secure random number generators is actually quite a bit harder, because a attacker tries to exploit any weakness in your RNG, but your tests do only tell you which specific attacks do not work.


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.


Just run NIST DieHard or similar. Of course that is only a statistical test which is necessary but not sufficient for CSPRNG but it can help find problems like this.


John Cook has some interesting material on testing PRNGs in his chapter for the book Beautiful Testing. His material is (was?) online free, here: http://www.johndcook.com/blog/2010/12/06/how-to-test-a-rando...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: