Cryptography II: hashing, digital signatures, public key infrastructure and key management

Encryption keeps data secret, but most of what keeps the internet trustworthy is about integrity and identity: knowing that a software update has not been altered, that a website really belongs to your bank, that a contract was signed by the person it claims. This lesson covers the tools for those jobs: hash functions, message authentication codes, digital signatures, the public key infrastructure that binds keys to identities, and the key management practices that keep the whole system working. They complete sub-domain 3.6.

Hash functions

A cryptographic hash function takes input of any length and produces a fixed-length output called a digest, hash or fingerprint. A good hash function has three security properties. Preimage resistance means that given a digest, it is infeasible to find any input that produces it, so hashes are one-way. Second preimage resistance means that given one input, it is infeasible to find a different input with the same digest. Collision resistance means it is infeasible to find any two different inputs with the same digest. A hash also shows the avalanche effect: changing one bit of the input changes about half the bits of the output. Hashing provides integrity, not confidentiality, and uses no key.

MD5, with a 128-bit digest, and SHA-1, with 160 bits, are both broken for collision resistance: practical MD5 collisions were demonstrated in 2004, and Google and CWI Amsterdam published the first practical SHA-1 collision, called SHAttered, in 2017. They must not be used for signatures or certificates. The SHA-2 family, including SHA-256 and SHA-512, is the current workhorse, and SHA-3, standardized in FIPS 202 in 2015 and based on the Keccak design, offers an alternative with a different internal structure. Collision resistance is limited by the birthday paradox: in a group of only 23 people there is about a 50 percent chance two share a birthday, and similarly an attacker needs only about 2 to the power n over 2 attempts to find a collision in an n-bit hash. That is why a 256-bit hash gives about 128 bits of collision resistance.

import math
# Birthday paradox: chance that at least two of k people share a birthday
k = 23
p_unique = math.prod((365 - i) / 365 for i in range(k))
print(f"{k} people: {1 - p_unique:.1%} chance of a shared birthday")
# Work to find a hash collision is about 2**(n/2)
for n in (128, 160, 256):
    print(f"{n}-bit hash: collision work about 2^{n // 2}")

23 people: 50.7% chance of a shared birthday
128-bit hash: collision work about 2^64
160-bit hash: collision work about 2^80
256-bit hash: collision work about 2^128

Passwords need special treatment. Storing plain hashes is unsafe, because attackers can use precomputed tables of common passwords, called rainbow tables, or simply guess billions of passwords per second on graphics processors. Password storage should add a unique random salt to each password, so identical passwords produce different hashes and precomputed tables are useless, and should use deliberately slow, memory-hard functions such as Argon2, scrypt, bcrypt or PBKDF2 with a high iteration count. A pepper, a secret value kept separately from the database, can add further protection.

Message authentication codes

A hash alone proves nothing about who created a message, because anyone can compute it. A message authentication code, or MAC, combines the message with a secret key, so only someone holding the key can produce or verify it. HMAC, defined in RFC 2104 and FIPS 198, builds a MAC from a hash function such as SHA-256 and is widely used in protocols and application programming interfaces. Authenticated encryption modes such as GCM build a MAC into encryption. MACs provide integrity and authenticity between parties who share a key, but not nonrepudiation, because either party could have created the MAC.

Digital signatures

A digital signature provides integrity, authentication of the signer and nonrepudiation. To sign, the sender hashes the message and transforms the digest with their private key. To verify, the recipient hashes the received message, uses the sender's public key to recover or check the signed digest, and compares the two. If they match, the message has not changed and only the holder of the private key could have signed it. Signing does not encrypt the message; if confidentiality is also needed, the message is encrypted separately with the recipient's public key or a session key. Signature algorithms include RSA signatures, the Digital Signature Algorithm, ECDSA and EdDSA, described in FIPS 186-5, and the new post-quantum ML-DSA and SLH-DSA covered in lesson 10.

