Cryptography Reference
In-Depth Information
Note that nonverifiable MACs are inherently more secure than their verifiable
counterparts (because it is not possible to find a correct MAC with a brute-force
attack). Also note that there is evidence that nonverifiable MACs really exist (even
if one assumes that the adversary knows the message to which a MAC is referring)
because, in principle, the verification of a MAC requires knowledge of the secret
key. From an adversary's viewpoint, however, it is sometimes possible to use an
entity that knows the key as an oracle. Consider, for example, an entity that knows
the key and provides an online service only if a request message is authenticated
with a MAC. In this case, the adversary can send (adaptively) chosen messages to
the server and look whether the server responds (in this case, the MAC is valid) or
not (in this case, the MAC is invalid). This type of chosen-message attack is often
considered when one analyzes the security of cryptographic protocols.
As mentioned earlier, a message authentication system is secure if an adver-
sary has no better possibility to forge a MAC than to guess. More specifically, even if
we assume that an adversary is able to perform an adaptive chosen-message attack,
we want to be sure that it is impossible or computationally infeasible for him or her
to (existentially or selectively) forge a MAC. In the first case (i.e., if it is impossible
for him or her to forge a MAC), then the message authentication system (or the
MACs, respectively) is (are) called
information-theoretically secure
. In the second
case (i.e., if it is computationally infeasible for him or her to forge a MAC), then the
message authentication system (or the MACs, respectively) is (are) called
computa-
tionally secure
. Because computationally secure MACs are more widely deployed
in practice, we begin with them.
11.2
COMPUTATIONALLY SECURE MACS
There are many possibilities to design and come up with MACs that are computa-
tionally secure. Examples include:
•
MACs that use symmetric encryption systems;
•
MACs that use keyed hash functions;
•
MACs that use pseudorandom functions (PRFs);
•
MACs that use universal hash functions.
In addition to these four classes that are overviewed and briefly discussed next,
some outdated proposals are standardized but not widely deployed. For example,
the
message authenticator algorithm
(MAA) as specified in ISO 8731-2 [1] was
published in 1984. Until today, no significant structural weakness has been found in
