Constructing Message Authentication Codes for Secure Communication
Explore the construction of Message Authentication Codes (MACs) for ensuring data integrity and secure communication in cryptography. Learn about key algorithms, verification processes, and the importance of strong MAC authentication in protecting information. Dive into the concept of building secure MACs and understanding side-channel attacks to enhance encryption schemes.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Cryptography CS 555 Topic 10: Constructing Message Authentication Codes 1
Reminder: Homework 1 Due on Friday (next class) at the beginning of class Please typeset your solutions 2
Recap Data Integrity Message Authentication Codes Side-Channel Attacks Build Secure MACs Today s Goals: Build a Secure MAC Key tool in Construction of CCA-Secure Encryption Schemes Construct CCA-Secure Encryption Scheme 3
Message Authentication Code Syntax Definition 4.1: A message authentication code (MAC) consists of three algorithms = Gen,Mac,Vrfy Gen(1?;?) (Key-generation algorithm) Input: security parameter 1n (unary) and random bits R Output: Secret key k ? Mack(?;?) (Tag Generation algorithm) Input: Secret key k ? and message m and random bits R Output: a tag t Vrfyk(?,?) (Verification algorithm) Input: Secret key k ?, a message m and a tag t Output: a bit b (b=1 means valid and b=0 means invalid ) Vrfyk(?,Mack(?;?)) = 1 4
Strong MAC Authentication (Macsforge?,(?)) m1 t1 = MacK(m1) m2 t2 = MacK (m2) mq tq = MacK(mq) m,t s.t m,t (m1,t1), ,(mq,t?) K = Gen(.) Macsforge?, (?) = Vrfyk(?,?) ??? ? ? (negligible) s.t Pr Macsforge?, ? = 1 ?(?) 5
Strong MAC Construction (Fixed Length) Simply uses a secure PRF F Mack(?) = FK(?) Canonical Verification Algorithm Vrfyk(?,?) = 1 if ? = FK(?) otherwise 0 6
Strong MAC Construction (Fixed Length) Mack(?) = FK(?) Vrfyk(?,?) = 1 if ? = FK(?) otherwise 0 Theorem 4.6: If F is a PRF then this is a secure (fixed-length) MAC for messages of length n. Proof: Start with attacker who breaks MAC security and build an attacker who breaks PRF security (contradiction!) Sufficient to start with attacker who breaks regular MAC security (why?) 7
Breaking MAC Security (Macforge?,(?)) m1 t1 = FK(m1) m2 t2 = FK (m2) mq tq = FK(mq) ?,? s.t ? ?1, ,?? K = Gen(.) Macforge?, (?) = Vrfyk(?,?) ??? ? ??? ? (positive/non negligible) s.t Pr Macforge?, ? = 1 > ?(?) 8
A Similar Game (Macforge?, (?)) m1 Why? Because f(m) is distributed uniformly in {0,1}n so Pr[f(m)=t]=2-n t1 = f(m1) m2 t2 = f(m2) mq tq = f(mq) ?,? s.t ? ?1, ,?? Truly Random Function f Funcn Macforge?, (?) = Vrfyk(?,?) Claim: ? ??? ???? ??? Pr Macforge?, ? = 1 2 ? 9
PRF Distinguisher D Given oracle O (either FK or truly random f) Run PPT Macforge adversary A When adversary queries with message m, respond with O(m) Output 1 if attacker wins (otherwise 0) If O = f then Pr ??1?= 1 = Pr Macforge?, ? = 1 2 ? If O=FK then Pr ??1?= 1 = Pr Macforge?, ? = 1 > ?(?) 10
PRF Distinguisher D If O = f then Pr ??1?= 1 = Pr Macforge?, ? = 1 2 ? If O=FK then Pr ??1?= 1 = Pr Macforge?, ? = 1 > ?(?) Advantage: Advantage: Pr ???1?= 1 Pr ??1?= 1 > ? ? 2 ? Note that ? ? 2 ? is non-negligible and D runs in PPT if A does. 11
Strong MAC Construction (Fixed Length) Mack(?) = FK(?) Vrfyk(?,?) = 1 if ? = FK(?) otherwise 0 Theorem 4.6: If F is a PRF then this is a secure (fixed-length) MAC for messages of length n. Limitation: What if we want to authenticate a longer message? 12
MACs for Arbitrary Length Messages Building Block =(Mac ,Vrfy ), a secure MAC for length n messages First: A few failed attempts Let m = m1, ,md where each mi is n bits and let ??= Mac? MacK(m) = ?1, ,?? ?? What is wrong? Block-reordering attack MacK(md, ,?1) = ??, ,?1 13
MACs for Arbitrary Length Messages Building Block =(Mac ,Vrfy ), a secure MAC for length n messages Attempt 2 Let m = m1, ,md where each mi is n bits and let ??= Mac? MacK(m) = ?1, ,?? ? ?? Addresses block-reordering attack. Any other concerns? Truncation attack! MacK(m1, ,?? 1) = ?1, ,?? 1 14
MACs for Arbitrary Length Messages Building Block =(Mac ,Vrfy ), a secure MAC for length n messages Attempt 3 Let m = m1, ,md where each mi is n bits and m has length = ?? Let ??= Mac? MacK(m) = ?1, ,?? ? ?? Addresses truncation. Any other concerns? Mix and Match Attack! 15
MACs for Arbitrary Length Messages Let m = m1, ,md where each mi is n bits and m has length = ?? Let m = m 1, ,m d where each m i is n bits and m has length = ?? ? ?? and ? ?= Mac? MacK(m) = ?1, ,?? MacK(m ) = ? 1, ,? ? Mix and Match Attack! MacK(m1,m 2,m3,...) = ?1,? 2,?3, ? ?? Let ??= Mac? 16
MACs for Arbitrary Length Messages A non-failed approach Building Block =(Mac ,Vrfy ), a secure MAC for length n messages Let m = m1, ,md where each mi is n/4 bits and m has length < 2?/4 MacK(m)= Select random n/4 bit string r Let ??= ???? (Note: encode i and as n/4 bit strings) Output ?,?1, ,?? ? ? ?? for i=1, ,d 17
MACs for Arbitrary Length Messages MacK(m)= Select random n/4 bit string r Let ??= Mac? (Note: encode i and as n/4 bit strings) Output ?,?1, ,?? ? ? ?? for i=1, ,d Theorem 4.8: If is a secure MAC for messages of fixed length n, above construction = (Mac,Vrfy) is secure MAC for arbitrary length messages. 18
Next Class Read Katz and Lindell 4.4-4.5 CBC-MAC and Authenticated Encryption 19
