Hash Functions, MACs, and Password Hashing

A cryptographic hash function $H: \{0,1\}^* \to \{0,1\}^n$ must satisfy three distinct properties — each strictly weaker than the next:

1. Preimage resistance (one-wayness): given $h$, it is infeasible to find any $m$ such that $H(m) = h$. Cost: $O(2^n)$.
2. Second-preimage resistance: given $m$, it is infeasible to find $m' \ne m$ such that $H(m') = H(m)$. Cost: $O(2^n)$.
3. Collision resistance: it is infeasible to find any pair $(m, m')$ with $m \ne m'$ and $H(m) = H(m')$. Cost: $O(2^{n/2})$ by birthday paradox.

Collision resistance is hardest to achieve and hardest to prove. MD5 and SHA-1 are collision-broken — real collisions are known and constructible in minutes. Never use them for integrity or signatures; they remain acceptable only for non-security checksums.

SHA-256 and SHA-512 (SHA-2 family, NIST 2001) are the workhorses. SHA-256 is a Merkle-Damgård construction with Davies-Meyer compression; SHA-512 is the same with 64-bit words — faster on 64-bit CPUs. No known practical attacks on SHA-2 despite 20+ years of scrutiny.

SHA-3 (Keccak, NIST 2015) uses a fundamentally different sponge construction — no Merkle-Damgård, no length-extension vulnerability. SHA3-256 and SHA3-512 are the fixed-output variants; SHAKE128/SHAKE256 are extendable-output functions (XOFs) useful as PRNGs or KDFs.

Merkle-Damgård hashes (SHA-256, SHA-512, MD5) retain the internal state after processing a message. That state is the hash output. An attacker who knows $H(m)$ can compute $H(m \;\|\; \text{padding} \;\|\; m')$ for any $m'$ without knowing $m$.

Consequence: SHA256(secret_key || message) is not a MAC. An attacker who intercepts the tag can extend the message and forge a valid tag. This broke early API authentication schemes (e.g., Flickr, Amazon S3 v1) in practice.

# BROKEN -- do not use
tag = hashlib.sha256(secret_key + message).digest()

# CORRECT -- HMAC
import hmac, hashlib
tag = hmac.new(secret_key, message, hashlib.sha256).digest()

HMAC wraps the hash in a two-layer construction that eliminates the length-extension attack regardless of whether the underlying hash is Merkle-Damgård.

HMAC (RFC 2104) is defined as:

$\text{HMAC}_K(m) = H\bigl((K \oplus \text{opad}) \;\|\; H((K \oplus \text{ipad}) \;\|\; m)\bigr)$

where ipad = 0x36 repeated and opad = 0x5C repeated. The outer hash hides the inner hash output completely — an attacker cannot extend it.

Security of HMAC rests on the PRF security of the compression function, not on collision resistance. This means HMAC-SHA1 is still secure as a MAC even though SHA-1 is collision-broken — because the attack path is different. That said, prefer HMAC-SHA256 in new code.

Always use a constant-time comparison when verifying tags — hmac.compare_digest() in Python, not ==. Timing attacks on tag comparison have leaked secrets in real APIs (e.g., GitHub webhooks pre-2014).

A Key Derivation Function stretches or diversifies key material. Two distinct use cases:

From high-entropy secrets (e.g., a shared ECDH secret → multiple symmetric keys): use HKDF (RFC 5869). It is HMAC applied twice — first to "extract" entropy into a pseudorandom key, then to "expand" it into as many bytes as needed.

from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes

kdf = HKDF(algorithm=hashes.SHA256(), length=32,
           salt=None, info=b"aes-256-gcm key")
key = kdf.derive(shared_secret)  # 32-byte AES key

From low-entropy secrets (passwords): use bcrypt, scrypt, or Argon2 — never HKDF. HKDF is fast by design; an attacker can run billions of HKDF calls per second on a GPU. Password KDFs are deliberately slow and memory-hard.

Passwords have ~20-40 bits of entropy. An attacker with a leaked database can crack unsalted SHA-256 hashes at 10–50 billion guesses/second on a modern GPU. Password KDFs fight back with intentional slowness and memory hardness:

• bcrypt (1999): cost factor doubles iteration count; cost 12 = ~250 ms on modern HW. No parallelism defense; vulnerable to FPGA/ASIC acceleration. Still widely deployed.
• scrypt (2009): adds a large memory requirement (N, r, p parameters). Harder to parallelize on custom hardware.
• Argon2 (Password Hashing Competition winner, 2015): three variants — Argon2d (GPU-resistant), Argon2i (side-channel-resistant), Argon2id (both). OWASP recommends Argon2id with m=19456 KiB, t=2, p=1 as a 2024 baseline.

import argon2
ph = argon2.PasswordHasher(time_cost=2, memory_cost=19456, parallelism=1)
hash_str = ph.hash("user_password")  # includes salt
ph.verify(hash_str, "user_password")  # True or raises

Salt: a random per-user value stored alongside the hash. It ensures two users with the same password get different hashes, defeating rainbow tables and enabling per-user cracking cost. All serious password KDFs (bcrypt, Argon2) generate and embed salts automatically — never implement salting manually.

Pepper: a secret value added to the password before hashing, stored separately from the database (e.g., in an HSM or env var). If the database leaks but the pepper does not, offline cracking is impossible. The downside: losing the pepper means losing all passwords.

Use salt always; pepper is a defense-in-depth addition, not a replacement.

Developers routinely reach for the wrong primitive. The decision depends on what you have and what you need:

Using a fast hash (SHA-256) for password storage is a critical vulnerability. Using Argon2 for an API MAC is wasteful and adds latency. Using HMAC where you need a key from a password will silently give weak security. Match the primitive to the problem.

Hashes unlock a suite of powerful protocols beyond authentication:

• Commitment schemes: Alice publishes $H(\text{secret})$, later reveals the secret. The preimage resistance guarantees she cannot change the secret after committing; the binding is computational, not information-theoretic.
• Merkle trees: Bitcoin and Git store large sets by hashing pairs of children recursively. A single root hash authenticates the whole set; membership proofs are $O(\log n)$ hashes.
• Hash-based signatures (XMSS, SPHINCS+): post-quantum signature schemes that rely only on hash security, not discrete log or factoring. NIST has standardized SPHINCS+ (FIPS 205) — relevant as RSA/ECC face future quantum threats.
• HMAC as a PRNG: HMAC-DRBG (NIST SP 800-90A) is a deterministic random bit generator built on HMAC. It is the default DRBG inside many TLS implementations.