Unwired

What is MD5 and Why Should You Care That It’s Broken

kris-szabo

I came across an interesting article today discussing a talk with one of Kapersky Lab’s analysts, Evgeny Aseev. The discussion centers around the use of MD5 hashes, how they are no longer enough, and involves a few dropped comments about the H B Gary attack by Anonymous this year. This quickly becomes a bit technical so here’s a quick run-down of MD5.

What is MD5?

MD5 is a cryptographic function (it’s math!) that takes a blob of data and creates a relatively short string from it. This string is called a hash value. Hash functions, such as MD5 are sometimes called one-way hashes, which means it’s easy to go from the blob to the hash value, but it’s difficult to go from the hash back to the blob of data. One peculiarity of MD5 is that, while not very common, different blobs of data can have the same hash value.

So what is MD5 used for and why is it important? One use of MD5 is as a checksum of files. For instance you can download a large file, say an installer from a company. The company supplies you with the installer file and an MD5 hash value. Once you have finished downloading the file you can run MD5 on the installer and if the result matches the MD5 hash value given by the company, you can be fairly sure it’s the file you wanted to receive and it hasn’t been corrupted in the download.

Password Hashing

More generally, MD5 is used in many password systems as storage for a user’s password. When your password is first set, the system creates a hash value and stores that to the database. When you try to log in, it takes your password and runs MD5 on it. If the resulting value matches the one present in the database, you are allowed to log in. As you can see, on the surface this means that even if someone manages to steal a password database they still wouldn’t be able to steal your password.

As a side note, many people make a difference between encryption and hashes. The media is particularly notorious for this. Many may note that during the Sony PlayStation Network attack, the media reported that the password database had been stolen, and it wasn’t encrypted. This is true, in that you didn’t need to decrypt the database, but the passwords were all stored in a hash value generated by any of a number of hashing functions. In general, passwords are stored hashed rather than encrypted because hashing a password response and comparing it to a stored hash is fairly secure, while still being fast. Decrypting a database each time a password is entered, on the other hand, is a slow process and grows exponentially slower as more accounts are added to the system.

How is MD5 Broken?

So, now what’s the deal with MD5 hashes? Well, remember we said that two different blobs of data can have the same MD5 hash value? Well in theory, an attacker doesn’t need your password to access your account, he just needs a password that has the same hash value as yours. Therein lays one of the major weaknesses of MD5. Currently, there are easily available databases called Rainbow Tables. These Rainbow Tables are essentially a combination of random letters, numbers, and symbols paired with their pre-calculated hash values. In theory, all an attacker needs to do is see the hash value of your password in the database, look up this hash in the Rainbow Table, and use a password that hashes to the same value as your password. Current Rainbow Tables seem to hold values of essentially every password up to ten characters comprised of only lower-case letters, and every password up to eight characters comprised of uppercases, lowercases, digits, and spaces.

Generally, this kind of attack is an “escalation” attack. At some point the attacker has gained enough access to copy the password database and can now start matching password hashes against Rainbow Tables. Another vector an attacker could use, is taking a Rainbow Table and using each value against an account until one of the passwords work. This latter approach doesn’t tend to work very well on modern systems. Most modern systems of any significant design, lock an account out after 3-30 password attempts and require administrator intervention. In general, it has been fairly accepted that MD5 is broken and should not be used for authentication for well over a decade now. That said, MD5 is still widely employed by web applications and even some enterprise equipment vendors.

Enter H B Gary

So how does H B Gary figure into this? Aseev makes a throw away comment about password standards that were being used at H B Gary. The principals whose accounts were compromised used passwords consisting of six letters and two numbers. If they were being hashed using the MD5 function, suitable password candidates would exist within the Rainbow Tables. A second throw away comment is that these same principals used the same passwords on both their Google accounts and H B Gary’s internal systems. The comments beg one question however, and this is how did the attackers from Anonymous know what the hashes were. Above we mentioned that most modern systems lock out an account if someone is trying to brute force the password. This train of thought and other reports on the situation make it seem as if Google accounts are missing these simple lockout functions.

Is My Password Safe?

So then, is my password safe? The short answer is no. The long answer is, it depends. Some systems are using more secure hashing functions, others still rely on MD5 and its hard or impossible to know which any given system is using. It’s best to assume that any service that doesn’t say how your password is being stored is running MD5. So, now that we are sufficiently paranoid, how do we protect ourselves? First approach is, unfortunately, only a stop gap. Use a password that is not in a Rainbow Table and hope for the best. This means picking a password that is greater than 10 characters and contains upper cases, lower cases, numbers, spaces, and symbols. This will only continue to work until new Rainbow Tables are developed that cover these password rules too. A better form is two-factor encryption: The use of a password and a hard token for instance. These systems have flaws too, mostly they are too complex for the average user, and the companies that provide them can, and do get cracked. In the long run, the final answer is simple: long, strong passwords, and training computer users to understand basic security principals.

MD5 password hashes are dead