Technical Report PHD-2011-08

TR#:PHD-2011-08
Class:PHD
Title: New Techniques for Cryptanalysis of Cryptographic Hash Functions
Authors: Rafael Chen
Supervisors: Eli Biham
PDFPHD-2011-08.pdf
Abstract: A cryptographic hash function H takes a message of an arbitrary length and produces an easy-to-compute message digest H(M) which has fixed, relatively short size. The message digest is used as the digital fingerprint of the message and it has to satisfy several properties. The most important property is “collision-freeness”, 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 string s that has the length of a message digest it should be difficult to find a message M such that H(M ) = s, and second-preimage resistance, i.e., given a message M1 it should be difficult to find M2 such that H(M1)=H(M2). An example for the importance of the “collision-freeness” property is demonstrated by digital signature schemes. In such a scheme the signer hashes a message, signs the message digest, and sends the message and signature to the receiver. The receiver hashes the message and verifies that the signature on the message digest is authentic. If the signature verification succeeds, the receiver concludes that the message is authentic, and if it fails he clearly concludes that the message is forged or modified. If the hash function is not collision-free, the sender may find two different messages with the same hash value. He can then sign and send one message along with the signature, and claim later that he sent and signed the other message with the same signature. The receiver cannot disprove the claim since the signatures on both messages are valid and identical. Similarly, if the receiver holds such a pair of messages, say an innocently looking message and an offending message, and he succeeds to receive a signature on the former, he can claim that he received the signature of the latter, and the signer cannot disprove it. In cryptanalysis of cryptographic hash functions the required properties of hash functions are studied. In case a property is shown wrong using some algorithm, the algorithm is called an “attack” and the function is considered “broken”. A widely known attack technique is differential cryptanalysis, which uses differences to attack a function. In this technique an attacker searches for a well chosen difference between the ciphertexts of two messages. If pairs of messages are selected with a particular difference, then the probability to find a pair with the well chosen ciphertexts difference is higher than in a random choice of pairs. Such predictions of the evaluation of differences from the plaintext through the intermediate data into the ciphertext are called characteristics. A characteristic defines the initial, intermediate and final differences, and the probabilities to receive these differences when a pair of messages (with the initial difference) is hashed. Differential cryptanalysis of hash functions aims at finding a characteristic with high probability, and at constructing an efficient algorithm that selects messages from which at least one follows the differences of the characteristic. Our contributions are in both aims. The multi-block technique is related to the first aim. It 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. Moreover, we identified a weakness of Merkle-Damgard construction that enables using these near and pseudo-collisions. The technique suggests to build the collision from a path of several blocks, each leads to a new (non-zero) difference, where the last block leads to a collision. In many cases such a technique is more efficient than the formerly used attacks of a single block. Moreover, we show that using a two-block collision in which the first and second message blocks have the same difference, is typically the most efficient attack. 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. In order to find high-probability characteristics of the compression function, we analyze the differential properties of each operation that the round function uses. Along with heuristics assumptions we construct a first-order characteristic of the compression function, that predicts collision. For an efficient selection of messages that follow the characteristic, we developed two novel techniques: The neutral bits technique and the second-order differential technique. 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). Hence, the complexity of the attack is affected by the probabilistic behavior after this round. 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 differences of the characteristic. We call these patterns second-order characteristics. The technique defines guidelines for the construction of a first-order characteristic such that second-order characteristics with high probability may be found. It also provides an efficient algorithm for selection of messages that uses the second-order characteristics. This algorithm uses the neutral bits technique along with other auxiliary techniques. 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, whose complexity was 2^51. This collision consisted of four blocks, and used the neutral bits technique.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2011/PHD/PHD-2011-08), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2011
To the main CS technical reports page

Computer science department, Technion