Cryptography Reference
In-Depth Information
We are going to present one variant of CBC-MAC that has been specified by NIST
under the name of CMAC (see [69]) and has a security reduction as shown in [105].
We also give an implementation of CMAC in Maple using AES as block cipher.
5.3.3 CMAC and Its Maple Implementation
The core of the CMAC algorithm is a variation of CBC-MAC that Black andRogaway
proposed under the name XCBC and that was later improved under the name OMAC
by Iwata and Kurosawa. CMAC is the NIST specification of OMAC1, one of the
variants of OMAC. In XCBC, the padding algorithm (the 10
i
padding) is modified
by not adding an extra block whenever the bit length of the message is already a
nonzero multiple of 128. In addition to the block cipher key
k
(anAESkeyinour
case), two additional keys
k
1,
k
2 are used. If no padding was added, the algorithm
is the same as CBC-MAC except for the fact that, before encrypting the last block
with
k
, this block is Xor-ed with
k
1. If, on the other hand, padding was added, then
a similar operation is performed, Xor-ing the last block with
k
2 before encryption.
CMAC proceeds in a similar way, except for the fact that keys
k
1 and
k
2 are not
independent from
k
but are derived from it. This is done as follows. Consider the field
F
2
128
defined by the irreducible polynomial
x
128
x
7
x
2
+
+
+
x
+
1of
Z
2
[
x
]
(this is
the “first” irreducible polynomial of degree 128 over
Z
2
as we saw in Example 2.26).
The elements of this field can be represented, as we have seen, by the integers in
the 0
2
128
-1 range and hence by the 128-bit (or 16-byte) vectors (where we assume
that the most significant bit—or byte—is the leftmost one). Let
L
..
0
128
=
F
k
(
)
be the
result of encrypting the 0-block with AES using
k
as key.
L
belongs to
F
2
128
and the
CMAC subkeys
k
1 and
k
2 are obtained by taking
k
1
=
2
·
L
and
k
2
=
4
·
L
, where '
·
'
denotes multiplication in
F
2
128
. Then the algorithm proceeds in the same way as
XCBC explained above.
As seen in Exercise 5.5, CBC-MAC is not CMA secure if 10
i
padding is used
but messages whose length is a multiple of the block length are left unpadded, for
then a forgery may be trivially constructed by finding two different messages with
the same tag. This is precisely the padding method used in CMAC but now there is
the additional operation of Xor-ing the last block with either
k
1
or
k
2
and this is what
makes it hard to produce forgeries where two different messages have the same tag.
CMAC may thus be regarded as CBC-MAC with a modified padding algorithm that
is key-dependent, if we regard Xor-ing the last block with one of the subkeys as part
of the padding. Since the subkeys are different, an adversary will be able to find two
messages which have the same tag only with negligible probability.
We start by giving an auxiliary function to make a cyclic left shift on the list of
bits corresponding to a 16-byte list:
> rotatebitsleft := proc(bytes)
uses ListTools;
map(bitstobyte, [LengthSplit(Rotate(Flatten(map(bytetobits, bytes)), 1), 8)])
end proc:
