5
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – thepacker
    Feb 24, 2016 at 21:24

1 Answer 1

Reset to default
5
$\begingroup$

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.

More information about the differential cryptanalysis of Keccak can be found here.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Why is it important that $a_{n} = 0$ ? $\endgroup$
    – k3170makan
    Feb 24, 2016 at 21:53
  • 3
    $\begingroup$ @k3170makan: because $a_n \ne 0$ isn't a collision $\endgroup$
    – poncho
    Feb 24, 2016 at 21:56
  • 1
    $\begingroup$ Oh my lawd, lols I okay I get it now haha $\endgroup$
    – k3170makan
    Feb 24, 2016 at 22:01
  • $\begingroup$ 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? $\endgroup$
    – k3170makan
    Feb 24, 2016 at 22:07
  • $\begingroup$ For a or some specific difference (you are not limited to one). But yes that is correct. $\endgroup$
    – Biv
    Feb 24, 2016 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.