SQL injection with raw MD5 hashes (Leet More CTF 2010 injection 300)

Team Kernel Sanders t-shirts

The University of Florida Student Infosec Team competed in the Leet More CTF 2010 yesterday. It was a 24-hour challenge-based event sort of like DEFCON quals. Ian and I made the team some ridiculous Team Kernel Sanders shirts at our hackerspace just before the competition started. The good colonel vs. Lenin: FIGHT!

Here’s a walkthrough/writeup of one of the challenges.

Injection 300: SQL injection with raw MD5 hashes

One challenge at yesterday’s CTF was a seemingly-impossible SQL injection worth 300 points. The point of the challenge was to submit a password to a PHP script that would be hashed with MD5 before being used in a query. At first glance, the challenge looked impossible. Here’s the code that was running on the game server:

The only injection point was the first mysql_query(). Without the complication of MD5, the vulnerable line of code would have looked like this:

$r = mysql_query("SELECT login FROM admins WHERE password = '" . $_GET['password'] . "'");

If the password foobar were submitted to the script, this SQL statement would be executed on the server:

SELECT login FROM admins WHERE password = 'foobar'

That would have been trivial to exploit. I could have submitted the password ' OR 1 = 1; -- instead:

SELECT login FROM admins WHERE password = '' OR 1 = 1; -- '

…which would have returned all the rows from the admins table and tricked the script into granting me access to the page.

However, this challenge was much more difficult than that. Since PHP’s md5() function was encrypting the password first, this was what was being sent to the server :

SELECT login FROM admins WHERE password = '[output of md5 function]'

So how could I possibly inject SQL when MD5 would destroy whatever I supplied?

1337 hax0rs

The trick: Raw MD5 hashes are dangerous in SQL

The trick in this challenge was that PHP’s md5() function can return its output in either hex or raw form. Here’s md5()’s method signature:

string md5( string $str [, bool $raw_output = false] )

If the second argument to MD5 is true, it will return ugly raw bits instead of a nice hex string. Raw MD5 hashes are dangerous in SQL statements because they can contain characters with special meaning to MySQL. The raw data could, for example, contain quotes (' or ") that would allow SQL injection.

I used this fact to create a raw MD5 hash that contained SQL injection code.

But it might take years to calculate

In order to spend the least possible time brute forcing MD5 hashes, I tried to think of the shortest possible SQL injection. I came up with one only 6 characters long:

'||1;#

I quickly wrote a C program to see how fast I could brute force MD5. My netbook could compute about 500,000 MD5 hashes per second using libssl’s MD5 functions. My quick (and possibly wrong) math told me every hash had a 1 in 28 trillion chance of containing my desired 6-character injection string.

So that would only take 2 years at 500,000 hashes per second.

Optimizing: Shortening the injection string

If I could shorten my injection string by even one character, I would reduce the number of hash calculations by a factor of 256. After thinking about the problem for a while and playing around a lot with MySQL, I was able to shorten my injection to only 5 characters:

'||'1

This would produce an SQL statement like this (assuming my injection happened to fall in about the middle of the MD5 hash and pretending xxxx is random data):

SELECT login FROM admins WHERE password = 'xxx'||'1xxxxxxxx'

|| is equivalent to OR, and a string starting with a 1 is cast as an integer when used as a boolean. Therefore, my injection would be equivalent to this:

SELECT login FROM admins WHERE password = 'xxx' OR 1

By Just removing a single character, that got me down to 2.3 days' worth of calculation. Still not fast enough, but getting closer.

Lopping off another character, and more improvements

Since any number from 1 to 9 would work in my injection, I could shorten my injection string to just '||' and then check to see if the injection string were followed by a digit from 1 to 9 (a very cheap check). This would simultaneously reduce my MD5 calculations by a factor of 256 and make it 9 times as likely that I’d find a usable injection string.

And since || is the same as OR, I could check for it too (2x speedup) and all its case variations (16x speedup). Running my program on a remote dual-core desktop instead of my netbook got me another 10x speedup.

The final hash

After computing only 19 million MD5 hashes, my program found an answer:

content: 129581926211651571912466741651878684928
count:   18933549
hex:     06da5430449f8f6f23dfc1276f722738
raw:     ?T0D??o#??'or'8.N=?

So I submitted the password 129581926211651571912466741651878684928 to the PHP script, and it worked! I was able to see this table:

admins-table

Last step

The last step of the challenge was to turn the MD5 hash into a password. I could have used a brute forcer like John, but instead I just searched Google. The password had been cracked by opencrack.hashkiller.com and was 13376843.

The code

Final scoreboard

hax hax hax

21 responses
Hey, a faster solution : http://blog.nibbles.fr/?p=2039
Nice work !
Brilliant! Now that is some leet cracking. I wonder how many other people even attempted it? Just goes to show that prepared statements are the only safe sql.....
Nice! The Nibbles injection is excellent! He found a way to shorten it to just 3 characters: '='
That, mister, is a ridiculously awesome shirt. Just thought you should know.
Thanks! Making shirts is fun. You guys should come out to hackerspace
soo-- OH WAIT. :(
Hi Guys,

that's a pretty neat solution to the problem. Unfortunately i cannot compare your solution to nibbles' because my online translator turns their french article into gibberish only. ;)

By the way, if you're searching for an MD5 cracker later i invite you to use the huge list of services over at my blog (http://www.stottmeister.com/blog/2009/04/14/how-to-crack-md5-passwords/). It's quite complete as far as i know. Feel free to come by!

Best'
Stotti

This is really a cool hacker experience!
Basically nibbles did the same as you, but searching for the string '=' in the hash. It produces a request like 'a'='b'='c' which evaluates to 1 since it's parsed as ('a'='b')='c' which is 0='c' in the general case, and if 'c' does not start with a digit, you have 0=0, bingo!
Well played, sir! Thankfully I've never seen anyone stupid enough to use a *raw* md5 hash (and I've seen A LOT of stupid PHP code), and this is impossible with a standard md5 call (with the 2nd parameter defaulting to false), though I'm sure the same potential vulnerability is there for any query that takes unencoded binary data. One question, why did you opt to correlate the password on hashkiller instead of using the generating the source string that was hashed once you found a suitable match?
Erhune: You have explained it perfectly.
Timothy: The scoring server was looking for the password corresponding to the hash stored in the admin user's password field, which served as proof that the account had been compromised.
ahhh. I see, I misunderstood. Thanks for the clarification.
I would like to emphasize Timothy's point: you almost -never- see the raw md5 flag in code, so this hack is moot outside of a decent problem-solving exercise.
Cool hack! Here's a THREE char string that should work if followed by a number 1 to 9: '+'
e.g. password = ''+'1'
Scratch that... needed brackets. Whoops
Great solution, thanks for sharing.
very nice
Well , Nice Work. What about Hex MD5 - this will not work , any other suggestions. How important it is to know the SALT.
Well , Nice Work. What about Hex MD5 - this will not work , any other suggestions. How important it is to know the SALT.
Okay, This was good. Finding a text string that encrypts into a sql injection query, you have a lot of time on your hands. But sounds fun :~