Nonrepudiation in practice depends on more than mathematics. If a private key is stored on a shared laptop or its password is known to several people, a signer can credibly claim someone else used it. Strong nonrepudiation needs keys held in hardware that only the signer controls, such as a smart card or a security key with a PIN, plus trustworthy timestamps from a time-stamping authority that prove when a signature was made.

Public key infrastructure

Public keys are only useful if you know whose they are. A public key infrastructure, PKI, binds public keys to identities through digital certificates. A certificate, in the X.509 format, contains the subject's name, public key, validity period, serial number, issuer, permitted key uses and extensions, all signed by a certificate authority, or CA. A registration authority checks the identity of applicants before the CA issues certificates. Trust flows down a chain: a root CA, whose self-signed certificate is installed in operating systems and browsers as a trust anchor, signs certificates for intermediate CAs, which in turn issue end-entity certificates to websites, people and devices. Root keys are kept offline in hardware security modules and used rarely, so that day-to-day issuing happens from intermediates whose compromise is easier to contain.

Certificates sometimes need to be revoked before they expire, for example when a private key is lost. Certificate revocation lists, CRLs, are signed lists of revoked serial numbers published by the CA. The Online Certificate Status Protocol, OCSP, lets a client ask about one certificate in real time, and OCSP stapling lets the server attach a recent signed status to the TLS handshake, which is faster and more private. Because revocation checking has always been unreliable, the industry is moving toward short certificate lifetimes instead. In April 2025 the CA/Browser Forum, which sets rules for publicly trusted TLS certificates, approved a phased reduction of the maximum lifetime: 200 days from 15 March 2026, 100 days from 15 March 2027 and 47 days from 15 March 2029. Automation through the ACME protocol, popularized by Let's Encrypt, is essential at those lifetimes.

Other PKI controls guard against rogue certificates. Certificate Transparency requires publicly trusted CAs to log every TLS certificate in public, append-only logs, so domain owners can spot certificates issued for their names without permission. Certification authority authorization, CAA, DNS records let a domain owner specify which CAs may issue for it. Certificate pinning, where an application accepts only specific keys, can block rogue certificates but makes key changes risky and is now used sparingly. Organizations also run private PKIs for internal servers, Wi-Fi, VPNs, smart card logon and device identity.

Governments run their own PKIs. The US Federal PKI links agency certificate authorities through a common policy framework, and federal employees use Personal Identity Verification smart cards, defined in FIPS 201, whose certificates support logon, signing and encryption. NIST guidance on algorithms and key lengths appears in SP 800-57 and SP 800-131A.

Key management

Key management is where most real cryptographic systems succeed or fail. NIST SP 800-57 describes the key life cycle: generation, using a strong random source, ideally inside a hardware module; registration and distribution, protecting keys in transit and binding them to owners; storage, in HSMs, TPMs or managed key services rather than in code or configuration files; use, restricted to authorized purposes; rotation, replacing keys on a schedule or after suspected compromise; backup and recovery, so encrypted data is not lost; archive; and destruction, securely erasing keys when they are no longer needed, which also makes data encrypted only under them unreadable, a technique called cryptographic erasure.

Several controls protect the most important keys. Split knowledge divides a key into parts so that no single person knows the whole key; dual control requires two or more people to act together, for example to load a master key into an HSM. M of n control, using schemes such as Shamir's secret sharing, lets any 3 of 5 custodians reconstruct a key, so the loss of one or two custodians does not lose the key. Key escrow places a copy of keys with a trusted third party so they can be recovered, for example under legal order; it supports recovery but creates a high-value target and has been controversial when proposed for government access. Keys should have a single purpose, so that the same key is not used for both encryption and signing, and systems should log every use of sensitive keys.

Thinking like a manager

When a question asks how to prove who sent a message, choose digital signatures; when it asks how two systems sharing a secret can check integrity, choose a MAC; when it asks how to store passwords, choose salted, slow hashing, never encryption. When a CA is compromised, the response is to revoke and replace affected certificates and keys and investigate the trust chain. And for critical keys, think dual control, split knowledge and HSMs.