The Only Thing the Table May Hold

A password table has to let you check a password and must not let anybody recover one. Those two requirements are compatible, and only one kind of value satisfies both.

The property the value needs

Start by assuming the table is gone. Somebody has a copy of every row of

your users table, taken through a backup, a restore drill, a query from a

console, or any of the other paths the threat modelling course draws. This

is not pessimism, it is the only assumption that produces a useful design,

because a design that holds only while the table stays private is a design

that provides nothing.

Now state what you need the stored value to do, which is two things that

sound like they conflict.

You must be able to confirm that a password somebody just typed is the

right one. And nobody holding the stored value must be able to produce the

password it corresponds to.

Those are compatible because they are different operations. Confirming is

answering a yes or no question about a candidate you were handed.

Producing is a search over everything the password could have been. A

function that is cheap in the first direction and expensive in the second

is exactly what is needed, and the rest of the course is about how

expensive the second direction can be made.

FIG 1Four ways to store a password, against the two requirements

	can confirm a login, 0 t	survives the table being	survives the key being c	survives a year of guess
the password itself	3	0	0	0
the password, encrypted	3	0	1	1
a fast one-way value	3	1	1	1
a slow one-way value wit	3	3	3	3

Every row can check a login, which is why every row has shipped. The columns to the right are where they separate. The first marked cell is the encryption case failing once the key travels with the data, which it does. The second is a fast one-way value failing against sustained guessing, which is the next lesson.

Why encryption fails

Encrypting the passwords is the design a sensible engineer reaches for

first, and it is wrong for a reason worth stating precisely, because the

reason is not that encryption is weak.

Encryption is designed to be undone. That is its purpose, and it does it

well. To check a login your server must undo it, which means the key has

to be available to the running service, which means it is in the

configuration, or in the environment, or in a vault the service can reach

with credentials that are themselves in the configuration.

Whoever obtained the table was inside far enough to read a database. The

step from there to the service configuration is short, and in most of the

paths the threat modelling exercise draws, it is not a step at all because

the backup contains both.

FIG 2What each design hands over when the table is copied

plaintext

design              | row holds           | attacker then needs
--------------------|---------------------|--------------------
the password        | hunter plus a space | nothing
encrypted           | an unreadable blob  | the key, usually nearby
a one-way value     | a fixed length tag  | to guess, once per candidate
slow and per-user   | a tag plus a salt   | to guess, per candidate
                    |                     | per account, slowly

Read the last column. The first two designs hand over every password immediately or nearly so. The third hands over a problem, and the size of that problem is what the remaining seven lessons are about.

There is a narrow case where encryption is right, and it is worth naming

so the rule does not sound like superstition. If you need to recover the

original value later, as with a stored credential for a third party

service you must sign into on the users behalf, you have no choice, and

then the key belongs in hardware that will not release it. A password you

only ever need to check is not that case, and treating it as one gives

away the whole table.

What one way means

A one-way function is easy to compute forwards and has no known method of

being run backwards that beats trying inputs until one matches.

That last clause is the entire subject. There is always a way backwards,

and it is to guess. So the security of the arrangement is never absolute,

it is an economic statement: the number of guesses required, multiplied by

the cost of a guess, exceeds what the result is worth.

FIG 3The two paths through a credential store

Note that the attackers path, on the right, joins the honest path at exactly the comparison step. They are doing the same operation you are. The difference is only that they do it a great many times, which is why making one operation slower is the whole technique.

What is actually stored

A credential row holds five things, and only one of them is secret.

The identifier, which says whose row this is. The one-way value. The

per-user value that the third lesson derives, usually called a salt. The

cost parameters, which say how much work was done. And the name of the

scheme, because you will change schemes and every row has to declare which

one produced it, which is what makes the final lesson of this course

possible.

The last three are stored in plain sight deliberately. An attacker

learning your cost parameter gains nothing, because the parameter is a

cost they have to pay too. Hiding it would buy nothing and would make the

migration in lesson eight impossible.

FIG 4What the loss actually is

: accounts at risk elsewhere, which is the real size of the loss
: accounts in your table
: share of people using that password on another service, measured at around a half

The accounts at risk r is your number of accounts a multiplied by the share s of people who use that password elsewhere. For forty thousand accounts and a reuse share of about half, a readable table exposes twenty thousand accounts on systems you have no relationship with, and they will never know where it came from.

FIG 5One stolen table, under four designs

step	design	what the attacker has after an hour	after a week	who else is affected	what happened
1	the password itself	every password	every password	every reused account, immediately	No work is required at any point. The hour and the week columns are the same because there is nothing to do.
2	encrypted	every password, if the key travelled	every password	every reused account	The only question is whether the key was in the same backup, and for most of the paths an attacker uses, it was.
3	a fast one-way value	the common passwords, which is most of t	nearly all of them	most reused accounts, within days	This is the design most teams believe is adequate, and the next lesson puts the number on how quickly it falls.
4	slow and per-user	a handful of the very weakest	a small minority	a few, and your users have time to be to	Nothing is perfect here either. What changed is that the loss is bounded and you have time to act, which is the whole of what good storage buys.

4 steps

Read across the bottom row. The slow design does not prevent the loss, it reduces it to the weakest passwords and buys the time needed to tell people. That is the realistic goal, and any description promising more is overselling.

The next lesson supplies the number that makes all of this feel urgent

rather than theoretical: how many guesses a machine you could rent this

afternoon makes per second against a fast one-way value, and how long a

password that looks reasonable survives it.

Recap

The requirement is not secrecy, it is irrecoverability. Assume the table has been copied, because every design decision in this course follows from that assumption.
Encryption fails the requirement, because anything your own code can reverse to serve a login can be reversed by whoever took the table and the key with it.
The loss from a readable table is not confined to your system, because people reuse passwords, so the real damage is to accounts you have never heard of.

This 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

NextGuessing Is Cheaper Than You Think →