10 ms·

SQL injection with raw MD5 hashes

125 points by philfreo 16y ago

philfreo 16y ago
And it looks like an even faster solution, here, but in French. http://blog.nibbles.fr/2039 http://blog.nibbles.fr/2039
- gus_massa 16y ago
  Automatic Google Translation: http://translate.google.com/translate?js=n&prev=_t&hl=en&ie=UTF-8&layout=2&eotf=1&sl=fr&tl=en&u=http%3A%2F%2Fblog.nibbles.fr%2F2039&act=url http://translate.google.com/translate?js=n&prev=_t&h...
hackermom 16y ago
This is all quite clever, but any wary developer makes sure to use either properly sanitized inputs, or better still, prepared SQL statements (as f.e. available through PHP's PDO method), so this trickery, no matter how clever, is really not a big issue.
- tptacek 16y ago
  "Any wary developer" ranks up there with "a sufficiently clever compiler" among the True Scotsmen of our industry. I don't think you're right; empirically, unsafe SQL is a very big issue, and the places where a QA team is unlikely to stumble across injection vectors (ie, any vector where the string "O'Malley" doesn't pop up an error to paste into a ticket) are worse still, since teams don't find them.
  - frederique 16y ago
    i think you don't look outside your own "boxeola" too much. no all development is done by a) clueless team that passes the software on to b) quality assurance + bughunters. relying on or assuming that someone else will take care of eventual loose ends is a very bad and ignorant approach to creating software, and in my soon 15 years of experience as a european programmer this is thankfully no where near the majority of cases.
    - daeken 16y ago
      I think one key difference is in when the software was developed. If I had to guess, most software developed in the past 5 years (being conservative here) is most likely not vulnerable to SQL injection, simply because doing things the right way (that is, using parameterized queries and the like) is so easy these days. But if you look at software developed prior -- and software built at a lower level, e.g. directly hitting the PHP mysql API -- you've got a fair shot at stumbling upon SQL injection, I'd say. That means that most developers writing say, Django or Rails apps, are never going to have to think about SQL injection, and won't see how prevalent it is. In theory, SQL injection is a solved problem -- we've known how to avoid it for a long, long time -- but in practice, it's still out there in full force, largely due to legacy code.
      - tptacek 16y ago
        Parameterized queries are also simply not the panacea they're made out to be; there remain plenty of opportunities for injection even with a parameterized query. SQL injection via MD5 digests are indeed unlikely, but not because of query structure --- rather, because most developers don't know to take the binary result instead of the more convenient hex result. It just rubs me the wrong way when people claim "if you do things right, you'll never run into this problem anyways". Two possible interpretations: either "do things right" is too broad to mean anything (no-true-Scotsman-style) or "do things right" involves a piece of advice like "used parameterized queries" which doesn't actually work reliably in the real world. We have absolutely found SQL injection in Rails code before. I've also had engagements on very modern financial codebases where the developers were able to expound at length on how impossible it would be for them to have injection --- providing entirely sane design rules to back it up --- that ended up losing their entire app to pre-auth SQLI. There's always some tiny corner of the app --- a custom query builder, a hand-hacked pagination system, a sort column generator, a table selector parameter, that one stored procedure that does dynamic SQL and doesn't know what U+2032 is --- that manages to slip up.
        jtdowney 16y ago
        > Parameterized queries are also simply not the panacea they're made out to be; there remain plenty of opportunities for injection even with a parameterized query. Can you describe a case or point to example code using a parameterized query that is vulnerable to SQL injection? I've seen a stored procedure that built raw queries and pass them to sp_executesql (T-SQL) that provided a vector for SQL injection. However I am struggling to think of a case where a parameterized query could allow for SQL injection.
tptacek 16y ago
Summary: binary MD5 hashes are, in fact, binary, and any given MD5 hash has a 1/16 chance of containing a given SQL metacharacter. The CTF challenge here required the calculation of a hash containing a whole 4-character injection string; this is harder, but not Hard. You should know that the exact same problem applies (moreso, in fact) to encrypted strings. Developer laziness insulates most apps from raw MD5 digests (most devs use the hex digest function, which returns human readable [and safe] output). But the exact same "iterate 1 bit at a time until you hit a jackpot block" trick works with almost every application that uses AES. It's not just SQL, either; I've used it to get XSS out of corrupted AES decryptions as well. And, of course, the same trick works in the opposite direction. If you encrypt a string with a quoting domain (say, where the character ';' needs to be quoted '\;' to preserve an encoded tuple), attackers can pad inputs to get the quote and the metacharacter to span blocks, then use block corruption to kill the quote but not the metacharacter. Have I mentioned today how you shouldn't be building crypto code? DON'T DATE ROBOTS.
- DougBTX 16y ago
  The winner managed it with a 3-char injection: http://blog.nibbles.fr/2039 http://blog.nibbles.fr/2039
- daeken 16y ago
  > It's not just SQL, either; I've used it to get XSS out of corrupted AES decryptions as well. How would you go about such a thing? My initial thought is to simply permute over the controllable bytes and see what comes out, looking for specific characters that get you what you need, e.g. a quote to break out of an HTML attribute, but I think I might be missing an easier path.
  - tptacek 16y ago
    Nope, that's how you do it. In the case I'm thinking of, I only needed one character (but it needed to be the last byte).
- pontifier 16y ago
  I wish there was an easy answer to encryption and security, but it seems like an arms race a la "The Cassini Division". No matter how you build a system there are always more inputs to compromise... and the attackers never give up.
aonic 16y ago
In all my years of dealing with ugly and insecure PHP code, never have I seen anyone using raw md5's in PHP Sounds like a fabricated situation just for the game to me, versus something trying to resemble real life situations. Not saying its not possible, but the type of coders that would make a SQL injection oversight with something like that would also not care to provide a non-default raw_output value to the function for the heck of it
deleted 16y ago
[deleted]
bl4k 16y ago
I am more impressed by whoever came up with the challenge, although setting the second parameter of md5 to 'true' made it obvious what the solution to the puzzle was (nobody would ever have binary output on irl). The French team came up with the solution quicker as they worked out that any '=' would work - their keyspace search was thus an order of magnitude quicker: http://blog.nibbles.fr/2039 http://blog.nibbles.fr/2039
- sgronblo 16y ago
  I thought it required '='[^1-9] ? Because real 'password' = 'bogus crap' would turn into 0 which would then be compared to a string starting with something else than 1-9 which gets turned into a 0 as well.
photon_off 16y ago
This might be only tangentially related, and I'm sure nearly everyone on HN knows this, but salting MD5's is probably the easiest way to significantly increase their security. By changing md5($var) to md5($var . "foo") this type of attack could be prevented, assuming that the crackers don't have access to the source code [in this challenge, they did]. To get an idea of what can be exposed if you don't salt, and thus use predictable hashes, have a look here: http://www.google.com/#q=inurl:c4ca4238a0b923820dcc509a6f75849b http://www.google.com/#q=inurl:c4ca4238a0b923820dcc509a6f758... md5(1) = c4ca4238...
- prodigal_erik 16y ago
  There are theoretical attacks against simply adding secret bits to a single hash. You're probably better off with HMAC, which is essentially md5($key . md5($key . $message)) with a few padding details. http://en.wikipedia.org/wiki/HMAC http://en.wikipedia.org/wiki/HMAC
- timtadh 16y ago
  +1 to prodigal_erik Also concatenating "foo" to the end of /every/ password is not salting your hash. You need to have a suitably random string for it be considered salt. Also you want to have a different random string for every password in your database. [+1 to tptacek for constantly saying don't write crypto code :-p]
  - photon_off 16y ago
    I should have noted that "foo" wasn't meant to be taken literally; clearly it should be something that wouldn't show up in a dictionary. Even so, the point was that any salt is substantially better than none, and is easy to implement.
- JoachimSchipper 16y ago
  "Salting" is not the solution to every problem. More to the point, if you put binary data in an SQL query things are going to break, even if you use tricks like this to make it a bit less predictable. (Really, the probability of random binary data containing a ' character is pretty high...)
sh1mmer 16y ago
PHP contains filters for a reason. They are there to protect you. While this was a clever challenge, in general you should sanitize all of your input using filters.
- getsat 16y ago
  In general, you should not use PHP, but, If you must, you should be using a framework that handles this kind of stuff for you. Input sanitisation has been solved thousands of times by people smarter than you. Do not reinvent the wheel (poorly).
- pornel 16y ago
  Filtering of input is not appropriate way of ensuring that SQL queries are safe, e.g. you'd be telling people named "O'Hara" that they're not SQL-compatible or you'll fall into magic_quotes trap. You should escape output. In this case there isn't anything wrong with the input, and you can't say that any byte of MD5 is wrong or dangerous. It's just data that is used improperly. Binary data in SQL queries is especially tricky, because strings may be expected to be in specific character encoding (e.g. UTF-8), so you either need to use prepared statements and pass argument explicitly as binary, or use string-safe escaping (e.g. hex).
- konad 16y ago
  magic_quotes is turned off by default for a reason too.
konad 16y ago
I know there was already a shorter solution but instead of '||'[1-9] one could have searched for '!=' or '<>' thus opening up the search space

125 points by philfreo 16y ago

philfreo 16y ago

And it looks like an even faster solution, here, but in French. http://blog.nibbles.fr/2039 http://blog.nibbles.fr/2039

gus_massa 16y ago
Automatic Google Translation: http://translate.google.com/translate?js=n&prev=_t&hl=en&ie=UTF-8&layout=2&eotf=1&sl=fr&tl=en&u=http%3A%2F%2Fblog.nibbles.fr%2F2039&act=url http://translate.google.com/translate?js=n&prev=_t&h...

hackermom 16y ago

This is all quite clever, but any wary developer makes sure to use either properly sanitized inputs, or better still, prepared SQL statements (as f.e. available through PHP's PDO method), so this trickery, no matter how clever, is really not a big issue.

tptacek 16y ago
"Any wary developer" ranks up there with "a sufficiently clever compiler" among the True Scotsmen of our industry. I don't think you're right; empirically, unsafe SQL is a very big issue, and the places where a QA team is unlikely to stumble across injection vectors (ie, any vector where the string "O'Malley" doesn't pop up an error to paste into a ticket) are worse still, since teams don't find them.
- frederique 16y ago
  i think you don't look outside your own "boxeola" too much. no all development is done by a) clueless team that passes the software on to b) quality assurance + bughunters. relying on or assuming that someone else will take care of eventual loose ends is a very bad and ignorant approach to creating software, and in my soon 15 years of experience as a european programmer this is thankfully no where near the majority of cases.
  - daeken 16y ago
    I think one key difference is in when the software was developed. If I had to guess, most software developed in the past 5 years (being conservative here) is most likely not vulnerable to SQL injection, simply because doing things the right way (that is, using parameterized queries and the like) is so easy these days. But if you look at software developed prior -- and software built at a lower level, e.g. directly hitting the PHP mysql API -- you've got a fair shot at stumbling upon SQL injection, I'd say. That means that most developers writing say, Django or Rails apps, are never going to have to think about SQL injection, and won't see how prevalent it is. In theory, SQL injection is a solved problem -- we've known how to avoid it for a long, long time -- but in practice, it's still out there in full force, largely due to legacy code.
    - tptacek 16y ago
      Parameterized queries are also simply not the panacea they're made out to be; there remain plenty of opportunities for injection even with a parameterized query. SQL injection via MD5 digests are indeed unlikely, but not because of query structure --- rather, because most developers don't know to take the binary result instead of the more convenient hex result. It just rubs me the wrong way when people claim "if you do things right, you'll never run into this problem anyways". Two possible interpretations: either "do things right" is too broad to mean anything (no-true-Scotsman-style) or "do things right" involves a piece of advice like "used parameterized queries" which doesn't actually work reliably in the real world. We have absolutely found SQL injection in Rails code before. I've also had engagements on very modern financial codebases where the developers were able to expound at length on how impossible it would be for them to have injection --- providing entirely sane design rules to back it up --- that ended up losing their entire app to pre-auth SQLI. There's always some tiny corner of the app --- a custom query builder, a hand-hacked pagination system, a sort column generator, a table selector parameter, that one stored procedure that does dynamic SQL and doesn't know what U+2032 is --- that manages to slip up.
      - jtdowney 16y ago
        > Parameterized queries are also simply not the panacea they're made out to be; there remain plenty of opportunities for injection even with a parameterized query. Can you describe a case or point to example code using a parameterized query that is vulnerable to SQL injection? I've seen a stored procedure that built raw queries and pass them to sp_executesql (T-SQL) that provided a vector for SQL injection. However I am struggling to think of a case where a parameterized query could allow for SQL injection.

tptacek 16y ago

Summary: binary MD5 hashes are, in fact, binary, and any given MD5 hash has a 1/16 chance of containing a given SQL metacharacter. The CTF challenge here required the calculation of a hash containing a whole 4-character injection string; this is harder, but not Hard. You should know that the exact same problem applies (moreso, in fact) to encrypted strings. Developer laziness insulates most apps from raw MD5 digests (most devs use the hex digest function, which returns human readable [and safe] output). But the exact same "iterate 1 bit at a time until you hit a jackpot block" trick works with almost every application that uses AES. It's not just SQL, either; I've used it to get XSS out of corrupted AES decryptions as well. And, of course, the same trick works in the opposite direction. If you encrypt a string with a quoting domain (say, where the character ';' needs to be quoted '\;' to preserve an encoded tuple), attackers can pad inputs to get the quote and the metacharacter to span blocks, then use block corruption to kill the quote but not the metacharacter. Have I mentioned today how you shouldn't be building crypto code? DON'T DATE ROBOTS.

DougBTX 16y ago
The winner managed it with a 3-char injection: http://blog.nibbles.fr/2039 http://blog.nibbles.fr/2039
daeken 16y ago
> It's not just SQL, either; I've used it to get XSS out of corrupted AES decryptions as well. How would you go about such a thing? My initial thought is to simply permute over the controllable bytes and see what comes out, looking for specific characters that get you what you need, e.g. a quote to break out of an HTML attribute, but I think I might be missing an easier path.
- tptacek 16y ago
  Nope, that's how you do it. In the case I'm thinking of, I only needed one character (but it needed to be the last byte).
pontifier 16y ago
I wish there was an easy answer to encryption and security, but it seems like an arms race a la "The Cassini Division". No matter how you build a system there are always more inputs to compromise... and the attackers never give up.

aonic 16y ago

In all my years of dealing with ugly and insecure PHP code, never have I seen anyone using raw md5's in PHP Sounds like a fabricated situation just for the game to me, versus something trying to resemble real life situations. Not saying its not possible, but the type of coders that would make a SQL injection oversight with something like that would also not care to provide a non-default raw_output value to the function for the heck of it

deleted 16y ago

[deleted]

bl4k 16y ago

I am more impressed by whoever came up with the challenge, although setting the second parameter of md5 to 'true' made it obvious what the solution to the puzzle was (nobody would ever have binary output on irl). The French team came up with the solution quicker as they worked out that any '=' would work - their keyspace search was thus an order of magnitude quicker: http://blog.nibbles.fr/2039 http://blog.nibbles.fr/2039

sgronblo 16y ago
I thought it required '='[^1-9] ? Because real 'password' = 'bogus crap' would turn into 0 which would then be compared to a string starting with something else than 1-9 which gets turned into a 0 as well.

photon_off 16y ago

This might be only tangentially related, and I'm sure nearly everyone on HN knows this, but salting MD5's is probably the easiest way to significantly increase their security. By changing md5($var) to md5($var . "foo") this type of attack could be prevented, assuming that the crackers don't have access to the source code [in this challenge, they did]. To get an idea of what can be exposed if you don't salt, and thus use predictable hashes, have a look here: http://www.google.com/#q=inurl:c4ca4238a0b923820dcc509a6f75849b http://www.google.com/#q=inurl:c4ca4238a0b923820dcc509a6f758... md5(1) = c4ca4238...

prodigal_erik 16y ago
There are theoretical attacks against simply adding secret bits to a single hash. You're probably better off with HMAC, which is essentially md5($key . md5($key . $message)) with a few padding details. http://en.wikipedia.org/wiki/HMAC http://en.wikipedia.org/wiki/HMAC
timtadh 16y ago
+1 to prodigal_erik Also concatenating "foo" to the end of /every/ password is not salting your hash. You need to have a suitably random string for it be considered salt. Also you want to have a different random string for every password in your database. [+1 to tptacek for constantly saying don't write crypto code :-p]
- photon_off 16y ago
  I should have noted that "foo" wasn't meant to be taken literally; clearly it should be something that wouldn't show up in a dictionary. Even so, the point was that any salt is substantially better than none, and is easy to implement.
JoachimSchipper 16y ago
"Salting" is not the solution to every problem. More to the point, if you put binary data in an SQL query things are going to break, even if you use tricks like this to make it a bit less predictable. (Really, the probability of random binary data containing a ' character is pretty high...)

sh1mmer 16y ago

PHP contains filters for a reason. They are there to protect you. While this was a clever challenge, in general you should sanitize all of your input using filters.

getsat 16y ago
In general, you should not use PHP, but, If you must, you should be using a framework that handles this kind of stuff for you. Input sanitisation has been solved thousands of times by people smarter than you. Do not reinvent the wheel (poorly).
pornel 16y ago
Filtering of input is not appropriate way of ensuring that SQL queries are safe, e.g. you'd be telling people named "O'Hara" that they're not SQL-compatible or you'll fall into magic_quotes trap. You should escape output. In this case there isn't anything wrong with the input, and you can't say that any byte of MD5 is wrong or dangerous. It's just data that is used improperly. Binary data in SQL queries is especially tricky, because strings may be expected to be in specific character encoding (e.g. UTF-8), so you either need to use prepared statements and pass argument explicitly as binary, or use string-safe escaping (e.g. hex).
konad 16y ago
magic_quotes is turned off by default for a reason too.

konad 16y ago

I know there was already a shorter solution but instead of '||'[1-9] one could have searched for '!=' or '<>' thus opening up the search space