Cryptography Reference
In-Depth Information
to obtain the MAC(s). In this case, the attack represents an
adaptive chosen-
message attack
.
It goes without saying that chosen-message attacks are more powerful than
known-message attacks and that adaptive chosen-message attack are more powerful
than their nonadaptive counterparts.
Furthermore, an adversary may be required to perform different tasks in order
to be successful (i.e., to break the security of the system). The tasks lead to different
notions of security.
•
If the adversary is able to determine the secret key in use, then he or she
totally
breaks
the system. The result is a
total break
.
•
If the adversary is able to determine a MAC for a (typically meaningful)
message selected by him or her, then he or she
selectively forges
aMAC.
The result is a
selective forgery
.
•
If the adversary is able to determine a MAC for any (not necessarily mean-
ingful) message, then he or she
existentially forges
a MAC. The result is an
existential forgery
.
Obviously, a message authentication system is absolutely worthless if it does
not provide protection against a total break, and a message authentication system
that provides protection against an existential forgery is inherently more secure than
one that provides protection against a selective forgery.
Note that it is always possible to guess a MAC. If, for example, an authenti-
cation tag space has
n
elements, then a MAC can be guessed with a probability of
1
/n
(this probability is always greater than 0 for all
n
). More specifically, if
aMACis
n
bits long, then it can be guessed with a probability of 2
−n
=1
/
2
n
.
This probability can be made arbitrarily small by increasing the tag length. From an
adversary's viewpoint, the major question is whether he or she is able to verify his
or her guesses.
∈
N
•
If the adversary is able to verify a guess, we are in the realm of
verifiable
MACs
. In this case, the adversary can always try all 2
n
possible
n
-bit MACs
and find a correct MAC after 2
n−
1
guesses on the average.
•
If the adversary is not able to verify a guess, we are in the realm of
non-
verifiable MACs
. In this case, the adversary can only guess and hope that he
or she has found a correct MAC.
Whether a MAC is verifiable largely depends on whether the message it
authenticates is known to the adversary. If the adversary does not know the message,
then it is impossible for him or her to decide whether a specific MAC is correct.
