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.