Cryptography Reference
In-Depth Information
We say that it is
ε
-strongly-universal
if for any
x
=
y
and any
a
and
b
we have
#
=
,
=
≤
Pr[
H
(
x
)
a
H
(
y
)
b
]
D
D
where
is the output domain of
H
.
A MAC algorithm is actually a random hash function whose distribution is defined
by the secret key choice. We can construct a secure MAC from a universal hash function
by simply encrypting the output with the Vernam cipher.
Theorem 3.6 (Wegman-Carter 1981 [184]).
Let
(
h
K
)
K
∈
U
K
be a family of hash func-
tions over the output domain
m
defined by a random key K which is chosen uni-
{
0
,
1
}
formly at random in a key space
K
. We assume that this family is
ε
-strongly-universal.
Given K and a sequence of keys K
1
,
K
2
,...,
which are independent and uniformly
m
, we define a MAC algorithm which changes the key for every
new message. Namely, the MAC of the message x
i
of sequence number i is defined by
distributed over
{
0
,
1
}
c
i
=
h
K
(
x
i
)
⊕
K
i
An authenticated message is a triplet
(
x
i
,
c
i
)
,wherec
i
is computed as above. No
chosen message attack can forge a new authenticated message with a probability of
success greater than
i
,
ε
.
Hugo Krawczyk improved this result as follows.
Theorem 3.7 (Krawczyk 1994 [108]).
Following the same notations, we say that h is
ε
-
XOR-universal
if for any x
=
y and any a we have
Pr[
h
K
(
x
)
⊕
h
K
(
y
)
=
a
]
≤
ε.
The previous theorem still holds when the strong-universality hypothesis is replaced by
XOR-universality.
Clearly, a
ε
-strongly universal hash function is
ε
-XOR-universal, so this result is
stronger.
Proof.
At the end, the adversary knows
d
authenticated messages (
x
i
,
,
=
i
c
i
) for
i
1
,...,
d
and forges (
x
,
j
,
c
) with
x
=
x
i
for any
i
. The
K
and
K
j
keys are conditioned
to the knowledge of all (
x
i
,
i
,
c
i
).
d
] interval, then
K
j
is uniformly distributed and independent
from this information, so the probability that
c
is a valid MAC of (
x
If
j
is not in the [1
,
j
)is2
−
m
. (Note that
,
must be greater than 2
−
m
,so
c
is valid with probability
if
h
is
ε
-XOR-universal, then
ε
less than
ε
.)
Search WWH ::
Custom Search