Why shouldn't I use the 23rd character in a crypt() function's salt?

Question

I'm learning about PHP's crypt() function and have been running some tests with it. According to this post, I should use a salt that's 22 characters long. I can, however, use a string that's 23 characters long with some limitations. When I use a 22 character long string I always get an outcome of '$2y$xxStringStringStringStri.HashHashHashHashHashHashHashHas'. I know the period is just part of the salt.

It seems that if I use 23 characters instead of just 22, I can successfully generate different hashes, but there is only 4 different outcomes for all 64 characters. The 23rd character "rounds down" to the nearest 1/4th of the 64 character alphabet (e.g. the 23rd character is "W" and rounds down to "O" or any number rounds down to "u")

v---------------v---------------v---------------v---------------
./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890

All four of these crypt functions generate the same salt:

crypt('Test123','$2y$09$AAAAAAAAAAAAAAAAAAAAAq');
crypt('Test123','$2y$09$AAAAAAAAAAAAAAAAAAAAAr');
crypt('Test123','$2y$09$AAAAAAAAAAAAAAAAAAAAAs');
crypt('Test123','$2y$09$AAAAAAAAAAAAAAAAAAAAAt');

But this one is different:

crypt('Test123','$2y$09$AAAAAAAAAAAAAAAAAAAAAu');

So why shouldn't I use the 23rd character when it can successfully generate different outcomes? Is there some kind of glitchy behavior in PHP that should be avoided by not using it?

For clarification on how I'm counting the 23rd character in the salt:

crypt('Test123','$2y$08$ABCDEFGHIJKLMNOPQRSTUV');
//        The salt is '$ABCDEFGHIJKLMNOPQRSTUV'
//        Which will be treated as '$ABCDEFGHIJKLMNOPQRSTUO'

Eyelid

There's a good explanation on this question: security.stackexchange.com/questions/20862/… – Knockabout

Thank you for this response. Although this only addresses what happens to the 23rd character as it only gets shortened due to the size of bits allowed in the crypt() function. My question, in another way of asking, is "Should I use the 23rd character even if it will get chopped up into two bits?" or another way is "Is there a glitch in PHP's algorithm that generates incorrect hashes whenever the 23rd character is used?" – Eyelid

Answer 1

It has to do with hash collisions. Once you exceed 22 characters your generated hashes are no longer unique depending on the NAMESPACE of the algorithm. To be said another way, more than 22 characters doesn't result in any increased security and can actually decrease your level of security.

Acyl

It seems to me like it adds 2 more bits of security. I can still generate different hashes by changing other characters throughout the salt while leaving the 23rd as, let's say "a". Is there an article about overflowing the salt? Even on php.net they use an example of a salt with more than 22 characters. – Eyelid

Of course it will generate different results but if you use 23 characters there is another string out there that will result in the exact same hash. This is called a collision and you don't want that when you are trying to keep everything unique. – Acyl

Hmmm.... I'm not sure how to explain this, but I can guarantee you that using 23 characters in a salt (even though there are salt collisions like you said) is more secure than using 22. Explanation: Let's say we have a a smaller form of blowfish. In this mini bowfish, we can put in a 1 character length salt, such as "a" or "4" or "I". There are 64 different combinations we can make with that before we start getting salt collisions. However, we can add just 2 more bits (".","O","e", and "u") and turn a combination of 64 unique salts into 256. Even when not the full alphabet, it's more secure. – Eyelid

@Andrew: What you're saying would be true if it weren't for rainbow tables. Rainbow tables are EXACTLY why you don't want collisions. Can you understand that having 2 strings (or more) that would generate the exact same hash would decrease the time needed to break the one-way encryption by a factor of 2, or more? – Acyl

$ is not part of the salt. Once you genuinely exceed 22 characters it's no longer part of the salt. – Flutist

Answer 2

$ is not part of the actual salt. It is a separator.

For Blowfish crypt, the format is $2[axy]$log2Rounds$[salt][hash]. You describe it adding a . -- that's because you are missing the last character. Blowfish's salt is 128 bits. You could use only 126, yes, but you are just unnecessarily weakening the salt.

Flutist

If you actually use too many characters, by the way, you're absolutely fine with crypt() because it's designed to be used as crypt(password, salt) for crypt, cryptedPassword == crypt(password, cryptedPassword) for verification, and it does this by appending the hash to the salt on output, and only using the relevant salt bytes on input. So you see, extra characters just won't be used. – Flutist