Last time we described a secure MAC (message authentication code) based on pseudorandom functions. Its disadvantage was the length of the tag, which grew with the length of the message.
Today we describe the CBC-MAC, also based on pseudorandom functions, which has the advantage of short tags. We skip its security analysis.
Next, we show that combining a CPA-secure encryption with a secure MAC gives a CCA-secure encryption scheme.
Suppose we have a pseudorandom function .
Last time we described a provably secure MAC in which a message is broken up into blocks , each of length , and the tag of is the sequence
where is a random string and is the key of the authentication scheme. Jonah suggested a more compact scheme, in which is broken into blocks of length and the tag is
for a random string . That is, the length of the message is not explicitly authenticated in each block, but we authenticate a single bit that says whether this is, or isn’t, the last block of the message.
Exercise 1 Prove that if is -secure then this scheme is -secure, where is an upper bound to the number of blocks of the message that we are going to authenticate.
A main disadvantage of such schemes is the length of the final tag.
The CBC-MAC scheme has the advantage of producing a tag whose length is only .
- for to :
- : check that
2. Combining MAC and Encryption
Suppose that we have an encryption scheme and a MAC . We can combine them to produce the following encryption scheme, in which a key is made of pair where is a key for and is a key for :
- if : return
- else return ERROR
The scheme is an encrypt-then-authenticate scheme in which we first encrypt the plaintext with key and then authenticate the ciphertext with key . The decryption aborts if given an incorrectly tagged ciphertext.
The idea of this scheme is that an adversary mounting a CCA attack (and hence having access to both an encryption oracle and a decryption oracle) has no use for the decryption oracle, because the adversary already knows the answer that the decryption oracle is going to provide for each oracle query:
- if the adversary queries a ciphertext previously obtained from the encryption oracle, then it already knows the corresponding plaintext
- if the adversary queries a ciphertext not previously obtained from the encryption oracle, then almost surely (assuming the security of the MAC), the tag in the ciphertext will be incorrect, and the oracle answer is going to be “ERROR”
This intuition is formalized in the proof of the following theorem.
Theorem 1 If is CPA secure, and is secure, then is CCA secure, where is an upper bound to the running time of the encryption algorithm and the tag algorithm , and is an upper bound to the length of the messages that we encrypt.