[SOUND] In the last lecture we introduced the notion of message authentication codes. In this lecture I want to explore a relatively simple construction of a message authentication code for short, fixed-length messages. Intuitively, we're looking for a keyed function Mac, such that the following properties hold: Given Mack of m1, Mack of m2, etc., where the key k is chosen uniformly. It should be infeasible for an attacker to predict the value of Mac k of m for any message m not equal to m1, m2, m3 et cetera. If you think about this a little bit, you'll notice that this seems very similar to a primitive we've seen before, namely a pseudorandom function. That's not to say that the requirements we have here are equivalent to a pseudorandom function. What I am claiming however is that a pseudorandom function would in particularly imply the properties we have stated here. And the reason for why that's the case is as follows. If we have a pseudorandom function then we know that it's indistinguishable from a random function. And a random function has exactly the property that if we learn the value of f of m1, f of m2 etc. We learn nothing about the value of f evaluated on any additional point. And this is exactly the property we're looking for here. So that means we have the following construction. Let's let F denote a length-preserving pseudorandom function, i.e a block cipher. We can define the following message authentication code Pi. The key generation algorithm will choose a uniform key k for F. And Mac k of m will simply output Fk of m. To verify a tag t on a message M with respect to the key k, we simply reevaluate Fk of m and output one if and only if that's equal to the tag t that we've been presented with. The theorem we can prove and we will prove in a moment. Is that if F is indeed a pseudorandom function, then this construction Pi is a secure message authentication code. As usual, we're going to give a proof by reduction. So imagine we have some attacker A, who's attacking the message authentication code Pi that we've just constructed. What we're going to do is use that attacker as a subroutine, in a distinguisher D, who's going to be interacting with either a random function or the pseudorandom function F with with a uniform key k. The reduction here is really the natural one. What D is going to do is run the attacker as a subroutine inside of it, and every time the attacker requests a tag on some message, m1 say, D will simply forward m1 to its oracle and get back a value t1, which it will give to the attacker. This will go on as long as the attacker wishes. Every time the attacker requests a tag on some message m, we forward D, D will forward that to its oracle, get back the corresponding value and give that value back to the attacker. Finally, the attacker outputs its forgery. It outputs a pair m,t, where t is supposed to represent a valid tag on m. Let's assume, without really any loss of generality, that m is not equal to any of the previous messages that the attacker on, on which the attacker has requested a tag. If the attacker can't succeed, if m is equal to one of his prior messages, so we can assume that for simplicity. What D will do is simply forward m to its external oracle, and get back a value t*. Now if t is equal to t*, right, if the value that the attacker output as its valid tag as its claimed valid tag, is equal to the value t* that D got back from its oracle, then D outputs 1. And otherwise it outputs 0. Let's analyse the behavior of D. So when D interacts with F-sub-k for the uniform k, that means we're in the pseudorandom case, and D is interacting with a pseudorandom function, then the view of the attacker being run as a subroutine inside of D. Is identical to its view in the real MAC experiment. Right, every message, for which the attacker requests a tag, is responded to with the tag Fk of M. And when the attacker outputs m,t it succeeds exactly when Fk of m is equal to t. So that means that the probability that D outputs 1, when D is interacting with F of k is exactly equal to the probability that forge output 1. It's exactly equal to the success probability of the attacker when interacting with Pi. On the other hand, when D interacts with the uniform function F, then what we know is that after observing the values of f(m1), f(m2), et cetera, D cannot possibly predict the value of f(m). Right because m is not equal to any of the m1, m2, m3 etc. And because f is a random function, the value of f of m is completely uniform. And so the probability with which t the value output by the attacker being run as a sub routine within D, happens to be equal to the value t*. That is the value that D gets back from its oracle, is exactly 2 to the minus n. So here, we're assuming that we have a length preserving pseudorandom function, f, whose input and output length are both end bit strings. Whose input and output range and domain are both end bit strings. So the probability that we can predict in advance, the value, of the n-bit string t* is exactly 2 to the -n. We're almost done. By assumption that F is a pseudorandom function, we know that the difference between the probability with which D outputs 1 when interacting with Fk and the probability that D outputs 1 when interacting with a random function must be negligible. And so, plugging in what we have from the previous slide, we see that the probability that the attacker succeeds in the forage experiment, which is equal to the probability with which D outputs 1 when interacting with F sub k, is at most 2 to the minus n plus negligible. And because 2 to the minus n is itself a negligible function. That means that indeed we've shown that the probability that the attacker can succeed in the original forgery experiment is negligible. Does this mean that we're done? Well, if you think about it a little bit, and what this would mean in terms of practice, recall that typical block ciphers, have short, fixed length block size. For example, AES has a 128 bit block size. So what the construction we've just shown would give us, is a message authentication code for 128 bit messages. And this is actually quite a limitation. Most messages that we're going to send in practice, are first of all going to be much longer than 128 bits long. And secondly, in the general case we'd like to be able to authenticate messages of different length. And the construction we've just set, we've just shown, assumes that every message being authenticated is exactly 128 bits long. So in the next few lectures, we're going to see, how we can take this idea that we've explored here, which gives us a Mac for short, fixed-length messages, and turn that into a more robust and more useful message authentication code that can handle long and variable length messages.
