11.18 Statistically Testing Random Numbers
11.18.1 ProblemYou are using a hardware random number generator or some other entropy source that hasn't been cryptographically postprocessed, and you would like to determine whether it ever stops producing quality data. Alternatively, you want to have your generator be FIPS 140 compliant (perhaps for FIPS certification purposes). 11.18.2 SolutionFIPS 140-2 tests, which are ongoing throughout the life of the generator, are necessary for FIPS 140 compliance. For actual statistical tests of data produced by a source, the full set of tests provided by FIPS 140-1 are much more useful, even though they are now irrelevant to the FIPS certification process. 11.18.3 Discussion
FIPS 140 is a standard authored by the U.S. National Institute of Standards and Technology (NIST; see http://csrc.nist.gov/cryptval/). The standard details general security requirements for cryptographic software deployed in government systems (primarily cryptographic "providers"). There are many aspects to the FIPS 140 standard, one of which is a set of tests that all entropy harvesters and pseudo-random number generators must be able to run to achieve certification. FIPS 140-1 was the original standard and had several tests for random number sources; most of these occurred on startup, but one occurred continuously. Those tests only needed to be implemented for the two highest levels of FIPS compliance (Levels 3 and 4), which few applications sought. In FIPS 140-2, only a single test from FIPS 140-1 remains. This test is mandatory any time a random number generator or entropy source is used. Although the FIPS 140-1 standard is being obsoleted by 140-2, it is important to note that a module can routinely fail the FIPS 140-1 tests and still be FIPS 140-1 compliant. For Level 3 compliance, the user must be able to run the tests on command, and if the tests fail, the module must go into an error state. For Level 4 compliance, the module must comply with the requirements of Level 3, plus the tests must be run at "power-up." A weak random number generator, such as the one implemented by the standard C library function rand( ), should be able to get Level 3 certification easily. FIPS 140-1 testing is a reasonable tool for ensuring that entropy sources are producing quality data, if those entropy sources are not using any cryptographic operations internally. If they are, the entropy source will almost certainly pass these tests, even if it is a very poor entropy source. For the same reason, this set of tests is not good for testing cryptographic PRNGs, because all such generators will pass these tests with ease, even if they are poor. For example, simply hashing an incrementing counter that starts at zero using MD5 will produce a data stream that passes these tests, even though the data in that stream is easily predictable. FIPS 140-2 testing generally is not very effective unless a failed hardware device starts producing a repeating pattern (e.g., a string of zero bits). The FIPS 140-2 test consists of comparing consecutive generator outputs (on a large boundary size; see the next section). If your "random number generator" consists only of an ever-incrementing 128-bit counter, you will never fail this test. For this reason, we think the full suite of FIPS 140-1 tests is the way to go any time you really want to test whether an entropy source is producing good data, and it is a good idea to run these tests on startup, and then periodically, when feasible. You should always support the continuous test that FIPS 140-2 mandates whenever you are using hardware random number generators that could possibly be prone to disastrous failure, because it might help you detect such a failure. 11.18.3.1 FIPS 140-1 power-up and on-demand testsThe FIPS 140-1 standard specifies four statistical tests that operate on 20,000 consecutive bits of output (2,500 bytes). In the first test, the "Monobit" test, the number of bits set to 1 are counted. The test passes if the number of bits set to 1 is within a reasonable proximity to 10,000. The function spc_fips_monobit( ), implemented as follows, performs this test, returning 1 on success, and 0 on failure. #define FIPS_NUMBYTES 2500 #define FIPS_MONO_LOBOUND 9654 #define FIPS_MONO_HIBOUND 10346 /* For each of the 256 possible bit values, how many 1 bits are set? */ static char nb_tbl[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 }; int spc_fips_monobit(unsigned char data[FIPS_NUMBYTES]) { int i, result; for (i = result = 0; i < FIPS_NUMBYTES; i++) result += nb_tbl[data[i]]; return (result > FIPS_MONO_LOBOUND && result < FIPS_MONO_HIBOUND); } The second test is the "Poker" test, in which the data is broken down into consecutive 4-bit values to determine how many times each of the 16 possible 4-bit values appears. The square of each result is then added together and scaled to see whether the result falls in a particular range. If so, the test passes. The function spc_fips_poker( ), implemented as follows, performs this test, returning 1 on success and 0 on failure: #define FIPS_NUMBYTES 2500 #define FIPS_POKER_LOBOUND 1.03 #define FIPS_POKER_HIBOUND 57.4 int spc_fips_poker(unsigned char data[FIPS_NUMBYTES]) { int i; long counts[16] = {0,}, sum = 0; double result; for (i = 0; i < FIPS_NUMBYTES; i++) { counts[data[i] & 0xf]++; counts[data[i] >> 4]++; } for (i = 0; i < 16; i++) sum += (counts[i] * counts[i]); result = (16.0 / 5000) * (double)sum - 5000.0; return (result > FIPS_POKER_LOBOUND && result < FIPS_POKER_HIBOUND); } The third and fourth FIPS 140-1 statistical tests are implemented as follows to run in parallel in a single routine. The third test, the "Runs" test, goes through the data stream and finds all the "runs" of consecutive bits that are identical. The test then counts the maximum length of each run. That is, if there are three consecutive zeros starting at the first position, that's one run of length three, but it doesn't count as any runs of length two or any runs of length one. Runs that are longer than six bits are counted as a six-bit run. At the end, for each length of run, the count for consecutive zeros of that run length and the count for consecutive ones are examined. If either fails to fall within a specified range, the test fails. If all of the results are in an appropriate range for the run length in question, the test passes. The fourth test, the "Long Runs" test, also calculates runs of bits. The test looks for runs of 34 bits or longer. Any such runs cause the test to fail; otherwise, it succeeds. #define FIPS_NUMBYTES 2500 #define FIPS_LONGRUN 34 #define FIPS_RUNS_1_LO 2267 #define FIPS_RUNS_1_HI 2733 #define FIPS_RUNS_2_LO 1079 #define FIPS_RUNS_2_HI 1421 #define FIPS_RUNS_3_LO 502 #define FIPS_RUNS_3_HI 748 #define FIPS_RUNS_4_LO 223 #define FIPS_RUNS_4_HI 402 #define FIPS_RUNS_5_LO 90 #define FIPS_RUNS_5_HI 223 #define FIPS_RUNS_6_LO 90 #define FIPS_RUNS_6_HI 223 /* Perform both the "Runs" test and the "Long Run" test */ int spc_fips_runs(unsigned char data[FIPS_NUMBYTES]) { /* We allow a zero-length run size, mainly just to keep the array indexing less * confusing. It also allows us to set cur_val arbitrarily below (if the first * bit of the stream is a 1, then runs[0] will be 1; otherwise, it will be 0). */ int runs[2][7] = {{0,},{0,}}; int cur_val, i, j, runsz; unsigned char curr; for (cur_val = i = runsz = 0; i < FIPS_NUMBYTES; i++) { curr = data[i]; for (j = 0; j < 8; j++) { /* Check to see if the current bit is the same as the last one */ if ((curr & 0x01) ^ cur_val) { /* The bits are different. A run is over, and a new run of 1 has begun */ if (runsz >= FIPS_LONGRUN) return 0; if (runsz > 6) runsz = 6; runs[cur_val][runsz]++; runsz = 1; cur_val = (cur_val + 1) & 1; /* Switch the value. */ } else runsz++; curr >>= 1; } } return (runs[0][1] > FIPS_RUNS_1_LO && runs[0][1] < FIPS_RUNS_1_HI && runs[0][2] > FIPS_RUNS_2_LO && runs[0][2] < FIPS_RUNS_2_HI && runs[0][3] > FIPS_RUNS_3_LO && runs[0][3] < FIPS_RUNS_3_HI && runs[0][4] > FIPS_RUNS_4_LO && runs[0][4] < FIPS_RUNS_4_HI && runs[0][5] > FIPS_RUNS_5_LO && runs[0][5] < FIPS_RUNS_5_HI && runs[0][6] > FIPS_RUNS_6_LO && runs[0][6] < FIPS_RUNS_6_HI && runs[1][1] > FIPS_RUNS_1_LO && runs[1][1] < FIPS_RUNS_1_HI && runs[1][2] > FIPS_RUNS_2_LO && runs[1][2] < FIPS_RUNS_2_HI && runs[1][3] > FIPS_RUNS_3_LO && runs[1][3] < FIPS_RUNS_3_HI && runs[1][4] > FIPS_RUNS_4_LO && runs[1][4] < FIPS_RUNS_4_HI && runs[1][5] > FIPS_RUNS_5_LO && runs[1][5] < FIPS_RUNS_5_HI && runs[1][6] > FIPS_RUNS_6_LO && runs[1][6] < FIPS_RUNS_6_HI); } 11.18.3.2 The FIPS continuous output testThe FIPS continuous output test requires that random number generators (which would include both entropy sources and PRNGs) have the data they are going to produce broken up into "blocks" of at least 16 bytes. If the generator has a "natural" block size of greater than 16 bytes, that should always get used. Otherwise, any size 16 bytes or greater can be used. We recommend never using blocks larger than 16 bytes (unless required) because the underlying generator uses larger blocks naturally.[2]
This test collects the first block of output and never gives it to anyone. Instead, it is compared against the second block of output and thrown away. The second block may be output if it is not identical to the first block; otherwise, the system must fail. The second output is also saved and is then compared to the third block. This process continues for all generator outputs. The following (non-thread-safe) code adds a FIPS-compliant wrapper to the spc_entropy( ) function from Recipe 11.2 (note that this assumes that spc_entropy( ) does not cryptographically postprocess its data, because otherwise the test is all but worthless). #include <stdlib.h> #include <string.h> #define RNG_BLOCK_SZ 16 char *spc_fips_entropy(char *outbuf, int n) { static int i, bufsz = -1; static char b1[RNG_BLOCK_SZ], b2[RNG_BLOCK_SZ]; static char *last = b1, *next = b2; char *p = outbuf; if (bufsz = = -1) { spc_entropy(next, RNG_BLOCK_SZ); bufsz = 0; } while (bufsz && n--) *p++ = last[RNG_BLOCK_SZ - bufsz--]; while (n >= RNG_BLOCK_SZ) { /* Old next becomes last here */ *next ^= *last; *last ^= *next; *next ^= *last; spc_entropy(next, RNG_BLOCK_SZ); for (i = 0; i < RNG_BLOCK_SZ; i++) if (next[i] != last[i]) goto okay; abort( ); okay: memcpy(p, next, RNG_BLOCK_SZ); p += RNG_BLOCK_SZ; n -= RNG_BLOCK_SZ; } if (n) { *next ^= *last; *last ^= *next; *next ^= *last; spc_entropy(next, RNG_BLOCK_SZ); for (i = 0; i < RNG_BLOCK_SZ; i++) if (next[i] != last[i]) goto okay2; abort( ); okay2: memcpy(p, next, n); bufsz = RNG_BLOCK_SZ - n; } return outbuf; } 11.18.4 See Also
|
EAN: 2147483647
Pages: 266