Message Authentication Codes (MACs)Cryptographic Hash FunctionsDigital SignaturesTrapdoor One-way FunctionsRSA Signatures: High-level OutlineNumber Theory BackgroundRSA SignaturesDefinition of Security for Digital SignaturesPaxsonSpring 2011CS 161Computer Security3/17Message Authentication Codes and Digital SignaturesUpdated 27Mar11: added minor clarification regarding Fact 3 in Section 6.We’ve now looked at symmetric- and asymmetric-key encryption. Encryption is used toprotect the confidentiality of communications over an insecure channel. Now we’ll look atcryptographic schemes that provide integrity and authentication. In particular, the threatwe’re concerned about is adversaries who send spoofed messages (pretending to be from alegitimate 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 recipientto detect spoofing and tampering.We’ll look at schemes in both the symmetric-key and asymmetric-key models. If Alice andBob 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 Bobknows Alice’s public key, Alice can sign her messages with her private key, using a digitalsignature scheme (also known as a public-key signature scheme). In tabular form, the bigfour types of cryptographic primitives are:Symmetric-key Asymmetric-keyConfidentiality Symmetric-key encryption(e.g., AES-CBC)Public-key encryption(e.g., El Gamal, RSA encryption)Integrity andauthenticationMACs(e.g., AES-CBC-MAC)Digital signatures(e.g., RSA signatures)1 Message Authentication Codes (MACs)Suppose Alice and Bob share a secret key K, and Alice wants to send a message to Bobover an insecure channel. The message isn’t secret, but she wants to prevent attackers frommodifying 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 anychange 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. Alicewill send the pair of values M, T to Bob, where she computed the tag T = F (K, M) usingthe MAC. When Bob receives M, T , Bob will compute F (K, M) and check that it matches3/17 CS 161, Spring 2011 — Material courtesy Prof. David Wagner 1 of 9the 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 sometampering 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 will almost certainly1no longer be valid: in particular, F (K, M) 6= F (K, M0).More generally, there will be no way for the adversary to modify the message and then makea 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 unableto find a different message M0and a tag T0such that T0is a valid tag on M0(i.e., suchthat T0= F (K, M0)). Secure MACs are designed to ensure that even small changes to themessage make unpredictable changes to the tag, so that the adversary cannot guess thecorrect tag for a message M0that Alice has never sent.Modern MACs are designed to be secure against known-plaintext attack. For instance, sup-pose Georgia the Forger eavesdrops on Alice’s communications and observes a number of mes-sages 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 M0(such that M0/∈ {M1, . . . , Mn})and a corresponding value T0such that T0is the correct tag on M0(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 wewant to store files on a removable USB flash drive, which we occasionally share with ourfriends. To protect against tampering with the files on our flash drive, our machine couldgenerate a secret key and store a MAC of each file somewhere on the flash drive. When ourmachine 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 oneis 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 simplifiedversion 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. Weset S0= 0 and computeSi= AESK1(Si−1⊕ Mi), for i = 1, 2, . . . , n.1Strictly 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 to be long enough—say, 128 bits—and if the MAC algorithm is secure, the chances of thishappening should be about 1/2128, which is small enough that it can be safely ignored.3/17 CS 161, Spring 2011 — Material courtesy Prof. David Wagner 2 of 9Finally we compute T = AESK2(Sn); T is the tag for message M. This scheme can be provensecure, assuming AES is a secure block cipher.What does it mean to say that a MAC algorithm is secure? Here is a formal definition. Weimagine 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 Miand 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) andask Reginald whether 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
View Full Document
Unlocking...