Question

An engineer Bob proposes the following long-input MAC based on a PRF "F" (you may think of "F" as AES encryption): for all "i" (where "i" is a block number, 1 £ i £ L , and "L" is the number of blocks): compute y[i] = F(k,m[i]), then XOR them together, i.e.: tag = y[1] Å y[2] Å … Å y[L]. Bob’s argument: since "F" is a PRF, the adversary cannot generate a tag (without knowing the key "k"), therefore the proposed MAC is secure.

Task: Show an attack, where the adversary can easily produce a message/tag pair, which was not generated by the challenger.
Hint: Consider the MAC security game

Answer 1

An attack on Bob's MAC scheme involves an adversary observing two valid message/tag pairs and then generating a new message/tag pair by exploiting the XOR property of the MAC computation. This replay and combination attack shows that the MAC is insecure because the adversary can forge a message/tag pair without the secret key.

Step-by-step explanation:

The student is asking about a cryptographic attack on a MAC (Message Authentication Code) that is based on a pseudo-random function (PRF), commonly exemplified by the AES encryption algorithm. The engineer, Bob, suggests a method to compute a MAC by applying the PRF to each block of the message and then XORing all of the results together to obtain a tag. However, there is a flaw in this approach that can be exploited by an adversary.a

To demonstrate the vulnerability, consider the standard MAC security game. In this game, an adversary tries to forge a MAC for a message that they have not been given by the challenger (who possesses the secret key). The adversary has observed valid message/tag pairs created with the key "k".

Here is an attack exploiting the XOR property of the proposed MAC scheme:

• The adversary observes two valid message/tag pairs, say (m1, tag1) and (m2, tag2), where tag1 and tag2 are the results of XORing the blocks of m1 and m2, respectively.
• The adversary can now generate a new message by concatenating m1 and m2 (or by interleaving blocks from m1 and m2 in any fashion). By the properties of XOR, the resulting tag for this new message is simply tag1 Å tag2.
• Because XOR is associative and commutative, the order of the blocks does not matter for the resulting tag. Thus, the adversary has successfully generated a new message/tag pair without knowing the secret key "k".

This kind of attack is known as a replay and combination attack. It demonstrates that Bob's proposed MAC scheme, while utilizing a PRF, fails to account for the properties of XOR, rendering it insecure because it allows an adversary to forge valid message/tag pairs without knowledge of the key.