Answers · Keeping it safe

How fast can an attacker guess passwords after stealing a hash database?

In shortAbout ten thousand million guesses a second on one rented graphics card against a fast hash, so most of a stolen table falls in under a second.

Roughly ten thousand million guesses per second, on a single rented graphics card, against a one-way function that was designed to be quick. At that rate a password that looks carefully chosen, a dictionary word with a digit and a symbol stuck on the end, is recovered in about a tenth of a second. Most of a stolen table goes sooner than that, because the attacker does not work through the table one row at a time: one pass down the list covers every row at once.

t = \frac{k}{g}

The two numbers are the guesses required, $k$ , and the rate, $g$ . A word with a digit and a symbol appended sits about $k = 10^9$ guesses into the list an attacker actually runs. With $g = 10^{10}$ guesses per second, $t = 10^9 / 10^{10} = 0.1$ seconds. The bare dictionary word underneath it sits at about $k = 10^4$ , so $t = 10^4 / 10^{10} = 10^{-6}$ seconds, a microsecond. Putting the digit and the symbol on bought a factor of a hundred thousand in the attacker's list and still lands inside a fifth of a heartbeat.

The usual calculation goes wrong here, and it goes wrong in a way that flatters you. Take ninety-five printable characters and eight positions: $95^8 \approx 6.6 \times 10^{15}$ possible strings. Divide by the same $10^{10}$ per second and you get $6.6 \times 10^5$ seconds, which is $660000 / 86400 \approx 7.6$ days, so about a week. That number is arithmetically correct and almost never describes what happens. It is the time to search the space, and nobody searches the space. Attackers run an ordered list built from previously leaked tables, so it is ordered by what people genuinely pick rather than by what the character set permits.

FIG 1

phase	guesses	cumulative share
the ten thousand commonest	1e4	0.31
every word plus common names	1e7	0.52
words with predictable endings	1e9	0.63
substitutions and joined pairs	1e11	0.82
everything of eight characters	6.6e15	0.95
what is left: manager output	not reached	0.05

Scale it to a table. Forty thousand stolen rows, one card, and the phases above map onto the clock as follows.

FIG 2One stolen table of forty thousand rows, by the clock

step	elapsed	guesses made	accounts broken	what is happening	what happened
1	one second	1e10	about 25000	the common list, which is already most of the table	1e10 guesses covers everything up to the end of the predictable-endings phase, which is 0.63 of 40000 = 25200 rows.
2	one minute	6e11	about 31000	words with endings, then substitutions	1e10 x 60 = 6e11 guesses, and 0.78 of the table is gone. The curve is already flattening.
3	one hour	3.6e13	about 33000	joined word pairs and longer patterns	1e10 x 3600 = 3.6e13 guesses, buying about two thousand more rows. Still an excellent return per account.
4	one week	6e15	about 38000	an exhaustive pass over everything short	3.6e13 x 24 x 7 is close to 6e15, which is the space figure finally becoming relevant, with 0.95 of the table already spent.
5	never	unbounded	the last 2000	nothing works against manager output	Five per cent of 40000 is 2000 rows, and no list reaches them at any rate worth renting.

5 steps

The first row is the whole story: sixty-three per cent of forty thousand is about twenty-five thousand accounts, and it costs one second of one card. Every row after that is the attacker paying real time for a shrinking return, which is a completely different situation from the one the space calculation describes.

This is why scrambling a password buys so little. Appending one digit and one symbol multiplies the nominal space by $10 \times 32 = 320$ , and it moves the password from roughly the $10^4$ phase of the list to roughly the $10^9$ phase, a factor of $10^5$ in exchange for about $10^{2.5}$ of supposed space. The reason is that substitution is itself one of the phases: capitalising the first letter, swapping o for zero, adding an exclamation mark, these are not variations the attacker has to discover, they are lines in the file. A password built by decorating a word has the entropy of the word, not the entropy of the decoration.

Only one of the two numbers is yours

$k$ is set by what your users choose, and decades of composition rules have failed to move it much. $g$ is set by the function in your database, and that is entirely a decision you make. Make each guess cost more and the whole trace above slides to the right. A cost parameter that makes one computation a million times more expensive drops the rate from $10^{10}$ to $10^4$ per second, and the password that took 0.1 seconds now takes $10^9 / 10^4 = 10^5$ seconds, which is $100000 / 3600 \approx 27.8$ hours. Salting attacks the other side of it: without a per-user value one pass covers every row, and with one the attacker must redo the list per account, so the same effort now covers one row instead of forty thousand.

Two things change the picture. If the attacker wants one specific account rather than the table, the multiplier from the table size disappears and only the cost per guess is left, which makes the cost parameter matter more, not less. If the password genuinely came from a manager and is long and random, none of these rates reach it, and no amount of tuning on your side changes that either: the shape of the password is irrelevant, the source is what decides. And a cost you cannot afford to pay on every login is not a cost, since a login page that takes ten seconds has moved the attack to the support queue.

Worth keeping

Time to break is the number of guesses needed divided by the rate, and only the rate is under your control.
Ninety-five printable characters to the eighth power is about 6.6e15, which looks like a week at 1e10 guesses a second and describes a search nobody performs.
Sixty-three per cent of a real table falls to the first 1e9 guesses, which is a tenth of a second on one rented card.

Where this goes next

This question is one step of How a Password Is Stored, a course that works through its subject from the beginning. The page that teaches this part of it is Guessing Is Cheaper Than You Think, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course

How fast can an attacker guess passwords after stealing a hash database?

Only one of the two numbers is yours

Worth keeping

Where this goes next

Read alongside