Ph.D Student | Chen Rafael |
---|---|

Subject | New Techniques for Cryptanalysis of Cryptographic Hash Functions |

Department | Department of Computer Science |

Supervisor | Professor Eli Biham |

Full Thesis text |

A cryptographic hash function *H*
takes a message *M* of an arbitrary length and produces an easy-to-compute
message digest *H(M)* which has fixed, relatively short size. *H(M)*
has to be collision free, i.e., it should be difficult to find any two messages
that have the same message digest. Two other important properties are: Preimage
resistance, i.e., given a message digest *s *it should be difficult to
find *M* such that *H(M)=s, *and second-preimage resistance, i.e.,
given *M _{1}* it should be difficult to find

* *

A widely known technique to attack the
collision freeness property is differential cryptanalysis. In this technique a
difference between two messages is chosen and the evolution of differences from
the plaintext through the intermediate data into the ciphertext is predicted.
The differences and the probabilities of the predictions are called *a characteristic*.
An attacker that uses the technique aims at finding a characteristic with high
probability, and at constructing an efficient algorithm that selects messages that
follow the differences of the characteristic. Our contributions are at both aims .

The *multi-block technique* is based
on our observation that characteristics of the compression function that
predict near-collisions and pseudo-collisions may have higher probabilities
than characteristics that predict collisions. It suggests building the
collision from a path of several blocks, each leads to a new (non-zero)
difference, where the last block leads to a collision. Moreover, we show that typically
the most efficient attack is constructed by using two blocks in which the first
and second message blocks have the same difference. We demonstrated this idea
by finding a collision of SHA-1 reduced to 40 rounds. All published attacks on
SHA-1 that we are aware of are based on these ideas.

For an efficient selection of
messages that follow the characteristic ,
we developed two techniques: *The neutral bits technique* eliminates the
probabilistic behavior of the characteristic up to some high round of the
compression function (typically Round 30 in SHA-1). *The second-order
differential technique* is based on our observation that differences with
specific patterns may be used for a more efficient selection of messages that
follows the characteristic. We call these patterns second-order characteristics.

Using these techniques we constructed
a collision attack on SHA-1 with a complexity of 2^{58} SHA
computations which is the most efficient published attack on this function.
These techniques were also crucial in finding the first collision of SHA-0 .