Unit 6: Cryptographic Protocols

I. Orientation: From Confidentiality to Integrity and Authenticity

Classical cryptography (pre-1976) protects secrecy; modern cryptographic protocols also guarantee that a message is unaltered (integrity), from whom it claims (authenticity), and undeniable (non-repudiation). This unit builds these guarantees from one-way functions and public-key primitives introduced by Diffie–Hellman (1976) and formalised through the RSA and discrete-log settings.

• One-way function: a function f easy to compute but computationally infeasible to invert — y = f(x) cheap, recovering x from y hard. The bedrock of every construction below.
• Trapdoor: a secret enabling efficient inversion (RSA private exponent d); underpins signatures.
• Adversary model: attacker sees public data and many message/tag pairs, has bounded computing power, and aims to forge or find collisions.
• Security parameter n: bit-length governing work factor; "infeasible" means effort ≈ 2^n or 2^{n/2}.
• Distinction to keep straight: integrity detects accidental or malicious change; authentication additionally binds the message to a key holder.

II. Hash Functions and Data Integrity

Compressing arbitrary data to a fixed fingerprint.

A cryptographic hash function H maps a message of any length to a fixed n-bit digest, acting as a message's fingerprint.

A. Definition and Structure

• Signature: H : {0,1}* → {0,1}^n, e.g. SHA-256 gives n = 256.
• Determinism: identical input always yields identical digest; one bit changed flips ≈ half the output bits (avalanche effect).
• Merkle–Damgård construction: message split into blocks M_1…M_k; a compression function f iterates a chaining value.

h_0 = IV
h_i = f(h_{i-1}, M_i)   for i = 1..k
H(M) = h_k

• IV — fixed initialisation vector; f — fixed-input-size compressor; padding appends the message length (Merkle–Damgård strengthening).

B. Hash Functions and Data Integrity

• Integrity check: store or transmit H(M) over a trusted channel; recompute on receipt and compare. Any change in M yields a mismatched digest.
• Concrete use: software downloads publish a SHA-256 digest; the user rehashes the file to confirm no corruption or tampering in transit.
• Limitation without a key: an attacker who can alter M can also recompute and replace H(M). Pure hashing detects accidental error and tampering only when the digest travels by a channel the attacker cannot touch — motivating keyed constructions (Section IV).

III. Security of Hash Functions

The three properties that make a hash cryptographic.

Security is defined by the infeasibility of three inversion/collision problems, ordered by strength.

A. The Three Security Properties

• Preimage resistance (one-wayness): given digest y, infeasible to find any x with H(x) = y. Work factor ≈ 2^n.
• Second-preimage resistance: given input x_1, infeasible to find x_2 ≠ x_1 with H(x_2) = H(x_1). Work factor ≈ 2^n.
• Collision resistance: infeasible to find any pair x_1 ≠ x_2 with H(x_1) = H(x_2). Strongest requirement.
  • Implication chain: collision resistance ⇒ second-preimage resistance; neither strictly implies preimage resistance in general.

B. Security of Hash Functions

• Birthday bound: collisions are found in ≈ 2^{n/2} trials, not 2^n, because any pair among many can collide.
  • Numeric anchor: for a 128-bit digest, collisions cost ≈ 2^64 — feasible for well-resourced attackers, so 256-bit outputs are standard today.
