Understanding Small-State Noncryptographic Pseudorandom Number Generators
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.
- Pseudorandom Number Generators
- Cryptography
- Pseudorandom Algorithms
- Noncryptographic
- Block Cipher Encryption
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
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; }
Outline of Talk Definitions Rules of thumb Chisquare tests Existing generators (Not-so-) New Tests New Generators
Block Cipher Encrypted text Mixing Function Message Secret Key Avalanche: every input bit hits every output bit Block ciphers do avalanche 12x or so
Hash Function Mixing Function Hash Value Postprocessing Initial Seed Combining step User Input
Pseudorandom Number Generator User Results Postprocessing Internal State Initialization Mixing Function Seed
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)
Mix Should be Reversible Random mix: average cycle of 2n/2 Reversible mix: average cycle of 2n-2 Reversible gives uniform distribution
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
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
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
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!
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
Chisquare Tests Central Limit Theorem: actual = n +- sqrt(n) (actual-expect)2 = sqrt(expect)2 = expect (actual-expect)2/expect = 1
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
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
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
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
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
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)
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;
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;
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];
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
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
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
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
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
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
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.
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
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.
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
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
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
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
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
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
Rules of thumb Reversible Nonlinear Fast mixing At least 128 bit state Iterate over state Not worthwhile unless it s faster than RC4
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
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
