Can using an unknown, non uniform random salt increase difficulty for password attacks?

Question

I remember reading a previous stack exchange post (unfortunately was unable to find the link, if someone knows the link that would be great!) about a method to make password checking time for the server be on average less than that for an attacker. Essentially, when the password is first created a random number between, for example, 1 and 100 is added to the salt and plain-text password. This result is not saved. Then, when checking the password for correctness, all numbers from 1 to 100 are added by the server and see if any of them matches the stored record. For a correct password, this takes 50 guesses on average. On the other hand, an attacker would have to try all 100 numbers for every single wrong password, making the average checking time 2x more expensive.

I was wondering if it makes any sense to use a nonuniform distribution at initialization time to be able to tune this ratio factor. For instance, one could weight the first 10 numbers higher, reducing the entropy and thus the average amount of checks for the server, but an attacker would still need to check all 100 numbers to be sure that the password is wrong.

• Would there be any problems with this?
• Would this have any advantages compared to a uniform distribution?

The one thing I think could potentially flaw my reasoning is that an attacker might just check all the likely guesses, and move on to other passwords if none show up (only returning back to this password and the less likely guesses much more later on).

Anyway, my overall thinking is that we could potentially use the fact that the percentage of correct passwords the server is checking is a lot different that the percentage of correct passwords an attacking is checking to create a wedge in the average hash times.

EDIT: Also realized that someone could potentially use response time to get an idea of what the guess number could be.

Answer 1

I don't think using non-uniform random pepper is a practical way to bring extra protection compared to the original proposition†, because:

1. As noted at the end of the question, timing attack becomes much more of an issue: the simple mitigation of having the legitimate password verifier trying the possible peppers in random order no longer works.
2. An adversary content with finding one in many passwords (rather than targeting the password of a single user) can make good use of the non-uniform distribution of pepper, by only trying the most likely peppers, much like they try only the weakest passwords against all the leaked password hashes.

However, if 1 could be solved in some reliable way, and if we consider only individual user security, yes I think that the idea has some merit: attackers will have to define some cutoff on the pepper, or be prepared to try again the same password with larger pepper in case of failure after some effort.

Much like the original idea, the gain in security is assuming that setting up a new password in the search engine is a large part of the cost of testing a password. That assumption is valid to an uncertain degree: it seems likely for an ASIC-based PBKDF2 password cracker, less so for something targeting Argon2.

---

† In summary: part of the salt is replaced by uniformly random pepper that is found by enumeration at legitimate password verification. That's practical, and was suggested long ago even if the security benefit was then not well articulated.