[lqfkpvkq] Incorrect passwords hang

To validate a given password, consider a program which tests every possibility of number of rounds of the password key derivation function, from 1 to infinity, until the validation succeeds, or the user signals "give up".  This is in contrast to the common technique in which the number of rounds is encoded in the hashed password database (e.g., /etc/shadow), along with salt.  The user selects the number of rounds probably by waiting an amount of time deemed within the limits of his or her patience when initially setting the password.  This number of rounds is not recorded anywhere.  Whenever the user enters the correct password in the future, he will she will have to wait that chosen amount of time for the password hashing to complete.  It is an easy UI therefore for the user to wait longer when setting important passwords, automatically getting more rounds.  If the user accidentally enters an incorrect password, he or she knows how long to wait (his or her internal measure of patience) before telling the UI to "give up" and let him or her try typing the password again.  An attacker doing a dictionary attack, not knowing how long to wait, i.e., not knowing how many rounds, will have to wait a long time just to be safe, for each guess.  This punishes incorrect password attempts.

There is a potential failure if the user had set the password on a much more powerful machine than later used to validate the password, e.g., mobile.

It also has the potential failure of an attacker being easily able to cause a denial-of-service attack if the server is validating the password.

This scheme could easily be implemented while maintaining the old password database schema.  Just have the new software ignore the specified number of rounds.  Could be useful for the GnuPG s2k-count parameter capped at 65 million rounds by the OpenPGP specification RFC 4880.

All this works fine if the password hashing algorithm has exactly one parameter, e.g., number of rounds, as is the case for the most commonly currently deployed password hashing schemes.  However, if the algorithm has more than one parameter, e.g., both memory and CPU, it is less clear what to do.

One possibility is for the hashed password database to record a function or path, selected by the user, through the parameter space.  When validating a password, it tries parameters along that path through parameter space until the password hash validates or the user signals to give up.  One likely common path will be just to use a specified constant amount of memory, just increasing the number of rounds, similar to before: a horizontal path through the parameter space.

When only the number of rounds is being increased, the previous computation for a lesser number of rounds can easily be reused.  The additional computation is just the additional rounds beyond the previous computation.  However, if the memory parameter is increased for a memory-hard password hashing functions like scrypt, I suspect the computation must be started from scratch each time.  This seems highly undesirable because it decreases the rate at which different parameters can be tried, lowering the number of possibilities for the attacker.

Can a multi parameter password hashing function be designed so that increasing any parameter can reuse the work of the smaller parameter?  Yescrypt has a lot of parameters.

Inspired by a comment on the PasswordSafe mailing list.  It is surprising that the Schneier-written software has a hardcoded unalterable number of hashing rounds.