Increase the security of an already stored password hash

Question

Right now we're using 1024 byte PBKDF2 with 256 byte user-specific salt and variable iterations. However, I would much prefer to be able to, perhaps once every year or two, to be able to flat out increase the rounds used in the algorithm. Neither BCrypt or PBKDF2 allow that, so...

Should I just forget about it, or implement our own version of recursive function that uses SHA512/256? The idea here is to take the password, append salt, hash, take the hash, append salt, hash, take THAT hash, append salt, hash... repeat ad nauseum.

... Or should we just make the system rehash the password with new amount of rounds once a year when user logs in?

Answer 1

Building your own algorithm is never a good idea. Even trained cryptographers, i.e. the people who toiled for years in the dark tunnels of academia and the battlefields of scientific congress, will resort to such inventiveness only when everything else has failed; and even then, they prefer to suggest schemes to be validated by their ferocious peers, certainly not to be deployed in production right away. Most of academic training is about acquiring an intuitive knowledge of the dangers of one's field.

Designing your algorithm is like tap-dancing in a minefield.

Nevertheless, the impossibility to simply extend the number of iterations of a stored hash, beginning with the hash value itself, is a known defect of the usual candidates (PBKDF2, bcrypt and scrypt). If you have to live with it, you could try the scheme described there, but I explicitly deny that security would be increased that way. My training and years of experience in the field allow me to state with some confidence that the extra hashing rounds I suggest would not decrease security.

In the future, things will be better because a new open competition for password hashing algorithms has been launched, using the model of the previous AES, eSTREAM and SHA-3 competitions. Submissions are due for the end of January 2014. A portfolio of "good algorithms" will be obtained by mid-2015, according to the provisional timeline. The call for submissions explicitly includes the following desired functionality:

Ability to transform an existing hash to a different cost setting without knowledge of the password.

So we can hope for a solution to your problem in a bit more than two years. Only two years, that's really fast by cryptographic design standards.

In the mean time, you will have to resort to the usual arrangement of waiting for the users to log in so that their password can be rehashed with more iterations. Most users who have not logged in for more than one year have probably forgotten their password anyway.

Answer 2

The classical solution is the one you write at the end -- "rehash the password [..] when user logs in". In other words:

1. The user logs in, presenting his password in plain text.
2. The system hashes the password using the old hash, and compares it with the stored value.
3. If they match, hash the plaintext password with the new stronger hashing algorithm, and write the result to database.
4. For accounts which don't log in within a certain time, send them a polite email requesting that they re-visit the site, or their account will be removed.

That said, be mindful of not going overboard with password hashing. The main purpose of password hashing is to delay the attacker in exploiting passwords after a successful breach -- allowing the end users time to change their passwords. At a certain point the password hashing becomes 'good enough' compared to the other components in the system.

Obviously, preventing the attacker from breaching the system in the first place is best -- so keep enough energy for the ongoing grind of building and maintaining secure systems. (Like ongoing code security audits, Web Application Firewall ruleset maintenance, Intrusion Detection System monitoring and configuration, securing backup media, etc.)

Answer 3

I had the same requirement, and solved it in this manner:

• Hash the salt and password in the usual manner with PBKDF2 and a work factor that's currently 16 (ie 2^16 iterations). Store the salt, hash, work factor, etc as a row in a database table.
• Asynchronously (ie not affecting the end-user) do this 3 more times, increasing the work factor by 1 each time. So now I have 4 database rows for that user, with work factors of 16, 17, 18, and 19 respectively.
• I always use the row with the lowest work factor to verify the password, but every 2 years I delete the row with the lowest work factor.