Cryptography Reference
In-Depth Information
11). Consequently, the adversary has a 2
/
4=1
/
2 chance of correctly guessing the
MAC, and there is nothing else he or she can do to increase his or her odds.
Note that this line of argumentation (about the security of a message authenti-
cation system or MAC) also applies if the sender provides a message with a correct
MAC and the adversary wants to modify the message (and its MAC). Going back to
our example, let us assume that the adversary has received H0, that he or she wants
to change the message from H to T, and that he or she wants to generate a valid MAC
for the new message (without actually knowing the secret key). If the adversary has
received H0, then the only possible keys are 00 and 01 (according to Table 11.1):
•
If 00 is the proper key, then the message T must be authenticated with 0, and
the adversary must change the message to T0.
•
Similarly, if 01 is the proper key, then the message T must be authenticated
with 1, and the adversary must change the message to T1.
In either case, the adversary has a probability of 1
/
2 to correctly guess the
proper key and to correctly change the message accordingly. Again, there is nothing
the adversary can do to increase the probability.
In lossy and unreliable networks, one may be concerned about the error
probability of a message authentication system. In this case, it is always possible to
reduce the error probability of a message authentication system simply by appending
s
MACs instead of just one. Consequently, the message
m
is accompanied by
s
MACs. If each of these MACs requires
n
key bits, then the total amount of key bits
sums up to
s
n
. Also, if each MAC has an error probability of
, then the total error
probability of
n
MACs is
s
. In the example given earlier,
=1
/
2 and the total error
probability is (1
/
2)
s
.
Similar to information-theoretically secure encryption systems, information-
theoretically secure message authentication systems and corresponding MACs re-
quire keys of a specific size. It has been shown that it is possible to construct
information-theoretically secure message authentication systems and corresponding
MACs that require relatively short keys. The disadvantage of all of these schemes is
that a different key must be used for every message. If this is not acceptable, then
one can also generate the keys using a cryptographically strong PRBG (see Chapter
12). In this case, however, the resulting scheme is at most computationally secure.
This is similar to the approximation of a one-time pad using a PRBG in the case of
symmetric encryption systems.
·
