Cryptographic primitives and their contracts

Prerequisites: Binary representations and probability.

Learning objectives

• Distinguish hashes, MACs, signatures, and encryption.
• Explain nonce requirements.
• Recognize password-storage requirements.

Name the property before the primitive

A cryptographic hash maps an arbitrary-length message to a fixed-size digest. Collision resistance means it should be computationally infeasible to find two distinct messages with the same digest. Preimage resistance concerns finding an input for a given digest. These are different properties. A plain hash does not authenticate a message: an attacker who changes the message can usually compute its new hash too.

A message authentication code uses a shared secret key to produce a tag. A verifier with that key can check integrity and authenticity relative to the key holders. A digital signature uses a private signing key and a public verification key. Anyone with the public key can verify, but verification still depends on knowing whose key it is and what statement was signed.

Encryption protects confidentiality under a specified threat model. It does not automatically provide integrity. Prefer established authenticated-encryption constructions through maintained libraries, with the algorithm's nonce and key requirements respected.

Trace the nonce problem

In a simplified stream construction, ciphertext C is plaintext P XOR keystream S. If two messages reuse the same S, then C₁ XOR C₂ equals P₁ XOR P₂ because S XOR S is zero. The cancellation exposes a relation between plaintexts. Known structure in one message can reveal information about the other. This calculation illustrates why reusing a key and nonce in constructions that require uniqueness can be catastrophic.

A nonce often needs uniqueness rather than secrecy. The exact requirement belongs to the chosen algorithm. Random generation is not automatically safe at arbitrary scale, and a counter that resets after a crash may repeat. Key rotation and persistent allocation need a design.

Passwords are not uniformly random keys

Human-chosen passwords are often guessable. A fast general-purpose hash lets an attacker test many guesses quickly after a credential database leak. Use a password-hashing scheme designed to impose computational and memory cost, with a separate salt per password and parameters chosen for the deployment. A salt prevents identical passwords from having identical stored representations and frustrates precomputed tables; it does not make weak passwords unguessable.

Do not invent a cryptographic protocol by assembling familiar primitives. Encoding ambiguity, missing context, replay, and key confusion can break an otherwise sound algorithm. Sign or authenticate an unambiguous representation that binds the purpose, version, and relevant identities. Use test vectors and reviewed protocol libraries, and keep the claimed guarantee narrower than the whole application's security.

Practice problem

A download page publishes a file and its SHA-256 digest from the same compromised server. Explain why this does not establish authenticity. Then compare a MAC and a digital signature for distributing software updates to many clients.

Worked solution

An attacker controlling both file and displayed digest can replace both consistently. The digest detects accidental corruption only when its expected value comes through a trusted channel or authenticated statement. A MAC requires verifiers to share a secret; a client holding that secret may also be able to forge tags. A signature allows clients to verify with a public key while the publisher keeps the signing key private. The client must trust the correct public key, verify the signed metadata and artifact, and reject inappropriate versions or contexts. Key compromise and rollback protection remain separate concerns.

Check your understanding

What does a plain unkeyed hash establish by itself?

• The sender’s identity.
• Confidentiality.
• A deterministic digest of the bytes, not their authorized origin.
• Protection against every replay.

Explanation

An attacker can hash modified bytes unless the expected digest is authenticated.

Why is stream-keystream reuse dangerous?

• XOR becomes slower.
• The keys become public automatically.
• It changes the message length.
• XORing ciphertexts cancels the repeated keystream.

Explanation

The resulting relation between plaintexts can reveal information.

Primary reading

• Computer Security textbook: UC Berkeley CS 161

Open the study and save your work →