Is PBKDF2-HMAC-SHA1 really broken? 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:
  
  plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd
  and eBkXQTfuBqp'cTcar&amp;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.