This program attempts to find iterative characteristics of a block cipher. If the block cipher is built of only shifts and xor, it works perfectly. If the block cipher has, oh, addition as well, the results of this program are amazingly worthless.

Some of the code is useful anyhow. bit.h and bit.c manage bitvectors. recycle.h and recycle.c are memory managers -- I've had programs that spend 90% of their time in malloc, so avoiding malloc is a good thing. gauss.c, well, Gaussian elimination is the closest thing there is to magic in the world, but this is all mod 2.

• makefile
• standard.h
• bit.h
• bit.c
• rand.h
• rand.c
• recycle.h
• recycle.c
• mix.h
• mix.c
• gauss.h
• gauss.c
• char.c

The program is currently rigged to detect characteristics in the mixing function I used in my old noncryptographic hash function LOOKUP.C. It finds one! (I've replaced that function with LOOKUP2.C.)

Here's how it works (or as the case may be, doesn't work):

First off, a characteristic is a delta in the input of a block cipher that is repeated in the output. For example, if f() is a block cipher and c is a characteristic, then f(x^c) = f(x)^c with greater than expected probability. You can substitute + or - or * for ^, then it's a characteristic relative to + or - or *.

Second: You can do linear algebra with ^. Specifically you can do Gaussian Elimination.

Applying the math: Suppose block cipher f has b bits. Choose a b-bit x at random. Calculate f(x^I), where I is a b-bit vector with just the i-th bit set, for all i in 0..b-1. Concatenate I with f(x^I). Then do Gaussian Elimination on those b vectors. If the initial vectors are linearly dependent in the bits that come from f(x^I), then there will be resulting vectors that are all 0 in the bits that come from f(x^I). Possible characteristics for f will be in those resulting vectors in the bits that come from I.

Note that the possible characteristics will not be zero because the original I's were linearly independentent. Note that even if there are no real characteristics, n possible characteristics will be found 2^-n of the time because that's how often b random b-bit vectors are linearly dependent n ways.

Finally, test all linear combinations of all possible characteristics found a few thousand times (other than the characteristic 0, which is known to always work but isn't interesting). Try it with different values of x.

Hash Functions and Block Ciphers

(Useful) Code for the Avalanche Test

Table of Contents