CSE4303 Introduction to Computer Security (Lecture 10)

MACs

MACs from Hash Functions

Construction:

$S_{big}(k, m) = S(k, H(m))$
$V_{big}(k, m, t) = V(k, H(m), t)$

If:

• $S$ is secure MAC for short messages
• $H$ is collision resistant

Then $S_{big}$ is secure MAC.

If collision exists: If $H(m_0) = H(m_1)$, query tag for $m_0$, forge $(m_1, t)$.

HMAC

$HMAC(k, m) = H((k \oplus opad) \| H((k \oplus ipad) \| m))$

Used in:

• TLS
• IPsec
• SSH

Properties:

• Built from hash function (for example SHA-256)
• Provably secure under PRF assumptions

Timing Attacks on MAC Verification

Problem: Byte-by-byte comparison leaks timing information.

Attack:

1. Send random tag.
2. Guess first byte.
3. Detect timing increase.
4. Repeat per byte.

Defense 1: Constant-time comparison loop.

Defense 2: Double-HMAC comparison: Compare $HMAC(k, mac)$ with $HMAC(k, sig)$.

Authenticated Encryption (AE)

AE provides:

1. Confidentiality (CPA security)
2. Ciphertext integrity

Cipher:

$E : K \times M \times N \to C$
$D : K \times C \times N \to M \cup \{\bot\}$

Ciphertext integrity: Attacker cannot produce new valid ciphertext.

Theorem: AE implies CCA security.

Implication: If $D(k, c) \neq \bot$,
receiver knows sender had key.

Encrypt-then-MAC

Correct construction:

1. Compute $c = E(k_E, m)$
2. Compute $tag = S(k_I, c)$
3. Send $(c, tag)$

Encrypt-then-MAC is always secure ordering.

AE Standards

• GCM: CTR mode encryption then polynomial MAC
• CCM: CBC-MAC then CTR mode encryption
• EAX: CTR mode encryption then CMAC

All support AEAD: Authenticated Encryption with Associated Data.
Example: authenticate packet headers but do not encrypt them.

Asymmetric Crypto Authentication: Digital Signatures

Motivation

Goal: Bind document to author.

Digital problem: Anyone can copy a visible signature from one document to another.

Solution: Make signature depend on document contents.

Digital Signature Scheme

Components:

• Secret signing key $sk$
• Public verification key $pk$
• $Sign(sk, m) \to signature$
• $Verify(pk, m, sig) \to$ accept or reject

Property: Anyone can verify.
Only signer can produce valid signature.

Signing a Certificate

Process:

1. Compute hash of data.
2. Sign hash with secret key.
3. Attach signature to data.

Verification:

1. Compute hash of received data.
2. Verify signature using public key.
3. Accept if hashes match.

Software Signing

Software vendor:

• Signs update with secret key.
• Publishes update and signature.

Clients:

• Use vendor public key.
• Verify signature.
• Install only if valid.

Allows distribution via untrusted hosting site.

Review: Three Approaches to Data Integrity

1. Collision resistant hashing
   Requires secure read-only public space.
   No secret keys.
   Suitable for public verification.

2. MACs
   Requires shared secret key.
   Must compute new MAC per user.
   Suitable when one signs and one verifies.

3. Digital signatures
   Requires long-term secret key.
   Public verification.
   Suitable when one signs and many verify.

Crypto Summary

Cryptographic goals:

• Confidentiality
• Data integrity
• Authentication
• Non-repudiation

Primitives:

• Hash functions
• MACs
• Digital signatures
• Symmetric ciphers
• Public key ciphers