Cryptography Reference
In-Depth Information
•
A
(
,
)
finally outputs a message/tag pair
m
t
. Then
D
queries its oracle on
m
and
t
.If
t
t
and
(
)
=
=
A
obtains as response
f
m
did not query its oracle on
m
, then
D
outputs 1, otherwise it outputs 0.
Let us now analyze
D
's advantage in the distinguishing experiment. If
D
is given
oracle access to a random function from
n
, then the view of
{
0
,
1
}
A
when run as
in experiment
Mac
uf-cma
indicated above is identical to the view of
since a
random function is used to compute the tags. On the other hand, if
D
is given oracle
access to some
F
k
, for a randomly chosen
k
, then the view of
A
A,
i
I
(
n
)
A
is the same as in
experiment
Mac
uf-cma
's oracle queries,
D
computes
the answer by using
F
k
. In both cases,
D
outputs 1 exactly when
A
,
I
(
n
)
because when answering
A
succeeds in the
corresponding authentication unforgeability experiment. Therefore we have, bearing
in mind Definition 4.2 and also the fact that
F
is a pseudo-random function, that there
exists a negligible function
negl
(
A
n
)
such that
Adv
prf
D
Adv
uf-cma
Adv
uf-cma
Adv
uf-cma
2
−
n
F
(
n
)
=|
A,I
(
n
)
−
A,
i
I
(
n
)
|=|
A,I
(
n
)
−
|≤
negl
(
n
).
,
This clearly implies that
Adv
uf-cma
2
−
n
A,I
(
n
)
≤
+
negl
(
n
)
, so that the adversary's
advantage is negligible and the proof is complete.
Remark 5.2
This construction can be implemented in practice by using a block
cipher
F
but it has the serious drawback that then the message length will be equal to
the block length, which is too short for practical use. However, there is the possibility
of extending this construction to variable-lengthmessages in such away that theMAC
obtained remains UF-CMA secure as proved, for example in [109, Theorem 4.6].
But this construction is very inefficient and there are more efficient ways of obtaining
secure MACs as we will see in the next sections.
implementation of the MAC
I
F
defined above, when
F
is the AES forward cipher
function.
5.3.2 CBC-MAC
One basic idea that permits the construction of a block cipher-based MAC which is,
at the same time, both efficient and secure, is to use as
Mac
algorithm CBC mode
on top of a block cipher
F
. The idea is simply to encrypt the message (which, after
padding, will consist of an integer number of blocks) in CBC mode with the 0 vector
as IV, and then to take the last ciphertext block as the message tag. In this case,
Gen
will simply choose the key uniformly at random and
Ve r
is the canonical algorithm
that given a key
k
, a message
m
, and a tag
t
, computes
Mac
and checks whether
its value is equal to
t
, outputting 1 in this case and 0 otherwise. Thus we only need
to define
Mac
, which is the following algorithm:
(
k
,
m
)
