Crypt for password hashing. Blowfish produces weird output

Question

I am having a bit little bit of trouble understanding php's crypt function. My PHP version is 5.4.7.

I want to use crypt to store salted passwords in the database, because as far as I am told, developers who use md5 to hash passwords are to be staked and burned on the spot.

I wanted to use the blowfish alg to generate the hash. Now, according to the php documentation, crypt uses blowfish if you call it with "$2y$" + cost (for instance: "08") + "$" + 22 characters salt ( ./0-9A-Za-z ). However, the output of this little bit of test code is confusing me:

echo "<pre>";
if (CRYPT_BLOWFISH == 1) {
    echo 'Blowfish SaltLen = 18:     ' . crypt('string that should be hashed', '$2y$08$123456789012345678') . "\n";
    echo 'Blowfish SaltLen = 19:     ' . crypt('string that should be hashed', '$2y$08$1234567890123456789') . "\n";
    echo 'Blowfish SaltLen = 20:     ' . crypt('string that should be hashed', '$2y$08$12345678901234567890') . "\n";
    echo 'Blowfish SaltLen = 21:     ' . crypt('string that should be hashed', '$2y$08$123456789012345678901') . "\n";
    echo 'Blowfish SaltLen = 22:     ' . crypt('string that should be hashed', '$2y$08$1234567890123456789012') . "\n";
}
echo "</pre>";

Output:

Blowfish SaltLen = 18:     $2y$08$123456789012345678$$$.Gq4WBozZb6XYmOJ88OC8gThSTUx8pRO
Blowfish SaltLen = 19:     $2y$08$1234567890123456789$$.u8Qm7Q9KVtvo2zwpKkN5ntAxu71k2pO
Blowfish SaltLen = 20:     $2y$08$12345678901234567890$.iIlIFEGaqDj6XbnKkK1F14HmMGLV.mu
Blowfish SaltLen = 21:     $2y$08$123456789012345678901.iIlIFEGaqDj6XbnKkK1F14HmMGLV.mu
Blowfish SaltLen = 22:     $2y$08$123456789012345678901uSFz9yPi/jA6e9aMcUkm7y.TJYhcCoSu

The apparently crypt fills the salt with $ if it is not long enough. The salt changes and so does the hash. So the output in line 1 and 2 are as expected.

What is puzzling me, however, are the last three hashes: Apparently the dot separates the hash from the salt (?) but if you actually give crypt the 22 characters it demands as salt, the dot vanishes. Also, the last character from the salt does not appear in the output, but changes the hash compared to the 21 character salt.

What is especially confusing is line 3 and 4 in the output! The salt is obviously different, but the hashes are exactly the same. I just cannot see any consistency in this and would greatly appreciate help.

Tommy

what is your php ver? – Crossbreed

As I have stated in my initial post in the first line: 5.4.7 – Tommy

err...sorry I missed that! facepalm – Crossbreed

Also see Openwall's PHP password hashing framework (PHPass). Its portable and hardened against a number of common attacks on user passwords. The guy who wrote the framework (SolarDesigner) is the same guy who wrote John The Ripper and sits as a judge in the Password Hashing Competition. So he knows a thing or two about attacks on passwords. – Gerrard

Answer 1

The reason that you're seeing problems is that it doesn't actually use 22 characters of salt. It only uses 21.25 characters. So a few bits of the 22nd character are used for salt, and the remaining are used for hash (the result).

The reason is that the salt isn't a string. It's a 128 bit number. The number is serialized into base64. To review how base 64 works, every 3 byte block is "translated" into a 4 byte block.

[byte1][byte2][byte3]
[new1][new2][new3][new4]

Now, remember that each original byte has 8 bits. Therefore, each "new byte" will only have 6 bits (because we aren't adding information, we're just representing it differently).

So what's happening is that you're only providing 21 characters of data. Which translates to 15.75 bytes when decoded. But you can't have a partial byte. So the last decoded block is thrown away (due to having insufficient info). And those 6 bits that we threw away map completely to the 21st character.

