Difference between Bday attack and preimage attack?

killuah72 · July 2010

I'm so confused... can someone please explain to me the difference between a birthday attack and a preimage attack?

Both of their definitions sounds exactly the same to me.

dynamik · July 2010

The birthday attack is a statistical model that exemplifies the effort involved with a pre-image attack.

The birthday paradox illustrates the tremendous difference between the effort required for a pre-image attack and a collision attack. If you are trying to find someone who has the same birthday as you, you'll have to ask 253 people to have a 50 per cent chance that at least one of them shares that birthday. But if you only want to have two people with the same birthday regardless of what day that is, you can make do with far fewer people. Within a group of only 23 people, there is a 50 percent chance that two of them will share a birthday.
If an attack is successful with far fewer attempts than in the brute force method, the procedure is considered cracked. According to Schneier, this is exactly what the Chinese research group has accomplished: they are said to have developed a method of finding a collision with 269 operations instead of 280. The number of operations now necessary would then be lower by a factor of 2,048 (211).

Hash cracked - The H Security: News and Features

killuah72 · July 2010

I'm using Darril's book too and that's the explanation on his book. From what I understand, both of them tries to create a message that produces the same hash. I tried youtube but couldn't find a video of someone showing the two attacks in action.

So from what dynamik is saying, the birthday attack is just the model and the preimage attack is the attack. They shouldn't have put the word "attack" in "birthday attack" if its not really an attack... It confused the heck out of me.

dynamik · July 2010

I like his definition better. Sorry, I was falling asleep when I wrote that. I'm more used to generally speaking about the birthday paradox/problem.

It seems like the differentiation in this context is that with the birthday attack, you only need to find two messages that produce the same hash while in the pre-image attack you have to find on hash that matches another specific hash.

Everlife · July 2010

The birthday attack could be used as an attack against the perceived integrity of a hash value. Take this for example:

The imaginary hash algorithm Techexam10 is the industry standard hash algorithm when used to verify the integrity of a forensic image. A suspect is accused of sending an email to a coworker threatening her life. The prosecution extracts the message from a forensic image of the suspect's machine.

Fast forward to the trial...

The suspect's attorney shows that their experts have been able to successfully create a collision using the Techexam10 algorithm using two files of similar sizes as the forensic image with minimal time, money, and minimal computing power. They present these findings in court stating that the integrity of the forensic image cannot be trusted due to the above, so the evidence extracted from the image should not be trusted either.

Let's ignore whether or not this would be a successful argument and instead look at what has occurred. The defense has been able to successfully tarnish the integrity of the Techexam10's algorithm using a birthday attack. It may not be an attack in the same way we see think of a DoS attack, but it is still an attack on the integrity the algorithm is providing.

With a preimage attack, think of something like 0phtcrack. You have the hash value of the password and you are attempting to find another password that produces the same hash value. This may or may not be the password that was used, but it is a password that produces the same hash value.

Hope this helps!

killuah72 · July 2010

Thanks I get it now. I'm taking the test in 3 days. Hopefully 10 days of study is good enough lol.

Difference between Bday attack and preimage attack?

Comments