Magic Hashes

Magic Hashes

Robert Hansen | May 11, 2015

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 Spacekand 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 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 numbers when hashed 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 hash 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 Hash	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 toJeremi 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.

숫자 : 240610708 - > 0e462097431906509019562988736854

문자열 : QNKCDZO -> 0e830400451993494058024219903391 

출처 : https://www.whitehatsec.com/blog/magic-hashes/