Cryptography Reference
In-Depth Information
11.3
INFORMATION-THEORETICALLY SECURE MACS
As mentioned before, a MAC is information-theoretically secure if it is impossible
to forge a MAC. Let us begin with a simple and pathological example. We consider
the situation in which we want to authenticate the outcome of a random coin flipping
experiment. The outcome of the experiment is a single bit saying either H (standing
for “head”) or T (standing for “tail”). The secret key is assumed to consist of two
randomly chosen bits (i.e., 00, 01, 10, or 11) and the MAC consists of one single bit.
An exemplary message authentication system scheme is illustrated in Table 11.1.
The rows in the table refer to the four possible keys. If, for example, the secret key
shared between the sender and the recipient is 01 (i.e., the key found in the second
row) and the outcome of the experiment is a head, then HO is transmitted. Similarly,
if the outcome of the experiment is a tail, then we transmit T1 (for the same secret
key 01).
Table 11.1
An Exemplary Message Authentication System
H0
H1
T0
T1
00
H-
T-
01
H-
-
T
10
-
HT-
11
-
H-
T
If we talk about information-theoretically secure message authentication sys-
tems and MACs, then we must be sure that every key can be used only once (this is
similar to the one-time pad in the case of information-theoretically secure symmet-
ric encryption systems). In the example given earlier, this means that we need 2 n
bits of keying material to authenticate n outcomes of the random experiment in an
information-theoretically secure way. If, for example, we wanted to authenticate the
sequence TTHTH using the five keys 00, 10, 11, 11, and 01, then we would actually
transmit T0, T0, H1, T1, and H0. We hence need a 10-bit key to authenticate a 5-bit
message.
In this example, the bit length of the MAC is one. Consequently, an adversary
can guess a MAC with a probability of 2 1 =1 / 2 1 =1 / 2. To show that the
message authentication system is secure, we must show that an adversary has no
better possibility to forge a MAC (for a message of his or her choice) than to guess.
We consider the case in which the adversary wants to forge a MAC for the message
H (for the message T, the line of argumentation is similar). Assuming all four keys
occur with equal probability (i.e., probability 1 / 4), the MAC is 0 for two out of
four possibilities (i.e., 00 and 01) and 1 for the other two possibilities (i.e., 10 and
Search WWH ::




Custom Search