Skip to content
wannacode

Passwords

In short: Passwords are stored as a slow salted hash (bcrypt or argon2id), not encrypted and not with fast SHA-256, so a database leak does not give away the passwords themselves.

Problem

The backup that went public

The shop keeps its buyers in a users table: an email and a password. Somebody uploads a database backup to a public folder, and a week later it is on the internet. What the buyers lose depends only on how the password was stored:

  • as text: every password is out in the open. Many people use one password everywhere, so their email accounts leak too;
  • encrypted with a key that sits next to the database: the same. The key is in the configuration of the same server and leaks with it;
  • as SHA-256 with no salt: the passwords are not visible, but equal passwords give equal hashes. The table itself shows who shares a password with whom. And whoever has the table can take a list of common passwords, hash each one and look for matches: that is a dictionary attack, and SHA-256 was built to be fast.

A leak can never be ruled out completely. So the password is stored in a way that a leak does not hand out the passwords.

The idea

Keep the fingerprint, not the password

The server does not need to know the password. It only has to check whether the typed password is the same one. That is what a cryptographic hash is for: a function that turns text into a fingerprint of fixed length and cannot be reversed. The same input gives the same fingerprint, and the fingerprint does not lead back to the input.

This is not the hash() from the dict and set lesson: that one is fast, short and collides often, because it is made for buckets. A cryptographic hash is a different kind.

The shop's old code keeps the SHA-256 of the password:

class Row(NamedTuple):
    email: str
    salt: str
    hash: str




def sha256(text):
    return hashlib.sha256(text.encode()).hexdigest()




# The shop's old code: SHA-256 without a salt.
def register(email, password):
    return Row(email, "", sha256(password))

Four buyers; ana and vera have the same password. The function shared_rows counts the rows whose hash appears more than once:

def shared_rows(users):
    per_hash = Counter(row.hash for row in users)
    return sum(1 for row in users if per_hash[row.hash] > 1)
users = [
    register("ana@example.com", "qwerty"),
    register("boris@example.com", "sofia2024"),
    register("vera@example.com", "qwerty"),
    register("georgi@example.com", "Kp7#vR!q2Lm9"),
]
print("The users table:")
for row in users:
    print(f"{row.email:<20}{row.hash[:16]}…")
print("Rows that share a hash:", shared_rows(users))
Output
The users table:
ana@example.com     65e84be33532fb78…
boris@example.com   6191711a1871a6bd…
vera@example.com    65e84be33532fb78…
georgi@example.com  9cbd9835924cf733…
Rows that share a hash: 2

The rows of ana and vera are equal. Without breaking anything, anyone with the table sees that the two have one password. If one of them gives it away, she gives away the other's too.

The idea

A salt: every row different

The fix for equal rows is a salt: random bytes, different for every row, that go next to the password before the hash. The salt is not a secret. It sits openly in the row, because the login needs it again.

# A random salt of its own for every row.
def register(email, password):
    salt = secrets.token_hex(16)
    return Row(email, salt, sha256(salt + password))

secrets is a cryptographic random number generator: its next value cannot be predicted. (Why the ordinary generator will not do is in the cryptography lesson.)

The salt is different on every run, so the program prints only what does not change:

users = [
    register("ana@example.com", "qwerty"),
    register("boris@example.com", "sofia2024"),
    register("vera@example.com", "qwerty"),
    register("georgi@example.com", "Kp7#vR!q2Lm9"),
]
print("Same record for ana and vera:", users[0].hash == users[2].hash)
print("Rows that share a hash:", shared_rows(users))
Output
Same record for ana and vera: False
Rows that share a hash: 0

Equal passwords no longer show, and one computation counts for one row only. But SHA-256 is still fast: a graphics card computes billions a second, so the dictionary attack still works, just row by row. The hash also has to be slow on purpose.

See it

The users table: no salt, a salt, a slow hash

N = 2**12  # demo; on a real server 2**17 (OWASP)




def hash_password(password):
    salt = secrets.token_bytes(16)
    digest = kdf(password, salt, N)
    return f"scrypt${N}${b64(salt)}${b64(digest)}"




def verify(password, record):
    _, n, salt, expected = record.split("$")
    actual = kdf(password, b64decode(salt), int(n))
    return hmac.compare_digest(b64decode(expected), actual)
Step by step, in words
  1. The users table with the shop's old code: an email and the SHA-256 of the password, with no salt.
  2. Equal passwords give equal hashes. ana and vera have the same value, so the table itself shows who shares a password: 2 rows.
  3. Now every row gets a random salt of its own, and the row keeps SHA-256(salt + password).
  4. Every row is different, ana and vera too: 0 rows share a hash. But SHA-256 is fast, so each guess at a row is still cheap.
  5. The fix is a slow hash: scrypt with cost N = 4,096 here (a demo), which also needs memory. On a real server N = 2^17.
  6. The record keeps everything needed to check it later: algorithm $ cost $ salt $ hash. The password itself is not in it.
  7. At login the code reads the cost and the salt from the record and hashes the typed password the same way.
  8. The two hashes are compared in constant time: "qwerty" gives ✓, "qwerty1" gives ✗. Equal passwords no longer show, and every guess is slow.

The last frame puts the three steps together: the column keeps a record with a salt and a cost, no two rows are equal, and the login checks the password against the record.

The idea

A slow hash and the record

A slow password hash repeats its work many times. How many times is the cost (work factor). A login computes it once and waits a fraction of a second. Whoever has the leaked table pays the same price for every guess.

The standard library has scrypt: besides time it needs memory, and memory is expensive for graphics cards.
def b64(data):
    return b64encode(data).decode()




def kdf(password, salt, n):
    return hashlib.scrypt(password.encode(), salt=salt,
                          n=n, r=8, p=1, dklen=32)