• Birthday reasoning: among 2^{n/2} random digests the expected number of colliding pairs exceeds one, mirroring the classic "23 people share a birthday" result.
• Broken examples: MD5 (128-bit) and SHA-1 (160-bit) have practical collision attacks and are deprecated for signatures; SHA-2 and SHA-3 remain sound.
• Length-extension weakness: Merkle–Damgård hashes allow computing H(M ‖ pad ‖ M') from H(M) without knowing M, breaking naive keyed use H(k ‖ M) — SHA-3's sponge design and HMAC avoid this.

IV. Message Authentication Codes

Keyed integrity — proving a message came from a shared-key holder.

A MAC binds a message to a secret key so that only key-holders can generate or verify the tag, giving integrity and authenticity in the symmetric setting.

A. Definition and Operation

• Algorithms: tag = MAC(k, M); verifier recomputes and checks equality using the same secret k.
• Symmetric key: sender and receiver share k in advance; a third party cannot forge a valid tag without k.
• Security goal — unforgeability: even after seeing many (M_i, tag_i) pairs, an attacker cannot produce a valid tag on a new message.

B. Message Authentication Codes

• HMAC construction: builds a MAC from any hash H while defeating length-extension.

HMAC(k, M) = H( (k ⊕ opad) ‖ H( (k ⊕ ipad) ‖ M ) )

• ipad = 0x36 repeated, opad = 0x5c repeated (block-length); ⊕ XOR; ‖ concatenation. Nested hashing hides the inner chaining value.
• CBC-MAC alternative: encrypts the message under a block cipher in CBC mode, using the last ciphertext block as the tag; secure only for fixed-length messages (CMAC fixes this).
• Verification discipline: compare tags in constant time to avoid timing side-channels leaking correct prefixes.
• What a MAC cannot do — non-repudiation: because the key is shared, either party could have produced the tag, so a MAC cannot prove authorship to a third party. That gap is filled by signatures.

V. Digital Signatures

Asymmetric authentication with public verifiability.

A digital signature uses a private key to sign and the matching public key to verify, so anyone can check authenticity while only the key owner can sign.

A. Principle and General Scheme

• Key pair: private signing key sk, public verification key pk.
• Three algorithms:
  • KeyGen → (sk, pk)
  • σ = Sign(sk, M)
  • Verify(pk, M, σ) → {accept, reject}
• Hash-then-sign: sign the digest H(M), not M, for efficiency and to handle arbitrary length — making signature security depend on hash collision resistance.

B. Digital Signatures

1. RSA signatures (trapdoor-based): signing is decryption with the private exponent.

σ = H(M)^d mod N        (sign)
H(M) =? σ^e mod N       (verify)

• N — RSA modulus; d — private exponent; e — public exponent. Security rests on the difficulty of factoring N. Practical schemes pad via RSA-PSS.

2. ElGamal / DSA signatures (discrete-log-based): produce a randomised two-part signature.
   • Contrast with RSA: DSA signatures are non-deterministic — each uses a fresh random nonce k; RSA (textbook) is deterministic. A repeated or predictable k in DSA/ECDSA leaks sk, so nonce quality is critical.
   • ECDSA: the elliptic-curve variant giving equivalent security with far shorter keys (256-bit ECDSA ≈ 3072-bit RSA).

• Non-repudiation achieved: because only the holder of sk can produce a signature Verify accepts, the signer cannot later deny it — the property a MAC lacks.

VI. Security Requirements for Signature Schemes

What "secure" formally demands of a signature.

Signature security is defined by the strongest forgery an adversary cannot achieve under the strongest attack it is allowed.

A. Attack Models and Forgery Goals

• Attack models (increasing power):
  • Key-only attack: adversary has only pk.
  • Known-message attack: adversary sees signatures on messages it did not choose.
  • Chosen-message attack (CMA): adversary obtains signatures on messages it selects — the strongest, and the standard benchmark.
• Forgery goals (decreasing severity):
  • Total break: recover sk.
  • Universal forgery: sign any message.
  • Existential forgery: produce one valid (M, σ) on some new message.

B. Security Requirements for Signature Schemes

• The gold standard — EUF-CMA: Existential Unforgeability under Chosen-Message Attack. Even after adaptively requesting signatures on chosen messages, the adversary cannot output a valid signature on any new message.
• Correctness: honestly generated signatures always verify — Verify(pk, M, Sign(sk, M)) = accept.
• Reliance on hash security: if H is not collision resistant, an attacker finds M_1, M_2 with H(M_1)=H(M_2), gets M_1 signed, and transfers σ to M_2 — a live existential forgery (why SHA-1 signatures are unsafe).
• Randomised padding requirement: textbook RSA is malleable — σ_1·σ_2 mod N signs M_1·M_2; RSA-PSS injects randomness and structure to reach EUF-CMA.
• Strong unforgeability (SUF-CMA): stronger still — the adversary cannot even produce a new signature on an already-signed message, closing malleability entirely.