Cryptography Reference
In-Depth Information
11.2.4
MACs Using Families of Universal Hash Functions
At the end of Chapter 8, we mentioned that universal hashing as originally proposed
in [18] provides an interesting design paradigm for cryptographic hash functions in
general, and message authentication in particular [19]. After the initial work of Larry
Carter and Mark Wegman, the use of universal hashing for message authentication
was further explored by Gilles Brassard [20] and many other researchers (see, for
example, [21]). Most of these constructions use two-universal families of hash
functions. In short, a family
H
of hash functions
h
:
X
→
Y
is two-universal if
for every
x, y
∈
X
with
x
=
y
1
Pr
h∈H
[
h
(
x
)=
h
(
y
)]
≤
.
|
Y
|
As of this writing, the most important MAC that uses families of universal
hash functions is known as
universal MAC
(UMAC) [22]. The output of the UMAC
construction is a 32-, 64- or 96-bit authentication tag (depending on the user's
preference). A 64-bit authentication tag is recommended for most applications.
Let
H
be a two-universal family of hash functions and
F
beaPRFfamily
(see Chapter 13) that generates outputs of the same length. A secret key
k
is used to
select a hash function
h
k
from
H
and a PRF
f
k
from
F
. The hash function
h
k
is then
used to hash a given message into a short string, and the short string is encrypted by
adding it modulo 2 to a string that is generated with the PRF
f
k
and a random value
(i.e., nonce)
r
. Consequently, the authentication tag
UMAC
k
(
m
) is constructed as
follows:
UMAC
k
(
m
)=
f
k
(
r
)
⊕
h
k
(
m
)
In this notation,
r
refers to the nonce that must change with every authen-
tication tag. The recipient needs to know which nonce was used by the sender,
so some method of synchronizing nonces needs to be used. This can be done by
explicitly sending the nonce along with the message and the tag (in this case,
r
and
UMAC
k
(
m
) must be sent together) or agreeing upon the use of some other
nonrepeating value such as message number. The nonce need not be kept secret, but
care needs to be taken to ensure that, over the lifetime of the shared secret key
k
,a
different nonce is used with each message
m
.
