Diffusion in a block cipher?

Question

For a given block cipher, I would like to verify if any input word diffuses to all output words.

For example in Twine block cipher, they define diffusion as "every output word is dependent of every input word".

How can we check by the program? Is there any algorithm or program to test this property?

I couldn't write a computer program for that. Any help or reference would be appreciated.

Answer 1

In order to assert the diffusion of a block cipher you need to show that every bit of the output depends on every bits of the input. This can be done by hand when the block cipher is not too complex.

A simple case: AES

AES you can see that a difference in a word will be propagated into the full block after 2 rounds (look at the $\star$).

This proves the word diffusion, now you need to prove that the S-box is actually safe. In other word show that any bits in the input have an influence on any bits in the output of the S-box (testing for differentials cryptanalysis is one of the way to do it).

A more complex case: Twine

Twine uses a 16 branches Feistel network with a round function. This round function uses multiple logical operations: $\lor, \land, \oplus$.

In order to show the bit dependency, we could take the code of the block cipher, and replace every of these 3 logical operators by $\lor$. We could also replace all the 4-bits S-box by a direct transposition to $15$ or $0x1111$ in binary.

Using a null input where only 1 bit is flipped (thus in the case of Twine, 64 test), and passing it through the modified, we verify that all the output bits are set to 1.

Also note that the bitwise shift << >> and rotations <<< >>> are preserved.

This approaches guarantees that any bits in the output depends of every input bits.

However we modified the S-box, therefore it is left to prove is that these S-box also have a nice diffusion using differential cryptanalysis for example.

This approach is the same as the one presented in this analysis of MD5.