This week, Wednesday’s office hours are moved to Thursday, February 12, 2-3pm, 679 Soda Hall.
Today we start to talk about message authentication codes (MACs). The goal of a MAC is to guarantee to the recipient the integrity of a message and the identity of the sender. We provide a very strong definition of security (existential unforgeability under adaptive chosen message attack) and show how to achieve it using pseudorandom functions.
Our solution will be secure, but inefficient in terms of length of the required authentication information.
Next time we shall see a more space-efficient authentication scheme, and we shall prove that given a CPA-secure encryption scheme and a secure MAC, one can get a CCA-secure encryption scheme. (That is, an encryption scheme secure against an adaptive chosen ciphertext and plaintext attack.)
1. Message Authentication
The goal of message authentication is for two parties (say, Alice and Bob) who share a secret key to ensure the integrity and authenticity of the messages they exchange. When Alice wants to send a message to Bob, she also computes a tag, using the secret key, which she appends to the message. When Bob receives the message, he verifies the validity of the tag, again using the secret key.
The syntax of an authentication scheme is the following.
Definition 1 (Authentication Scheme) An authentication scheme is a pair of algorithms , where takes in input a key and a message and outputs a tag , and takes in input a key, a message, and a tag, and outputs a boolean answers. We require that for every key , and very message
if is deterministic, and we require
if is randomized.
In defining security, we want to ensure that an adversary who does not know the private key is unable to produce a valid tag. Usually, an adversary may attempt to forge a tag for a message after having seen other tagged messages, so our definition of security must ensure that seeing tagged messages does not help in producing a forgery. We provide a very strong definition of security by making sure that the adversary is able to tag no new messages, even after having seen tags of any other messages of her choice.
Definition 2 (Existential unforgeability under chosen message attack) We say that an authentication scheme is -secure if for every algorithm of complexity at most
where a pair is a “forge” if and is none of the messages that queried to the tag oracle.
This definition rules out any possible attack by an active adversary except a replay attack, in which the adversary stores a tagged message it sees on the channel, and later sends a copy of it.
2. Construction for Short Messages
Suppose is a pseudorandom function. A simple scheme is to use the pseudorandom function as a tag:
- if , otherwise
This construction works only for short messages (of the same length as the input of the pseudorandom function), but is secure.
Theorem 3 If is a -secure pseudorandom function, then the above construction is a -secure authentication scheme.
3. Construction for Messages of Arbitrary Length
Suppose we now have a longer message , which we write as with each block being of the same length as the input of a given pseudorandom function.
There are various simple constructions we described in class that do not work.
The following construction works:
Let be a pseudorandom function, be the message we want to tag, and write where each block is bits long.
- Pick a random ,
- output , where
- Output if and only if
Theorem 4 If is -secure, the above scheme is -secure.