Christian von Kleist

I met Steve Wozniak at a talk he gave. I asked him what he thought about the Singularity (which is when the machines take over the world, very roughly speaking), and he talked with me about it for a minute. He was really cool! He even gave me his business card, which is made of titanium and can cut steak (seriously!).

I asked him to sign my copy of his book iWoz, and he inscribed it for me:

Christian, When the computers take off over, you will be missed.
-- Woz

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?

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:

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

Recently H.D. Moore discovered a serious vulnerability in the widespread VxWorks 5.x operating system (or at least rediscovered it, expanded upon it, and publicized it). I was lucky enough to be one of the sixty people who saw his DEFCON 18 skytalk on the subject. He released information about the vulnerability to the public on August 2nd, 2010.

In addition to the main vulnerability (the fact that many vendor implementations of VxWorks 5.x had a publicly-accessible debug service running on port 17185), H.D. Moore discovered that the default VxWorks password hashing algorithm was insecure. He said he would release much more information about it one month from the initial release, which would mean September 2nd, 2010.

That was too long a wait for me, so I started working on the problem soon after I got home from DEFCON, and I was successful in finding the weakness H.D. talked about. I’ve also written a tool which can turn any password hash into a workalike password (i.e., a password different from the original password that produces the same hash), and another tool which scans VxWorks memory dumps for password hashes and reveals the workalike password for each one.

Although I’ve completed this work in early August, I have decided to follow the same release schedule that H.D. Moore has committed to, so this post is set to publish at midnight on September 2nd. I’m sure that I’ve only discovered part of what he will reveal on that day.

Background on VxWorks' weak password hash

By default, passwords in VxWorks 5.x are hashed using a really stupid one-way hashing mechanism. I don’t understand why the VxWorks developers didn’t use a stronger hash. MD5 was popular as a one-way hash when VxWorks 5.x was being written, but they didn’t use it. Instead, they created their own hash, what H.D. Moore called a “Bob the Wizard” hash at the skytalk.

The meat of VxWorks password hashing algorithm is a checksumming step where each byte of the plaintext (the password to be hashed) is multiplied by and then XOR’d with its position in the string, and added to an accumulator. It looks like this in C (modified slightly from the original source for clarity):

checksum = 0;
for (ix = 0; ix < strlen(plaintext); ix++)    /* sum the string */
  checksum += (plaintext[ix]) * (ix+1) ^ (ix+1);

Next, this checksum (an integer) is multiplied by a magic number and turned into a string in decimal:

sprintf (hash, "%u", (long) (checksum * 31695317)); /* convert interger
                                                    to string */

(The lulzy typo in interger is original.)

The final step of computing a hash is doing a character substitution for each byte in the string:

for (ix = 0; ix < strlen (hash); ix++)
{
  if (hash[ix] < '3')
    hash[ix] = hash[ix] + '!';    /* arbitrary */

  if (hash[ix] < '7')
    hash[ix] = hash[ix] + '/';    /* arbitrary */

  if (hash[ix] < '9')
    hash[ix] = hash[ix] + 'B';    /* arbitrary */
}

This character-substitution step really has no point other than making the hash look “hashlike.” It simply converts decimal digits to letters (except 9, which isn’t changed). For example, it always converts 0 to Q, 1 to R, 2 to S, 3 to b, etc. The input string 0123456789 would come out as QRSbcdeyz9 every time. It might look more like a bonafide hash of some sort, but it’s not.

In the end, every VxWorks 5.x password hash is composed of the alphabet QRSbcdeyz9 and is up to 10 characters long.

Reversing the VxWorks password hash

For any password hashing algorithm, if you can generate a list of all possible outputs, and you know the inputs that generated those outputs, then you can turn any given password hash into a workalike password. (This is also called “reversing” the hash.) For a hashing algorithm like MD5 or SHA1, doing this is infeasible; however, the VxWorks checksum space is so small that it’s possible to generate such a list pretty easily.

The weakness in the VxWorks hashing algorithm is the summing step (the first step). For any output value of the summing step (checksum), it’s easy to modify the input (plaintext) to produce an output incremented by one (checksum + 1). This means you can start with an input that generates the lowest possible checksum and then, by continuously generating subsequent checksums, you can create a table of all possible output values and all the input values needed to create them.

I started working on this approach, but very quickly realized that there is a simpler way to generate such a table that requires very little thinking!

The VxWorks hashing algorithm just happens to be so bad (because it crunches so large an input space into so small an output space), that randomly generating a few million input values generates nearly every possible output value. In my tests, this approach found a workalike password for 100% of dictionary words and more than 99.99% of random input strings composed of all legal input characters.

Download my code

I’m releasing some Ruby scripts and a C program here:

vxworks_hash on GitHub

This is what’s included:

1. vxworks_collide.rb: VxWorks password hash reverser library (plus vxworks_find_collision.rb, a handy command-line tool for using the library)
2. vxworks_mem_search.rb: Scanner that finds and reverses hashes in VxWorks memory dumps
3. vxworks_make_hash_table.rb and vxworks_collide.c: C program for generating VxWorks password checksum tables and a Ruby script to turn checksum tables into hash tables (for use with #1 and #2)

I’m also releasing a precomputed hash table (lookup.txt) for use with #1 and #2.