This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.
CBC-MAC
Loading...
Do curso por University of Maryland, College Park
Cryptography
435 ratings
Conheça os instrutores
Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center
Maryland Cybersecurity Center
[MUSIC]
Let's remember where things stand.
In the last lecture we showed how to construct a secure message
authentication code for short fixed length messages.
Based on any pseudo random function, AKA block cipher.
And what we'd like to do, is to make this more useful and
more practical, by extending those ideas.
To give a construction of a secure message authentication code that can
handle arbitrary length messages.
And in particular messages that are much longer than a single block length.
And in this lecture we'll explore one popular way of doing that.
Called CBC MAC.
The basic CBC MAC construction works in the following ways.
Given a message m1 to ml, where each mi represents a block of the message.
Whose length is equal to the block length of some underlying block cipher.
We compute the tag in the following way.
We first apply our block cipher, F sub k, to the initial block, m1.
Take that value and
use it as a chaining value, XOR it with the next message block, m2.
Pass that result through the block cipher, and so on until the final block.
The result of the final invocation of the block cipher,
is the tag T on the message m1 through ml.
Now, even though CBC-MAC looks very similar to CBC-Mode encryption,
there are a few differences that are crucial for the security of CBC-MAC.
The first thing to observe is that CBC-MAC is deterministic.
And in particular, there's no initialization vector.
Or another way to think about it is that it's what you would get if you
ran CBC mode encryption with the all zero IV.
And this is important for security.
There's no reason for
a MAC to be randomized, in contrast to the case of encryption.
And in fact, if you tried to modify CBC-MAC by including an IV,.
What you would get would be insecure.
Another difference is that in CBC-MAC, only the final value,
the output of the final invocation of the block cypher is output as the tag.
And, of course, this is
different from what we have in the case of CBC-mode encryption.
Where every output of this pseudo random function, every block.
Has to be output in order to enable decryption.
This means that when we verify the tag, when the receiver verifies the tag.
What they can do, is simply recompute the entire CBC-MAC and
check whether the result they get matches the tag that they've received.
And again if things are changed by outputting every block.
As the tag, then not only would that make the construction much less efficient.
All right, it would expand the length of the tag, but
it would again in fact make the construction insecure.
So both of these modifications relative to CBC mode encryption are in
fact essential for security of CBC MAC.
What can we say about the security of CBC MAC as we presented it?
Well it turns out that it's possible to prove the following result.
That if F is length preserving pseudorandom function.
Then for any fixed value l.
Were remember l represented the number of
blocks in the message that we were authenticating.
So for any fixed value l the basic CBC-MAC instruction is a secure MAC for
messages of length l times n.
So I'm assuming here that each block is n bits long.
And so an l block message has length ln bits.
Turns out that the proof here works by showing the CBC-MAC.
For a fixed length parameter, l is in fact a pseudorandom function.
And then very similar to what we saw in the last lecture,
we can use that to prove that CBC-MAC with a fixed length l is a secure MAC.
This issue of the fixed length parameter,
l is again something that is crucial for security.
And what I mean here by saying that we fix l.
Is that as part of the scheme, the sender and
receiver must agree on what length parameter they're going to use.
And the sender must agree to only authenticate messages
whose length is precisely l blocks.
And the receiver has to agree to only possibly accept messages if they're
exactly l blocks long.
and it will just,
it should just immediately reject if it ever gets a message whose length is
not equal to l blocks.
And once again, it turns out that if the sender and receiver aren't careful.
And either the sender will authenticate messages of different length or
the receiver will accept messages of different length.
Then basic CBC-MAC is not secure in that kind of a setting.
So what this means basically is that basic CBC-MAC can handle messages of arbitrary,
but fixed, length.
So we are doing better than the small, than, than,
the construction we saw last time.
Which could handle fixed length and short messages,
because now we are able to handle fixed length but much longer messages.
Now it turns out, further that there are ways to
modify CBC-MAC in order to handle messages of variable length.
So in practice this restriction to messages who's length is
exactly el blocks is not a reasonable one.
And we would like to obtain a construction that doesn't have that restriction and
there is various ways of doing that.
One of the simplest is to prepend the length of
the message before applying the CBC-MAC construction.
And this looks like the following.
So now to authenticate a message m1 through ml, where l can be anything.
What the sender will do is to encode the value l as a single block.
So represent l using m bits padding to the left if necessary with zeros.
And then just run the basic CBC-MAC construction on the encoded message,
as it were, l, m1, m2 up to ml.
And it turns out, as we said, that this will work and
this will give us a Q on MAC which can handle messages of any block length l.
So the sender can now authenticate.
Arbitrary length messages the receiver can safely accept.
Arbitrary length messages if it,
too prepends the length L, before applying CBC-MAC and checking the result.
Now, as I've described it here.
The extended var, variant of CBC-MAC assumes that
messages have length exactly a multiple of the block length.
This restriction can be waived also.
It's actually a little bit technical and
not cryptographically interesting and so I haven't shown that here.
But you should know that in fact,
CBC-MAC can be modified to handle really messages of any arbitrary length.
In the next lecture, we'll explore another approach for
constructing a secure MAC for variable length messages.
This one based on a new cryptographic primitive that we'll introduce there
called a hash function.
I'll see you next time
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.
