Dedicated Conventional Cryptographic Primitives - A Classical Introduction to Cryptography: Applications for Communications Security - page 81

x 1 x 2 x 3 ··· x n

⊕ ··· ⊕

C C C C

···

C

trunc

MAC

Figure 3.13. Encrypted CBC-MAC.

e − θ

2

/ 2 , he is likely to observe a collision: he gets a pair

of the attack), which is 1 −

( M 1 , c ) with the same MAC c . If the opponent can now request the

MAC corresponding to a message M 3 =

c ) and a pair ( M 2 ,

M 3

M 1 || obtained by concatenating M 1 with

any M 3 , he will get ( M 3 , c ). He will then be able to create a new pair ( M 4 , c ) with

M 3 . This attack is essentially optimal as the result in the next section shows.

M 4 = M 2 ||

A third idea consists of dropping a few bits to avoid collision attacks (see Fig. 3.13),
e.g. truncating the MAC to the first half of the bits. This is actually the ISO/IEC 9797
standard (Ref. [11]) MAC algorithm.

One problem remains: how to handle messages whose lengths are not multiples of
the block size? For this, three constructions called XCBC, RMAC, and TMAC has been
proposed. Furthermore, the key length in the previous constructions looks unnecessarily
long. A final variant called OMAC as “One-key CBC MAC” has been proposed as a
new standard (see Ref. [94]). OMAC is actually a family of MAC algorithms whose
OMAC1 seems to be the favorite instance at this time. An instance of the family is
defined by two constants Cst 1 and Cst 2 , a MAC length t , and a function H which maps
a message block and a constant to a message block. Given a message block L ,we
let H L denote the function which maps the remaining constant to a message block.
OMAC works as follows. Let us assume that we are given a MAC key K and a message
M

=

x 1 || x 2 ||···|| x n where all x i (except x n ) are full message blocks and the length of

x n is at most the size of a full message block.

1. Let L be the encryption of the zero block, i.e. the message block whose all bits
are set to zero. Compute H L (Cst 1 ) and H L (Cst 2 ). (Note that this step can be
preprocessed for a given key K since it does not depend on the message M .)
2. If x n has not the full block length, concatenate it with a bit 1 followed by as
many bits as necessary (if any) to reach the block length. In the latter case, we
say that the message was padded.