Hash functions, message authentication codes and secure password storage

A cryptographic hash function turns any input, from a single byte to a whole disk image, into a short fixed-size fingerprint. Hashes are everywhere in security: they identify software releases and container images, they anchor digital signatures and certificates, they build message authentication codes, they make Git commits tamper-evident, and, used carefully, they protect stored passwords. This lesson explains what a good hash guarantees, how a message authentication code adds a secret key to give integrity and authenticity, and how to store passwords so that a database leak does as little damage as possible.

The lesson takes the defender's point of view throughout. Password storage is covered as a design problem: which algorithm, which parameters, what to store, how to verify and how to migrate old hashes. Lesson 3 covered keys and authenticated encryption; CISSP-114 covered authentication policy for managers, including multifactor authentication and passkeys. Here we look at the mechanisms underneath.

What a cryptographic hash function guarantees

A hash function \( H \) maps a message of any length to a digest of fixed length, 256 bits for SHA-256. To be useful for security it must have three properties. Preimage resistance: given a digest \( h \), it is infeasible to find any message \( m \) with \( H(m) = h \). Second-preimage resistance: given a message \( m_1 \), it is infeasible to find a different \( m_2 \) with the same digest. Collision resistance: it is infeasible to find any two different messages with the same digest. Collision resistance is the strongest and the hardest to keep; MD5 lost it in 2004 and SHA-1 in 2017, when researchers produced two different PDF files with the same SHA-1 digest. Both remain fine as non-security checksums but must not be used where an attacker chooses the inputs.

A good hash also behaves like a random function: a one-character change to the input changes about half of the output bits, and nothing about the input can be read from the output. The digest length is fixed no matter how large the input is.

import hashlib
msgs = [b"Pay Ana $100", b"Pay Ana $900", b"Pay Ana $100"]
for m in msgs:
    print(f"{m.decode():<14} sha256 = {hashlib.sha256(m).hexdigest()[:32]}...")
a, b = hashlib.sha256(msgs[0]).digest(), hashlib.sha256(msgs[1]).digest()
diff = sum(bin(x ^ y).count("1") for x, y in zip(a, b))
print(f"one character changed -> {diff} of 256 digest bits differ")
print("same input, same digest:", hashlib.sha256(msgs[0]).digest() == hashlib.sha256(msgs[2]).digest())
big = b"x" * 10_000_000
print("10 MB input still gives", len(hashlib.sha256(big).digest()), "bytes of digest")

Pay Ana $100   sha256 = f6847ce6f1eb838e518383d4468b4122...
Pay Ana $900   sha256 = 4a25b4065579136cd436c042dbd81070...
Pay Ana $100   sha256 = f6847ce6f1eb838e518383d4468b4122...
one character changed -> 125 of 256 digest bits differ
same input, same digest: True
10 MB input still gives 32 bytes of digest

The birthday bound

Collision resistance is limited by the birthday paradox. In a room of only 23 people, there is a better than even chance that two share a birthday, because the number of pairs grows with the square of the number of people. In the same way, a generic collision search on an \( n \)-bit digest needs only about \( 2^{n/2} \) evaluations, not \( 2^n \). That is why a 128-bit digest gives only 64 bits of collision security, too little today, and why 256-bit digests are the norm.

import math
# Probability that at least two of k random n-bit values collide: about 1 - exp(-k^2 / 2^(n+1))
def p_collision(k, bits):
    return -math.expm1(-k * k / 2 ** (bits + 1))
for bits in (32, 64, 128, 256):
    k50 = math.sqrt(2 * math.log(2)) * 2 ** (bits / 2)
    print(f"{bits:>3}-bit digest: 50% collision chance after about 2^{math.log2(k50):.1f} values")
print()
for k in (10_000, 77_000, 1_000_000):
    print(f"{k:>9,} values in a 32-bit space: P(collision) = {p_collision(k, 32):.3f}")

 32-bit digest: 50% collision chance after about 2^16.2 values
 64-bit digest: 50% collision chance after about 2^32.2 values
128-bit digest: 50% collision chance after about 2^64.2 values
256-bit digest: 50% collision chance after about 2^128.2 values

   10,000 values in a 32-bit space: P(collision) = 0.012
   77,000 values in a 32-bit space: P(collision) = 0.499
1,000,000 values in a 32-bit space: P(collision) = 1.000

The same arithmetic matters outside hashing. Random identifiers, nonces and session tokens must be long enough that collisions are practically impossible across every value a system will ever generate. A 32-bit random ID is almost certain to collide somewhere among a million records, while a 128-bit random token from the secrets module will not collide in the lifetime of the universe.

Message authentication codes

A hash alone does not prove who produced a message: anyone can recompute it after changing the data. A message authentication code (MAC) adds a secret key shared by sender and receiver. Only someone with the key can produce a valid tag, so a correct tag shows that the message came from a key holder and was not changed. HMAC, standardized in RFC 2104 and FIPS 198-1, builds a MAC from any hash function by hashing the key and message twice with two derived pads:

The nested structure matters. The obvious shortcut, hashing the key followed by the message, is unsafe with SHA-256 and other Merkle–Damgård hashes because of a property called length extension: from the digest of a message, anyone can compute the digest of that message with extra data appended, without knowing the key. HMAC's construction is immune, as are SHA-3 and BLAKE2 in keyed mode. The practical rule is simple: use HMAC from your standard library, never a home-made key-plus-message hash.

import hmac, hashlib
key = b"demo-only shared secret; load real keys from a secrets manager"
def tag(msg: bytes) -> str:
    return hmac.new(key, msg, hashlib.sha256).hexdigest()
def verify(msg: bytes, t: str) -> bool:
    return hmac.compare_digest(tag(msg), t)        # constant-time comparison
order = b"order=1042&amount=59.00&currency=CAD"
t = tag(order)
print("tag     :", t[:40] + "...")
print("genuine :", verify(order, t))
changed = order.replace(b"59.00", b"5.90")
print("changed :", verify(changed, t))
print("wrong key gives a different tag:", hmac.new(b"other key", order, hashlib.sha256).hexdigest() != t)

tag     : 5f63d4b45b9415a509df71ddc755f7494f2d3fae...
genuine : True
changed : False
wrong key gives a different tag: True

Verification uses hmac.compare_digest rather than ==. An ordinary comparison stops at the first differing byte, so in principle the time it takes reveals how many leading bytes of a guess were correct. A constant-time comparison always examines every byte. The same function belongs anywhere a secret value is compared: API keys, password reset tokens, CSRF tokens and webhook signatures.

Where hashes and MACs are used

Why password storage is a special problem

Passwords are low-entropy secrets chosen by people. Even with good habits, many users pick passwords that are far easier to guess than a 128-bit key. If a site stores passwords in plain text, a single database leak exposes every account, and because people reuse passwords, accounts on other sites too. Encrypting passwords is also a poor answer, because whoever obtains the key, including an insider or an attacker with access to the server, can decrypt them all. The standard answer is to store a one-way verifier: a value computed from the password from which the password cannot feasibly be recovered, but which lets the server check a login attempt.

An ordinary fast hash such as SHA-256 is the wrong tool for this. It was designed to be fast, so an attacker holding a leaked table can test enormous numbers of candidate passwords per second on graphics processors. Defenders therefore use functions that are deliberately slow and, ideally, memory-hard, so that each guess costs real time and memory. Three further measures complete the design. A unique random salt per user, stored alongside the hash, means two users with the same password get different stored values and that precomputed tables are useless. A pepper, an additional secret kept outside the database (for example in a hardware security module or a secrets manager), means a database leak alone is not enough. And the cost parameters are stored with each hash so they can be raised over time.

The example below stores and verifies passwords with scrypt from the standard library. The stored string records the algorithm, the cost parameters, the salt and the derived key, a self-describing format similar to the one Argon2 and bcrypt libraries use. Fixed salts appear only so the printed output is reproducible.

import hashlib, hmac, base64
# Parameters for scrypt: N (cost, power of 2), r (block size), p (parallelism)
N, R, P = 2**14, 8, 1
def hash_password(password: str, salt: bytes) -> str:
    dk = hashlib.scrypt(password.encode(), salt=salt, n=N, r=R, p=P, dklen=32)
    return "scrypt$%d$%d$%d$%s$%s" % (N, R, P, base64.b64encode(salt).decode(), base64.b64encode(dk).decode())
def verify_password(password: str, stored: str) -> bool:
    _, n, r, p, s, d = stored.split("$")
    dk = hashlib.scrypt(password.encode(), salt=base64.b64decode(s), n=int(n), r=int(r), p=int(p), dklen=32)
    return hmac.compare_digest(dk, base64.b64decode(d))
# Fixed salts so the printed output is reproducible; real code uses os.urandom(16) per user.
alice = hash_password("correct horse battery staple", b"salt-for-alice!!")
bob   = hash_password("correct horse battery staple", b"salt-for-bob-123")
print("alice:", alice[:60] + "...")
print("bob  :", bob[:60] + "...")
print("same password, different stored values:", alice != bob)
print("verify correct  :", verify_password("correct horse battery staple", alice))
print("verify incorrect:", verify_password("correct horse battery stapler", alice))
print(f"memory per hash: 128 * r * N = {128 * R * N / 2**20:.0f} MiB")

alice: scrypt$16384$8$1$c2FsdC1mb3ItYWxpY2UhIQ==$+YSqXXI5OlZ801rFdX...
bob  : scrypt$16384$8$1$c2FsdC1mb3ItYm9iLTEyMw==$lO5er5SPzDJuTKa5wA...
same password, different stored values: True
verify correct  : True
verify incorrect: False
memory per hash: 128 * r * N = 16 MiB

