Code for Testing for Avalanche

A delta is the difference between two inputs, difference either from subtraction or exclusive-or. A hash causes a delta to achieve avalanche if every output bit differs with probability about 1/2 when two inputs differ by that delta. A function is said to achieve avalanche (no delta specified) if every one-bit input delta achieves avalanche.

Functions that do not achieve avalanche make bad hashes and rotten ciphers. The paper Evaluating Hash Functions examines these issues. One of the tasks in designing fast hashes and ciphers is finding functions that achieve avalanche quickly. Most such functions have "magic constants" -- constants that seem to be chosen at random. Often these constants are chosen at random, or from the first few digits of pi, or such. Choosing constants this way means there is no reason to believe they will be better or worse than any other constants.

This code allows magic constants to be chosen to pass the avalanche test. This guarantees that they will be exceptionally good for something. They may be exceptionally bad at something else, who knows. That is a danger of having a purpose.

This is the code:

standard.h maketest.txt
rand.h rand.c
recycle.h recycle.c
test.h testb.c
test.c

The current code is checking that, for every 2-bit input delta, the function (myff, reverse in mybb, similar to three calls to myf) causes at least 32 bits of the internal state to change with probability 1/4 (for random input pairs are tried).

A typical search regime:

I consider a hash to pass if it passes 24 configurations: all combinations of (tbtop, tbbot, tbone, tbtwo) x (tpran, tpcou) x (ttlim (ppp=1), ttcou (ppp=2), ttlea (ppp=1)). (See theorem Nofunnel to see where these tests come from.) Then I plug the hash into the self-test in lookup.c -- sometimes it still fails. I haven't identified what that self-test tests that these avalanche tests don't.

Other useful programs: sort.c and distinct.c, they can handle files of arbitrary length. Distinct only works correctly on sorted files.


Internal links:
Finding Characteristics in Block Ciphers
Evaluating Hash Functions
Calculating the HOMFLY knot polynomial
Table of Contents