## ISAAC: a fast cryptographic random number generator

I have a challenge and small prize associated with breaking ISAAC.

The files below implement ISAAC in C. The function randinit() must be called before ISAAC can be used, but after that any module that #includes rand.h can call rand() to get 32-bit random values.

• standard.h
• rand.h
• rand.c (rand.c is optimized for speed)
• randport.c (randport.c is optimized for speed except it's portable to platforms where integers are bigger than 4 bytes or characters are bigger than 1 byte)
• readable.c (readable.c produces the same results as rand.c but the C code is easier to read, and it doesn't need rand.h or standard.h)
• randvect.txt (the results if you compile any of these with -DNEVER and run it)
• randseed.txt (the results if you do "gcc -O rand.c randtest.c -o rand" then run rand)

ISAAC (Indirection, Shift, Accumulate, Add, and Count) generates 32-bit random numbers. Averaged out, it requires 18.75 machine cycles to generate each 32-bit value. Cycles are guaranteed to be at least 240 values long, and they are 28295 values long on average. The results are uniformly distributed, unbiased, and unpredictable unless you know the seed.

Others have translated ISAAC into other languages:

ISAAC-64 generates a different sequence than ISAAC, but it uses the same principles. It uses 64-bit arithmetic. It generates a 64-bit result every 19 instructions. All cycles are at least 272 values, and the average cycle length is 216583.

The following files implement ISAAC-64. The constants were tuned for a 64-bit machine, and a complement was thrown in so that all-zero states become nonzero faster.

There are lots of random number generators out there. Why use ISAAC?

• Why not use x=ax+b mod p? Because multiplication and mod are slow. On a Sparc it was clocked at being five times slower than ISAAC. Also, ISAAC gives any 32-bit number, while ax+b mod p gives numbers between 0 and p-1 for some prime p. Also, ax+b has easily detected patterns (for example, xi+1 is always axi+b mod p).
• Why not use RC4? RC4 is three times slower, more biased, has a shorter minimum and average cycle length, and is proprietary. No way is known to break either RC4 or ISAAC; both are immune to Gaussian elimination. Use the gap test on scaled-down RC4 to see its bias. (RC4 is still very good, much much better than x=(ax+b)%p.)
• I've written some tests for random number generators, which can be used to test ISAAC, RC4, ax+b mod p, or any random number generator you feel like writing.
• ISAAC should work on any 32-bit platform. (Porting it to a 64-bit machine like ALPHA may require masking out overflows in a, randrsl, and mm, or it may just need an adjustment of the definition of ub4, or it may work without modification. If someone ports it to an ALPHA, send me mail at bob_jenkins@burtleburtle.net showing me what you did.) The code in isaac64.c has been run on an ALPHA and a x486 with gcc; it produces the same results on both.
• I presented a paper, ISAAC, at the 3rd Fast Software Encryption Workshop. An online version, somewhat more complete than the published version, is here.
• Bias is detectable after 237 values for RANDSIZL=3, 245 for 4, 253 for 5, 261 for 6, 269 for 7, and 277 values for RANDSIZL=8.
• Challenge, started 1996/march/27: The files randtest.c gives the first 2560 results of ISAAC initialized with an unknown seed, along with the program that initialized ISAAC and produced the results. What was the seed? Send mail to bob_jenkins@burtleburtle.net. (Converting bytes to ub4's is endian-dependent, so the seed will only be English on something like an 80?86 machine.)

I changed the seed 1998/february/10 because I can't reproduce the old seed. Breaking either the old or the new counts.

• PRIZE, started 1998/february/6: \$1000 (USA dollars) to whoever sends me the solution to the above challenge (plus publicly revealing a repeatable method for determining it) first. I'll also offer \$100 for the first bias that can be detected with RANDSIZL=8 (in sequences of length less than 264 values) (starting with almost all seeds) (exceeding an absolute value of 4 times the standard deviation) (the test must start not knowing the seed).

ISAAC hasn't been broken since it was published 11 years ago. No bias has been detected either. I am offering these prizes in an attempt to get others to try to break it and assure those techniques are published. Apologies for having such a small prize. If you find successful attacks or biases in smaller versions of ISAAC, I'll include them in isaac.html, even though there are no prizes for them. I'm interested in attacks and biases against RC4 as well. Other fast stream ciphers are SEAL and WAKE.

Attacks on ISAAC by someone other than Bob Jenkins:

• 2001: Marina Pudovkina published an attack on ISAAC with estimated running time of 4.67x101240.
• 2006: Jean-Phillipe Aumasson pointed out that I provided no official way of seeding ISAAC. If the lack of an official seeding routine is interpreted as allowing a null seeding routine (directly setting the internal state to a known value), that allows the output to be predicted.

I provided no official seeding routine because I didn't feel competent to give one. Seeding a random number generator is essentially the same problem as encrypting the seed with a block cipher. ISAAC should be initialized with the encryption of the seed by some secure cipher. I've provided a seeding routine in my implementations, which nobody has broken so far, but I have less faith in that initialization routine than I have in ISAAC.

As ISAAC is intended to be a secure cipher, if you want to reseed it, one way is to use some other cipher to seed some initial version of ISAAC, then use ISAAC's output as a seed for other instances of ISAAC whenever they need to be reseeded.