Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
Collision resistance isn't considered a required property for password hashes. So this is generally just a curiosity, not a vulnerability. –  CodesInChaos Mar 25 at 17:24
    
Surely it should be a required property? Does it not reduce the potential for brute-forcing alternative passwords? –  Polynomial Mar 25 at 17:29
1  
These collisions are relatively rare. If bruteforce attacker needs to go through $499999999$ passwords instead of $500000000$ it does not affect the time for brute forcing significantly. –  user4982 Mar 25 at 17:59
1  
On the PHC mailing list, it was also realized recently that because the password in PBKDF2 takes the place of the key HMAC parameter (rather than the message), passwords also collide when they have trailing ASCII NULs on the end (ex. "password", "password\0", "password\0\0", etc.). –  Stephen Touset Mar 25 at 18:21

2 Answers 2

up vote 5 down vote accepted

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:

plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd and eBkXQTfuBqp'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.

share|improve this answer

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.

What happens now?

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.).

share|improve this answer
1  
It might have one effect: The designers of entries to the password hashing competition will avoid these collisions. –  CodesInChaos Mar 25 at 18:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.