Cryptography
Password Hashing
RockYou breach (2009): 32 million passwords in plaintext. Adobe breach (2013): 153 million accounts with 3DES-encrypted passwords - not even hashed. LinkedIn (2012): 117 million SHA-1 hashes, 90% cracked within 24 hours. Every one of these disasters had a single root cause: choosing the wrong password storage algorithm. The correct choice - Argon2id or bcrypt with adequate parameters - makes cracking years-long instead of hours-long.
- **LinkedIn 2012**: 117 million unsalted SHA-1 password hashes. 90% cracked within 24 hours. Root cause: no salt, wrong algorithm.
- **1Password migration (2023)**: switched from PBKDF2-SHA256 (650k iterations) to Argon2id (m=64MB). GPU cracking rate dropped from thousands per second to single digits.
- **Bitwarden**: Argon2id with m=64MB, t=3, p=4 as default since 2023. Each password verification takes ~200ms on the server.
- **Signal PIN backup**: Argon2 protects encrypted key backups on Signal's servers. Even with database access, server operators cannot recover PINs without breaking Argon2.
Rainbow Tables: Why Salt is Mandatory
A rainbow table is a precomputed data structure mapping hash values back to plaintexts. For unsalted SHA-256 hashes, a table covering all 8-character passwords can be precomputed once and reused forever. The salt - a random per-user value stored alongside the hash - makes precomputation infeasible by making each hash unique.
HaveIBeenPwned stores 800+ million cracked passwords as SHA-1 hashes (unsalted, as they appeared in real breaches). LinkedIn's 2012 breach leaked 117 million unsalted SHA-1 passwords; crackers recovered 90% within 24 hours using GPU rainbow tables.
Why does a salt defeat rainbow table attacks even if the salt value is stored in the database?
bcrypt: Adaptive Cost
bcrypt (Provos & Mazieres, 1999) is the first password hashing function designed with adaptive cost. The cost parameter (work factor) controls the number of iterations: cost 12 means 2^12 = 4096 iterations. Doubling the cost doubles the cracking time for attackers while hardware gets faster every year.
bcrypt has a critical limitation: it truncates passwords at 72 bytes. A 73-byte and 72-byte password differing only in the 73rd character produce the same hash. Django uses bcrypt as an optional backend; the default is PBKDF2. Auth0 uses bcrypt with cost 10 for most accounts.
What does increasing the bcrypt cost factor from 10 to 12 accomplish?
scrypt: Memory-Hard Protection Against GPUs
scrypt (Colin Percival, 2009) is a memory-hard password hash. It allocates a large amount of RAM during computation, making massive GPU parallelism expensive because GPU memory per core is limited. Used as the proof-of-work in Litecoin and as the key derivation function in many wallets.
scrypt has a complex parameter set (N, r, p) that most developers misconfigure. Argon2 was designed to be simpler and more secure. OpenSSL 3.0 includes scrypt; libsodium exposes it as crypto_pwhash_scryptsalsa208sha256.
Why does scrypt's memory usage limit GPU parallelism?
Argon2: Password Hashing Competition Winner
Argon2 won the Password Hashing Competition (PHC) in 2015. Three variants: Argon2d (data-dependent memory access, fastest, vulnerable to side-channels), Argon2i (data-independent, CUDA-safe), Argon2id (hybrid, PHC-recommended). OWASP recommends Argon2id as the first choice for new systems.
1Password migrated from PBKDF2 to Argon2id in 2023. Bitwarden uses Argon2id with m=64MB, t=3, p=4 by default since 2023. Signal uses a variant for PIN protection on key backups. Python's argon2-cffi library is the recommended implementation.
A higher bcrypt cost factor makes it as secure as Argon2 against GPU attacks
bcrypt is not memory-hard: GPUs can parallelize bcrypt at roughly 180k/sec per RTX 4090; Argon2id with 64MB memory reduces this to hundreds per second due to GPU memory constraints
Memory-hardness, not iteration count, is the key property for GPU resistance. An attacker with 100 GPUs and unlimited CPU time benefits asymmetrically from bcrypt's lack of memory pressure.
Why is Argon2id recommended over Argon2d and Argon2i for most applications?
Key Ideas
- **Salt is mandatory**: random per-user salt defeats rainbow tables. Even a weak algorithm with salt is far better than unsalted SHA-256.
- **bcrypt**: adaptive cost, self-contained salt encoding, 72-byte password truncation caveat. Default for many legacy systems.
- **scrypt**: memory-hard (N, r, p parameters). Complex tuning; prefer Argon2 for new systems.
- **Argon2id**: OWASP first choice. Parameters: m=64MB, t=3, p=4. Combines GPU resistance (memory-hard) with side-channel resistance (data-independent first pass).
Related Topics
Password hashing connects authentication, key derivation, and cryptographic design:
- Key Management (PBKDF2) — PBKDF2 is a KDF usable for password hashing, but lacks memory-hardness. Covered with key management fundamentals.
- Hash Functions — All password hashing schemes build on cryptographic hash primitives. Their security bounds determine maximum protection.
- Authentication and Authorization — Password hashing is the core of credential storage. Incorrect implementation leads to credential theft even from encrypted databases.
Вопросы для размышления
- A system stores bcrypt hashes with cost 10 from 2015. Hardware has improved 8x since then. What is the correct remediation strategy without forcing all users to reset passwords?
- Why does bcrypt's 72-byte truncation matter in practice, and which common password patterns does it affect?
- Argon2id with m=64MB takes 300ms on the login server. The product team says this is too slow. What parameters adjustment preserves security while meeting a 100ms budget?