Scribed by James Cook
Summary
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.
1. CBC-MAC
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 .
CBC-MAC scheme:
-
:
-
- for
to
:
- return
-
-
: 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
:
-
:
-
-
- return
-
-
:
- if
: return
- else return ERROR
- if
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.
Proof: Suppose is not CCA-secure. Then there exist an algorithm
of complexity
and two messages
and
such that
(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
.
Define
-
:
- pick a random key
-
- simulate
with these oracles:
-
returns
;
-
always returns ERROR.
-
- pick a random key
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:
One of (2), (3) or (4) must be greater than .
If (3) , then algorithm
breaks the CPA-security of
. We assumed
was CPA-secure, so one of (2) or (4) must be greater than
. In either case, there exists a message
with the property that
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…
-
:
-
-
- return
-
-
always returns ERROR
…until
makes its
-th query to
-
- Let
be the
-th query
made to
.
- return
- choose a random key
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.