The demonstration uses \( N = 2^{14} \) so the example runs quickly; production settings use a larger \( N \) such as \( 2^{17} \), which needs 128 MiB per hash. Tune parameters so that one verification takes roughly a quarter to half a second on your servers, then protect the login endpoint with rate limiting so that this cost cannot be turned into a denial of service.

Rehashing and migration

Because each stored hash records its own parameters, a system can raise its cost over time without forcing everyone to reset. After a successful login, when the plaintext password is briefly available, the server checks whether the stored hash uses old parameters or an old algorithm and, if so, rehashes with the current settings. For a legacy database of fast hashes, a common transitional technique is to wrap them: compute the new slow hash over the old hash for every user immediately, then replace the wrapped value with a direct hash at each user's next login. That way no weak hash stays exposed while waiting for users to return.

Password policy that helps rather than hinders

Password rules have changed. NIST SP 800-63B-4, finalized in August 2025, tells verifiers to require at least 15 characters when a password is the only authenticator and at least 8 when it is part of multifactor authentication, to accept at least 64 characters and all printable and Unicode characters, and to screen new passwords against lists of common, expected or breached values. It also tells verifiers not to impose composition rules such as one digit and one symbol, not to force periodic changes unless there is evidence of compromise, and not to use hints or knowledge-based questions. Long passphrases are easier to remember and harder to guess than short complex strings.

# A password checker that follows NIST SP 800-63B-4 (2025) rather than old composition rules
BLOCKLIST = {"password", "password123", "qwerty123", "letmein", "iloveyou", "welcome1",
             "hsmuniversity", "123456789012345"}
def check(pw: str, multifactor: bool, context=("ana", "lima", "hsm")) -> list[str]:
    problems = []
    minimum = 8 if multifactor else 15
    if len(pw) < minimum:
        problems.append(f"shorter than {minimum} characters")
    if len(pw) > 64:
        problems.append("longer than our 64-character limit (allow at least 64)")
    low = pw.lower()
    if low in BLOCKLIST:
        problems.append("appears on the blocklist of common or breached passwords")
    if any(word in low for word in context):
        problems.append("contains the user's name or the service name")
    return problems or ["acceptable"]
tests = [("Summer2026!", False), ("Summer2026!", True), ("password123", True),
         ("violet canoe under the bridge", False), ("ana-lima-2026-xyz", False)]
for pw, mfa in tests:
    print(f"{pw!r:<32} mfa={str(mfa):<5} -> {'; '.join(check(pw, mfa))}")

'Summer2026!'                    mfa=False -> shorter than 15 characters
'Summer2026!'                    mfa=True  -> acceptable
'password123'                    mfa=True  -> appears on the blocklist of common or breached passwords
'violet canoe under the bridge'  mfa=False -> acceptable
'ana-lima-2026-xyz'              mfa=False -> contains the user's name or the service name

Screening against breached passwords raises a privacy question: how can a service check a password against a breach database without sending the password, or even its full hash, to a third party? The widely used answer is a k-anonymity range query. The client hashes the password, sends only the first five hexadecimal characters of the hash, receives every breached-hash suffix that shares that prefix, and compares locally. The service never learns which password was checked. The toy below shows the idea with a local list instead of a network service.

import hashlib
# Checking a password against a breach list without revealing it (the k-anonymity range idea).
# A local toy "service" stands in for a real breach-list API; no network call is made.
breached = ["123456", "password", "qwerty", "iloveyou", "dragon2020", "monkey", "letmein"]
service = {}
for p in breached:
    h = hashlib.sha1(p.encode()).hexdigest().upper()
    service.setdefault(h[:5], []).append(h[5:])
def range_query(prefix):                 # the service only ever sees 5 hex characters
    return service.get(prefix, [])
def is_breached(candidate: str) -> bool:
    h = hashlib.sha1(candidate.encode()).hexdigest().upper()
    return h[5:] in range_query(h[:5])    # the full hash is compared locally
for pw in ("letmein", "violet canoe under the bridge"):
    print(f"{pw!r:<32} prefix sent: {hashlib.sha1(pw.encode()).hexdigest().upper()[:5]}  breached: {is_breached(pw)}")
print("each prefix covers about 1 in", 16**5, "of all possible hashes")

'letmein'                        prefix sent: B7A87  breached: True
'violet canoe under the bridge'  prefix sent: 1C67F  breached: False
each prefix covers about 1 in 1048576 of all possible hashes

Canadian guidance points the same way. The Canadian Centre for Cyber Security recommends passphrases of at least four words or 15 characters, multifactor authentication wherever possible, and password managers, and it advises against forced periodic changes. Under PIPEDA and provincial laws such as Quebec's Law 25, a breach of security safeguards that creates a real risk of significant harm must be reported to the regulator and to affected people, so a leaked table of weak hashes is a legal problem as well as a technical one.

Worked examples