Paxson Spring 2011 CS 161 Computer Security 3 17 Message Authentication Codes and Digital Signatures Updated 27Mar11 added minor clarification regarding Fact 3 in Section 6 We ve now looked at symmetric and asymmetric key encryption Encryption is used to protect the confidentiality of communications over an insecure channel Now we ll look at cryptographic schemes that provide integrity and authentication In particular the threat we re concerned about is adversaries who send spoofed messages pretending to be from a legitimate participant or who modify the contents of a message from a legitimate participant To address these threats we will introduce cryptographic schemes that enable the recipient to detect spoofing and tampering We ll look at schemes in both the symmetric key and asymmetric key models If Alice and Bob share a secret key K they can use a Message Authentication Code also called a MAC for short to detect tampering with their messages If they don t have a shared key but Bob knows Alice s public key Alice can sign her messages with her private key using a digital signature scheme also known as a public key signature scheme In tabular form the big four types of cryptographic primitives are Confidentiality Integrity and authentication 1 Symmetric key Asymmetric key Symmetric key encryption e g AES CBC MACs e g AES CBC MAC Public key encryption e g El Gamal RSA encryption Digital signatures e g RSA signatures Message Authentication Codes MACs Suppose Alice and Bob share a secret key K and Alice wants to send a message to Bob over an insecure channel The message isn t secret but she wants to prevent attackers from modifying the contents of the message The idea of a Message Authentication Code MAC is to send a keyed checksum of the message along with the message chosen so that any change to the message will render the checksum invalid The MAC on a message M is a value F K M computed from K and M the value F K M is called the tag for M Typically we might use a 128 bit key K and 128 bit tags Alice will send the pair of values M T to Bob where she computed the tag T F K M using the MAC When Bob receives M T Bob will compute F K M and check that it matches 3 17 CS 161 Spring 2011 Material courtesy Prof David Wagner 1 of 9 the provided tag T If it matches Bob will accept the message M as valid authentic and untampered if F K M 6 T Bob will ignore the message M and presume that some tampering or message corruption has occurred The algorithm F is chosen so that if the attacker replaces M by some other message M 0 then the tag will almost certainly1 no longer be valid in particular F K M 6 F K M 0 More generally there will be no way for the adversary to modify the message and then make a corresponding modification to the tag to trick Bob into accepting the modified message given M and T F K M an attacker who does not know the key K should be unable to find a different message M 0 and a tag T 0 such that T 0 is a valid tag on M 0 i e such that T 0 F K M 0 Secure MACs are designed to ensure that even small changes to the message make unpredictable changes to the tag so that the adversary cannot guess the correct tag for a message M 0 that Alice has never sent Modern MACs are designed to be secure against known plaintext attack For instance suppose Georgia the Forger eavesdrops on Alice s communications and observes a number of messages and their corresponding tags M1 T1 M2 T2 Mn Tn where Ti F K Mi Then Georgia has no hope of finding some new message M 0 such that M 0 M1 Mn 0 0 0 and a corresponding value T such that T is the correct tag on M i e such that T 0 F K M 0 The same is true even if Georgia was able to choose the Mi s MACs can be used for more than just communication security For instance suppose we want to store files on a removable USB flash drive which we occasionally share with our friends To protect against tampering with the files on our flash drive our machine could generate a secret key and store a MAC of each file somewhere on the flash drive When our machine reads the file it could check that the MAC is valid before using the file contents In a sense this is a case where we are communicating to a future version of ourselves so security for stored data can be viewed as a variant of communication security How do we build secure MACs There are a number of schemes out there but one good one is AES CMAC an algorithm standardized by NIST Instead of showing you AES CMAC we ll look at a related algorithm called AES EMAC AES EMAC is a slightly simplified version of AES CMAC that retains its essential character but differs in a few details In AES EMAC the key K is 256 bits viewed as a pair of 128 bit AES keys K K1 K2 The message M is decomposed into a sequence of 128 bit blocks M M1 M2 Mn We set S0 0 and compute Si AESK1 Si 1 Mi for i 1 2 n Strictly speaking there is a very small chance that the tag for M will also be a valid tag for M 0 However if we choose tags to be long enough say 128 bits and if the MAC algorithm is secure the chances of this happening should be about 1 2128 which is small enough that it can be safely ignored 1 3 17 CS 161 Spring 2011 Material courtesy Prof David Wagner 2 of 9 Finally we compute T AESK2 Sn T is the tag for message M This scheme can be proven secure assuming AES is a secure block cipher What does it mean to say that a MAC algorithm is secure Here is a formal definition We imagine a game played between Georgia the adversary and Reginald the referee Initially Reginald picks a random key K which will be used for all subsequent rounds of the game In each round of the game Georgia may query Reginald with one of two kinds of queries Generation query Georgia may specify a message Mi and ask for the tag for Mi Reginald will respond with Ti F K Mi Verification query Alternatively Georgia may specify a pair of values Mi Ti and ask Reginald whether Ti is a valid tag on Mi Reginald checks whether Ti F K Mi and responds Yes or No accordingly Georgia is allowed to repeatedly interact with Reginald in this way Georgia wins if she ever asks Reginald a verification query Mn Tn where Reginald responds Yes and where Mn did not appear in any …
View Full Document
Unlocking...