Cryptography Reference
In-Depth Information
Attack Against Secret Prefix MACs
Alice
Oscar
Bob
x
=(
x
1
,...,
x
n
)
m
=
h
(
k
||
x
1
,...,
x
n
)
(
x
,
m
)
←−−−−−−
intercept
x
O
=
(
x
1
,...,
x
n
,
x
n
+1
)
m
O
=
h
(
m
||
x
n
+1
)
(
x
O
,
m
O
)
←−−−−−−
m
' =
h
(
k
||
x
1
,...,
x
n
,
x
n
+1
)
since
m
' =
m
O
⇒
valid signature!
Note that Alice will accept the message (
x
1
,...,
x
n
,
x
n
+1
) as valid, even though
Bob only authenticated (
x
1
,...,
x
n
). The last block
x
n
+1
could, for instance, be an
appendix to an electronic contract, a situation that could have serious consequences.
The attack is possible since the MAC of the additional message block only needs
the previous hash output, which is equal to Bob's
m
, and
x
n
+1
as input but not the
key
k
.
Attacks Against Secret Suffix MACs
After studying the attack above, it seems to be safe to use the other basic con-
struction method, namely
m
=
h
(
x
k
). However, a different weakness occurs here.
Assume Oscar is capable of constructing a collision in the hash function, i.e., he can
find
x
and
x
O
such that:
||
h
(
x
)=
h
(
x
O
)
.
The two messages
x
and
x
O
can be, for instance, two versions of a contract which
are different in some crucial aspect, e.g., the agreed upon payment. If Bob signs
x
with a message authentication code
m
=
h
(
x
||
k
)
m
is also a valid checksum for
x
O
, i.e.,
m
=
h
(
x
||
k
)=
h
(
x
O
||
k
)
The reason for this is again given by the iterative nature of the MAC computation.
Whether this attack presents Oscar with an advantage depends on the parameters
used in the construction. As a practical example, let's consider a secret suffix MAC
which uses SHA-1 as hash function, which has an output length of 160 bits, and
a 128-bit key. One would expect that this hash offers a security level of 128 bits,
