MAC .pdf

Message Authentication Codes Saravanan Vijayakumaran Department of Electrical Engineering, IIT Bombay August 25, 2023 1 Message Integrity Encryption schemes achieve secrecy But an active adversary can modify the ciphertext or inject new ciphertexts We need mechanisms to ensure that a message was...

Message Authentication Codes Saravanan Vijayakumaran Department of Electrical Engineering, IIT Bombay August 25, 2023 1 Message Integrity Encryption schemes achieve secrecy But an active adversary can modify the ciphertext or inject new ciphertexts We need mechanisms to ensure that a message was sent by the party claiming to send it and that it was not modified in transit All the schemes we have seen so far do not provide message integrity 2 Syntax of a Message Authentication Code 3 Formal Definition of a MAC A message authentication code (MAC) consists of three PPT algorithms (Gen, Mac, Vrfy) such that: 1. Gen takes as input the security parameter 1n and outputs a key k with ∣k∣ ≥ n. 2. The tag-generation algorithm Mac takes as input a key k ∈ {0, 1}∗ , and outputs a tag t. We write t ← Mack (m). and a message m ​ 3. The deterministic verification algorithm Vrfy takes as input a key k , a message m, and a tag t. It outputs a bit b = 1 meaning valid and b = 0 meaning invalid. We write this as b := Vrfyk (m, t). with b ​ 4 Canonical Verification For deterministic message authentication codes, the canonical way to perform verification is to simply recompute the tag and check for equality ~: Vrfk (m, t) computes t = Mack (m) and then outputs 1 ~ if and only if t = t ​ ​ 5 Message Authentication Experiment Consider the experiment Mac-forgeA,Π (n): ​ A key k is generated by running Gen(1n ) The adversary A is given input 1n and oracle access to Mack (⋅) ​ The adversary eventually outputs (m, t) Let Q denote the set of all queries that A asked its oracle A succeeds if and only if 1. Vrfyk (m, t) ​ 2. m = 1 and ∈ /Q If A succeeds, the output of the experiment is 1. 6 Security Definition A MAC is secure if no efficient adversary can succeed in the above experiment with non-negligible probability A message authentication code Π = (Gen, Mac, Vrfy) is existentially unforgeable under an adaptive chosenmessage attack, or just secure, if for all PPT adversaries A, there is a negligible function such that Pr [Mac-forgeA,Π (n) = 1] ≤ negl(n). ​ 7 Replay Attacks MACs which satisfy previous security definition offer no protection against replay attacks In current setting, verification is stateless Vrfy outputs 1 every time a valid pair (m, t) is presented Protection against replay attacks must be handled by some higher-level application Common techniques use sequence numbers or timestamps 8 Timing Attacks Timing attacks use the time taken by the receiver to verify the tag to forge a valid tag Consider a MAC that uses canonical verification On receiving (m, t), the receiver computes t′ ′ := Mack (m) and checks if t = t ​ Suppose t and t′ are compared one byte at a time An attacker can incrementally learn a valid tag on m by measuring time to rejection 9 Fixed-Length MAC Construction We will construct a MAC for messages of length n using a pseudorandom function F Security of the MAC will follow from the assumption that F is pseudorandom 11 Fixed-Length MAC Construction Let F be a length-preserving pseudorandom function Define a fixed-length MAC for messages of length n as follows: Mac: on input a key k ∈ {0, 1} and a message m ∈ {0, 1}n , output the tag t := Fk (m). n ​ Vrfy: on input a key k , message m, and a tag t all in {0, 1}n , output a 1 if and only if t = Fk (m). If t =  Fk (m), output 0. ​ ​ 12 Security Proof Theorem: If F is a pseudorandom function, then the above construction is a secure fixed-length MAC for messages of length n. Proof strategy Let Π = (Gen, Mac, Vrfy) be the same as Π = (Gen, Mac, Vrfy) with Fk replaced with f ← Funcn ​ ​ ​ Construct a distinguisher D that uses A as a subroutine and show that ∣ ​ ∣ ​ Pr [Mac-forgeA,Π (n) = 1] ​ − Pr [Mac-forge ∣ (n) = 1] ≤ negl(n) ​ ​ ​ 13 Distinguisher Definition D is given 1n and access to an oracle O : {0, 1}n → {0, 1}n . It uses A as a subroutine 1. Whenever A queries its MAC oracle on message m ∈ {0, 1}n , answer as follows Query O with m and obtain response t; return t to A 2. When A outputs (m, t): Query O with m and obtain response t If t′ ′ = t and m  ∈ Q, then output 1. Else, output 0. 14 Finishing the Proof Pr [D Fk (⋅) Pr [D f (⋅) ​ (1 ) = 1] = Pr [Mac-forgeA,Π (n) = 1] n ​ (1 ) = 1] = Pr [Mac-forgeA,Π (n) = 1] n ​ Since F is pseudorandom ∣ ​ ∣ Pr [D Fk (⋅) ​ (1 ) = 1] − Pr [D n f (⋅) (1 ) = 1] n ≤ negl(n) Pr [Mac-forgeA,Π (n) = 1] = 2 ∣ ​ ∣ −n ​ Pr [Mac-forgeA,Π (n) = 1] ≤ 2−n + negl(n) 15 Domain Extension for MACs The secure MAC construction we saw can only handle messages of length n How can we authenticate arbitrary-length messages? Before seeing a secure construction, let us reject some insecure ones 17 Insecure MAC 1 Suppose message m can be broken up into d blocks m1 , m2 , … , md ∈ {0, 1}n ​ ​ ​ Ignore efficiency in terms of the tag length for now Let Π ′ ′ ′ = (Mac , Vrfy ) be a secure fixed-length MAC for messages of length n We want to construct a secure MAC Π = (Mac, Vrfy) for messages of length dn Suppose we compute a per-block tag ti output ⟨t1 , … , td ⟩ as the tag for m ​ ​ = ′ Mack (mi ) and ​ ​ ​ An adversary can perform a block reordering attack 18 Insecure MAC 2 Block reordering attacks can be prevented by authenticating the block index After reducing the size of the blocks, we can compute ti ′ Mack (i∥mi ) ​ = ​ But this does not prevent a truncation attack An attacker can simply drops blocks from the end of the message 19 Insecure MAC 3 Truncation attacks can be prevented by authenticating the message length After further reducing the size of the blocks, we compute ′ ti = Mack (l∥i∥mi ) and output ⟨t1 , … , td ⟩ as the tag ​ ​ ​ ​ ​ for m Here l is the length of the message in bits This is still vulnerable to a mix-and-match attack 20 Secure MAC Construction To prevent mix-and-match attacks, we include a random message identifier in the authentication of each block 22 Secure MAC Construction ′ The following is a secure MAC if Π is a secure MAC. Let m ∗ ∈ {0, 1} be a message of length l < 2 n/4 Parse m into d blocks m1 , m2 , … , md of length n/4 bits each ​ ​ ​ Choose r uniformly from {0, 1}n/4 For i = 1, 2, … , d, compute ti ← ​ ′ Mack (r∥l∥i∥mi ) ​ ​ where i and l are encoded as n/4-bit strings Output the tag t := ⟨r, t1 , t2 , … , td ⟩ ​ ​ ​ 23 The Birthday Problem If we choose q elements y1 , … , yq uniformly from a set of ​ ​ size N , what is the probability of collision? By collision, we mean the event when yi ​ = yj for distinct ​ i, j Let coll(q, N ) denote the collision probability Birthday problem: How many people do we need such that 1 with probability 2 we can find a pair who share a birthday? ​ It turns out that coll(q, 365) ≥ 1 for q 2 ​ ≥ 23 24 Birthday Problem Lemma Lemma: Fix a positive integer N , and let q ≤ 2N . IF ​ y1 , y2 , … , yq are chosen uniformly and independently from a set of size N . Then ​ ​ q(q − 1) q(q − 1) ≤ coll(q, N ) ≤ . 4N 2N ​ See section A.4 of Katz & Lindell for the proof 25 Security Proof (1/5) We need to show that Pr [Mac-forgeA,Π (n) negligible ​ = 1] is Let repeat denote the event that the same random identifier appears in more than one MAC oracle response Let A’s final output be (m, t) where m = ⟨m1 , m2 , … , md ⟩ and t = ⟨r, t1 , … , td ⟩ ​ ​ ​ ​ ​ Let NewBlock denote the event that at least one of the blocks r∥l∥i∥mi was never previously authenticated by ​ ′ Mac while answering A’s queries 26 Security Proof (2/5) Let Forge denote the event Mac-forgeA,Π (n) ​ =1 We have Pr [Mac-forgeA,Π (n) = 1] = ​ = Pr [Forge ⋂ repeat] + Pr [Forge ⋂ repeat ⋂ NewBlock] c + Pr [Forge ⋂ repeat ⋂ NewBlock ] c ​ c ​ ≤ Pr [repeat] + Pr [Forge ⋂ NewBlock] 27 Security Proof (3/5) Pr[repeat] ≤ oracle queries [q(n)]2 n +1 where q(n) is the number of MAC 24 ​ ​ Claim: Pr [Forge ⋂ repeat c c ⋂ NewBlock ] = 0 In words, if the adversary succeeds and repeat did not occur, then NewBlock must have occurred If repeat does not occur then the values r1 , … , rq are distinct ​ If r ​ ∈ / {r1 , … , rq }, then NewBlock clearly occurs ​ ​ 28 Security Proof (4/5) If r ∈ {r1 , … , rq }, then r = rj for a unique j ​ ​ ​ Only the j th query to the MAC oracle could have authenticated one of r∥l∥1∥m1 , … , r∥l∥d∥md ​ ​ Let m(j) be the message that A used in its j th oracle query Let lj be the length of m (j) ​ Case 1: l  lj = Case 2: l = lj ​ ​ 29 Security Proof (5/5) We need to show that Pr [Forge ⋂ NewBlock] is negligible We construct an adversary A′ that attacks Π′ by using A as a subroutine We will have Pr [Mac-forgeA,Π (n) = 1 ⋂ NewBlock] ​ ≤ Pr [Mac-forgeA′ ,Π′ (n) = 1] ​ Since Π′ is secure, the RHS is negligible 30 CBC-MAC The previous construction is inefficient because the tag is more than four times longer than the message length CBC-MAC is a secure MAC with tag length equal to message block length 32 CBC-MAC for Fixed-Length Messages Let F be a length-preserving pseudorandom function with length n bits Let m ∈ {0, 1} dn be a message for a fixed d > 0. Mac: 1. Parse the message m in to d blocks m1 , … , md of ​ ​ length n bits each. 2. Set t0 ​ = 0n . For i = 1, … , d, set ti = Fk (ti−1 ⊕ mi ). ​ ​ ​ ​ 3. Output td as the tag. ​ Vrfy: For a message-tag pair (m, t) output 0, if the 33 CBC-MAC for Fixed-Length Messages Theorem: If d = l(n) for some polynomial l and F is a pseudorandom function, then the above construction is secure for messages of length dn. 34 CBC-MAC for Arbitrary Length Messages 35 Further Reading Sections 4.1 — 4.3 from Katz & Lindell Section A.4 from Katz & Lindell 36