Just as with encryption algorithms and hash functions, we
can group attacks on MACs into two categories: brute-force attacks and
A brute-force attack on a MAC is a more difficult undertaking than a
brute-force attack on a hash function because it requires known message-tag
pairs. Let us see why this is so. To attack a hash code, we can proceed in the following
way. Given a fixed message x with n-bit hash code h = H(x), a brute-force method of finding a collision is to pick a random bit string y and check if H(y) = H(x). The attacker can do this repeatedly off line. Whether
an off-line attack can be used on a MAC algo- rithm depends on the relative size of the key and the tag.
To proceed, we need to state the desired
security property of a MAC algo- rithm, which can be expressed as follows.
Computation resistance: Given one or more text-MAC pairs
[xi, MAC(K, xi)], it is
computationally infeasible to
compute any text-MAC pair [x,
MAC(K, x)] for any new input x |=xi.
In other words, the attacker would like to
come up with the valid MAC code for a given message x. There are two lines of attack possible: attack the key space and
attack the MAC value. We examine each of these in turn.
If an attacker can determine the MAC key,
then it is possible to generate a valid
MAC value for any input x. Suppose
the key size is k bits
and that the attacker
has one known text–tag pair. Then the attacker can compute the n-bit tag on the known text for all possible keys. At least one key is guaranteed to produce the cor-
rect tag, namely, the valid key that was initially used to produce
the known text–tag pair. This phase of the attack
takes a level of effort proportional to 2k (that
is, one operation for each of the 2k possible key values).
However, as was described earlier, because the MAC is a many-to-one mapping,
there may be other keys that produce the correct value. Thus, if more than one key is found
to produce the correct value, additional text–tag pairs must be
tested. It can be shown that the level of effort
drops off rapidly with each additional text–MAC pair and that the
overall level of effort is roughly
An attacker can also work on the tag without
attempting to recover the key. Here, the objective is to generate a valid tag
for a given message or to find a message that matches a given tag. In either
case, the level of effort is comparable to that for attacking the one-way or
weak collision-resistant property of a hash code, or 2n. In the case of the MAC, the attack cannot be conducted
off line without further input; the attacker will require chosen text–tag pairs
or knowl- edge of the key.
To summarize, the level of effort for
brute-force attack on a MAC algorithm can be expressed as min(2k, 2n). The assessment of
strength is similar to that for symmetric encryption algorithms. It would
appear reasonable to require that the key length and tag length satisfy a
relationship such as min(k, n) Ú N, where N is
perhaps in the range of 128 bits.
As with encryption algorithms and hash
functions, cryptanalytic attacks on MAC algorithms seek to exploit some
property of the algorithm to perform some attack other than an exhaustive
search. The way to measure the resistance of a MAC algorithm to cryptanalysis
is to compare its strength to the effort required for a brute-force attack.
That is, an ideal MAC algorithm will require a cryptanalytic effort greater
than or equal to the brute-force effort.
There is much more variety in the structure
of MACs than in hash functions, so
it is difficult to generalize about the cryptanalysis of MACs. Furthermore, far less work has been
done on developing such attacks. A useful survey of some methods for specific MACs is [PREN96].