CS 161 Computer SecuritySpring 2010 Paxson/Wagner Notes 3/5Message Authentication Codes and Digital SignaturesIn the last two lectures, we looked at symmetric- and asymmetric-key encryption. Encryption is used toprotect the confidentiality of communications over an insecure channel. This lecture, we’ll look at crypto-graphic schemes that provide integrity and authentication. In particular, the threat we’re concerned aboutis adversaries who send spoofed messages (pretending to be from a legitimate participant) or who mod-ify the contents of a message from a legitimate participant. To address these threats, we will introducecryptographic 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 asecret key K, they can use a Message Authentication Code (also called a MAC, for short) to detect tamperingwith their messages. If they don’t have a shared key, but Bob knows Alice’s public key, Alice can sign hermessages with her private key, using a digital signature scheme (also known as a public-key signaturescheme). In tabular form, the big four types of cryptographic primitives are:Symmetric-key Asymmetric-keyConfidentiality Symmetric-key encryption(e.g., AES-CBC)Public-key encryption(e.g., El Gamal)Integrity andauthenticationMACs (e.g., AES-CBC-MAC) Digital signatures (e.g., RSA)1 Message Authentication Codes (MACs)Suppose Alice and Bob share a secret key K, and Alice wants to send a message to Bob over an insecurechannel. The message isn’t secret, but she wants to prevent attackers from modifying the contents of themessage. The idea of a Message Authentication Code (MAC) is to send a keyed checksum of the messagealong 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 thetag for M. Typically, we might use a 128-bit key K and 128-bit tags. Alice will send the pair of valuesM,T to Bob, where she computed the tag T = F(K,M) using the MAC. When Bob receives M,T , Bob willcompute F(K,M) and check that it matches the provided tag T . If it matches, Bob will accept the messageM as valid, authentic, and untampered; if F(K,M) 6= T , Bob will ignore the message M and presume thatsome tampering or message corruption has occurred.The algorithm F is chosen so that if the attacker replaces M by some other message M0, then the tag willalmost certainly1no longer be valid: in particular, F(K,M) 6= F(K, M0). More generally, there will be no1Strictly speaking, there is a very small chance that the tag for M will also be a valid tag for M0. However, if we choose tags toCS 161, Spring 2010, Notes 3/5 1way for the adversary to modify the message and then make a corresponding modification to the tag to trickBob into accepting the modified message: given M and T = F(K,M), an attacker who does not know thekey K should be unable to find a different message M0and a tag T0such that T0is a valid tag on M0(i.e.,such that T0= F(K,M0)). Secure MACs are designed to ensure that even small changes to the messagemake unpredictable changes to the tag, and so that the adversary cannot guess the correct tag for a messageM0that Alice has never sent.Modern MACs are designed to be secure against known-plaintext attack. For instance, suppose Georgia theForger eavesdrops on Alice’s communications and observes a number of messages and their correspondingtags: (M1,T1),(M2,T2),..., (Mn,Tn), where Ti= F(K,Mi). Then Georgia has no hope of finding some newmessage M0(such that M0/∈ {M1,..., Mn}) and a corresponding value T0such that T0is the correct tag onM0(i.e., such that T0= F(K,M0)). 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 fileson a removable USB flash drive, which we occasionally share with our friends. To protect against tamperingwith the files on our flash drive, our machine could generate a secret key and store a MAC of each filesomewhere on the flash drive. When our machine reads the file, it could check that the MAC is valid beforeusing the file contents. In a sense, this is a case where we are “communicating” to a “future version ofourselves,” 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, I will show you a relatedalgorithm called AES-EMAC. AES-EMAC is a slightly simplified version of AES-CMAC that retains itsessential 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 Mis decomposed into a sequence of 128-bit blocks: M = M1· M2···Mn. We set S0= 0 and computeSi= AESK1(Si−1⊕ Mi), for i = 1, 2, ...,n.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 gameplayed between Georgia (the adversary) and Reginald (the referee). Initially, Reginald picks a random keyK, which will be used for all subsequent rounds of the game. In each round of the game, Georgia may queryReginald with one of two kinds of queries:• Generation query: Georgia may specify a message Miand ask for the tag for Mi. Reginald willrespond with Ti= F(K,Mi).• Verification query: Alternatively, Georgia may specify a pair of values (Mi,Ti) and ask Reginaldwhether Tiis 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 Reginalda verification query (Mn,Tn) where Reginald responds “Yes”, and where Mndid not appear in any previousgeneration query to Reginald. In this case, we say that Georgia has successfully forged a tag. If Georgiacan successfully forge, then the MAC algorithm is insecure. Otherwise, if there is no strategy that allowsGeorgia to forge (given a generous allotment of computation time and any reasonable number of rounds ofthe game), then we say that the MAC algorithm is secure.be long enough—say, 128 bits—and if the MAC algorithm is secure, the
View Full Document
Unlocking...