Cryptography is an indispensable tool for protecting information in computer systems. In this course you will learn the inner workings of cryptographic systems and how to correctly use them in real-world applications. The course begins with a detailed discussion of how two parties who have a shared secret key can communicate securely when a powerful adversary eavesdrops and tampers with traffic. We will examine many deployed protocols and analyze mistakes in existing systems. The second half of the course discusses public-key techniques that let two parties generate a shared secret key. Throughout the course participants will be exposed to many exciting open problems in the field and work on fun (optional) programming projects. In a second course (Crypto II) we will cover more advanced cryptographic tasks such as zero-knowledge, privacy mechanisms, and other forms of encryption.
Timing attacks on MAC verification
Loading...
Do curso por Stanford University
Cryptography I
2062 classificações
Na lição
Message Integrity
Week 3. This week's topic is data integrity. We will discuss a number of classic constructions for MAC systems that are used to ensure data integrity. For now we only discuss how to prevent modification of non-secret data. Next week we will come back to encryption and show how to provide both confidentiality and integrity. This week's programming project shows how to authenticate large video files. Even if you don't do the project, please read the project description --- it teaches an important concept called a hash chain.
Conheça os instrutores
Dan BonehProfessor
Computer Science
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.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
