Cryptography Reference
In-Depth Information
Algorithm 5.1. CBC-Mac
.
Input
:An
l
-block message
m
=
m
1
...
m
l
, and a block cipher key
k
.
Output
:Thetag
t
l
.
Tag computation
:
t
0
:=
0
n
;
for
i
from
1
to
l
do
t
i
:=
F
k
(
m
i
⊕
t
i
−
1
)
end do
;
return
t
l
.
When CBC mode is used for encryption, it is crucial that the IV must be
unpredictable and this is the reason why it is chosen at random. However, in the
authentication version of CBC the IV is not random and this is for a good reason as
the following exercise shows:
Exercise 5.3
Prove that the variant of CBC-MAC which chooses
t
0
uniformly at
random in
n
and outputs
t
0
||
{
0
,
1
}
t
l
as tag is not CMA secure.
Remark 5.3
The CBC-MAC construction is CMA secure as long as it is applied
to messages of fixed length
l
n
as was proved in [15], see also [90, Theorem 9.5]
and [109, Theorem 4.10]. However, CBC-MAC is not CMA secure when applied
to messages of variable length. Indeed, suppose that an adversary obtains the valid
pairs
·
(
m
1
,
t
1
)
and
(
m
1
||
m
2
,
t
2
)
. Then the adversary outputs the pair
(
m
2
⊕
t
1
,
t
2
)
and
has advantage 1 in the authentication unforgeability experiment because
m
2
⊕
t
1
=
m
1
,
m
1
||
m
2
and, by the above algorithm,
Mac
k
(
m
2
⊕
t
1
)
=
F
k
(
m
2
⊕
t
1
⊕
t
0
)
=
t
2
. In this case we see that only two oracle queries are sufficient for
a security break.
F
k
(
m
2
⊕
t
1
)
=
There are several known ways to obtain versions of CBC-MAC that are CMA
secure for variable-length messages, cf. [109, 4.5] for an outline. For example, one
method described in [15] consists simply of
prepending
the message
m
to be authen-
ticated with an
n
-bit encoding of the message length len
. However, the method
consisting of
appending
the length of the message as the last
n
-bit block is not secure
as the following exercise shows:
(
m
)
Exercise 5.4
Show that the variant of CBC-MAC that appends to the message a
block encoding the message length before computing the tag, is not CMA secure
when messages of varying length are used. (Hint: Consider three arbitrary
n
-bit
blocks
x
,
y
,
z
, such that
x
=
y
. Query the oracle about
x
,
y
, and
x
||
1
||
z
to obtain
the corresponding tags. Then consider the message
y
z
and check that the tag corresponding to this message is the same as the tag for the
message
x
||
1
||
Mac
k
(
x
)
⊕
Mac
k
(
y
)
⊕
||
1
||
z
.)
Exercise 5.5
Prove that the version of CBC-MAC that uses the 10
i
padding algo-
rithm for messages whose length is not a multiple of the block length
n
but does not
add an extra block whenever the length of the message is already a multiple of
n
,is
not CMA secure.