Therefore, without the 2 bits that are used from the 22nd character, the 21st must be thrown away (because partial bytes don't make sense).

We can test this out:

$chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ./";
for ($i = 0; $i < strlen($chars); $i++) {
    echo crypt('string that should be hashed', '$2y$08$12345678901234567890' . $chars[$i]) . "\n";
}

Produces:

$2y$08$123456789012345678900.iIlIFEGaqDj6XbnKkK1F14HmMGLV.mu
$2y$08$123456789012345678901.iIlIFEGaqDj6XbnKkK1F14HmMGLV.mu
$2y$08$123456789012345678902.iIlIFEGaqDj6XbnKkK1F14HmMGLV.mu
.
.
.
$2y$08$12345678901234567890/.iIlIFEGaqDj6XbnKkK1F14HmMGLV.mu

But if we add a 22nd byte (irrespective of what it is):

$chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ./";
for ($i = 0; $i < strlen($chars); $i++) {
    echo crypt('string that should be hashed', '$2y$08$12345678901234567890' . $chars[$i] . 'a') . "\n";
}

Then we get the effect of the random distribution:

$2y$08$123456789012345678900OtUUu.EAOjrOztGKf2m.TZIe7HGzFgF.
$2y$08$123456789012345678901Ou28wcnld1gB2vjW9obdQdz6kLMasqKC
$2y$08$123456789012345678902Oum7Yp/p4TEeEC5JxsmnQsACNnnK0cv2
$2y$08$123456789012345678903OxMer1AD.P.UpAMlykl5SokMmDM1BU0W
$2y$08$123456789012345678904OpoNDsh7DaAoSjiZFJKO7iMy53BqwsjO
$2y$08$123456789012345678905OQRUqlnlEpBzccxrCgyZVtl6a.tQxNz6
$2y$08$123456789012345678906O6QMFdYZ.tvQpSdYaxlFl1Rlsk05/Aym
$2y$08$123456789012345678907OwF1TKI.OYT3xtBxg8tqex4L8mZttUCm
$2y$08$123456789012345678908OtzJXaS8/x0KYQ2epPRgVSjWSy/yAwMK
$2y$08$123456789012345678909O17D/xQeJGLIzpwBZuN2kxdpxi6p3aDq
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890bOD9Z5cUlQgJtvhqSOIK/3BV/1QIEmHby
$2y$08$12345678901234567890cOG5DxIU4B/ftl01V/MhViyi8YymLKEdC
$2y$08$12345678901234567890dOcd0.C8PVpjqW7oGI9AZuTVjNwxZDDpa
$2y$08$12345678901234567890eOLQSg5zmHm2nOCmRMdNeY8LxW1xMKnwm
$2y$08$12345678901234567890fOI.DZa4KuxngvaBT8JFtRWY8oRs9A266
$2y$08$12345678901234567890gOTA9XsdwxujLBdLaypPHehWjj1GyjDRC
$2y$08$12345678901234567890hOkS/cZmSqtdHSWz3zPkImTfZbHvdC8Wm
$2y$08$12345678901234567890iOXDaVzn/h7/oQtUgHyPodyggGkOqxFdW
$2y$08$12345678901234567890jODbaT2pRSwnD2qHm43YdAbHVPBJ8iapi
$2y$08$12345678901234567890kOrUyng3J5OCChkP6tHiM.rz4o4CdPkTO
$2y$08$12345678901234567890lOtscWm7fnlUJXZIXLKhVI7E2Abh7uc3i
$2y$08$12345678901234567890mOCeJM40E/G0WrJ4utkSaJwtZUMCae326
$2y$08$12345678901234567890nO4ac8AzrsXk6HpAtOaGEvGfS8eceFtSC
$2y$08$12345678901234567890oOv3BFJmdPMx9josbfOHHtu/7xgoGUygq
$2y$08$12345678901234567890pOPWQlIGa.WBx8kDEEG05uWhUioyNqWiq
$2y$08$12345678901234567890qOg2ufL5bmYfAoZEFknsRaSOlI4GVBKWy
$2y$08$12345678901234567890rOJZTvmghag6zIY5Ha7iOCgArPZGotche
$2y$08$12345678901234567890sOZjZ2OaVZy.GeXp/BQvjbCpXgNa/GAlK
$2y$08$12345678901234567890tO3bAZAMEXEZm72/mAkbJkefUua9CUFuy
$2y$08$12345678901234567890uOQ.i2vydj6OGyl84Qhg5OXPq7OkRQomu
$2y$08$12345678901234567890vOc9BKZfLu6mcd2mIfLtmT6C6JwDT.Siq
$2y$08$12345678901234567890wO7ow2JgV.7yzEsllHUbhbMrOMKXSihsq
$2y$08$12345678901234567890xOUI89zc5eDCCCHoTljMyXuGXmIz9b0PW
$2y$08$12345678901234567890yORmKbjoeO.1HSpQB7L5EBMSRjJr4lR62
$2y$08$12345678901234567890zOZkhGY/cILtgQRmHLkx//nuzLXSwLqYy
$2y$08$12345678901234567890AOuJWX5/tdzRCTTs5EXYioLP1t7u1Ao7u
$2y$08$12345678901234567890BO2vHWuKdbL2lsbBQwaAkWCXz/YVEaHP2
$2y$08$12345678901234567890COedKIdK.eAjm2zF0CAnuM9XxbO3CakoK
$2y$08$12345678901234567890DOpunwAyx9X4/tJzDmUXARABluQdRV7Ji
$2y$08$12345678901234567890EOB1ONHz9lELb7iUvtzTi.PTSgN2tFv1.
$2y$08$12345678901234567890FOplAZBguPKXbAQDxq9PXqgjH/1ZX6u7C
$2y$08$12345678901234567890GOP/G3kfN/r92DIQlC0eVyGi3jWRUoVXK
$2y$08$12345678901234567890HOmala7V1QCL7PX79yODRg2Y5lTq6i/ii
$2y$08$12345678901234567890IOWbq1AXhTucizWIBn58rgVYFpRxMpm8.
$2y$08$12345678901234567890JOxgmM1XAcDg7AUpzeHzHxn6z75ljNoDy
$2y$08$12345678901234567890KOTnfd7pzmfzf80CrXxWC24sK3y1DAbb6
$2y$08$12345678901234567890LOXxQX37TiNlNMfZUtMLZFrZah8u39q9K
$2y$08$12345678901234567890MOmpvWu3ZKbbilLb4f8QF6OUPPpEbsM42
$2y$08$12345678901234567890NO8VjZ2KNbOVoOzgP/Tjd6IFtwjRG2PJ2
$2y$08$12345678901234567890OOvSnZoahC5g1Ewlm6K7US13i6vJIQSqm
$2y$08$12345678901234567890POVs5m/8eCyLd11zjEPYoYhpaZAz6PYF2
$2y$08$12345678901234567890QOk4MBZhDwzS8dwJl6lm.hdAVBcllSid2
$2y$08$12345678901234567890ROWh4H3TuKSuFfrtx1vqHnU/RrQ0HrbNW
$2y$08$12345678901234567890SOd/USMzVBx6wyPgsuvAszCIVZ6zOA44O
$2y$08$12345678901234567890TO53YobspFDSFshtGX9hH4LTw2OT2T4P.
$2y$08$12345678901234567890UOMLp7HSCxWMMxgJVN6JTN7WRKlRPN17y
$2y$08$12345678901234567890VOmOMGgpLXOV/mft8WXOWXmQjc71SN6g2
$2y$08$12345678901234567890WOiAkYTQmitOHabdScoZivJ4JeKtJ6t7.
$2y$08$12345678901234567890XOUUqRtGjd/nob.UiRrJvFyKSMELAIuZe
$2y$08$12345678901234567890YOukccL1Y2PDV9ErOLHileZOq5m6zIzSy
$2y$08$12345678901234567890ZOMNrfK..n1YjuP3F.S4Taxn0XvIf5gXW
$2y$08$12345678901234567890.OmG2XbJMpLDBrtq44ptVtXkVaGdAT9oO
$2y$08$12345678901234567890/OTN4hG/XcY.FtrT85TGI.Vm0sH0tpQ.a

Now, to prove that we're only using a few bits from the last byte, let's vary that one, holding the 21st fixed:

$chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ./";
for ($i = 0; $i < strlen($chars); $i++) {
    echo crypt('string that should be hashed', '$2y$08$12345678901234567890a' . $chars[$i]) . "\n";
}

Here it is:

$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890aeDDHXF42QK8mY.t4/x9I.DNpdmARsDG.
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890auYqXTg7.1WNKn8Yxc4wW2p2ppsJb9rZa
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890aOQs9arCVhxFtQ.Z7yJUOtp8UCDsR1rHa
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO
$2y$08$12345678901234567890a.FpXM0OnHV1fSxeBCiU8eEDae5LtBtAO

Notice how that only produces 4 unique hashes? That's because we're only using the first 2 bits (2^2) of that last byte. The rest are actually part of the result hash (and hence thrown away).

Make sense?

And BTW: for this and other reasons, I would suggest not using crypt() directly, but instead using a library. Such as password which is coming in PHP 5.5, or it's compatibility library (which I maintain) password_compat.

Cowman

Thank you for this amazing answer. It was really well explained and should actually be part of the php documentation (i didn't find anything explaining this in the doc). – Tommy