Why does crypt/blowfish generate the same hash with two different salts?

by

After some experimentation, I have come to the conclusion that this is due to the way the salt is treated. The salt is not considered to be literal text, but rather to be a base64 encoded string, such that 22 bytes of salt data would actually represent a 16 byte string (floor(22 * 24 / 32) == 16) of salt. The “Gotcha!” with this implementation, though, is that, like Unix crypt, it uses a “non-standard” base64 alphabet. To be exact, it uses this alphabet:

./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789$

The 65th character, ‘$‘, is the padding character.

Now, the crypt() function appears to be capable of taking a salt of any length less than or equal to its maximum, and silently handling any inconsistencies in the base64 by discarding any data that doesn’t make up another full byte. The crypt function will fail completely if you pass it characters in the salt that are not part of its base64 alphabet, which just confirms this theory of its operation.

Take an imaginary salt ‘1234‘. This is perfectly base64 consistent in that it represents 24 bits of data, so 3 bytes, and does not carry any data that needs to be discarded. This is a salt whose Len Mod 4 is zero. Append any character to that salt, and it becomes a 5 character salt, and Len Mod 4 is now 1. However, this additional character represents only six bits of data, and therefore cannot be transformed into another full byte, so it is discarded.

Thus, for any two salts A and B, where 

   Len A Mod 4 == 0 
&& Len B Mod 4 == 1  // these two lines mean the same thing
&& Len B = Len A + 1 // but are semantically important separately
&& A == substr B, 0, Len A

The actual salt used by crypt() to calculate the hash will, in fact, be identical. As proof, I’m including some example PHP code that can be used to show this. The salt constantly rotates in a seminon-random way (based on a randomish segment of the whirlpool hash of the current time to the microsecond), and the data to be hashed (herein called $seed) is simply the current Unix-Epoch time.

$salt = substr(hash('whirlpool',microtime()),rand(0,105),22);
$seed = time();
for ($i = 0, $j = strlen($salt); $i <= $j; ++$i) {
    printf('%02d = %s%s%c',
        $i,
        crypt($seed,'$2a$07$' . substr($salt, 0, $i)),
        $i%4 == 0 || $i % 4 == 1 ? ' <-' : '',
        0x0A
    );
}

And this produces output similar to the following

00 = $2a$07$$$$$$$$$$$$$$$$$$$$$$.rBxL4x0LvuUp8rhGfnEKSOevBKB5V2. <-
01 = $2a$07$e$$$$$$$$$$$$$$$$$$$$.rBxL4x0LvuUp8rhGfnEKSOevBKB5V2. <-
02 = $2a$07$e8$$$$$$$$$$$$$$$$$$$.WEimjvvOvQ.lGh/V6HFkts7Rq5rpXZG
03 = $2a$07$e89$$$$$$$$$$$$$$$$$$.Ww5p352lsfQCWarRIWWGGbKa074K4/.
04 = $2a$07$e895$$$$$$$$$$$$$$$$$.ZGSPawtL.pOeNI74nhhnHowYrJBrLuW <-
05 = $2a$07$e8955$$$$$$$$$$$$$$$$.ZGSPawtL.pOeNI74nhhnHowYrJBrLuW <-
06 = $2a$07$e8955b$$$$$$$$$$$$$$$.2UumGVfyc4SgAZBs5P6IKlUYma7sxqa
07 = $2a$07$e8955be$$$$$$$$$$$$$$.gb6deOAckxHP/WIZOGPZ6/P3oUSQkPm
08 = $2a$07$e8955be6$$$$$$$$$$$$$.5gox0YOqQMfF6FBU9weAz5RmcIKZoki <-
09 = $2a$07$e8955be61$$$$$$$$$$$$.5gox0YOqQMfF6FBU9weAz5RmcIKZoki <-
10 = $2a$07$e8955be616$$$$$$$$$$$.hWHhdkS9Z3m7/PMKn1Ko7Qf2S7H4ttK
11 = $2a$07$e8955be6162$$$$$$$$$$.meHPOa25CYG2G8JrbC8dPQuWf9yw0Iy
12 = $2a$07$e8955be61624$$$$$$$$$.vcp/UGtAwLJWvtKTndM7w1/30NuYdYa <-
13 = $2a$07$e8955be616246$$$$$$$$.vcp/UGtAwLJWvtKTndM7w1/30NuYdYa <-
14 = $2a$07$e8955be6162468$$$$$$$.OTzcPMwrtXxx6YHKtaX0mypWvqJK5Ye
15 = $2a$07$e8955be6162468d$$$$$$.pDcOFp68WnHqU8tZJxuf2V0nqUqwc0W
16 = $2a$07$e8955be6162468de$$$$$.YDv5tkOeXkOECJmjl1R8zXVRMlU0rJi <-
17 = $2a$07$e8955be6162468deb$$$$.YDv5tkOeXkOECJmjl1R8zXVRMlU0rJi <-
18 = $2a$07$e8955be6162468deb0$$$.aNZIHogUlCn8H7W3naR50pzEsQgnakq
19 = $2a$07$e8955be6162468deb0d$$.ytfAwRL.czZr/K3hGPmbgJlheoZUyL2
20 = $2a$07$e8955be6162468deb0da$.0xhS8VgxJOn4skeI02VNI6jI6324EPe <-
21 = $2a$07$e8955be6162468deb0da3.0xhS8VgxJOn4skeI02VNI6jI6324EPe <-
22 = $2a$07$e8955be6162468deb0da3ucYVpET7X/5YddEeJxVqqUIxs3COrdym

The conclusion? Twofold. First, it’s working as intended, and second, know your own salt or don’t roll your own salt.

More Related Contents:

  1. Why hash_equals and password_verify are not working properly?
  2. Divide md5 function with colon (:) [closed]
  3. Secure hash and salt for PHP passwords
  4. Cleansing User Passwords
  5. How to use PHP’s password_hash to hash and verify passwords
  6. How can I store my users’ passwords safely?
  7. php mysqli_connect: authentication method unknown to the client [caching_sha2_password]
  8. Why is the hash part of the URL not available on the server side?
  9. Using PHP 5.5’s password_hash and password_verify function
  10. Secure random number generation in PHP
  11. How to retract a salted password from the Database and auth user?
  12. What type of hash does WordPress use?
  13. encrypt and decrypt md5
  14. PHP short hash like URL-shortening websites
  15. How to create a laravel hashed password
  16. bcrypt and randomly generated salts
  17. Hiding true database object ID in url’s
  18. password_hash returns different value every time
  19. What are fragment URLs and why to use them?
  20. Fastest hash for non-cryptographic uses?
  21. PHP & Hash / Fragment Portion of URL
  22. php: number only hash?
  23. Improve password hashing with a random salt
  24. What is SALT and how do i use it?
  25. PHP error: “Cannot pass parameter 2 by reference”
  26. How can I emulate a get request exactly like a web browser?
  27. Show image using file_get_contents
  28. get UTC time in PHP
  29. Truncate float numbers with PHP
  30. How to route .html and .js files as PHP on Nginx FastCGI server?

Leave a Comment