Magic hashes – PHP hash "collisions"

Register with password 1 and then sign in with password 2. If you're in then the storage uses specified algorithm to hash the password and PHP uses == to compare them (for MD5, SHA-1, and plaintext).

MD5, SHA-1, SHA-224, SHA-256 and others

For MD5, SHA-1 and SHA-2 family, it uses the long-known trick (it actually is a documented feature, see PHP type comparison tables & Floating point numbers) that for PHP '0e1' == '00e2' == '0', it just uses it for practical purposes. Any password matches any other password from the list. This is a different trick than integral strings overflowing into floating point numbers, just spot the difference between these two lines.

These are all the algorithms with magic hashes:

• CRC32
• CRC32b
• FNV-1a/32
• FNV-1a/64
• FNV-1/32
• FNV-1/64
• HAVAL-128,3
• HAVAL-128,4
• HAVAL-128,5
• HAVAL-160,3
• HAVAL-160,4
• HAVAL-160,5
• JOAAT
• MD2
• MD4
• MD5
• MurmurHash3_x86_32/Murmur3a
• MurmurHash3_x86_128/Murmur3c
• MurmurHash3_x64_128/Murmur3f
• PHOTON-80/20/16
• PHOTON-128/16/16
• PHOTON-160/36/36
• Quark u-Quark-136
• RIPEMD-128
• RIPEMD-160
• SHA-1
• SHA-224
• SHA-256
• SPONGENT-88/80/8
• SPONGENT-88/176/88
• SPONGENT-128/128/8
• SPONGENT-128/256/128
• Tiger/128,3
• Tiger/128,4
• Tiger/160,3
• Tiger/160,4
• Tiger/192,3
• xxHash-XXH32
• xxHash-XXH64
• xxHash-XXH3_64bits
• xxHash-XXH3_128bits

To quote @0xb0bb, "there are other applications for magic hashes other than password comparisons (such as caching layers or data derived from the output of a hash function) where these known insecure, lesser known and pseudo-hash algorithms can be found more readily."

Plaintext

For plaintext, it uses various conversion tricks. First password will match just the second one. Tricks are grouped by PHP versions allowing them.

bcrypt

bcrypt truncates passwords to a maximum length of 72 characters. The passwords match if the first 72 characters of both passwords match.

descrypt

descrypt (traditional UNIX DES crypt) truncates passwords to a maximum length of 8 characters. The passwords also match if the first 8 characters of both passwords match, see the "General cross-check" section.

PBKDF2-HMAC-SHA1, PBKDF2-HMAC-SHA224, PBKDF2-HMAC-SHA256

If you use a password longer than 64 bytes and hash it with PBKDF2-HMAC-SHA1, it is first pre-hashed with SHA1, so PBKDF2-HMAC-SHA1(password1) === PBKDF2-HMAC-SHA1(password2) because sha1(password1) === bin2hex(password2). The similar pre-hashing is applied in case of PBKDF2-HMAC-SHA224 and PBKDF2-HMAC-SHA256.

Tiger/192,3

Right now there's just one magic hash in each thanks to Norbert Tihanyi, more will be hopefully added in the future.

Conclusion

Use === when comparing anything* in PHP, not ==. And use password_hash() and password_verify() for password hashing in PHP, don't use MD5 or SHA-1. *Use hash_equals() when comparing hashes.

History

It all started with this tweet, I've generated QNKCDZO and 240610708 in February 2014 and it has since spread all over the intertubes. Just google it.

• MD5: Tweet, code, contributions by roycewilliams, Norbert Tihanyi, ethernetlord, 0xb0bb, myst404
• SHA-1: Tweet, code, contributions by roycewilliams, 0xb0bb, matlink, myst404, Maxim Masiutin
• Plaintext: Tweet, code
• bcrypt: code
• PBKDF2-HMAC-SHA1 by Christian "CodesInChaos" Winnerlein, as explained by Mathias Bynens, code
• PBKDF2-HMAC-SHA224 by Norbert Tihanyi, code
• PBKDF2-HMAC-SHA256 by Jens 'atom' Steube, code
• Tiger/192,3 by Norbert Tihanyi
• SHA-224 by Norbert Tihanyi, hops, 0xb0bb, myst404, Maxim Masiutin
• SHA-256 by Norbert Tihanyi, Chick3nman, roycewilliams, matlink
• CRC32, CRC32b, FNV-1a/32, FNV-1a/64, FNV-1/32, FNV-1/64, HAVAL-128,3, HAVAL-128,4, HAVAL-128,5, HAVAL-160,3, HAVAL-160,4, HAVAL-160,5, JOAAT, MD2, MD4, RIPEMD-128, RIPEMD-160, Tiger/128,3, Tiger/128,4, Tiger/160,3, Tiger/160,4 by 0xb0bb
• descrypt by James M. Hall, hops
• PHOTON-80/20/16, PHOTON-128/16/16, PHOTON-160/36/36 by Norbert Tihanyi & Bertalan Borsos
• u-Quark-136 by Norbert Tihanyi & Bertalan Borsos
• SPONGENT-88/80/8, SPONGENT-88/176/88, SPONGENT-128/128/8, SPONGENT-128/256/128 by Norbert Tihanyi & Bertalan Borsos
• xxHash by me (#27)
• MurmurHash3 by me (#28)

How to calculate your own

I've used my laptop, few for (or foreach?) loops, many CPU cycles and an external fan back in 2014 but today you can/should use a GPU and a modified hashcat for that. See this write-up by Carl Löndahl and 0xb0bb.

Chick3nman & co. is also working on their version of hashcat, stay tuned.

Real collisions

If you need a real alphanumerical collision, here's a 72-byte alphanum MD5 collision with 1-byte difference, 1-bit even, by Marc Stevens:

md5("TEXTCOLLBYfGiJUETHQ4hAcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak")
=
md5("TEXTCOLLBYfGiJUETHQ4hEcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak")

Note that if you register with the first password, and log in with the second, it may still mean that the site uses bcrypt(md5($password)), not just md5($password). Such hash wrapping is sometimes used when upgrading password hashing but it should be used only temporarily.

See Marc's Project HashClash if you're interested in these real collisions or if you'd like to create your own.