International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.

Details

Rafi Chen (#651)
Name Rafi Chen
Topic of his/her doctorate. New Techniques for Cryptanalysis of Cryptographic Hash Functions
Category foundations
Keywords hash functions
Ph.D. Supervisor(s) Eli Biham
Year of completion 2011
Abstract 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 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.
E-Mail Address rafi_hen (at) inter.net.il
Last Change 2011-08-10 11:27:11
To provide an update on this entry, please click .

Contact: phds (at) iacr.org

[ IACR home page ] [ IACR PhDs page ] © IACR