Recover Passwords from Fast Hashes

Finding F1 is still open: the reading list stores each password as plain text. Chapter 2 said that a hash cannot be undone. So here is a tempting fix: store hashlib.sha256(password) and never the password itself. A thief who copies the state finds digests, and digests cannot be turned back.

This lesson plays the thief against exactly that design, and the design loses.

First, a word about this chapter’s project. Your server has one change that does nothing new yet: the login decision now sits in its own function, login_user(state, credentials), which handle() calls. There are two new constants in reading_server.py, ANA_RECORD and BEN_RECORD, which wait for Lesson 6. And there is a new file, passwords.py, where you will work for most of the chapter.

The leak

The project holds a file that stands for a leak: leaked_table.json. It comes from an invented book club site that stored a SHA-256 digest for every user. Look at it:

cat leaked_table.json

Eight users, eight digests of 64 hex characters, and no password in sight. The thief here is the third attacker of Chapter 1. They have the file and send no requests, so nothing on the server slows them down. They work on their own machine, for as long as they like.

Guess and check

A digest cannot be turned back, and it does not need to be. The thief can hash a guess and compare. If hashlib.sha256(b"letmein").hexdigest() equals a digest in the table, that user’s password is letmein.

All the thief needs is good guesses, and people are predictable. words.txt holds 300 guesses of the kind people choose: a word, sometimes followed by a year, 123, or !. The file starts reading, reading1, reading12. It was written for this course by a simple rule: twenty base words, each with fifteen endings.

One pass over the words

Here is the idea that makes this attack cheap. Hash every word once, and keep the results in a dict that maps each digest to its word. Then go through the users of the table and look each user’s digest up in that dict.

The 300 digests are computed one time and serve all eight users. They would serve eight million users just as well. The thief’s work grows with the number of guesses and not with the number of accounts.

Your task

In passwords.py, write crack(table, words).

• table is a dict from user name to the SHA-256 hex digest of that user’s password.

• words is a list of strings to try.

• Hash each word as hashlib.sha256(word.encode("utf-8")).hexdigest().

• Return a dict from user name to password, for every user whose digest matches a word. Leave out the users you did not recover.

Use only the two arguments. main() at the bottom of the file reads leaked_table.json and words.txt and calls your function. Then run it:

python passwords.py

Read the result

amir bookworm123
bea coffee!
chidi letmein
dana sunshine2024
eli (not recovered)
farah dragon99
gus sunshine2024
hana (not recovered)
6 of 8 passwords recovered from 300 words

Six of eight accounts, from 300 guesses, in the time it takes to press Enter.

Look at dana and gus. They have the same password, and you could have known that before cracking anything: their digests in the table are equal. The same input always gives the same digest. That was what made a digest a good ETag, and it is a leak here. One cracked password now opens two accounts.

eli and hana survived. Their passwords are not in the list, and that is the only reason. The hash did not protect them. A longer list might find them.

SHA-256 is not broken, and it is still the right tool for an ETag. It is the wrong tool for a password for one reason: it was built to be fast. A single graphics card can try an enormous number of SHA-256 guesses every second, and a real word list has many millions of entries, not 300.

So storing a plain digest does not close F1. The thief of this lesson had two advantages: one guess served every user, and every guess cost almost nothing. The next lesson takes away both.

The rule of this course applies to what you wrote today as much as to anything else. This table was invented for the course. Never run crack against data that is not yours.

Press Check my work when python passwords.py prints six passwords.