> What about a birthday attack? a birthday attack seems to work against MD5
Doesn't help.
A birthday attack means you can find two messages with the same hash
(i.e. a collision). It doesn't enable you to find a second message
with a particular hash value.
To sum it up
1. To finda particular hash:
Given H(m1) find m2 such that H(m2)=H(m1)
If H is a cryptographic hashing function with n-bits this requires 2^n
operations
2. To find a collision (birthday attack)
Find m1 and m2 such that H(m1) = H(m2)
This takes 2^(n/2) operations
Thus for a birthday attack to be successful, you need control over
BOTH the hashes. Thus it can be used to attack a digital signature
scheme by producing a good message and a malicious message with the
same hash (and thus same signature). It can't be used to recover
passwords.
Anyhow, even a birthday attack takes 213 days for our fantastic
trillion-MD5-ops-per-second machine... definately doable by the NSA,
CIA, KGB or something... but still not of much concern to most.
A birthday attack is fairly easy to defeat in a digital signature
scheme, plus if you're really paranoid you can use the 160-bit SHA
algorithm instead.