I just read through this article which demonstrates practical (and seemingly trivial) collisions in PBKDF2-HMAC-SHA1, and provides a few examples of collisions.
Am I missing something here? Is PBKDF2-HMAC-SHA1 really broken this badly and trivially? Or am I missing some wider context?
Password hashes need first pre-image resistance and should not cause many collisions among typical passwords (preserve the entropy). This collision "attack" violates neither requirement and causes no practical security issues.
While this issue can find trivial collisions, they're not between commonly chosen passwords. A SHA-1 hash (and thus the shorter of the colliding passwords) has 160 bits, the longer has at least 65 characters. There is no way two users will end up with such a colliding pair by accident.
Doing it deliberately doesn't cause any problems either. It only means that the legitimate user knows two valid passwords for their own account.
I'm sure that cryptographers have known about this issue for years, but didn't care since it's no real attack if PBKDF2 is used as intended. I mainly posted it for fun and because I'd prefer new password hashes coming out of the PHC competition to be collision resistant. Programmers expect these function to be collision resistant, so they might use it in an unusual way that, unlike normal password hashing, relies on collision resistance.
It's also fun to surprise the "MD5 is bad as a password hash because collisions" crowd a bit since it's just as easy to find collisions in the "proper choice". (MD5 is bad because it's fast. Its known cryptographic weaknesses don't apply to password hashing.)
We had a discussion about this on the password hashing competition mailing list, where I posted this:
This results from PBKDF2 using the password as HMAC key instead of message.
HMAC seems to be designed with a fixed length uniformly random key (i.e. it aims to be a PRF), so I consider using the password as key instead of message abuse.
HMAC is a bit weird with variable size keys:
- If the key is shorter than the block size, pad it with zero bytes
- If the key is longer than the block size, hash it
This is generally not a problem for the usual thread model of HMAC (assumes uniformly random keys with fixed size) and PBKDF2 (password hashing, only first pre-images matter). But it means that there are trivial collisions and even second pre-images (add a 0 byte at the end, if the original key was shorter than the block size, this won't have any effect).
As an example with nice printable characters in both passwords:
plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmdandeBkXQTfuBqp'cTcar&g*have the same PBKDF2-HMAC-SHA1 hash (no matter the salt or the number of iterations).I found those with a CPU and unoptimized code. One of our GPU hashing friends could easily find a similar pair for PBKDF2-HMAC-SHA-256.
No, it is not broken. This is NOT A PROBLEM for PBKDF2-HMAC-SHA1.
The PBKDF2-HMAC-SHA1 function is a key derivation function (password-based key derivation). It is fairly good function, for instance it is recommended by NIST (NIST SP 800-132). It is (relatively) rare for this function to have a collision, but collisions generally are not a problem for key derivation functions (in their proper use).
Instead, collisions are a problem for applications like digital signatures if they are found in the underlying SHA-1 hash function. SHA-1 hash is already considered weak for digital signature etc. and some parties, most notably NIST, are no longer recommending its use for applications where collisions are a problem.
This is just a trick: eBkXQTfuBqp'cTcar&g* is hash of plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd. Given a little time, it is easy to find such pairs. This is related to how HMAC works: large arguments are hashed before use.
HMAC-SHA-1 is expected to protect your password less than what you'd expect from 160-bit crypto. If you password is significantly larger than that, good chances are that there are shorter printable passwords which are equivalent.
For PBKDF2-HMAC-SHA1, nothing. For HMAC, nothing. For SHA-1, nothing. Almost nothing happens.
All the users using password plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd could start using shorter password eBkXQTfuBqp'cTcar&g*, and the other way around. But, in fact, any passwords that get any kind of publicity (including e.g. that password is the most common or least common $n$ letter password) are recommended to be not used anymore. So thereafter, it is good idea to avoid both of the above passwords (just like there was previously reason to avoid password, test123, Tr0ub4dor&3, etc.).
keyHMAC parameter (rather than themessage), passwords also collide when they have trailing ASCIINULs on the end (ex. "password", "password\0", "password\0\0", etc.). $\endgroup$