Cryptography Reference
In-Depth Information
always possible. However, the work in [27] demonstrates that, for universal hash
functions based MACs, once a successful forgery is achieved, subsequent forgeries
can succeed with high probabilities. The main idea in their attacks is to look
for a collision in the message compression phase. Once a message that causes a
collision is found, partial information about the hashing keys can be exposed.
Using this key information an attacker can forge valid tags for fake messages.
We give a detailed example below.
Example 1.
Consider the universal hash family presented in this paper. Assume
an adversary calling the signing oracle on
M
=
m
1
||
m
2
, thus obtaining its
authentication tag
τ
. The adversary now can call the verification oracle with
M
=
m
2
||
m
1
and the same tag
τ
. Obviously, the verification will pass if and
only if
k
1
≡
k
2
m
1
+
k
1
m
2
mod
p
).
Although the verification will pass with a small probability, the adversary
can continuously call the verification oracle with
M
=
m
2
||
k
2
mod
p
(in which case
k
1
m
1
+
k
2
m
2
≡
α
i
m
1
,fordifferent
α
i
's until the message is authenticated. Let
M
=
m
2
||αm
1
be the message that
passes the verification test, for some
α ∈
Z
p
. Then, the relation
k
1
≡
βk
2
mod
p,
(11)
m
2
)
−
1
is exposed. With this knowledge, a man in the
middle can always replace the first two blocks,
m
1
||
where
β
=(
αm
1
−
m
2
)(
m
1
−
m
2
, of any future message
M
with
β
−
1
m
2
||
βm
1
without violating its tag. This is because
k
1
(
β
−
1
m
2
)+
k
2
(
βm
1
)=
k
2
m
2
+
k
1
m
1
regardless of values of
m
1
and
m
2
.
Handschuh and Preneel [27] defined three classes of weak keys in universal hash
functions. Each class can be exploited in a way similar to the one discussed in
the above example to substantially increase the probability of successful forgery
after a single collision. This attack is shared by all universal hash based MACs
[27]. As per [27], the recommended mitigations to this attack are to use the less
ecient block cipher based MACs, or not to reuse the same hashing key for
multiple authentication.
Compared to standard MACs, however,
-MACs can utilize the structure
of the
E
&
A
system to overcome the key-recovery problem discovered in [27].
Consider the
E
E
-MAC proposed in Section 4, and recall that a random number
r
∈
R
Z
p
is generated internally in the
E
&
A
process. In the basic construction
of Section 4, the goal of
r
is to encrypt the authentication tag. However, the
random
r
can play a pivotal role in key-recovery security.
In the basic construction in Section 4, the universal hashing key is
K
=
k
1
||
k
2
||···||
k
B
and the authentication tag is computed as:
B−
1
τ
=
k
i
m
i
+
k
B
r
mod
p.
(12)
i
=1
Now, with the same shared key, consider another use of
r
. More specifically, let
the authentication tag be computed as follows:
B−
1
τ
=
(
k
i
⊕
r
)
m
i
+
k
B
r
mod
p.
(13)
i
=1
Search WWH ::
Custom Search