Scribed by James Cook
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
This scheme is similar to in structure to CBC encryption:
We will not prove CBC-MAC to be secure, but the general approach is to show that all the inputs to are distinct with high probability.
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.
(In (1), and should take keys as input; we have omitted the keys to simplify notation.)
Without loss of generality, we assume never queries on any ciphertext previously returned by . We can make this assumption because we can modify to keep a record of all the queries it makes to , and to use the record to avoid redundant queries to .
We now wish to convert to a new algorithm such that
Note that is given the oracles and , but is given as an oracle just the original CPA-secure encryption algorithm .
- pick a random key
- simulate with these oracles:
- returns ;
- always returns ERROR.
has to run the tagging algorithm , which has complexity , every time makes an oracle call. Since has complexity at most , has complexity at most .
Now, assuming the attack works, we can apply the triangle inequality to (1) to obtain:
If when is simulating , never makes a call to which results in an output other than “ERROR”, then behaves exactly as would with the same key . So (5) implies that with probability greater than , makes a call to the decryption oracle resulting in an output other than “ERROR”. This means manages to generate valid messages that it has never seen before, and we can use this fact to define an algorithm that breaks the Message Authentication Code .
makes at most oracle queries to , and with probability , at least one of those results in an output other than “ERROR”. There must exist a number such that with probability at least , the -th query makes to is the first one that does not result in an error. Then define algorithm as follows.
- (no input)
- choose a random key
- simulate , with the following two oracles…
- always returns ERROR
…until makes its -th query to
- Let be the -th query made to .
Note that has complexity at most , and by our analysis of algorithm , produces a correct tage for a message it has never seen before with probability at least .
Since we assumed was -secure, we have reached a contradiction: is therefore CCA secure.