Talk:Birthday attack

Readability

Could someone who is not a mathematician add a layman's description of the problem and its social significance right at the start? After reading the entire article, I'm still struggling to grasp what the Birthday Attack is exactly. Thanks. Meservy (talk) 10:09, 10 June 2010 (UTC)

I am not sure if the above has been answered.

[Electronic] Messages usually have some sort checksum (hash) to verify that the message has not been corrupted in transit. Examples of hashes people are more familiar with would be their zip code when placing something on layaway, the last four numbers of their social security number, or their day of the year they were born. The birthday problem is used to illustrate a counterintuitive phenomenon of hashes. It takes only 23 people in a room to have a greater than 50% chance of any two people in the room being born on the same day.

Applied to communication an illustrative scenario might go like this. Bob sends a message to Alice stating: “Eve should be demoted”. Eve intercepts the message and tries to get something like “Eve should be promoted” or “Steve should be demoted”, to hash to the same value as the true message. Coining it the ‘birthday attack’ emphasizes that it is not implausible given the probability. Though it is probably not something a script kiddie hacker would successfully execute or be interested in. More like a state sponsor or major corporate entity motivated to engage in misinformation such as “do launch the missiles now” verses “do not launch the missiles now”

Another application might be a piece of software with a publicly know hash code with just a few lines of malicious code planted in it in just the right way so that the software still hashes to the same value. Possible, but no simple feat. Bdayresponse (talk) 05:31, 15 April 2012 (UTC)

Bdayresponse, please note that the birthday attack does not apply to the scenarios that you describe. What you describe are situations for a preimage attack. The birthday attack does however work against digitial signatures in the scenario that is already described in the article (as well as many other situations). 178.195.230.127 (talk) 06:30, 15 April 2012 (UTC)

Very good clarification. As a lay person, this is the first I have heard of pre-image to distinguish the subtlety, but it makes sense. Both are trying to discover a hash collision, except in the fair/fraud example Alice might have a little bit of control over the intended target message, although in limited way since the target message is constrained to be a fair contract (assuming the number of ways to make a contract fair is far less than the number of ways to make a contract fraudulent). The birthday problem is not someone in the room having YOUR birthday, but ANY two people in the room having the same birthday, ergo to qualify as a birthday attack, the attacker must have room to play with both messages.

Though, in the contract problem it is not entirely clear why Bob is signing a hash prepared by someone else. One would think Bob would add something unique to him, such as a serial number and time stamp, to every contract before hashing and signing, ergo Alice would not know the hash value to be signed a priori. Also, in court it would seem easy to demonstrate that both the fair and fraud contracts have the same hash and that is not a coincidence. The only question would be who did it, Bob or Alice, so it sounds more a like a non-repudiation problem solved by always adding something unique before hashing.

As another aside, organizations may have documents that required 5 signatures that protocol dictates occur in a precise order. With pen and paper it may difficult to prove if something was signed out of order, but with hashes and digital signatures it seem signature order could be enforced.Bdayresponse (talk) 02:46, 17 April 2012 (UTC)

Digital signature susceptibility

I changed the name "Alice" to "Mallet". Because in IT Sec. it is common to use the names Bob and Alice for good communication partners and Eve or Mallet for bad communication partners. So Alice wouldn't fake signatur, but Mallet would. — Preceding unsigned comment added by 138.246.2.74 (talk) 10:58, 2 July 2011 (UTC)

Which table is correct?

The table given here and the table at Birthday_problem#Probability_table have different values. Which one is correct? Or if they're calculating different things, that probably should be made clearer. -- 205.175.124.30 (talk) 19:15, 12 November 2012 (UTC)

Git hash collisions

It would be interesting to add some discussion about the probability of git hash collisions, since git absolutely relies on the probability of hash collision being so low. — Preceding unsigned comment added by 108.68.105.246 (talk) 03:36, 24 November 2012 (UTC)

Doesn't the security of git depend on the collision resistance of the underlying hash function and not on the probability of a random collision? 178.195.225.28 (talk) 11:25, 24 November 2012 (UTC)