Logo



Subscribe:
RSS 2.0 | Atom 1.0
Categories:
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Sign In
[Giagnocavo]Michael::Write()

# Thursday, July 22, 2004
Birthday attack in C#
How strong is a 128-bit hash? If you are looking to avoid collisions, the answer is not 2^^127, but 2^^64. Why? Due to the birthday paradox. Wikipedia says: “Specifically, if a function yields any of n different outputs with equal probability and n is sufficiently large, then after evaluating the function for about √n different arguments we expect to have found a pair of arguments x1 and x2 with f(x1) = f(x2).” The name “birthday“ comes into play because this holds true in a group of 23 or more people, chances are about 50% that two of them will share a birthday. The actual formula is Sqrt(n) * 1.2.

For a hash function, where strength is measured in powers of two, it's simple to calculate. For the exponent (128), just divide by two. So, we have 1.2(2^^(128/2)), but for most purposes, we leave off the 1.2 and just say 2^^64.

This means that if you're trying to find a collision, say, when attacking a digital signature system, the hash strength is considerably weaker than it sounds.

This sample program (Birthday.cs.txt (4.49 KB)) demonstrates this in C#, against a 32-bit hash (the first four bytes of MD5). Type in two messages, and it will find a collision by overwriting the first for chars of the message with random data. The code is not as clean, and it's definately not optimized for performance. That said, the 32-bit hash is successfully attacked in about 2.3 seconds on my machine (3GHz P4).

How effective is this attack? Very. It's extremely easy to modify most document formats these days. Pretty much every document has some place where you can insert or replace “hidden data” -- things a user or system do not see or process. For instance, in HTML, you could simply add the collision data inside an HTML comment. In a plain text file, you could modify spacing, tabs, and perhaps some other punctuation. It wouldn't change the meaning or validity of the document, but it allows you to generate enough combinations to find a collision.

After finding two colliding documents, you send the “original” to the victim, who then signs it. Then you take the good signature and substitute your “bad” document -- presto, a fake signature.

How can you prevent this? One way which might not always work is to modify a document before signing it. The real way is to use a hash long enough to provide the level of security you need. If you want “128-bit” security, in the sense that someone needs 2^^127 or so processing power to break it, then use SHA256. If for some reason you only have shorter algorithms at your disposal, a possibility is running the hash function again, with modifications to the document (for instance, switch every two bytes). This would give you a longer output.
Code | Security
Thursday, July 22, 2004 9:29:51 PM UTC  #    Comments [1]  |  Trackback

Monday, August 23, 2004 1:18:22 AM UTC
Michael: You are the man. This is definitely a kick a33 post. Where did you come across this? I'd love to read some more on it.
Bill | billAT NOSPAMdevbuzz dot com
OpenID
Please login with either your OpenID above, or your details below.
Name
E-mail
Home page

Comment (HTML not allowed)  

Enter the code shown (prevents robots):
Live Comment Preview