29
$\begingroup$

Say a server wants to hash a password $p$. It would use a secure hash function $H$ and a unique salt $s$ to hash the password as $H(p,s)$. If one has access to the salt, each password candidate requires one run of the hash function to be ruled out; the same amount of time it would take for the server to verify a password candidate.

If, on the other hand, the password was hashed as $H'(p,s+r)$, where $r$ is a random integer in the range $[0,n]$ and that is not stored anywhere. Verifying a correct password would require on average $n/2$ runs of $H'$, whereas ruling out an incorrect password candidate would require $n$ runs of $H'$, i.e. twice as slow for the attacker than for the server.

I'm thinking that this means that if $H'$ is $n$ times faster than $H$, this yields up to twice as fast password validation for the server but equally slow password testing for an attacker as before. And one could then use this either to make the sign-in quicker for users or the hash function slower for an attacker.

Are there any obvious issues with this approach or ways to improve it?

Edit:
The idea here is for there to be many different options for what is stored in the database and that more of these options need to be tried for an attacker than for the server. This could also be implemented in ways that don't use it as a salt. E.g. password hash $=H_r(p,s)$, where $H_r$ denotes the number of iterations of the hash, i.e. $r=3\rightarrow H_r=H'(H'(H'(p,s)))$.

An attacker would need to calculate $n$ hashes for each password but the server only needs to calculate $r$ hashes to validate a correct password (and $n$ hashes to reject an incorrect password).

$\endgroup$
9
  • 6
    $\begingroup$ The concept of "non-public/secret salt" is known as "pepper". $\endgroup$
    – DannyNiu
    Feb 16, 2023 at 8:26
  • 2
    $\begingroup$ Yes so I'm talking about a pepper not known to the server either. Say the pepper can be any number between "0" and "100" then, for each potential password, the server or the attacker needs to try all of these options. If a match is found then they can stop. $\endgroup$
    – n-l-i
    Feb 16, 2023 at 9:39
  • $\begingroup$ Yes, this is exactly the concept known as peppering :) $\endgroup$ Feb 16, 2023 at 13:16
  • 2
    $\begingroup$ Re-posting my link from another comment because it contains useful pointers: see e.g. here. $\endgroup$ Feb 16, 2023 at 13:24
  • 2
    $\begingroup$ The paper you've linked is very interesting and answers my question well. This is exactly what I wanted to find. It seems that "pepper" is a fairly broad term and I've been familiarised with a definition that suggests that the pepper is a second salt but stored elsewhere. Both types of pepper seem to have big but very different types of drawbacks which is interesting. $\endgroup$
    – n-l-i
    Feb 16, 2023 at 13:53

4 Answers 4

24
$\begingroup$

That's is an interesting idea (that was new to me) and turns out to be known as (random) peppering, as pointed in these comments.

Indeed, the average number of evaluations of $H'$ by the server when testing the correct password (which is usually the most common, except for Denial of Service attack) is reduced by $\frac{n-1}{2n}$ compared to work for an attacker that proceeds by eliminating passwords one by one. That gain converges quickly to $\frac12$ when $n$ grows. And while attackers are not bound to that test strategy†, it is typically the less costly for them, because moving from one password tested to the next typically has a large cost.

A gain of at most 50% is not game-changing. But implementers of password hashes like Argon2 optimize their code carefully (because that makes it possible to use more iterations at a given cost, thus ultimately makes using their code safer), and even a 20% gain should be something they consider notable.

If this is in use in some modern login system(s), I want link(s) to see how the potential issue I note next is addressed. And if this is not used, I wonder why because once you see this relatively easy and sizable gain, it looks like it should be a standard technique.


The one major caveat I see is that we should fear that an adversary finds (or approximates) $r$ by a side channel attack on the genuine server while a genuine user logs in (the simplest such attack being timing the login; since $H'$ is slow, that's relatively easy). With the exact $r$, the attacker's effort is divided by a factor of $n$, which is bad.

For this reason, it's probably best not to make $n$ too big, so that even a leak of $r$ is not a major disaster; and that the genuine server, when verifying a password, tries the $n$ possible values of $r$ in some random order. With small prime $n$ (e.g. $n=7$ saving on average >42% of the work for correct password)

  • draw ephemeral secret $r$ random in $[0,n)$
  • set $\delta=1$, or better‡ draw ephemeral secret $\delta$ in $[1,n)$
  • $r_0\gets r$
  • repeat
    • test if $H'(p,s+r)$ verifies, if so accept password $p$.

    • $r\gets r-\delta$

    • if $r<0$ then $r\gets r+n$, in constant time

      In modern C, if r is of type int32_t, we can use r += (int32_t)((0-((uint32_t)r>>31))&(uint32_t)n)

  • until $r=r_0$
  • reject password $p$.

