Ph.D Thesis

Ph.D StudentChen Rafael
SubjectNew Techniques for Cryptanalysis of Cryptographic Hash
DepartmentDepartment of Computer Science
Supervisor PROF. Eli Biham
Full Thesis textFull thesis text - English Version


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 M1 it should be difficult to find M2 such that H(M1)=H(M2).

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 258 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 .