Small-State Noncryptographic Pseudorandom Number Generators
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;#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;
}
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);
}
}
Outline of Talk
•
Definitions
•
Rules of thumb
•
Chisquare tests
•
Existing generators
•
(Not-so-) New Tests
•
New Generators
Block Cipher
Message
Mixing Function
Encrypted text
Secret Key
•
Avalanche: every input bit hits every output bit
•
Block ciphers do avalanche 12x or so
Hash Function
User Input
Combining step
Initial Seed
Hash Value
Mixing Function
Postprocessing
Pseudorandom Number Generator
Seed
Initialization
Internal State
Postprocessing
User Results
Mixing Function
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)
Rules of Thumb
Mix Should be Reversible
•
Random mix: average cycle of 2
n/2
•
Reversible mix: average cycle of 2
n-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 2
64
values per application
•
2
32
seeds producing 2
32
values each
•
2
-32
chance of cycle or overlapping sequence
•
2
32
*(2
32
*2
32
)/2
3*32
= 1, not good enough
•
2
32
*(2
32
*2
32
)/2
4*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 Testing
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 pn
2
values
•
p=1/1000, n=1000, 2
30
values, 30 seconds
•
2
42
, 2
44
values is a day to a month
•
Often, no “up” is detectable
Existing generators
LFSR
for (i=0; i<32; ++i) { s = (s>>1) ^ ((s & 1) ? 0xedb88320 : 0); }yield
s;
•
L
inear
F
eedback
S
hift
R
egister
•
N bits, cycle length of 2
n
-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
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680UL;
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);
yield y;
•
623 32-bit words of internal state (+ 1 bit)
•
Iterates through state like Delayed Fibonacci
•
Super Mega LFSR (cycle of 2
19937
-1)
•
16 seconds to sum 2 billion results
•
Postprocessing per result, shown below:
ISAAC
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;
•
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
RC4
i = (i + 1) % 256;
j = (j + s[i]) % 256;
swap(s[i], s[j]);
return s[(s[i] + s[j]) % 256];
•
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
4
5
2
6
3
0
7
1
1
0
7
1
0
1
3
0
3
2
3
6
6
3
5
6
3
4
5
5
3
7
0
6
4
7
4
6
FLEA(256)
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;
}
•
Based on ISAAC, 256+4 words of state
•
Modifies random value, not iterated value
•
Less secure than ISAAC, no faster, boo
a
b
d
c
e
r
FLEA(1)
e = a;
a = b;
b = (c<<19) + (c>>13) + d;
c = d ^ a;
d = e + b;
yield c;
•
Reduce array a[] to 1 term
•
4 seconds to sum 2 billion values
•
Passed noncryptographic tests for 2
42
!
a
b
d
c
e
r
Post to sci.crypt.random-numbers …
(Not-so-) New Tests
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 2
30
values, that’s fast
•
Value shifted by 19: different values, so GAP
missed it
•
Tuned run tests, 2
24
values (bits 0,1,19,20)
•
X + permute(X) = nonuniform
•
Cure: mix those bits with something else
FLEA, the sequel
e = a;
a = (b << 15) + (b >> 17);
b = (c << 27) + (c >> 5) + d;
c = d + a;
d = e + b;
yield c;
•
Extra rotate so bits don’t hit themselves
•
Changed ^ back to +, fiddled constants
•
Passed noncryptographic tests for 2
42
!
a
b
d
c
e
r
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 2
36
•
Old version failed in 2
24
, no tuning needed
•
Everything like FLEA fails by 2
36
•
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, 2
18
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
New Generators
8.8 bits avalanche
typedef unsigned long int u4;
typedef struct ranctx { u4 a; u4 b; u4 c; u4 d;} ranctx;#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;
}
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);
}
}
•
Passes bitcount and other chisquare tests for 2
42
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;#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;
}
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);
}
}
•
Overkill? Still not doing full avalanche
•
11 seconds to sum 2 billion values
Summary
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
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.
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
