1 | |
---|

2 | On Testing Randomness |
---|

3 | --------------------- |
---|

4 | |
---|

5 | + RFC-1750 |
---|

6 | |
---|

7 | + Knuth, "The Art of Computer Programming" (volume 2) |
---|

8 | |
---|

9 | + NIST publication 800-22 |
---|

10 | |
---|

11 | + FIPS publication 140-2 |
---|

12 | |
---|

13 | |
---|

14 | Different Kinds of Randomness |
---|

15 | ----------------------------- |
---|

16 | |
---|

17 | + Chaitin-Kolmogorov randomness (Algorithmic randomness), defined in terms of computational |
---|

18 | models. A string of bits is random iff it is shorter than any program that can produce it. |
---|

19 | |
---|

20 | + Statistical randomness, defined as having no recognizable patterns or regularities (in the |
---|

21 | long run). |
---|

22 | |
---|

23 | + "True" randomness, defined as being unpredictable. |
---|

24 | |
---|

25 | How are these different definitions related? |
---|

26 | |
---|

27 | |
---|

28 | Bias Removal |
---|

29 | ------------ |
---|

30 | |
---|

31 | The output of the RNG will, most likely, contain bias (more 1s than 0s or visa-versa). The bias |
---|

32 | can be removed with hardware filtering or in software after the fact. Hardware bias removal |
---|

33 | methods include: feeding back the output to adjust the generator, using two generators with |
---|

34 | different mechanisms, beating the output against an uncorrelated clock, etc. Software bias |
---|

35 | removal methods include: von Neumann decorrelation, XOR with output of cryptographically strong |
---|

36 | PRNG, XOR two correlated bit streams together (see "piling-up" lemma), use a secure hash on the |
---|

37 | bits (little theoretical support?) |
---|

38 | |
---|

39 | von Neumann decorrelation: |
---|

40 | 00, 11 -> throw away |
---|

41 | 10 -> 1 |
---|

42 | 01 -> 0 |
---|

43 | |
---|

44 | This forces 50% occurance of 1 (and, of course, 0) bits , but it throws away 75% of the bits. |
---|

45 | Alternatively one might XOR adjacent bits together. This only throws away 50% of the bits. |
---|

46 | |
---|

47 | Both hardware and software "whitening" techniques should be used. Statistical tests on the |
---|

48 | device should probably be done before software bias removal so that the tests can better observe |
---|

49 | changes in the underlying hardware. |
---|

50 | |
---|

51 | |
---|

52 | Security Analysis |
---|

53 | ----------------- |
---|

54 | |
---|

55 | Since this system will be used in security sensitive applications it may make sense to do a |
---|

56 | careful security review of the software and system design. It would be especially nice to use |
---|

57 | some formal methods in that review, but that may be too time consuming for the first version. |
---|

58 | |
---|