From: Bob Jenkins
<74512.261@compuserve.com>
Newsgroups: sci.crypt.research
Subject: Avalanche test for finding magic constants
Date: 16 Mar 1996 13:31:37 +1100
Organization: Sterling Software (Aust). Pty. Ltd.
A function passes the avalanche test if, for every input and output bit, a pair of inputs differing only in the input bit will differ in the output bit half the time.
I just finished code that runs the avalanche test. A trial run scanned 16 million functions and returned the 80,000 that did best, and it ran in about 4 hours on a 66mhz x486. Further iterations narrowed that down to 1 best function in less than a day.
This is a way of choosing the "magic constants" that are used in hash functions and block ciphers. The trial run above, for example, was finding 4 6-bit constants for shifts in ISAAC-64 (a cryptographic random number generator for 64-bit machines that requires 19 instructions per 64-bit result). They let the accumulator achieve avalanche after accumulating only 8 (uniformly distributed) values.
Bob Jenkins
PS Thank you Vincent Rimjen for your reference code for SHARK, which showed me how to use gcc to do 8-bit arithmetic on my x486!
Back to @Man's Homepage