In the last segment in this module, I wanna show you a general attack that affects many implementations of Mac algorithms. And there's a nice lesson to be learned from an attack like this. So let's look at a particular implementation of HMAC verification. This happens to be an implementation from the Keyczar library, that happens to be written in Python. So here's the code that's used to verify a tag generated by HMAC. This code is actually simplified. I just wanted to kinda simplify it as much as I can to get the point across. So basically, what the inputs are, the key, the message, and the tag bytes. The way we verify it is, we re-compute the HMAC on the message and then we compare say the resulting sixteen bytes. To the actual given signature bites. So this looks perfectly fine. In fact, anyone might implement it like this. And, in fact, many people have implemented it like this. The problem is, that if you look at how the comparison is done, the comparison, as you might expect, is done byte by byte. There's a loop inside of the Python interpreter that loops over all sixteen bytes. And it so happens that the first time it finds an inequality, the loop terminates and says the strings are not equal. And the fact that the comparator exits when the first inequality is found introduces a significant timing attack on this library. So let me show you how one might attack it. So imagine you're the attacker, and you have the message m, for which you want to obtain a valid tag. Now, your goal is to attack a server that has an HMAC secret key stored in it. And the server exposes an interface that basically takes message MAC pairs. Checks that the MAC is valid, if the MAC is valid it does something with the message. And if the MAC is not valid, it says reject. Okay, so it's back to the originator or the message rejects. So now this attacker has an opportunity to basically submit lots of message it appears and see if it can deduce the tags of the particular message for which it once attacked. Here's how we might use the broken implementation from the previous slide to do just that. So what the attacker is gonna do is to submit many message tag queries, where the message is always the same. But with a tag, he's gonna experiment with lots and lots and lots of different tags. So in the first query, what he's gonna do is just submit a random tag along with the target message. And he's gonna measure how long the server took to respond. The next query that he's gonna submit, is he's gonna try all possible first bytes for the tags. Let me explain what I mean by that. So the remaining bytes of the tags that he submits are just arbitrary, doesn't really matter what they are. But for the first bite, what he'll do is he'll submit a tag starting with a byte zero. And then he's gonna see whether the server took a little bit longer to verify the tag than before. If the server took exactly the same amount of time to verify the tag as in step one, then he's gonna try again, this time with bytes at one. If still the server responded very quickly, he's going to try with byte sets of two. If the server responded quickly then he's going to try with byte sets of three, and so on until finally, let's say, when the byte sets of three the server takes a little bit longer to respond. What that means is actually when it did the comparison between the correct MAC and the MAC submitted by the attacker. The two matched on this byte, and the rejection happened on the second bytes. Aha. So now the attacker knows that the first bite of the tag is set to three and now he can mount exactly the same attack on the second bite. So here. It's going to submit the tag. And the second, back here. Here This should go here. So it's gonna submit a tag when the second byte is set to zero. And it's gonna measure whether this took a little bit longer than in step two. If not, he's gonna change this to be set to one, and he's gonna measure if the server's response time is a little longer than before. Eventually, let's say when he sets this to, I don't know. When the byte is set to, to 53, say, all of a sudden, the server takes a little bit longer to respond. Which means that now, the comparator matched on the first two bytes. And now the attacker learned that the first two bytes of the Mac are three and 53. And now he can move on and do the exact same thing on the third byte and then on the fourth byte and so on and so forth. Until finally, the server says, yes, I accept. You actually gave me the right Mac. And then we'll go ahead and act on this bogus message. That, attack our supply. So this is a beautiful example of how a timing attack can reveal the value of a MAC, the correct value of the MAC. Kind of byte by byte, until eventually, the attacker obtains all the correct bytes of the tag, and then he's able to fool the server into accepting this message tag pair. The reason I like this example is this is a perfectly reasonable way of implementing a MAC verification routine. And yet, if you right it this way, it will be completely broken. So what do we do? So let me show you two defenses, the first defense, I'll write it in again in python is, is as follows. In fact the Keyczar library exactly implemented this defense. This code is actually taken out of the updated version of the library. The first thing we do is we test if the signature bytes submitted by the attacker are of the correct length, say for HMAC this would be say, you know 96 bits or 128 bits, and if not we reject that as an invalid MAC. But now, if the signature bytes really do have the correct length, what we do is implement our own comparator. And it always takes the same amount of time to compare the two strings. So in particular, this uses the zip function in Python, which will, essentially, if you are giving it two sixteen byte strings. It will create sixteen pairs. Of bytes. So it'll just create a, a list of sixteen elements, where each element is a pair of bytes. One taken from the left and one taken from the right. And then you loop, you know, you loop through this list of pairs. You compute the XOR of the first pair, and the OR into the result. Then you compute the XOR of the second pair, and you OR that into the result. And you note that, if at any point in this loop, two bytes happen to be not equal, then the XOR will evaluate to something that's non zero. And therefore, when we OR'ed it into the result. The result will also be counting on zero, and then we'll return false, at the end of the comparison. So the point here is that now the comparator always takes the same amount of time. Even if it finds difference in byte number three, it will continue running down the both strings until the very end. And only then will it return the results. So now the timing attack supposedly is impossible. However, this can be quite problematic, because compilers tried to be too helpful here. So an optimized compiler might look at this code and say, hey, wait a minute. I can actually improve this code by making the four loop end. As soon as an incompatible set of bytes is discovered. And so, an optimizing compiler could be your, kind of, Achilles heel when it comes to making programs always take the same amount of time. And so a different defense, which is not as widely implemented, is to try and hide from the adversary, what strings are actually being compared. So let me show you what I mean by that. So again, here we have our verification algorithm. So it takes as inputs, a key, a message, and a candidate's MAC from the adversary. And then, the way we do the comparison is we first of all, compute the correct MAC on the message. But then instead of directly comparing the MAC and the signature bytes adversary, what we're gonna do is we're gonna hash one more time. So we compute a hash here of the MAC. We compute a hash of the signature bytes. Of course, if these two happen to be the same, then the resulting HMACs will also be the same, so the comparison will actually succeed. But the point is now, if sig bytes happen to equal MAC on the first byte, but not on the remaining bytes. Then, when we do this additional hash layer, it's likely that the two resulting values are completely different. And as a result, the byte by byte comparator will just output on the first iteration. The point here is that the adversary doesn't actually know what strings are being compared. And as a result, he can't mount a timing attack that we discussed earlier. Okay, so this is another defense. At least now, you're not at the mercy of an optimizing compiler. The main lesson from all of this is that you realize that people who even are experts at implementing cryptolibraries, get this stuff wrong. And the right code that words perfectly fine and yet is completely vulnerable to a timing attack that completely undo all security of the system. So the lesson here is of course you should not be inventing your own crypto but you shouldn't even be implementing your own crypto because most likely it'll be vulnerable to the side channel attacks. Just use a standard library like OpenSSL. Keyczar is actually a fine library to use that would reduce the chances that you're vulnerable to these types of attacks.