hashlib.scrypt takes n (the cost, a power of two), r (the block size), p (parallelism) and dklen (the length in bytes).

The record keeps everything the check needs: algorithm, cost, salt and hash, with $ between them. That way the cost can go up later without breaking the old records.

N = 2**12  # demo; on a real server 2**17 (OWASP)




def hash_password(password):
    salt = secrets.token_bytes(16)
    digest = kdf(password, salt, N)
    return f"scrypt${N}${b64(salt)}${b64(digest)}"




def verify(password, record):
    _, n, salt, expected = record.split("$")
    actual = kdf(password, b64decode(salt), int(n))
    return hmac.compare_digest(b64decode(expected), actual)
record = hash_password("qwerty")
parts = record.split("$")
print(f"Algorithm and cost: {parts[0]}, {parts[1]}")
print("Log in with the right password:", verify("qwerty", record))
print("Log in with a wrong password:", verify("qwerty1", record))
print("One password, two records, equal:", record == hash_password("qwerty"))
Output
Algorithm and cost: scrypt, 4096
Log in with the right password: True
Log in with a wrong password: False
One password, two records, equal: False

The cost in the program is small, so that it runs fast. On a real server OWASP recommends N = 2¹⁷ (r = 8, p = 1) for scrypt. In a real project you usually do not write this yourself but use bcrypt or argon2id from a proven library (details under "More").

Try it

Predict the output

One and the same password, hashed twice. What will it print?

first = hash_password("qwerty")
second = hash_password("qwerty")
print(first == second)
print(verify("qwerty", first))
print(verify("qwerty", second))
Answer

Try it

Fill in

At login the two hashes are compared. An ordinary comparison stops at the first different byte, and the response time can reveal how far they match. Which comparison always goes through all the bytes?

actual = kdf(password, b64decode(salt), int(n))
return hmac.(b64decode(expected), actual)

Try it

Find the bug

A colleague "simplifies" the code: instead of a random salt for every row, one salt for all. The slow hash is the same. Where is the problem?

Pick the line with the bug.

See it

The cost grows over the years

Computers get faster, so a cost that was enough last year is not enough some time later. Old records cannot be recomputed: a hash does not go backwards, and the server has the password only at the moment of a login. So the new hash happens on a successful login. Here hash_password takes the cost as a parameter, and every record keeps its own, so the old records go on working.

N = 2**12  # last year it was 2**11




def cost_of(record):
    return int(record.split("$")[1])




def login(account, password):
    if not verify(password, account.record):
        return False
    if cost_of(account.record) < N:
        # only now do we hold the password: hash it at the new cost
        account.record = hash_password(password, N)
    return True
account = Account(hash_password("qwerty", 2**11))
print("Cost before the login:", cost_of(account.record))
print("Log in:", login(account, "qwerty"))
print("Cost after the login:", cost_of(account.record))
Output
Cost before the login: 2048
Log in: True
Cost after the login: 4096
More precisely, if you are curious

Which settings (OWASP, Password Storage Cheat Sheet):

  • argon2id: 19 MiB of memory, 2 iterations, parallelism 1. The first choice for a new project;
  • scrypt: N = 2¹⁷, r = 8, p = 1. It needs 128 MiB of memory, and in both Python and Node the default limit is 32 MiB, so it is raised with maxmem;
  • bcrypt: cost 10 or more. It uses only the first 72 bytes of the password;
  • PBKDF2-HMAC-SHA256: 600,000 iterations, when a FIPS-approved algorithm is required.

What real projects use. You rarely write this yourself; you use the framework's library: The packages argon2-cffi and bcrypt (the standard library has neither). Django stores passwords exactly in the shape of this lesson: pbkdf2_sha256$<iterations>$<salt>$<hash>, and hashes again at login when the cost goes up.

Pepper. Some also add a secret value, shared by all rows, that lives outside the database (in a secret store, see the secrets lesson). A leak of the database alone is then not enough. It helps, but it does not replace the salt and the slow hash.

The password policy. A long password (at least 12 characters) and a check against lists of leaked passwords help more than "a capital letter and a digit" rules. That is also the exercise below.

How it is in the other languages: Java and C# have PBKDF2 in the standard library but no scrypt; Python and Node have both (hashlib.pbkdf2_hmac, crypto.pbkdf2Sync). None of the four has argon2id or bcrypt built in.

Exercise

Changing the password

Solve it in your editor.

The buyer's account has the password "qwerty". Write change_password(account, old_password, new_password), which:

  1. checks the current password with verify and refuses if it is wrong;
  2. refuses a new password shorter than 12 characters;
  3. refuses a new password that (ignoring upper and lower case) is in the list password1234, qwerty123456, 123456789012;
  4. otherwise stores a new record with a new salt and returns "Password changed".

Call it with ("qwerty1", "new-pass-2026!"), ("qwerty", "short1"), ("qwerty", "Qwerty123456") and ("qwerty", "tram-9-to-vitosha"), then check the login with the new password:

Output
Wrong current password
The new password is shorter than 12 characters
This password is on the lists of leaked passwords
Password changed
Log in with the new password: True

More tasks

  • A new hash at login. Add login from "The cost grows over the years" and check that an old account with a lower cost comes out of the login with the new one.
  • The same time for a wrong email. If the email does not exist, the login answers at once; if it does, it computes the slow hash. How would you make both cases take the same time?

Test

Check yourself

1. Why are passwords not stored encrypted with a key?
2. What does a salt do, and what does it NOT do?
3. Why does a slow hash help rather than hurt?
4. Why is the hash compared in constant time at login?
5. You raise the cost from 10,000 to 20,000 iterations. What happens to the old records?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·