Two Rows That Look the Same
Last timeGuessing Is Cheaper Than You Think
If two accounts chose the same password their stored rows are identical, and that one fact hands an attacker both a free census of your users and the whole precomputation industry.
What two equal rows tell you
Suppose you take the previous lesson seriously and store only a one-way
value. Forty thousand rows, each holding an account name and a stored
value, nothing reversible anywhere.
Now sort the stored values and look for duplicates. You will find them,
because people choose the same passwords, and the commonest one in a table
of that size is typically shared by several hundred accounts.
account | stored value
----------------|------------------------------
a.okafor | 5e884898da28047151d0e56f8dc62927
t.bergstrom | 5e884898da28047151d0e56f8dc62927
m.whitfield | 7c4a8d09ca3762af61e59520943dc264
r.santos | ef92b778bafe771e89245b89ecbc08a4
duplicates found in a table of 40000 rows:
largest group | 612 accounts
second group | 341 accounts
groups of 10 plus | 1890 accounts
rows in some group | 0.37 of the tableConsider what that is worth before any guessing starts. The largest
duplicate group is almost certainly the commonest password in the world
for that year, which tells the attacker what to guess first. More
usefully, one successful guess no longer opens one account. It opens six
hundred, in a single lookup, with no further computation.
The shape of the problem is that your stored value depends on exactly one
thing: the password. Equal inputs give equal outputs. That is the
defining property of the function, and here it is working against you.
| duplicates visible, 0 or | a bought table works, 0 | accounts opened per corr | work must be redone per | |
|---|---|---|---|---|
| plain text stored | 1 | 1 | 3 | 0 |
| fast one-way value, no p | 1 | 1 | 3 | 0 |
| fast one-way value, one | 1 | 0 | 2 | 1 |
| fast value, random per a | 0 | 0 | 0 | 3 |
| slow value, random per a | 0 | 0 | 0 | 3 |
| slow value, random per a | 0 | 0 | 0 | 3 |
Work done in advance
The duplicate problem is the small half. The larger half is that your
stored values can be computed by somebody who has never seen your table.
If the stored value is a function of the password alone, then anybody can
take a list of likely passwords, compute the stored value for each one,
and keep the result. That table is built once, by somebody with a budget,
and used against every breach forever, including yours, including breaches
that have not happened yet.
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