I understand that the MD5 algorithm isn't collision resistant, and that collisions between data of arbitrary size can be found with more efficient methods than brute-forcing.
However, I have read that MD5 is still a safe algorithm for, say, password hashing, because no method has been found to reverse-engineer the hashing algorithm.
In what cases could a hacker exploit a webpage or other secure client which was using MD5 for security?
If they were to break in to the system and download the hashed password file, they could, with difficulty, find passwords that would work.
While nobody has been able to turn the output of the MD5 hash into the original text. The bad news is MD5 does not take very much CPU time.
“Wait, is that bad news?” Actually, it is. When calculating hash values, you want to take more CPU time, rather than less. The faster the bad guys can test millions and billions of passwords, the quicker they can arrive at the one you are trying to keep secret.
I ran a test of five million nine character passwords and got the following results on my machine (using openssl, results in milliseconds):
If they want to test about 5 billion passwords, which would cover almost all the possible six character passwords, the CPU time would range from about 28 days for MD5 to 44 days for SHA256. This is with a single thread on a not very fast computer. If they invested a few hundred dollars for half a dozen graphics cards, this could be done in hours.
It is common for the hashing process to calculate the hash multiple times. We would calculate the hash of the password "abc123" and get “8be8efb0bfa…” If we then calculate the hash of the hash, we will get “98dead38ed2…”. You can see that if we do this ten or 100 times, we will hardly notice the difference in the time but the bad guys will have to take not hours but days or months.
Don’t forget, you only need to find a string that hashes to the value stored in the password table, not necessarily the original value. Any collision will do. There are ways of attacking the hash itself to find collisions that may be simpler that this brute force attack. For what it is worth, I doubt there are very many pairs of printable character strings that hash to the same value.
I am not sure this exactly answers your question but it seems relevant.
sha256 will perform faster in newer CPU compare to md5 . stackoverflow.com/questions/2722943/…
– mootmoot
Aug 12 '16 at 9:33
Consider a security system where users each have their own secret key, which is known by a server. When they send commands to the server, they hash the command and their secret key and then send the command the hash. The server does the same hash and confirms that the command was hashed with your secret key. This is basically what OAuth does (except they use SHA-1).
If an attacker can generate hashes without your secret key, they can send commands as you without getting access to your key.
Similar cases happen when you use hash functions to verify data. I could have a database of known good programs on my computer, and refuse to run any program that isn't in the database. If an attacker can cause a collision, they can maliciously alter a program, but get it to show up in the database as if it hadn't changed. This is basically what the Flame malware did:
Flame was signed with a fraudulent certificate purportedly from the Microsoft Enforced Licensing Intermediate PCA certificate authority. The malware authors identified a Microsoft Terminal Server Licensing Service certificate that inadvertently was enabled for code signing and that still used the weak MD5 hashing algorithm, then produced a counterfeit copy of the certificate that they used to sign some components of the malware to make them appear to have originated from Microsoft.
The reason this isn't a problem for password hashing is twofold:
Using a normal cryptographic hash function (MD5, SHA-*, etc.) for hashing passwords is completely broken anyway. Why bother breaking the hash function when you can brute-force the password? If you do password hashing correctly (PBKDF2), then you're not vulnerable, even if the internal hash function is MD5 (I'm guessing the salt and large number of iterations make this much harder).
There's very little point to finding a password hash collision. I guess you could log in as someone, assuming the server program (written by idiots who think MD5 is a password hashing function) doesn't choke on your gigantic binary password. And, if you have access to the hashes, you probably already have access to the server.
For situations like using as a hash of a password (where all you need is preimage resistance against classical computers), MD5 in practice is basically as good as SHA-1 and the SHA-2 hashes (SHA-256, SHA-512). The best published attack against MD5 only reduces its preimage resistance from its complexity from 2128 by a factor of 24 (to 2123.4), which is perfectly secure.
Granted if large-scale general purpose quantum computers were developed, the brute-force preimage attacks on MD5 would require only roughly sqrt(2128) = 264. Against the threat of quantum computers its recommended to use larger hashes; like SHA-256 (for preimage resistance) or SHA-512 (if you also want collision resistance with a complexity above sqrt(2128) for a quantum attacker).
Yes, MD5 is slightly faster than SHA-1 and the SHA-2 family, which is a bad for a hash function; but the difference is roughly a factor of two which is fairly negligible. And as any simple cryptographic hash function is way too fast for modern purposes, you need to perform many iterated rounds like MD5-crypt (and have a unique salt) to prevent computationally easy dictionary attacks.
But the bottom-line is that security-conscious developers need to know to avoid MD5 when collision resistance is necessary. For only partially justified reasons, they often decide to avoid MD5 even in domains where only preimage resistance is needed. Maybe they don't want to face criticism from others who have heard about collision attacks against MD5 and don't understand the subtle difference between a preimage attack and a collision attack. Maybe they haven't fully convinced themselves that their system only needs preimage resistance and that a clever attacker could not exploit their system using a collision attack against the MD5 hash. Or maybe they feel that since MD5 lacks collision resistance, that MD5 is inherently weaker than the others and more likely to be fully broken against preimage attacks before SHA-1/SHA-2 hash functions are broken.
