The death of MD5

[tA-Kane]

It's an interesting read. I tried the provided sample Win32 executable, but it failed with an error of 0x8009000F.

[Skywing]

It's an interesting read. I tried the provided sample Win32 executable, but it failed with an error of 0x8009000F.

I'll let him know and ask him to post an updated version.  That's because he was doing something wrong with how he was generating a random number with cryptoapi.  It should probably work if you reboot after running it, since the keyset it creates is temporary I think.

(For that version, executions after the first are likely to break due to that bug.)

[tA-Kane]

What I did is I loaded the source up in VS2005 and simply replaced "CRYPT_NEWKEYSET" with 0.

However, since I'm not too familiar with the Cryptography API, I fear I may have broken the speed at which it works: it has been running for about four hours and has displayed "block #1 done" for several hours and has yet to display "block #2 done". Perhaps I misinterpreted the 45 minutes as being best-time rather than average-time?

[Arta]

I disagree.  As far as I know, there's still no practicle way (without a full brute force) to obtain the original data of MD5 based on the hash.  In other words, it's still safe for storing passwords. 

Not true at all -- if you can generate a collision, you don't need the original data.

[iago]

To generate a collision, you need the password, don't you?  Or is it actually possible to generate a collision based purely on the hashed data? 

[Arta]

It is. Generating a collision entails finding data to match a given hash. The hash is needed for comparison, but not the original data. I'm not sure if a brute-force attack on an unknown hash is feasible yet.

[iago]

It is. Generating a collision entails finding data to match a given hash. The hash is needed for comparison, but not the original data. I'm not sure if a brute-force attack on an unknown hash is feasible yet.

I thought that the collisions discussed here entailed finding two pieces of data that generates the same hash.  Am I mistaken about that, or did we make different assumptions? I haven't read the paper or anything, so I could very well be wrong there. 

[Kp]

It is. Generating a collision entails finding data to match a given hash. The hash is needed for comparison, but not the original data. I'm not sure if a brute-force attack on an unknown hash is feasible yet.

I thought that the collisions discussed here entailed finding two pieces of data that generates the same hash.  Am I mistaken about that, or did we make different assumptions? I haven't read the paper or anything, so I could very well be wrong there.

It depends what use of MD5 you're trying to defeat.  If you obtain the MD5 of someone's password and you simply want to masquerade as that user (but are satisfied with never learning their original password), you need only come up with a data sequence which suffers a collision with the known hash.  Then when you send that sequence off claiming it to be the password, the server will compute its MD5, get the same value as the MD5 as the correct password (since you picked this data sequence specifically for this property!), and conclude that you're the legitimate owner.  If the target site is badly thought out, you could then edit his account settings to point the e-mail associated with it to an account you own, then trigger the "password recovery" feature to get his real password (instead of some random sequence which happens to collide with his password).  On the other hand, if you're trying to spoof a document whose MD5 signature is known, you'd need the original document so you could check if your forgery looked even vaguely like the original.

Though, given that we're dealing with hashing algorithms, if you have the original input data, you can compute the hash result easily enough.

[iago]

It is. Generating a collision entails finding data to match a given hash. The hash is needed for comparison, but not the original data. I'm not sure if a brute-force attack on an unknown hash is feasible yet.

I thought that the collisions discussed here entailed finding two pieces of data that generates the same hash.  Am I mistaken about that, or did we make different assumptions? I haven't read the paper or anything, so I could very well be wrong there.

It depends what use of MD5 you're trying to defeat.  If you obtain the MD5 of someone's password and you simply want to masquerade as that user (but are satisfied with never learning their original password), you need only come up with a data sequence which suffers a collision with the known hash.  Then when you send that sequence off claiming it to be the password, the server will compute its MD5, get the same value as the MD5 as the correct password (since you picked this data sequence specifically for this property!), and conclude that you're the legitimate owner.  If the target site is badly thought out, you could then edit his account settings to point the e-mail associated with it to an account you own, then trigger the "password recovery" feature to get his real password (instead of some random sequence which happens to collide with his password).  On the other hand, if you're trying to spoof a document whose MD5 signature is known, you'd need the original document so you could check if your forgery looked even vaguely like the original.

Though, given that we're dealing with hashing algorithms, if you have the original input data, you can compute the hash result easily enough.

The first scenario is the one I was considering.  I fully agree that it's useless for signing documents now, that's not even an issue. 

For it to be an issue with passwords, it seems like it depends on how the passwords are used, then.  To be a threat, you have to find some way to obtain the MD5 of the password.  That could likely be done in 2 ways:
1. Sniff traffic containing the MD5 -- if you can sniff their traffic, odds are (in any webapp) you can see their password go by in plaintext.  It's still rare to see SSL used for sites.  So that's irrelevant. 
2. Have access to the password database -- if they have access to the database of MD5's, odds are it's already game over. 

However, if all you have is access to the MD5 hash, and the server requires that you send it an MD5 hash, which I don't think is very common at all, then yeah, this MD5 weakness is a danger.  But I don't believe I've ever seen a server that does that. 

For a web-app like, for example, Warrior's, I think the only weakenss in MD5 that could adversely affect its security is if there was a large amount of clustering, narrowing the number of brute-force attempts needed to guess the correct password.  But I don't believe that MD5 contains that particular weakness, so that's not a problem.

I guess what I'm saying is that whether or not it's a danger to an application depends rather strongly on how it's being used, and in the most common cases, web apps aren't secure anyway, so using MD5 to store passwords really doesn't matter. 

[dxoigmn]

If the target site is badly thought out, you could then edit his account settings to point the e-mail associated with it to an account you own, then trigger the "password recovery" feature to get his real password (instead of some random sequence which happens to collide with his password).

Minor nit-pick: Badly thought out as in storing a hash of the password and the password plain text. If the website only stores the hash, you're probably never going to recover the original password.

[Arta]

Note that numerous web apps don't guard password hashes very carefully. They are often stored in a cookie to facilitate autologon, and are easily exposed by  XSS attacks.

[Joe[x86]]

Personally, I bruteforced a password (a friend of mine's, we were exploiting a IPB, but enough about that) in about 45 seconds. It was two numbers and three letters, so not all that long, but eh?

[dxoigmn]

Note that numerous web apps don't guard password hashes very carefully. They are often stored in a cookie to facilitate autologon, and are easily exposed by  XSS attacks.

Well regardless, autologon is a pretty insecure concept as anyone with physical access can impersonate a user (unless you have the stored cookies expire after some set amount of time). I'm sure many websites don't even require physical access, just the contents of the stored cookie unless that cookie contains a hash of variables unique to a computer (i.e. IP address).

[iago]

Note that numerous web apps don't guard password hashes very carefully. They are often stored in a cookie to facilitate autologon, and are easily exposed by  XSS attacks.

If they are stored in a cookie, then you don't need to find a collision.  You just copy/paste the hash into your own cookie and proceed to log in. 

That's an interesting point, though.  How would you recommend storing passwords in cookies?  I was thinking of storing a salted hash, as well as the salt, but that wouldn't create any advantages versus packetlogs.  Maybe the IP and the password (or password hash) together, hashed.  But that would be annoying for dial-up users. 

[Arta]

You can't do it securely. It's just one of those times when lots of convinience outweighs a small security risk.