Report

CIS 5371 Cryptography 4. Message Authentication Codes Based on: Jonathan Katz and Yehuda Lindell Introduction to Modern Cryptography 1 Message Authentication Codes Encryption vs message authentication • Different functionalities • Encryption does not provide message authentication! • Encryption with stream ciphers • For ≔ () one just needs to flip a bit of the ciphertext. • Encryption with block ciphers • Same attack (flipping bits) works, only this time blocks are affected. 2 Definition 4.1 Message Authentication Code A message authentication code (MAC) is a tuple (Gen, Mac, Vrfy) such that: • Gen takes input the security parameter 1 and outputs a key with || ≥ . • Mac takes as input a key and a message ∈ {0,1}∗ and outputs a tag . We write: Mac (). • Vrfy takes as input a key , a message ∈ {0,1}∗ and a tag and outputs a bit : = 1 means valid, while = 0 means . We write, :=Vrfy(, ). 3 Message authentication experiment Mac-forge(A,) () 1. 2. 3. A random key is generated running Gen 1 . The adversary is given input 1 and oracle access to Ma ∙ . The adversary eventually outputs a pair , . Let Q be the set of all queries of A asked to its oracle. The output of the experiment i 1 if and only if a. Vrf , = 1, and b. .. 4 Definition 4.2 -- Secure MAC A message authentication code = (Gen, Mac, Vrfy) is existentially unforgeable under adaptive chosen message attack, or just secure, if for all probabilistic polynomial-time adversaries , there exists a negligible function negl such that: Pr[Mac-forge(A,) = 1] ≤ negl. 5 Construction 4.3 A fixed length MAC from any PRF Let be a pseudorandom function. Define a fixed length MAC on messages of length as follows: • Gen: on input 1 choose {0,1} uniformly at random. • Mac: on input a key {0,1} and a message {0,1} , output tag ≔ . (If ≠ || then output nothing.) • Vrfy: on input a key {0,1} and a message {0,1} , output 1 if and only if = . (If ≠ || then output 0.) 6 Theorem 4.4 Let be a pseudorandom function. Then Construction 4.3 is a fixed-length MAC for messages of length n that is existentially unforgeable under an adaptive chosen message attack. 7 A secure fixed length MAC Proof Let A be a probabilistic polynomial time adversary. Define: ≝ Pr[Mac-forge(A,) = 1] Let be a MAC that is the same as = (Gen, Mac, Vrfy) except that a truly random function is used instead of a PRF . Then Pr[Mac-forge(A, ) = 1] ≤ 2− . 8 Distinguisher D is given access to and oracle O ∶ {0,1} → ∶ {0,1} 1. Run (1 ): whenever queries its MAC oracle on a message , answer as follows: • Query O with to get response . Return t to A. 2. When A outputs (, ) at the end of its execution do: a) Query O with to get ′. b) If ′ = and A never queried its MAC oracle with then output 1; else output 0. 9 Distinguisher D If oracle is a PRF then, Pr ∙ 1 = 1 = Pr[Mac−forge A, ) = 1 = () If the oracle is a random function - then, Pr ∙ 1 = 1 = Pr[Mac-forge , = 1] ≤ 1 2 Therefore, |Pr ∙ 1 = 1 − Pr ∙ 1 1 =1 | + 2 10 Distinguisher D Since is a PRF it follows that there is a negligible function negl with + 2− = negl . and so is negligible. 11 Replay attacks MACs do not protect against replay attacks. This is because the definition of a MAC does not incorporate any notion of state in the verification algorithm. • Two common techniques for preventing replay attacks involve the use of and . 12 Construction 4.5 A variable length MAC Let ′ = (Gen′, Mac′, Vrfy′) be fixed length MAC for messages of length . • Gen’: identical to Gen. • Mac’: on input a key {0,1} and a message {0,1}∗ of length < 2 /4 parse = 1 into blocks of length /4 and choose a random identifier in {0,1}/4 . Compute ← MAC ′ | ||| , for = 1, … , , and output ≔ (, 1 , … , ) • Vrfy: parse into blocks and re-compute the MAC. Output 1 if and only if the answer is the same for all || 13 Theorem 4.6 If ’ is a secure fixed length MAC for messages of length , then Construction 4.6 is a MAC that is existentially unforgeable under an adaptive chosen message attack. 14 Construction 4.9 CBC-MAC Let be a pseudorandom function. Fix a length function . The CBC-MAC construction is as follows: • Gen: on input 1 choose {0,1} uniformly at random. • Mac: on input a key {0,1} and message {0,1} ∙ 1. Parse = 1 ∙∙∙ into blocks of length , and set 0 ≔ 0 . 2. Compute ← −1 , for = 1, … , . Output ≔ • Vrfy: on input a key {0,1} , a message {0,1} , and a tag output 1 if and only if = MAC . 15 Theorem 4.10 Let be a polynomial. If F is a pseudorandom function then Construction 4.9 is a fixed length MAC for messages of length () ∙ that is existentially unforgeable under an adaptive chosen message attack. 16 CBC-MAC vs CBC-mode encryption 1. CBC-mode encryption uses a random IV. If we use a random IV for CBS-MAC then we lose security. 2. In CBC-mode encryption all encrypted blocks are output as part of the ciphertext. This is not the case with CBC-MAC. If we do so we loose security. 17 Variable length CBC-MAC 1 2 3 18 Secure CBC-MAC for variable length messages – three options 1. Apply the pseudorandom function to the length of the input message to get a key , e.g. set ≔ (). Then compute the CBC-MAC with this key. 2. Prepend the message with length || and then compute the basic CBC-MAC. If we append instead of prepending it we lose security. 2. Choose two keys 1 , 2 . Compute the CBC-MAC with the first key to get . The tag is ≔ 2 (). 19 Variable length CBC-MAC || 1 2 3 20