# Differential Cryptanalysis for Hash functions

How is differential cryptanalysis used to attack hash functions? I've been struggling through a couple academic papers and thesis's on the subject but they all sound like greek to me. Does anyone know who to explain this in simple enough (layish) terms?

I get how differential cryptanalysis methods work (a few of them) against Block ciphers but I'd really like to know how they can be used to target hash functions.

• The main goal in respect to hashfunctions is to create collisions. h(m_1) = h(m_2). Differential cryptanalysis of hash functions is all about creating (small) differences in messages and creating the same hash value or expected differences in hashed values. In very layish terms. – thepacker Feb 24 '16 at 21:24

In the case of block ciphers, differential cryptanalysis aim to measure the changes between inputs and outputs with a probability. The goal is to predict what the result will be before the last round and try to extract the key.

For hash functions, your aim is to find a second-pre-image.

I will take Keccak as an example. It is a sponge construction interweaved with 24 iterations of a round function $\text{Keccak-$f$}$.

How does it work (very simple version)?

1. Analyse the round function and retrieve its differential probabilities or interesting properties (here $\text{Keccak-$f$}$ has some invariants). Consider $(a_0 \implies a_1)$ where [$a_0$/$a_1$] is the difference [before/after] the application of the round function.

2. Try to find a trail such as $(a_0 \implies a_1 \implies \ldots \implies a_n)$ which keeps an interesting probability and where $a_n = 0$.

In the case of SHA3-256, you will be looking for the 256 first bit of the difference state to be $0$ as they correspond to the output.

Once you get this characteristic (good luck with that!), you can try to find a collision by computing random inputs with difference $a_0$ and try to find two with the same hash. There you got a collision.

• Why is it important that $a_{n} = 0$ ? – k3170makan Feb 24 '16 at 21:53
• @k3170makan: because $a_n \ne 0$ isn't a collision – poncho Feb 24 '16 at 21:56
• You want to look for a specific input difference that when processed through all the rounds results in an output difference of nothing i.e. $a_{n} = 0$ with a probability that is significant enough. Correct? – k3170makan Feb 24 '16 at 22:07