Cracking MD5 ... with Google?!

The MD5 algorithm has a new vulnerability: Google!

Here's a piece of news that will worry anyone interested in security (which should be pretty much everyone who reads Network World): A programmer by the name of Juuso Salonen has created a Ruby script called BozoCrack that cracks MD5 hashed passwords with remarkable success and with very little effort.

Before we go any further, let's have a little background: Computer systems need a mechanism to authenticate users and processes so that the good guys can get in to do work and the bad guys are locked out.

IN PICTURES: The Security Industry All-Stars

The most common authentication method is to use a name and a password, but if you were to store the password in plaintext on the system you would run the risk that passwords could be exposed. A common solution is to not store the password at all but instead keep something called an MD5 hash of the password.

MD5 is the fifth version of the Message-Digest cryptographic hash "function" created by the renowned computer scientist Ron Rivest. An algorithm implementing MD5 takes in strings and outputs 128-bit hash values that have several interesting attributes.

Those attributes: Any input string can be hashed (the string can be of arbitrary length and character set) in a reasonable amount of time and it is computationally impossible in practical terms (unless you have years and access to a supercomputer) to generate a string with a specific hash value, make a change in a string without changing the hash value, and find two different strings with the same hash value.

So, if you take a string such as "mysecretpassword" and run it through an MD5 implementation you get the hash value "4cab2a2db6a3c31b01d804def28276e6." Change a single character and the hash value will also change and do so unpredictably.

With 128 bits you have 3.4 x 10^38, or around 340 undecillion possible hash values. As the relationship of input string to hash value and vice versa isn't predictable, you have what is called a "one way" function; you can go from string to hash value but not from hash value to string.

In practice, when a user logs in to a computer, the password's MD5 hash value is calculated on the fly, the account name looked up in a database, and the saved and calculated hash values compared. Only if the values match is the user allowed access.

You can see that storing the account name and its password hash value together on a computer system is obviously far more secure than saving the account name with a plain text password, and this is the basis of user authentication checking for many operating systems and applications.

The problem with the MD5 function is that it has been shown to be "breakable" through several types of sophisticated attacks. But as these attacks are technically very complicated to perform, MD5 hashes are still widely used.

CASE IN POINT: Researchers devise undetectable phishing attack

Alas, the BozoCrack algorithm adds a whole new dimension of vulnerability to MD5, as Salonen commented: "BozoCrack is a depressingly effective MD5 password hash cracker with almost zero CPU/GPU load."

How does BozoCrack do its voodoo? The author explains: "Instead of rainbow tables, dictionaries, or brute force, BozoCrack simply finds the plaintext password. Specifically, it googles the MD5 hash and hopes the plaintext appears somewhere on the first page of results. / It works way better than it ever should."

Why did he create it? "To show just how bad an idea it is to use plain MD5 as a password hashing mechanism. Honestly, if the passwords can be cracked with this software, there are no excuses."

Thus, once again, does the power of Google make fools of us all.

Gibbs is secure in Ventura, Calif. Settle your hash at gearhead@gibbs.com.

Learn more about this topic

Security: Never mind the products, educate the users

Stronger IPsec VPN configurations needed

Researchers devise undetectable phishing attack

Insider Tip: 12 easy ways to tune your Wi-Fi network
Join the discussion
Be the first to comment on this article. Our Commenting Policies