User manual VIA C3 WHITE PAPER

[. . . ] EVALUATION OF VIA C3 NEHEMIAH RANDOM NUMBER GENERATOR PREPARED BY Cryptography Research, Inc. 607 Market St. , 5th Floor San Francisco, CA 94105 (415) 397-0123 Last Revision: February 27, 2003 Information in this white paper is provided without guarantee or warranty of any kind. This review was performed for VIA Technologies, Inc. but represents the findings and opinions of Cryptography Research, Inc. and may or may not reflect opinions of VIA Technologies, Inc. [. . . ] These tests measure the suitability of the RNG for numerical applications. They are not particularly relevant to security applications, since insecure pseudorandom bit generators have been known to pass these statistical tests. The tests run with SHA mixing all produced excellent statistics. This is unsurprising, since good SHA mixing produces excellent statistics for all known input streams. Tests run without SHA mixing tended to fail the demanding statistical tests that were applied. This does not prove that the random bits are particularly poor, since tests encompassing so much data will detect very small flaws in an RNG; but it does indicate that applications requiring high quality randomness should not use this RNG without mixing. It is possible that by experimenting with the bias settings, a setting may be located that produces random bits with better statistics. However, every chip might not have such an optimal bias setting, and chip performance may drift with time and/or temperature. To minimize the likelihood of a problem, users of this RNG (as well as virtually any other FEBRUARY 27, 2003 CRYPTOGRAPHY RESEARCH, INC. PAGE 24 OF 41 VIA C3 NEHEMIAH RNG EVALUATION hardware-based entropy source) who require high quality randomness should use appropriate mixing functions. 4. 5. Source Whitening: Extrapolating Test Results The above RNG tests were performed with the von Neumann whitener deactivated. The usefulness of von Neumann whitening depends on the characteristics of the input bitstream and the intended use of the output bits. Specifically, · · · · · von Neumann whitening works well on bits from memory-less generators. It works less well on bit streams with serial correlations. Its bit-balancing effect is important for numerical work. Under normal circumstances, it will improve the entropy of the output, although in some unusual (largely theoretical) situations it can reduce entropy. Its bit-balancing effect is often less important for cryptographic applications where post-processing is used to produce high-entropy output from lower-entropy sources. To illustrate these points, consider the following simple examples. The whitener is ideally suited for input bits that are independent but biased. If each bit is 1 with probability p, then the entropy per input bit is - p log 2 ( p ) - (1 - p ) log 2 (1 - p ) , and the average number of output bits produced per input bit is p (1 - p ) . These two functions agree nicely, as shown in the following figure. FEBRUARY 27, 2003 CRYPTOGRAPHY RESEARCH, INC. PAGE 25 OF 41 VIA C3 NEHEMIAH RNG EVALUATION Figure 10: von Neumann correction of biased, independent bits The rate at which output bits are produced never exceeds the rate at which input bits can be imagined as "bringing entropy" in, so it seems reasonable (and is in fact true) that each output bit holds a bit of entropy. In other words, each output bit from a von Neumann corrector brings one bit of entropy if the raw bits are independent but biased with any probability p between 0 and 1. Consider a bit generator where the probability that any two consecutive bits differ is p. [. . . ] Raw bits are produced at rates of 30 to 50 Mbits/sec, and whitened bits were observed at rates of 4 to 9 Mbits/sec. We estimate that PRNGs seeded with the Nehemiah RNG can sustain output in excess of 2 Mbits of entropy per second, which should eliminate blocked PRNG reads in virtually all applications. Even more important, the high bit rates enable sensitive applications to use more conservative per-bit estimates of entropy with little performance penalty. FEBRUARY 27, 2003 CRYPTOGRAPHY RESEARCH, INC. PAGE 39 OF 41 VIA C3 NEHEMIAH RNG EVALUATION On-die location. Unlike all PC-based random number sources known to the authors, the Nehemiah RNG is located entirely on the microprocessor die. [. . . ]