Earlier on page 193 he introduces CBC (Cipher Block Chaining mode), upon which CBC-MAC is based, and recommends it for many applications. Both protocols are in various standards.
As far as I can tell these are each strong protocols for doing what they are designed to do and yet if they are used together in the most obvious way, the authentication function fails silently; it decrypts bogus cipher text and calls it authentic!
This sort of MAC requires that the authenticator and authenticated share a secret. It is not, after all, a digital signature, where the authenticator need not and must not be able to produce the signature.
E and D are two boxes in a one way data stream performing CBC with some shared secret key which we need not name. We consider here the text in one packet which is to be kept secret and checked for authenticity. The blocks of the text to be protected during transmission are Pi for i from 1 thru n. The CBC-MAC is tantamount to adding another block Pn+1 = 0 to the end of the message. The resulting cipher block, Cn+1, will be the MAC. If our encryption of a message diffused the bits of the message thruout the entire ciphertext, as a block cipher is supposed to diffuse bits thruout an entire block, then the recipient could authenticate the message by merely verifying that the last decrypted block of the message was indeed 0. CBC is self synchronizing, however, and this is incompatible with total diffusion. If Mallet modifies a bit in the transmitted cipher text more than two blocks from the end of the transmission, then the last block will still decrypt to 0, despite two earlier garbled blocks.
D can clearly recompute the CBC-MAC as prescribed by Schneier and compare it explicitly with Cn+1. It would be slick and probably edifying if that calculation were folded into the decryption that is D’s primary function. If this cannot be done I want to understand why.
Let us Calculate.
Take C0 = iv, a value somehow agreed upon by sender and receiver and unknown to Mallet.
Now we can write
Pn+1 = 0 and Ci = E(Ci-1 xor Pi) for i from 1 thru n+1.
As above Cn+1 serves as the MAC.
Mallet produces corrupted the cipher text C'i = Ci except for C'1 which differs from C1 by one bit.
D operates on the corrupted ciphertext to produce corrupted plaintext P'i for i from 1 to n+1 as follows:
P'i = C'i-1 xor E-1(C'i) taking C'0 = iv as above.
C'n+1 = Cn+1, the authentication code, has been transmitted. What shall we do with it? Once I would have viewed P'n+1 as the computation done by the receiver to verify authenticity. This idea is clearly wrong for self synchronization indicates that P'n+1 will be 0, providing false authentication. This is an easy and fatal bug!
Forgetting the insight that we may already have done the computation necessary for verifying the CBC-MAC we compute, ab initio:
X0 = iv and Xi = E(Xi-1 xor P'i) for i from 1 thru n+1.
We then compare Xn+1 which is our keyed hash with the transmitted value: Cn+1.
Xn+1 is the keyed hash computed by the receiver.
P'n+1 is the transmitted authentication code.
They should be different if CBC-MAC theory is correct.
How does Cn+1 compare with these?
Alas it turns out that Xn+1 = Cn+1 whenever the last two blocks arrive unmodified! The authentication test will pass even though many blocks are garbled. Even the block count may have changed!
There are two ways of confirming this opinion. Perhaps the most convincing way is to see code run.
For others there is a rather unsatisfying observation that Xi = C'i for 0<=i<=n+1 merely because reencrypting the message that we have just decrypted, with the same key and iv, should, after all, produce the received corrupted ciphertext.
One way of describing the situation is to note that D innocently counterfeits an authentication code as a byproduct to decrypting the message. D does, after all, have the secret which is necessary to do this.
Such a perspective leads to one idea to avoid such pitfalls: The shared secret involved with the MAC must not be shared with even trusted parties, such as the CBC decrypter here.