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$.
