[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.76,Default,,0000,0000,0000,,In the last segment in this module, I\Nwanna show you a general attack that
Dialogue: 0,0:00:03.76,0:00:07.62,Default,,0000,0000,0000,,affects many implementations of Mac\Nalgorithms. And there's a nice lesson to
Dialogue: 0,0:00:07.62,0:00:11.73,Default,,0000,0000,0000,,be learned from an attack like this. So\Nlet's look at a particular implementation
Dialogue: 0,0:00:11.73,0:00:15.94,Default,,0000,0000,0000,,of HMAC verification. This happens to be\Nan implementation from the Keyczar library,
Dialogue: 0,0:00:15.94,0:00:20.00,Default,,0000,0000,0000,,that happens to be written in Python. So\Nhere's the code that's used to verify a
Dialogue: 0,0:00:20.00,0:00:23.71,Default,,0000,0000,0000,,tag generated by HMAC. This code is\Nactually simplified. I just wanted to
Dialogue: 0,0:00:23.71,0:00:27.82,Default,,0000,0000,0000,,kinda simplify it as much as I can to get\Nthe point across. So basically, what the
Dialogue: 0,0:00:27.82,0:00:32.24,Default,,0000,0000,0000,,inputs are, the key, the message, and the\Ntag bytes. The way we verify it is, we
Dialogue: 0,0:00:32.24,0:00:38.08,Default,,0000,0000,0000,,re-compute the HMAC on the message and\Nthen we compare say the resulting sixteen
Dialogue: 0,0:00:38.08,0:00:43.27,Default,,0000,0000,0000,,bytes. To the actual given signature\Nbites. So this looks perfectly fine.
Dialogue: 0,0:00:43.27,0:00:47.83,Default,,0000,0000,0000,,In fact, anyone might implement it like this.\NAnd, in fact, many people have implemented
Dialogue: 0,0:00:47.83,0:00:52.23,Default,,0000,0000,0000,,it like this. The problem is, that if you\Nlook at how the comparison is done, the
Dialogue: 0,0:00:52.23,0:00:56.74,Default,,0000,0000,0000,,comparison, as you might expect, is done\Nbyte by byte. There's a loop inside of the
Dialogue: 0,0:00:56.74,0:01:01.37,Default,,0000,0000,0000,,Python interpreter that loops over all\Nsixteen bytes. And it so happens that the
Dialogue: 0,0:01:01.37,0:01:06.30,Default,,0000,0000,0000,,first time it finds an inequality, the\Nloop terminates and says the strings are
Dialogue: 0,0:01:06.30,0:01:10.97,Default,,0000,0000,0000,,not equal. And the fact that the\Ncomparator exits when the first inequality
Dialogue: 0,0:01:10.97,0:01:16.15,Default,,0000,0000,0000,,is found introduces a significant timing\Nattack on this library. So let me show you
Dialogue: 0,0:01:16.15,0:01:21.26,Default,,0000,0000,0000,,how one might attack it. So imagine you're\Nthe attacker, and you have the message m,
Dialogue: 0,0:01:21.26,0:01:26.37,Default,,0000,0000,0000,,for which you want to obtain a valid tag.\NNow, your goal is to attack a server that
Dialogue: 0,0:01:26.37,0:01:31.23,Default,,0000,0000,0000,,has an HMAC secret key stored in it. And\Nthe server exposes an interface that
Dialogue: 0,0:01:31.23,0:01:36.09,Default,,0000,0000,0000,,basically takes message MAC pairs. Checks\Nthat the MAC is valid, if the MAC is valid
Dialogue: 0,0:01:36.09,0:01:40.45,Default,,0000,0000,0000,,it does something with the message. And if\Nthe MAC is not valid, it says reject.
Dialogue: 0,0:01:40.45,0:01:45.04,Default,,0000,0000,0000,,Okay, so it's back to the originator or\Nthe message rejects. So now this attacker
Dialogue: 0,0:01:45.04,0:01:49.68,Default,,0000,0000,0000,,has an opportunity to basically submit\Nlots of message it appears and see if it
Dialogue: 0,0:01:49.68,0:01:54.27,Default,,0000,0000,0000,,can deduce the tags of the particular\Nmessage for which it once attacked. Here's
Dialogue: 0,0:01:54.27,0:01:59.04,Default,,0000,0000,0000,,how we might use the broken implementation\Nfrom the previous slide to do just that.
Dialogue: 0,0:01:59.04,0:02:03.66,Default,,0000,0000,0000,,So what the attacker is gonna do is to\Nsubmit many message tag queries, where the
Dialogue: 0,0:02:03.66,0:02:08.04,Default,,0000,0000,0000,,message is always the same. But with a\Ntag, he's gonna experiment with lots and
Dialogue: 0,0:02:08.04,0:02:12.60,Default,,0000,0000,0000,,lots and lots of different tags. So in the\Nfirst query, what he's gonna do is just
Dialogue: 0,0:02:12.60,0:02:17.20,Default,,0000,0000,0000,,submit a random tag along with the target\Nmessage. And he's gonna measure how long
Dialogue: 0,0:02:17.20,0:02:21.67,Default,,0000,0000,0000,,the server took to respond. The next query\Nthat he's gonna submit, is he's gonna try
Dialogue: 0,0:02:21.67,0:02:25.90,Default,,0000,0000,0000,,all possible first bytes for the tags. Let\Nme explain what I mean by that. So the
Dialogue: 0,0:02:25.90,0:02:30.01,Default,,0000,0000,0000,,remaining bytes of the tags that he\Nsubmits are just arbitrary, doesn't really
Dialogue: 0,0:02:30.01,0:02:34.56,Default,,0000,0000,0000,,matter what they are. But for the first\Nbite, what he'll do is he'll submit a tag
Dialogue: 0,0:02:34.56,0:02:39.39,Default,,0000,0000,0000,,starting with a byte zero. And then he's\Ngonna see whether the server took a little
Dialogue: 0,0:02:39.39,0:02:44.28,Default,,0000,0000,0000,,bit longer to verify the tag than before.\NIf the server took exactly the same amount
Dialogue: 0,0:02:44.28,0:02:49.06,Default,,0000,0000,0000,,of time to verify the tag as in step one,\Nthen he's gonna try again, this time with
Dialogue: 0,0:02:49.06,0:02:52.98,Default,,0000,0000,0000,,bytes at one. If still the server\Nresponded very quickly, he's going to try
Dialogue: 0,0:02:52.98,0:02:56.96,Default,,0000,0000,0000,,with byte sets of two. If the server\Nresponded quickly then he's going to try
Dialogue: 0,0:02:56.96,0:03:01.10,Default,,0000,0000,0000,,with byte sets of three, and so on until\Nfinally, let's say, when the byte sets of
Dialogue: 0,0:03:01.10,0:03:05.34,Default,,0000,0000,0000,,three the server takes a little bit longer\Nto respond. What that means is actually
Dialogue: 0,0:03:05.34,0:03:09.48,Default,,0000,0000,0000,,when it did the comparison between the\Ncorrect MAC and the MAC submitted by the
Dialogue: 0,0:03:09.48,0:03:14.33,Default,,0000,0000,0000,,attacker. The two matched on this byte,\Nand the rejection happened on the second
Dialogue: 0,0:03:14.33,0:03:19.07,Default,,0000,0000,0000,,bytes. Aha. So now the attacker knows that\Nthe first bite of the tag is set to three
Dialogue: 0,0:03:19.07,0:03:23.44,Default,,0000,0000,0000,,and now he can mount exactly the same\Nattack on the second bite. So here. It's
Dialogue: 0,0:03:23.44,0:03:28.52,Default,,0000,0000,0000,,going to submit the tag. And the second,\Nback here. Here This should go here. So
Dialogue: 0,0:03:28.52,0:03:32.51,Default,,0000,0000,0000,,it's gonna submit a tag when the second\Nbyte is set to zero. And it's gonna
Dialogue: 0,0:03:32.51,0:03:36.52,Default,,0000,0000,0000,,measure whether this took a little bit\Nlonger than in step two. If not, he's
Dialogue: 0,0:03:36.52,0:03:40.50,Default,,0000,0000,0000,,gonna change this to be set to one, and\Nhe's gonna measure if the server's
Dialogue: 0,0:03:40.50,0:03:44.76,Default,,0000,0000,0000,,response time is a little longer than\Nbefore. Eventually, let's say when he sets
Dialogue: 0,0:03:44.76,0:03:48.96,Default,,0000,0000,0000,,this to, I don't know. When the byte is\Nset to, to 53, say, all of a sudden, the
Dialogue: 0,0:03:48.96,0:03:52.68,Default,,0000,0000,0000,,server takes a little bit longer to\Nrespond. Which means that now, the
Dialogue: 0,0:03:52.68,0:03:56.94,Default,,0000,0000,0000,,comparator matched on the first two bytes.\NAnd now the attacker learned that the
Dialogue: 0,0:03:56.94,0:04:01.06,Default,,0000,0000,0000,,first two bytes of the Mac are three and\N53. And now he can move on and do the
Dialogue: 0,0:04:01.06,0:04:05.27,Default,,0000,0000,0000,,exact same thing on the third byte and\Nthen on the fourth byte and so on and so
Dialogue: 0,0:04:05.27,0:04:09.18,Default,,0000,0000,0000,,forth. Until finally, the server says,\Nyes, I accept. You actually gave me the
Dialogue: 0,0:04:09.18,0:04:13.86,Default,,0000,0000,0000,,right Mac. And then we'll go ahead and act\Non this bogus message. That, attack our
Dialogue: 0,0:04:13.86,0:04:18.71,Default,,0000,0000,0000,,supply. So this is a beautiful example of\Nhow a timing attack can reveal the value
Dialogue: 0,0:04:18.71,0:04:23.14,Default,,0000,0000,0000,,of a MAC, the correct value of the MAC.\NKind of byte by byte, until eventually,
Dialogue: 0,0:04:23.14,0:04:28.09,Default,,0000,0000,0000,,the attacker obtains all the correct bytes\Nof the tag, and then he's able to fool the
Dialogue: 0,0:04:28.09,0:04:32.64,Default,,0000,0000,0000,,server into accepting this message tag\Npair. The reason I like this example is
Dialogue: 0,0:04:32.64,0:04:37.19,Default,,0000,0000,0000,,this is a perfectly reasonable way of\Nimplementing a MAC verification routine.
Dialogue: 0,0:04:37.19,0:04:41.94,Default,,0000,0000,0000,,And yet, if you right it this way, it will\Nbe completely broken. So what do we do? So
Dialogue: 0,0:04:41.94,0:04:46.51,Default,,0000,0000,0000,,let me show you two defenses, the first\Ndefense, I'll write it in again in python
Dialogue: 0,0:04:46.51,0:04:51.02,Default,,0000,0000,0000,,is, is as follows. In fact the Keyczar\Nlibrary exactly implemented this defense.
Dialogue: 0,0:04:51.02,0:04:55.59,Default,,0000,0000,0000,,This code is actually taken out of the\Nupdated version of the library. The first
Dialogue: 0,0:04:55.59,0:05:00.33,Default,,0000,0000,0000,,thing we do is we test if the signature\Nbytes submitted by the attacker are of the
Dialogue: 0,0:05:00.33,0:05:04.90,Default,,0000,0000,0000,,correct length, say for HMAC this would\Nbe say, you know 96 bits or 128 bits, and
Dialogue: 0,0:05:04.90,0:05:09.42,Default,,0000,0000,0000,,if not we reject that as an invalid MAC.\NBut now, if the signature bytes really do
Dialogue: 0,0:05:09.42,0:05:13.47,Default,,0000,0000,0000,,have the correct length, what we do is\Nimplement our own comparator. And it
Dialogue: 0,0:05:13.47,0:05:17.90,Default,,0000,0000,0000,,always takes the same amount of time to\Ncompare the two strings. So in particular,
Dialogue: 0,0:05:17.90,0:05:22.16,Default,,0000,0000,0000,,this uses the zip function in Python,\Nwhich will, essentially, if you are giving
Dialogue: 0,0:05:22.16,0:05:28.12,Default,,0000,0000,0000,,it two sixteen byte strings. It will\Ncreate sixteen pairs. Of bytes. So it'll
Dialogue: 0,0:05:28.12,0:05:32.67,Default,,0000,0000,0000,,just create a, a list of sixteen elements,\Nwhere each element is a pair of bytes. One
Dialogue: 0,0:05:32.67,0:05:37.05,Default,,0000,0000,0000,,taken from the left and one taken from the\Nright. And then you loop, you know, you
Dialogue: 0,0:05:37.05,0:05:41.33,Default,,0000,0000,0000,,loop through this list of pairs. You\Ncompute the XOR of the first pair, and the
Dialogue: 0,0:05:41.33,0:05:45.49,Default,,0000,0000,0000,,OR into the result. Then you\Ncompute the XOR of the second pair, and
Dialogue: 0,0:05:45.49,0:05:49.93,Default,,0000,0000,0000,,you OR that into the result. And\Nyou note that, if at any point in this
Dialogue: 0,0:05:49.93,0:05:54.21,Default,,0000,0000,0000,,loop, two bytes happen to be not equal,\Nthen the XOR will evaluate to something
Dialogue: 0,0:05:54.21,0:05:58.58,Default,,0000,0000,0000,,that's non zero. And therefore, when we\NOR'ed it into the result. The result
Dialogue: 0,0:05:58.58,0:06:02.63,Default,,0000,0000,0000,,will also be counting on zero, and then\Nwe'll return false, at the end of the
Dialogue: 0,0:06:02.63,0:06:06.58,Default,,0000,0000,0000,,comparison. So the point here is that now\Nthe comparator always takes the same
Dialogue: 0,0:06:06.58,0:06:10.72,Default,,0000,0000,0000,,amount of time. Even if it finds\Ndifference in byte number three, it will
Dialogue: 0,0:06:10.72,0:06:15.48,Default,,0000,0000,0000,,continue running down the both strings\Nuntil the very end. And only then will it
Dialogue: 0,0:06:15.48,0:06:20.24,Default,,0000,0000,0000,,return the results. So now the timing\Nattack supposedly is impossible. However,
Dialogue: 0,0:06:20.24,0:06:25.26,Default,,0000,0000,0000,,this can be quite problematic, because\Ncompilers tried to be too helpful here. So
Dialogue: 0,0:06:25.26,0:06:30.14,Default,,0000,0000,0000,,an optimized compiler might look at this\Ncode and say, hey, wait a minute. I can
Dialogue: 0,0:06:30.14,0:06:35.11,Default,,0000,0000,0000,,actually improve this code by making the\Nfour loop end. As soon as an incompatible
Dialogue: 0,0:06:35.11,0:06:39.38,Default,,0000,0000,0000,,set of bytes is discovered. And so, an\Noptimizing compiler could be your, kind
Dialogue: 0,0:06:39.38,0:06:43.93,Default,,0000,0000,0000,,of, Achilles heel when it comes to making\Nprograms always take the same amount of
Dialogue: 0,0:06:43.93,0:06:48.48,Default,,0000,0000,0000,,time. And so a different defense, which is\Nnot as widely implemented, is to try and
Dialogue: 0,0:06:48.48,0:06:52.98,Default,,0000,0000,0000,,hide from the adversary, what strings are\Nactually being compared. So let me show
Dialogue: 0,0:06:52.98,0:06:57.42,Default,,0000,0000,0000,,you what I mean by that. So again, here we\Nhave our verification algorithm. So it
Dialogue: 0,0:06:57.42,0:07:01.74,Default,,0000,0000,0000,,takes as inputs, a key, a message, and a\Ncandidate's MAC from the adversary. And
Dialogue: 0,0:07:01.74,0:07:06.16,Default,,0000,0000,0000,,then, the way we do the comparison is we\Nfirst of all, compute the correct MAC on
Dialogue: 0,0:07:06.16,0:07:10.41,Default,,0000,0000,0000,,the message. But then instead of directly\Ncomparing the MAC and the signature
Dialogue: 0,0:07:10.41,0:07:14.93,Default,,0000,0000,0000,,bytes adversary, what we're gonna do\Nis we're gonna hash one more time. So we
Dialogue: 0,0:07:14.93,0:07:19.46,Default,,0000,0000,0000,,compute a hash here of the MAC. We compute\Na hash of the signature bytes. Of course,
Dialogue: 0,0:07:19.46,0:07:23.76,Default,,0000,0000,0000,,if these two happen to be the same, then\Nthe resulting HMACs will also be the
Dialogue: 0,0:07:23.76,0:07:27.79,Default,,0000,0000,0000,,same, so the comparison will actually\Nsucceed. But the point is now, if sig
Dialogue: 0,0:07:27.79,0:07:31.69,Default,,0000,0000,0000,,bytes happen to equal MAC on the first\Nbyte, but not on the remaining bytes.
Dialogue: 0,0:07:31.69,0:07:35.61,Default,,0000,0000,0000,,Then, when we do this additional hash\Nlayer, it's likely that the two resulting
Dialogue: 0,0:07:35.61,0:07:39.68,Default,,0000,0000,0000,,values are completely different. And as a\Nresult, the byte by byte comparator will
Dialogue: 0,0:07:39.68,0:07:43.69,Default,,0000,0000,0000,,just output on the first iteration. The\Npoint here is that the adversary doesn't
Dialogue: 0,0:07:43.69,0:07:47.26,Default,,0000,0000,0000,,actually know what strings are being\Ncompared. And as a result, he can't
Dialogue: 0,0:07:47.26,0:07:50.81,Default,,0000,0000,0000,,mount a timing attack that we\Ndiscussed earlier. Okay, so this is
Dialogue: 0,0:07:50.81,0:07:55.45,Default,,0000,0000,0000,,another defense. At least now, you're not\Nat the mercy of an optimizing compiler.
Dialogue: 0,0:07:55.45,0:08:00.03,Default,,0000,0000,0000,,The main lesson from all of this is that\Nyou realize that people who even are
Dialogue: 0,0:08:00.03,0:08:04.49,Default,,0000,0000,0000,,experts at implementing cryptolibraries,\Nget this stuff wrong. And the right code
Dialogue: 0,0:08:04.49,0:08:08.35,Default,,0000,0000,0000,,that words perfectly fine and yet is\Ncompletely vulnerable to a timing attack
Dialogue: 0,0:08:08.35,0:08:12.31,Default,,0000,0000,0000,,that completely undo all security of the\Nsystem. So the lesson here is of course
Dialogue: 0,0:08:12.31,0:08:15.78,Default,,0000,0000,0000,,you should not be inventing your own\Ncrypto but you shouldn't even be
Dialogue: 0,0:08:15.78,0:08:19.78,Default,,0000,0000,0000,,implementing your own crypto because most\Nlikely it'll be vulnerable to the side
Dialogue: 0,0:08:19.78,0:08:23.55,Default,,0000,0000,0000,,channel attacks. Just use a standard\Nlibrary like OpenSSL. Keyczar is actually a
Dialogue: 0,0:08:23.55,0:08:27.60,Default,,0000,0000,0000,,fine library to use that would reduce the\Nchances that you're vulnerable to these
Dialogue: 0,0:08:27.60,0:08:28.45,Default,,0000,0000,0000,,types of attacks.