† For example, an adversary having captured so many login/salt/hashes that several of them are likely to be for password 123456, satisfied by finding one, and able to move from one login/salt/hash to the next at negligible cost, would not be impaired by the proposed change if they tested values of $r$ incrementally for all the login/salt/hashes they have, and the fixed password 123456.

‡ From the perspective of timing attacks, using fixed $\delta=1$ is fine. Random secret $\delta$ is only intended as an extra protection against other side-channel attacks. We make $n$ prime so that any $\delta\in[1,n)$ is coprime with $n$.

$\endgroup$
8
  • 2
    $\begingroup$ Note that this concept of peppering is actually well known. I don't know how much it's used in practice, but it has been discussed in many papers, and is essentially identical to OP's idea. There's even a Wikipedia entry: en.wikipedia.org/wiki/Pepper_(cryptography) $\endgroup$ Feb 16, 2023 at 13:18
  • 2
    $\begingroup$ Oh actually this entry is a bit too general. But "peppering" is used in the security community to refer precisely to OP's idea. Also, there are apparently some complications when one tries to use peppering with memory-hard functions such as Argon: see e.g. here for a recent work on the subjet. $\endgroup$ Feb 16, 2023 at 13:23
  • 4
    $\begingroup$ @Geoffrey Couteau: I knew fixed secret pepper, not "randomly-selected number that must be re-discovered on every password input" (per question) as this wikipedia entry puts it, with details not so long ago. And at first glance at least I do not see this idea in the reference quoted for that. Undoubtedly, it's in your reference. $\endgroup$
    – fgrieu
    Feb 16, 2023 at 13:26
  • 1
    $\begingroup$ @Geoffrey Couteau: your reference cites this 1996 source as the origin of (random) peppering. That does as in the question, notes that the work factor for the attacker grows with $S$ (the question's $n$), and makes $S$ 100 to 1000. But it does not tell that the workfactor is increased by only $\frac{S+1}{2S}$ for legitimate use with correct password, which is the interesting point in the question, as it remains relevant in an era with a workfactor parameter to password hashes. $\endgroup$
    – fgrieu
    Feb 16, 2023 at 13:53
  • $\begingroup$ I might have misunderstood some part of your caveat but wouldn't it suffice if the server checks the candidates for r in a random order? If the server checks them in order from 1 to n than a timing attack can help you find r but if the server first randomly reorders the number from 1 to n and then checks them in that order the timing attack will not tell you anything about r. $\endgroup$
    – quarague
    Feb 17, 2023 at 21:05
5
$\begingroup$

First of all, I'll assume that you'd use a password hash (or a Password Based Key Derivation Function, PBKDF) to hash the password. Password hashes require a work factor or number of iterations to calculate the result, slowing down both the server (once, if the password is correct) and the adversary (once for each try). Let's assume that the number of iterations is $n$ in the following sections.

The approach you describe does seem to work. There are however a few drawbacks:

  • the worst case for the number of tries is still $n$;
  • a user that types the wrong password will also experience the worse case scenario.

It seems that the approach simply relies on a full search and that always takes $n \over 2$ operations on average. That means that the speed for the server compared to the adversary is only doubled. This also means that $r$ might as well simply be set to $2$ otherwise the difference between the minimum and maximum time may be too large, without providing any benefit to the user.

So yes, there is and you've described a scheme that is faster on the server. But it is limited in the advantages and it does come with some drawbacks. For such a scheme to be successful I do think that it needs to provide a higher advantage than 2 times. In cryptography this is adding a single bit to the security strength, normally a PBKDF should at least provide ~20 bits of security (i.e. over a million iterations).

$\endgroup$
5
$\begingroup$

It's worth considering the attacker's goals and the threat model of users and the server.

For a given password, guessing only $k$ out of $n$ values of $r$ can create false negatives: a case where you have the right password but you don't realize it because you didn't pick the right $r$.

From a usability point of view, you want the false negative rate to be $0$: a user with the correct password should never be prevented from logging in.

From an attackers point of view, the false negative rate could be almost anything less than $1$: if I breach the password server and get the database of hashed passwords, I probably only care about compromising some number of users, not any specific users. Thus, if I only try $k$ different values of $r$, then I miss a fraction of $\frac{n-k}{n}$ passwords that I would otherwise find, but if I still get $\frac{k}{n}$, I probably don't care (whatever malicious behaviour I wanted to do will still go through).

(there are also different threat models where an attacker would also want a false negative rate of $0$, and your idea could be useful for those).

But, I disagree with the premise that this generally forces an attacker to use an extra factor of $n$ for each password guess.

$\endgroup$
6
  • 5
    $\begingroup$ I don't think there is any advantage to reducing k instead of reducing the number of accounts you try -- e.g. if 10% of all users have bruteforceable passwords, if you try 50% of all users, you get 5% of all users, and if you set k to n/2 and try all users, you still get 5% of all users for the same number of hashes. Another scenario: you try all users in both cases, but set k to n/2 in the second case so the brute force is 2x faster. It's likely that you'll lose many more accounts by halving k than by trying 2x fewer passwords, since passwords are guessed in order of decreasing frequency. $\endgroup$ Feb 16, 2023 at 16:06
  • $\begingroup$ Password frequency is a great point. I suppose if password $p_1$ is more likely than $p_2$, then the probability that (password,pepper)$=(p_1,r)$ is always greater than the probability that it equals $(p_2,r)$. $\endgroup$
    – Sam Jaques
    Feb 17, 2023 at 17:22
  • $\begingroup$ What if instead of picking a random r each time, the server would pick a fixed subset R of [0, n) (let‘s say |R| = n/2), and then for each created password would take a random r E R. In that case, when the attacker takes a subset A of [0, n) (|A| = n/2) of rs to try, there might even be a case that no single password matches (if there is no common element in R and A). For sure as the attacker finds (password, r) combos they learn about R, so their chances of finding a password in < O(n / 2) slowly increase. $\endgroup$ Feb 22, 2023 at 12:39
  • $\begingroup$ @JonasWilms How does the server know $R$ when it checks a password? If the server deletes $R$ then it takes them just as much work, since they must still check all $r$ in $[0,n)$. If the server keeps $R$ secret, then (a) if the attacker compromises $R$, the server loses its advantage; (b) the server could do more effective things if it's willing to use an extra secret, like encrypting the hashes of the passwords $\endgroup$
    – Sam Jaques
    Feb 24, 2023 at 11:24
  • $\begingroup$ @SamJaques I had a real world scenario in mind, where you would have multiple servers, each server picking a random r, storing that somewhere secure in memory and then using that to create multiple passwords. They do not know R but only one r out of it, so for checking a password their advantage is only based on the fact that the password to try is likely correct, whereas the password the attacker tries is likely incorrect (the original premise of the question). I tried to construct a case where the assumption that r is randomly chosen from [0, n) is incorrect and thus the attacker gains ... $\endgroup$ Feb 24, 2023 at 11:33
0
$\begingroup$

A hash function is usually expensive because you are doing many hashing rounds. You could do a million rounds for letting someone in, but somehow be able to find out after 100 rounds that the password is definitely wrong - and then wait the appropriate time to report the failure, at zero cost. That could help against DOS attacks.

$\endgroup$
6
  • $\begingroup$ What authentication scheme works this way? $\endgroup$
    – user253751
    Feb 17, 2023 at 18:54
  • $\begingroup$ You could store the hash after 100 rounds. If it is wrong after 100 rounds, the attacker failed. If it is right after 100 rounds, you do another 999,900 rounds. The attacker never finds out that he was right after 100 rounds. $\endgroup$
    – gnasher729
    Feb 17, 2023 at 19:10
  • $\begingroup$ Why would you do another 999,900 rounds if it's right? why not if it's wrong? attackers make mostly wrong guesses. but why bother doing the rounds, why not just sleep() ? $\endgroup$
    – user253751
    Feb 17, 2023 at 19:18
  • $\begingroup$ How do you avoid an attacker to also stop after 100 rounds when brute-forcing? $\endgroup$ Feb 24, 2023 at 0:13
  • $\begingroup$ Waiting "the appropriate time to report the failure" is definitely not zero cost. You'd have to maintain a network connection for one, which definitely isn't free, and also enough state, and some kind of CPU/memory to 'stop waiting' eventually. It might be less expensive tho. $\endgroup$ Feb 24, 2023 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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