Where are the FIPS 140-1 tests for randomness now?
in [Cryptography]
|
Prev: Operator Protocols for using a PRF
Next: 6th Int. Conf. on Technology and Medical Sciences – Announce & Call for Papers
From: Mok-Kong Shen on 3 Apr 2010 03:22 I just looked at FIPS 140-2 which replaces FIPS-1 and saw that the statistical tests for randomness have been crossed out there. Is there no replacement? Why? (Sorry for this ignorant's question.) M. K. Shen
From: amzoti on 3 Apr 2010 09:40 On Apr 3, 12:22 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > I just looked at FIPS 140-2 which replaces FIPS-1 and saw that > the statistical tests for randomness have been crossed out there. > Is there no replacement? Why? (Sorry for this ignorant's question.) > > M. K. Shen Read the summary here: http://csrc.nist.gov/groups/ST/toolkit/rng/index.html Also see this: http://www.random.org/analysis/ (see the NIST analysis discussion) Try this: http://www.iro.umontreal.ca/~simardr/testu01/tu01.html
From: Mok-Kong Shen on 3 Apr 2010 12:17 Am 03.04.2010 15:40, schrieb amzoti: > On Apr 3, 12:22 am, Mok-Kong Shen<mok-kong.s...(a)t-online.de> wrote: >> I just looked at FIPS 140-2 which replaces FIPS-1 and saw that >> the statistical tests for randomness have been crossed out there. >> Is there no replacement? Why? (Sorry for this ignorant's question.) > Read the summary here: http://csrc.nist.gov/groups/ST/toolkit/rng/index.html > > Also see this: http://www.random.org/analysis/ (see the NIST analysis > discussion) > > Try this: http://www.iro.umontreal.ca/~simardr/testu01/tu01.html Yet I don't see what actually (officially) caused the text in FIPS 140-1 on randomness tests to be crossed out and no longer be retained (perhaps in a modified version) in FIPS 140-2. I had expected to see at least some remarks on the rationale of the exclusion in the new standard. M. K. Shen
From: Scott Fluhrer on 3 Apr 2010 13:37 "Mok-Kong Shen" <mok-kong.shen(a)t-online.de> wrote in message news:hp6qc3$btt$02$1(a)news.t-online.com... > > I just looked at FIPS 140-2 which replaces FIPS-1 and saw that > the statistical tests for randomness have been crossed out there. > Is there no replacement? Why? (Sorry for this ignorant's question.) Well, I suspect it's because FIPS changed how they dealt with random number generators between 140-1 and 140-2. In 140-1, they let you use pretty much any random number generator you wanted. In an attempt to make sure that you didn't make a totally dreadful choice, they insisted that the random number generator pass a series of statistical tests. As any sci.crypt regular knows, this isn't *much* better than nothing, but it was where they were. In 140-2, they changed tactics. Instead of allowing you to use a random random-number generator, they had a list of 'approved' random number generators, which you had to pick from. Presumably, the good people at NIST have gone through all approved random number generators and decided that their outputs where perfectly acceptable (even Dual_EC_DRBG -- apparently, NIST was forced to accept that one). So, they don't need to test the statistics of the output, they already know that if you implemented the specified rng correctly, then the output will look random. So, the statistics tests were effectively replaced by implementation tests (one time testing of test vectors, along with a known answer test at start-up time). Now, they didn't do this completely: FIPS 140-1 also specified a 'continuous random number test' (where you look at adjacent outputs of the random number generator, and reject them if they output the same random number twice in succession). One would think that this test would not be needed for the approved random-number generators, but that test got left in in FIPS 140-2. However, this test gets removed in the current FIPS 140-3 draft, so it looks like someone in NIST agrees that it's no longer needed. Also, about the statistics tests in FIPS 140-1; one problem with how they were specified was that whoever computed the probabilities got them wrong; they have far too high probability of detecting a failure on a truly random stream. I don't remember if the probability was 10**-5 or 10**-6, but it was high enough to be seen in practice by customers (who weren't amused because the box shut down because 'the random number generator failed its NIST test'). In addition, sci.crypt regulars should know that a good rng is not sufficient; you also have to seed it with good entropy. FIPS 140-2 doesn't address that; FIPS 140-3 (actually, NIST SP 800-90) tries to address this by insisting on a good entropy source. That is certainly heading in the right direction -- poncho
From: Mok-Kong Shen on 3 Apr 2010 15:43
Scott Fluhrer wrote: > "Mok-Kong Shen" wrote: >> I just looked at FIPS 140-2 which replaces FIPS-1 and saw that >> the statistical tests for randomness have been crossed out there. >> Is there no replacement? Why? (Sorry for this ignorant's question.) > > Well, I suspect it's because FIPS changed how they dealt with random number > generators between 140-1 and 140-2. > > In 140-1, they let you use pretty much any random number generator you > wanted. In an attempt to make sure that you didn't make a totally dreadful > choice, they insisted that the random number generator pass a series of > statistical tests. As any sci.crypt regular knows, this isn't *much* better > than nothing, but it was where they were. > > In 140-2, they changed tactics. Instead of allowing you to use a random > random-number generator, they had a list of 'approved' random number > generators, which you had to pick from. Presumably, the good people at NIST > have gone through all approved random number generators and decided that > their outputs where perfectly acceptable (even Dual_EC_DRBG -- apparently, > NIST was forced to accept that one). So, they don't need to test the > statistics of the output, they already know that if you implemented the > specified rng correctly, then the output will look random. So, the > statistics tests were effectively replaced by implementation tests (one time > testing of test vectors, along with a known answer test at start-up time). > > Now, they didn't do this completely: FIPS 140-1 also specified a 'continuous > random number test' (where you look at adjacent outputs of the random number > generator, and reject them if they output the same random number twice in > succession). One would think that this test would not be needed for the > approved random-number generators, but that test got left in in FIPS 140-2. > However, this test gets removed in the current FIPS 140-3 draft, so it looks > like someone in NIST agrees that it's no longer needed. > > Also, about the statistics tests in FIPS 140-1; one problem with how they > were specified was that whoever computed the probabilities got them wrong; > they have far too high probability of detecting a failure on a truly random > stream. I don't remember if the probability was 10**-5 or 10**-6, but it > was high enough to be seen in practice by customers (who weren't amused > because the box shut down because 'the random number generator failed its > NIST test'). > > In addition, sci.crypt regulars should know that a good rng is not > sufficient; you also have to seed it with good entropy. FIPS 140-2 doesn't > address that; FIPS 140-3 (actually, NIST SP 800-90) tries to address this by > insisting on a good entropy source. That is certainly heading in the right > direction Thanks for the informations. Still I am of the personal opinion that a revision of a standard should spend a couple of words hinting at some major changes and the reasons thereof. It may be interesting to note that the German BSI has a document: https://www.bsi.bund.de/cae/servlet/contentblob/478152/publicationFile/30275/ais20e_pdf.pdf (I just accessed it in order to know that it is still current) that contains statistical tests practically the same as those in FIPS 140-1 (with some differences in the ranges) plus an autocorrelation test. It may also be noted that, apparently encouraged by FIPS 140-1, there have since been (till fairly recently, if I don't err) quite some scientific papers on design or applications of random number generators employing results of tests conforming to that standard, implicitly implying that everything must be o.k., if these "standard" tests were passed. (I have even seen one paper where one of the tests was left out, presumably failed.) M. K. Shen |