Cryptanalysis: Collision attack in Hashing

By Paladion

June 15, 2005

In general two types of attacks have been found prevalent in hashing -preimage attack and collision attack. In this article we look at some of the details of the collision attack including - which hashing algorithms are vulnerable and how difficult it is to perform these attacks.

Collision attacks in hashing

A hash function takes a variable-length digital input and coverts it into a fixed-length random hash value. This random hash received is used to fingerprint the sent input file. But this method may not be free from vulnerabilities. In general two types of attacks have been found prevalent in hashing. These attacks are:

  1. Preimage attack
  2. Collision attack

In a preimage attack, an attacker tries to guess the input message from which a hash function produces a particular output. In a collision attack an attacker finds two messages with the same hashed output and sends the incorrect one to the receiver.

How can an attacker exploit this?

Now we will see how an attacker will exploit the collision vulnerability in the hashing functions. An attacker typically begins by constructing two messages with the same hash value where one message appears legal. For example when an attacker, ABC, discovers that the message "I,XYZ, agree to pay ABC Rs.5000.00 on 01/06/2005." has the same hash as "I,XYZ, agree to pay ABC Rs.50000.00 on 09/09/2005.",then he can try to get the victim,XYZ, to digitally sign the first message. The attacker, ABC, can then claim that XYZ actually signed the second message, and 'prove' his claim by showing that signature matches the second message.

How difficult is the collision attack?

Now we will see how difficult is the computation task to produce the collision in the SHA-1. SHA-1 function generates a 160-bit hash. That means every message hashes down to a 160-bit number. But as the number of possible hashes is so large, the probability of finding one is 2(power)80. This means if we hashed 2(power)80 random messages, we will find one pair that has been hashed to the same value. This is the 'brute force' way of finding collisions, and it depends on the length of the hash value. 'Breaking' the hash function means being able to find collisions faster than that. And that's what the researchers,Xiaoyun Wang, Lisa Yiqun Yin, and Hongbo Yu, did recently.

According to the research carried out by these scientists collision attack on SHA-1 requires an estimated work factor of 2(power)69 (approximately 590 billion) hash computations and it is way beyond the capacity of a normal computer.

On the hardware front these computations can be compared to the DES cracker which a group of cryptographers built in 1999. It was able to perform 2(power)56 DES operations in 56 hours. This machine requires a massive sum of Two fifty thousand dollars to build. If we extrapolate this machine using Moore's Law, a similar machine built today could perform 2(power)60 calculations in 56 hours, and 2(power)69 calculations in three and a quarter years. To build such a machine which will perform 2(power)69 calculations in 56 hours we will need 25-38 Million dollars. Computing improvements predicted by Moore's Law will make the attack more practical over time. Once a collision has been found, additional collisions can be found trivially by concatenating data to the matching messages.

Collisions were announced in SHA-0, MD4, MD5, HAVAL-128, RIPEMD and the latest victim is SHA-1.


Tags: Technical