1

Regarding hash collisions, an attacker only has to do half of the work to find a collision when they can control both messages compared to when they are trying to find a weak collision. This can be explained with the birthday paradox.

I understand the birthday paradox, but can't quite see how it relates fully to strong collisions and why it shows they only take half the work of weak collisions. With the birthday paradox, each person already knows their own birthday in advance, so when the first person 'says' their birthday, everyone else can compare that with their own, and so on and so on.

If an attacker is trying to find two message that hash to the same value, the hashes of the newly modified messages aren't already known (unlike people's birthdays), so wouldn't an attacker have to create a load of hashes for one of the messages, store them, and then do the same for the other message and start comparing, how is this quicker than finding a weak collision?

My question is, how would an attacker try and find two messages that hash to the same value, so that it only takes half the work as if they were trying to find a weak collision?

Thanks.

Improve this question

2 Answers 2

Reset to default
3

To find a collision, the attacker generates a large number of unique messages and their corresponding hashes. The attack succeeds when any two hashes match. This is just like the birthday paradox, which speaks of the probability of any two people having the same birth date.

it only takes half the work

Careful, 2^128 isn't half of 2^256. 2^128 is the square root of 2^256. 2^128 is one "2^128th" of 2^256.

the attacker has 2 messages 'place 10$ in my account' and 'place $1000 in my account' and they want them to hash to the same value [...] the attacker would continually keep changing both message until they hash to the same value

In this situation, the attacker is given m1 and m2, and wants to find an x1 and x2 such that H(m1 + x1) = H(m2 + x2). Let's suppose that H is a 256-bit hash function, like SHA-256. The attacker tries 2^128 different values for x1, computing and storing 2^128 hashes H(m1 + x1). The attacker now tries different values for x2, computing hashes H(m2 + x2), looking for one that matches one of the x1 hashes. Eventually, this will succeed, but after how many attempts?

There are 2^256 possible hash values, so the probability of each attempt succeeding is 2^128/2^256 = 1/2^128. Therefore, we can expect this step to require about 2^128 attempts. Adding the two steps together, this attack would require, on average, about 2^128 + 2^128 = 2^129 evaluations of the hash function.

I don't think this usually goes by the name "birthday attack", since the probability math is quite different. Both attacks do have a similar complexity, however (about a square root of the search space, or 2^(n/2) for an n-bit hash function).

Improve this answer
5
  • Thanks @user595228, An example I read was along the lines of the attacker has 2 messages 'place 10$ in my account' and 'place $1000 in my account' and they want them to hash to the same value, so they add invisible spaces at the start and then end in both messages (not the best example but you get the idea). It said the attacker would continually keep changing both message until they hash to the same value. How would this work in line with the birthday paradox, the attacker changes the first message, hashes it and stores it...
    – RJSmith92
    Commented Oct 25, 2015 at 10:04
  • ...They then change the second, hash it and compare it with what's stored and then go back and change the first message, and so on, continually comparing with hashes from both previous messages? Thanks.
    – RJSmith92
    Commented Oct 25, 2015 at 10:05
  • 1
    Updated answer with that scenario.
    – Tim McLean
    Commented Oct 25, 2015 at 21:34
  • Thanks for all that @user595228, really appreciate it. The method you used equalled 2^129, whereas the birthday attack equals 2^128 (with the 256-bit hash). If you did the method that I described, given M1 and M2, you first modify M1 once, hash and store it. Then modify M2 once, hash it, compare with the previous and then store it. Then you go back to M1, modify it once again, hash it and then compare with the stored results, then store it. Would this equal 2^128? As you are not having to generate a bunch of hashes previous before you start comparing them. Thanks again.
    – RJSmith92
    Commented Oct 26, 2015 at 11:04
  • Hey @user595228 sorry to bother you, do you mind having a look at my previous post? I can't figure it out and just wanted to know if would work / would take 2^128 attempts in line with a birthday attack. Thank you
    – RJSmith92
    Commented Oct 29, 2015 at 13:55
2

Finding a collision using the birthday problem means during your attack you're storing the hashes of all previous attempts, and for each new hash, you're comparing that with all previous hashes.

Instead of targeting a certain hash, we're looking for looking for any collision.

Assuming we have a lot of memory and can quickly check against all previous hashes, it becomes faster.

Improve this answer
2
  • Thanks @Ammar, An example I read was along the lines of the attacker has 2 messages 'place 10$ in my account' and 'place $1000 in my account' and they want them to hash to the same value, so they add invisible spaces etc. in both messages (not the best example but you get the idea). It said the attacker would continually keep changing both message until they hash to the same value. How would this work, the attacker changes the first message, hashes it and stores it. They then change the second, hash it and compare it with what's stored and then go back and change the first message, and so on?
    – RJSmith92
    Commented Oct 24, 2015 at 23:27
  • The attacker would continuously generate something along the lines of hash("place $10 in my account[ARBITRARY_INVISIBLE_DATA]") and save the outputs. Every new hash he generates he would check against all previous outputs.
    – Ammar Bandukwala
    Commented Oct 25, 2015 at 16:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .