The Comparison That Tells You How Close You Were
Last timeSlow on Their Hardware Too
Verification ends in a comparison of two values, and the obvious way to write it stops at the first byte that differs. That difference in time is an answer the attacker was not supposed to get.
What an early exit reveals
Verification ends in one step. You have recomputed the stored value from
the password somebody typed, and you compare it against the value in the
row. Equal means let them in.
The natural way to compare two sequences of bytes is to walk them and
return false the moment they differ, because that is correct and it is
faster. Every language's default equality does this, and in almost every
other context it is the right implementation.
Here it is a leak. A comparison that stops at the first difference takes
longer when more leading bytes matched, so the duration of a failed login
is a measurement of how close the guess was.
| step | leading bytes that matched | byte comparisons performed | time taken, nanoseconds | what the attacker learns | what happened |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 20 | nothing matched | The usual case. One comparison, one difference, immediate return. This is the baseline against which everything else is measured. |
| 2 | 1 | 2 | 40 | the first byte is right | Twenty nanoseconds longer, every single time, for any guess whose first byte happens to be correct. The difference is tiny and it is perfectly consistent. |
| 3 | 8 | 9 | 180 | half the value is right | Now the attacker is being guided. They vary one byte at a time, keep whatever increases the duration, and walk forward through the value. |
| 4 | 31 | 32 | 640 | all but the last byte | Thirty-two times the baseline. At this point the remaining work is one byte, which is at most two hundred and fifty-six attempts. |
It is worth being precise about what is at risk, because the usual
objection is that the value being compared is not the password. That is
true, and the attack is not against the password. It is against anything
where a correct value grants access and the attacker can submit guesses:
a session token, a password reset token, an interface signature, a
one-time code. For stored passwords specifically the expensive function
in front of the comparison makes the channel much harder to exploit, and
the habit of comparing properly is what carries over to the cases where
nothing else protects you.
- the extra time taken, compared with a guess matching nothing
- leading bytes of the stored value that the guess reproduced
- time one byte comparison costs, a few tens of nanoseconds
Measuring something far below the noise
Twenty nanoseconds is six orders of magnitude below the variation in a
single network round trip, so the natural response is that this cannot
possibly be measured remotely. That response was tested and it is wrong.
The reason is that the signal and the noise behave differently under
repetition. The timing difference is consistent: it is present in every
single request with those leading bytes, always in the same direction,
always the same size. The network noise is not: it is scattered in both
directions around its own average.
So take many samples of each candidate and compare the averages. The noise
shrinks relative to the signal as samples accumulate, and the only cost is
the number of requests. Measured work puts the requirement at a few
thousand samples for a difference of tens of nanoseconds over a local
network, and more over the open internet, which makes it a budget rather
than an obstacle.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents