In this video, we will discuss message authentication codes
or Mac.
We start by defining the security guarantees that Mac
provide and what are they useful for?
We will see how we construct Mac from log ciphers
and from cryptographic hash functions.
We look at both secure and insecure constructions
and discuss an example of variability we
have with an N secure Construction.
We have seen in the previous video how using cryptographic hash
function retrieve message integrity.
for instance at least sends a message and its
corresponding digest why to Bob
and Bob does the Integrity verification by recomputing
the digest and comparing it with
the digest sent by Alice.
This way Pope is sure that the message was not
modified during its transmission.
Nevertheless Bob has no guarantee
about the origin of the message.
An adversary can pretend to be Alice and
send a pair of message that passed the
Integrity verification of Bob.
If Bob would like to check the origin of
the message.
the digest must be transmitted through secure Channel
which guarantees the authenticity
for example in the previous video. We
have seen that Bob obtained the digest of some
Ubuntu image from the official
Ubuntu website. So he was sure that
the digest comes from Ubuntu and not
from adversary.
So if Bob wants to verify the authenticity of
the message X.
Alice must transmit the dangerous through another authenticator
channel. For example her website that
Bob trusts.
But you see this is a constraint that we
cannot always fulfilling several applications.
And this is exactly the problem that message authentication
codes or Mac proposed to
solve.
They guarantee the authenticity of a message.
even over an insecure Channel
Mac requires that the key K was
generated and distributed to both
Alice and Bob
using this key K and the message X
at least computes or code C.
And Depends it to her message X.
And she sends the pair xnc to
Bob.
Bob that has the key can be compute the
Mac on the message you received.
And can check that the computed code.
C Prime matches with the code here received from
a party that pretends to be Alice.
If the verification passes Bob can conclude
that the center of the message must be Alice.
the security guarantees that we need from Mac is
that an adversary that does not
have access to the key k
is unable to forge new messages.
in other words
an adversary is not able to create new pairs of
messages and corresponding valid codes.
Let's better clarify this unforgibility guarantee
of Mac.
We assume that adversary.
Has already intercepted several pairs of messages denoted
by X1 X2
all the way to xn.
And their respective goals C1 C2
all the way to CN.
So remark here.
In the notation, we are using the super scripts to
distinguish messages, but it doesn't
mean that these are like powers of some X interests
notation to say that.
The message X1 was sent first then
X2 Etc.
So we expect the unforgibility guarantee to
prevent these adversary from
being able to create a pair of new message.
X and plus 1 and its corresponding
code C and plus 1
that passes the Mac check that Bob's runs.
We call this attack of creating a
new pair of message and code macfoldery.
In a couple of slides. We'll see how the adversary
can succeed to do a Mac forgery on our
Mac Construction. That was not insecure.
Now we'll move to see how we can construct message authentication
codes from the cryptographic algorithms
that we have already seen.
We'll start with the idea of using block
ciphers and in particular
the CDC mode of operation that
we have seen in section 2.
Remember that CBC does a training of
the outputs of the encryption function using an
xor operation?
The CDC Mac Construction is
as follows.
We divide the message X into n blocks.
Each block is of the size of the encryption function.
So for example, if we are using as encryption
function, then we
have blocks of 128 bits.
We encrypt the blocks following CBC Style.
And we take the last encrypted block of
the CBC encryption of the message as the
Mac.
a couple of remarks here
first remark
unlike what we have seen with encryption for CBC Mac
Allison ball.
before exactly the same operations
that's why we are only using the
Encryption function that is denoted by E. We don't
use at all the decryption function the like
we have seen with
regular encryption encryption flow
secondary mark
with Mac
like with encryption we need key. We
just omit to represent the key in
the diagram, but keep in mind the key is always there.
And it is the second input to the encryption function
and it is the same for all the blocks.
Great, we should be done for our first Mac
Construction, but unfortunately this construction is
unsecure.
The previous construction is insecure.
Because an adversary who intercepted messages on
the communication channel is able to do a
Mac filtering.
Let's see scenario that leads to search Mac
rotary.
Here, we assume that Alice sent three
messages.
X1 X2 and X3
of this format. So X3 is
the concatenation of X1 and some Block B.
if the adversary intercepts all these
Messages and their corresponding codes then
the adversary is able to submit
a new pair X4.
Which is of this format X2 concatenated with
B Prime?
And its corresponding code to
Bob.
By only manipulating the messages that he intercepted
he is able to do such forgery.
Let's see how we can do that. Okay. So
let's we go back to how we Define
our CBC Mac Construction. So remember
this is a schema of
the construction.
And we will write the equations particularly for
the third message. So the
third message X3 is of this format X1
xorbed sort X1
concatenate with B.
Then the code C3.
is actually
the encryption of the last
output
which is actually C1 here.
Exhort with a B that is here.
all this was encrypted under the encryption
function e with a key k
So this is how we computed the C3 here.
So if the adversary defines now B Prime as B
xor C1 xor
C2
Let's look now at the message authentication
code of X4.
So X4 remember is of this format X2 concatenated
with B Prime and
similar to what we have done for the C3
here this x2exort with
P Prime.
leads that we have here C2 and
here B Prime that is
exalt then encrypted.
So the C4 is the encryption
of C2 xor
with d Prime.
and
remember this equality. This Excel is
equal to C1 exalt with
B.
And a C1 exhort with me that's exactly the C3
that we have seen here.
So actually C4 is equal to C3.
So the adversary didn't need to
compute C4. He has it already and
that's how he can create new valid
pair X4 and C4 without
knowing the key.
To fix the variability that we have seen.
We can encrypt the last encrypted block.
of the CBC encryption with a new key
key Prime
having this last encryption with the new key
prevents an adversary from being able
to create new messages that satisfies some
relationship with previous messages that he
intercepted.
You can take the time to return to the previous attack and
verify yourself. That is no longer applicable.
I think it's a good exercise to strengthen your
understanding.
And also make Mac from cryptographic hash
functions.
This is a construction called hmac that
was published as the internet standard
RFC 2104. We
assume that we are given some cryptographic
hash function h.
Which internally processes messages by blocks
of b-bytes?
and produces in digest of L bytes
the construction relies on
two bit strings named iPad and
opad
each is of length B bytes.
iPad consists of B bytes equal to
the value
36 in hexadecimal
opad consists of b-bytes equal to 5c
in hexadecimal
Computing the mark of message X under
a key K is as follows
if the key is shorter than b we
need to pad it with zeros to
have exactly B bytes.
Once the padded key is of length
B bytes. We accelerate with
iPad, which remember is of length also B
bytes.
Then the output is
concatenated with the message X.
And the whole thing is hashed
with the hash function
each.
Then the result is concatenated
with the xor of
opat with the padded key.
to construct a new block
This block is hashed a second time.
And we finally truncate the result to its.
T left most bytes
and this is how we obtain the hmac of
X under the key k
This construction was proven to be secure and
is today the standard of Mac
from cryptographic hash functions.
The following table summarizes some of
the main hash Mac algorithms using the
Shell 256 hash functions family.
Each algorithm is specified by three lengths B
L and T.
B corresponds to the input length to the
hash function
L corresponds to the output length of the hash function
while T is the size of the truncated final
output.
the hashmaksha256
algorithm operates on 512 bit blocks
of data.
while the
hashmaksha, 384 and
hashmaksha 512 algorithms
operate on blocks of
length 1024 bits
as we have seen in the previous video.
Shot 256 gives the digest of
length 256 while Shah
300 84 gives.
digest of length 304
and the same for 512
and the truncation in this algorithms divides
the length of the output by two. So
as you see for the first algorithm the truncated
length is 128 or for
the second one is 192. And
for the last one 256
So you can notice here the convention of the naming of
each hmac algorithm. So the
first part here corresponding to the hash function.
And then the second part corresponds to
the truncation.
length
So this is how we name each of these hash
Mac algorithms.
We have seen in this video message authentication codes
or Mac and how they provide us
with a way to ensure the Integrity of the message and
the origin Authentication.
We discussed how we construct Mac from other symmetric
key cryptographic algorithms such as
block ciphers using CBC mode of operation and
cryptographic hash functions.
With this video we reach the end of our third section of
the course and also the end of our journey
through symmetric key cryptography.
In this introductive course, we present to
you the main cryptographic Primitives. However, there
are other useful symmetric key to Primitives
for instance cryptographic to
the random machine readers or key derivation
functions.
We hope you enjoyed this journey through the universe of
symmetric key cryptography.
In the next video, we'll switch to another exciting branch
of cryptography the famous
public key cryptography.
So see you in the next section.