Understanding Small-State Noncryptographic Pseudorandom Number Generators

Slide Note
Embed
Share

Explore the design and testing of small-state noncryptographic pseudorandom number generators, including definitions, rules of thumb, chisquare tests, existing and new generators, and more. Learn about block cipher encryption, hash functions, pseudorandom number generation, reversible mixing, and reversible primitives.


Uploaded on Sep 07, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. The testing and design of small-state noncryptographic pseudorandom number generators typedef unsigned long int u4; typedef struct ranctx { u4 a; u4 b; u4 c; u4 d;} ranctx; static void raninit( ranctx *x, u4 seed ) { u4 i; x->a = 0xf1ea5eed; x->b = x->c = x->d = seed; for (i=0; i<20; ++i) { (void)ranval(x); } } #define rot(x,k) ((x<<k)|(x>>(32-k))) static u4 ranval( ranctx *x ) { u4 e = x->a - rot(x->b, 27); x->a = x->b ^ rot(x->c, 17); x->b = x->c + x->d; x->c = x->d + e; x->d = e + x->a; return x->d; }

  2. Outline of Talk Definitions Rules of thumb Chisquare tests Existing generators (Not-so-) New Tests New Generators

  3. Block Cipher Encrypted text Mixing Function Message Secret Key Avalanche: every input bit hits every output bit Block ciphers do avalanche 12x or so

  4. Hash Function Mixing Function Hash Value Postprocessing Initial Seed Combining step User Input

  5. Pseudorandom Number Generator User Results Postprocessing Internal State Initialization Mixing Function Seed

  6. Pseudorandom Number Generators Deterministic, based on seed, look random Noncryptographic: only reasonable tests Used for simulations, games, nondeterministic algorithms Central Limit Theorem: a total of n implies a random fluctuation of sqrt(n)

  7. Rules of Thumb

  8. Mix Should be Reversible Random mix: average cycle of 2n/2 Reversible mix: average cycle of 2n-2 Reversible gives uniform distribution

  9. Some Reversible Primitives A = A + f(B) A = A - f(B) A = A ^ f(B) A = A*k (where k is odd) A += (A<<k) A ^= (A>>k) A = rotate(A,i) ^ rotate(A,j) ^ rotate(A,k) A = (A + permute(A)) is never reversible

  10. No Nice Math Nice math causes long range patterns Linearity (spectral test, linear complexity) Partitioned states (less mixing, cyclic behavior) Unreachable states (bias from absence) A=A+B; B=B^A together is nonlinear Sign of nice math: cycle length can be predicted exactly

  11. Size of Internal State No more than 264 values per application 232 seeds producing 232 values each 2-32 chance of cycle or overlapping sequence 232*(232*232)/23*32 = 1, not good enough 232*(232*232)/24*32 = 2-32, good enough Internal state needs at least four 32-bit terms (128 bits) to be good enough for today

  12. Iterate over the Internal State For each term, compute a result, replace it n terms in internal state implies n consecutive results each owning its own true entropy Usually, no bias for n consecutive results Bigger state = more time for mixing!

  13. Remaining Bias Reversible function: uniform distribution No nice math: no long term patterns Iterate through state: first n results OK n+1 is the most biased, then it tapers off

  14. Chisquare Testing

  15. Chisquare Tests Central Limit Theorem: actual = n +- sqrt(n) (actual-expect)2 = sqrt(expect)2 = expect (actual-expect)2/expect = 1

  16. Chisquare Tests, cont m buckets, m-1 degrees of freedom Sum((actual-expect)2/expect) = m-1, not m Really (m-1) +- sqrt(m-1), central limit again 99.7% of the time, (m-1) +- 3sqrt(m-1) Normalize: usually between -3 and 3 If biased, doubling input doubles the result

  17. Random number tests They re all chisquare tests FREQUENCY: how often does value X happen? GAP: Just saw X, how long since last X? RUN: How long is strictly increasing sequence? CONSTRUCTED VALUES: other tests on r[i+n] r[i] Low bits of several consecutive values Pieces of the internal state

  18. RUN test Probability 1/2, 1/3, 1/8, 1/30, 1/144, n!/(n+1) 8-bit values, everything eventually fails! 2-bit values, everything fails immediately! What s the chance of a strictly increasing sequence of length 5? 1/144? Moral: Kick the tires

  19. Chisquare tests are expensive Central limit theorem: total n, error sqrt(n) Bias of sqrt(n) lost in the noise Bias of n, probability p, need pn2 values p=1/1000, n=1000, 230 values, 30 seconds 242, 244 values is a day to a month Often, no up is detectable

  20. Existing generators

  21. LFSR for (i=0; i<32; ++i) { s = (s>>1) ^ ((s & 1) ? 0xedb88320 : 0); } yield s; Linear Feedback Shift Register N bits, cycle length of 2n-1, all except zero Same math as CRCs Trivial in hardware

  22. Delayed Fibonacci s[i] = s[i] s[(i+31) % 55]; i = (i + 1) % 55; yield s[i]; Recommended by Knuth Bottom bits form a 55-bit LFSR High bits more complicated, due to carries 3 seconds to sum 2 billion results (unrolled)

  23. Mersenne Twister 623 32-bit words of internal state (+ 1 bit) Iterates through state like Delayed Fibonacci Super Mega LFSR (cycle of 219937-1) 16 seconds to sum 2 billion results Postprocessing per result, shown below: y ^= (y >> 11); y ^= (y << 7) & 0x9d2c5680UL; y ^= (y << 15) & 0xefc60000UL; y ^= (y >> 18); yield y;

  24. ISAAC 256+3 32-bit words of internal state Iterates AND does pseudorandom lookup Reversible, nonlinear, no postprocessing Accumulator a does avalanche quickly 11 seconds to sum 2 billion results x = s[i]; a = (a ^ shift(a)) + s[(i+128) % 256]; s[i] = y = s[(x/4) % 256] + a + b; i = (i+1) % 256; yield b = s[(y/1024) % 256] + x;

  25. RC4 i,j, plus 256+bytes of internal state State is a permutation of 0..255 Nice math. Short cycles. Equivalent states. Results time of ISAAC, bytes 3x slower 0 1 2 3 4 5 6 7 1 0 3 6 3 5 0 4 1 7 3 7 1 3 0 0 3 6 5 5 6 4 2 6 3 7 4 6 i = (i + 1) % 256; j = (j + s[i]) % 256; swap(s[i], s[j]); return s[(s[i] + s[j]) % 256];

  26. FLEA(256) Based on ISAAC, 256+4 words of state Modifies random value, not iterated value Less secure than ISAAC, no faster, boo r for (i=0; i<256; ++i) { e = a[d % 256]; a[d % 256] = b; b = (c<<9) + (c>>23) + d; c = d ^ a[i]; d = e + b; yield c; } b c d a e

  27. FLEA(1) Reduce array a[] to 1 term 4 seconds to sum 2 billion values Passed noncryptographic tests for 242! r b c e = a; a = b; b = (c<<19) + (c>>13) + d; c = d ^ a; d = e + b; yield c; d a e Post to sci.crypt.random-numbers

  28. (Not-so-) New Tests

  29. NDA By Geronimo Jones, aka John Blackman http://gjrand.sourceforge.net/ Modified GAP test: saw x, how long since y? 4-bit chunks, gaps up to 48+1 16*16*49=12544 buckets Over 16x slower than GAP test over n values

  30. NDA vs FLEA(1) Found bias in 230values, that s fast Value shifted by 19: different values, so GAP missed it Tuned run tests, 224 values (bits 0,1,19,20) X + permute(X) = nonuniform Cure: mix those bits with something else

  31. FLEA, the sequel Extra rotate so bits don t hit themselves Changed ^ back to +, fiddled constants Passed noncryptographic tests for 242! r b c e = a; a = (b << 15) + (b >> 17); b = (c << 27) + (c >> 5) + d; c = d + a; d = e + b; yield c; d a e Post to sci.crypt.random-numbers

  32. Bitcounting By Orz, aka Bob Blorp2 Count the bits in a 32-bit values, divide by 2 Concatenate 5 such counts Estimate probabilities with a good generator Combine buckets with expect < 5

  33. Reimplement Bitcounting http://burtleburtle.net/bob/c/countx.c Map bitcounts to low, medium, high groups Concatenate groups for n words Calculate probabilities exactly Graycoding can deal with subtraction Buckets are correlated, fine, -5..5 not -3..3.

  34. FLEA vs Bitcounting New version fails in 236 Old version failed in 224, no tuning needed Everything like FLEA fails by 236 Shift amounts don t matter much. It s not where the bits are, it s whether they re there. Not enough avalanche from r[i] to r[i+4] Bitcounting is best chisquare test I ve seen

  35. Bitcounting is old Marsaglia s DIEHARD: COUNT-THE-1s Counts bits in bytes, not words Tries to account for correlated values Checks 5 consecutive bytes, 218 values I never saw it fail.

  36. Initialization Pretend initialization is a (slow) random number generator Seed it with a counting sequence John Blackman (aka Geronimo Jones) suggested seeding with random 1-bit differences

  37. Initialization, revisited Pretend initialization is a block cipher Apply avalanche test Pair of internal states differ in one bit Is every bit of internal state affected after init? Repeat for each bit in initial internal state Under a second, not hours And it does a better job than chisquare

  38. Avalanche, revisited Pretend pseudorandom number generator is a block cipher: internal state maps to r[i+4] Apply avalanche test: for every bit of internal state, how many bits of r[i+4] flip, don t flip? Test r[i+4] r [i+4] graycoded, too Test the generator in reverse, too Ideal result: 15.8/32. Actual result: 4/32. Runs in 1/10 a second

  39. Design with the avalanche test http://burtleburtle.net/bob/c/rngav.c Optimization: quit at first bad bit Optimization: do 256 pairs, then 512, Use rules of thumb & timings to arrange operations Use avalanche to choose best shift constants Run chisquare for a month for sanity testing

  40. New Generators

  41. 8.8 bits avalanche typedef unsigned long int u4; typedef struct ranctx { u4 a; u4 b; u4 c; u4 d;} ranctx; static void raninit( ranctx *x, u4 seed ) { u4 i; x->a = 0xf1ea5eed; x->b = x->c = x->d = seed; for (i=0; i<20; ++i) { (void)ranval(x); } } #define rot(x,k) ((x<<k)|(x>>(32-k))) static u4 ranval( ranctx *x ) { u4 e = x->a - rot(x->b, 27); x->a = x->b ^ rot(x->c, 17); x->b = x->c + x->d; x->c = x->d + e; x->d = e + x->a; return x->d; } Passes bitcount and other chisquare tests for 242 values 6 seconds to sum 2 billion values Posted it to sci.crypt.random-numbers

  42. 13 bits avalanche typedef unsigned long int u4; typedef struct ranctx { u4 a; u4 b; u4 c; u4 d;} ranctx; static void raninit( ranctx *x, u4 seed ) { u4 i; x->a = 0xf1ea5eed; x->b = x->c = x->d = seed; for (i=0; i<20; ++i) { (void)ranval(x); } } #define rot(x,k) ((x<<k)|(x>>(32-k))) static u4 ranval( ranctx *x ) { u4 e = x->a - rot(x->b, 23); x->a = x->b ^ rot(x->c, 16); x->b = x->c + rot(x->d, 11); x->c = x->d + e; x->d = e + x->a; return x->d; } Overkill? Still not doing full avalanche 11 seconds to sum 2 billion values

  43. Summary

  44. Rules of thumb Reversible Nonlinear Fast mixing At least 128 bit state Iterate over state Not worthwhile unless it s faster than RC4

  45. Chisquare tests Really slow, results in -3 to 3 are OK Need samples bigger than internal state Gap is good for big-state generators Run and bitcount good for small-state

  46. Designing noncryptographic pseudorandom number generators Use rules of thumb and timings to choose candidates Use avalanche test to compare candidates Use chisquare tests for sanity checking

Related


More Related Content