Re: Linux-style kernel PRNGs and the FIPS140-2 test (fwd)

---------- Forwarded message ---------- Date: Wed, 16 Jan 2002 13:20:17 +1100 From: Greg Rose To: Thor Lancelot Simon Cc: cryptography@wasabisystems.com, tls@reefedge.com Subject: Re: Linux-style kernel PRNGs and the FIPS140-2 test There was an error in the bounds for the runs test specified by NIST; last october they updated FIPS 140-2 to specify new bounds. An updated version of my code can be found at http://people.qualcomm.com/ggr/QC/ (our old web pages are stale, and I'm still trying to have them taken down by our ex-ISP). Here's an excerpt from the comment in the new code: * Version 1.3 -- Bill Chauncey and his colleages pointed out to NIST that * the bounds in the runs test were incorrect. * They issued an update 2001-oct-10. If the new one still shows an anomalous number of runs test failures, there is a real problem. regards, Greg. At 03:23 PM 1/15/2002 -0500, Thor Lancelot Simon wrote:

Many operating systems use "Linux-style" (environmental noise stirred with a hash function) generators to provide "random" and pseudorandom data on /dev/random and /dev/urandom respectively. A few modify the general Linux design by adding an output buffer which is not stirred so that bits which have already been output are not stirred into the pool of "new" "random" data (IMO, not doing this is insane, but that's a different subject).

The enclosed implementation of the FIPS140-1/2 statistical test appears to show that such generators fail the "runs" test quite regularly. Interestingly, the Linux generator seems to do better the longer you let it run (which, perhaps, suggests that quite a bit of data should be run through it at boot time and discarded) but other, related generators do not.

The usual failure mode is "too many runs of 1 1s". Using MD5 instead of SHA1 as the mixing function, the Linux generator also displays "too many runs of 1 0s". I have not yet seen other failure modes from these generators.

To reproduce my results, just compile the enclosed and do "a.out < /dev/urandom" on your platform of choice.

Thor

Greg Rose INTERNET: ggr@qualcomm.com Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com