This week, Wednesday’s office hours are moved to Thursday, February 12, 2-3pm, 679 Soda Hall.

** Summary **

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 messageif 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 3If 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 4If is -secure, the above scheme is -secure.

Something to consider mentioning, although it’s hard to talk about precisely at this point in the course: in practice people treat the following constructions as MACs:

Tag(K,M) := MD5(M||K)

and

Tag(K,M) := MD5(K||M)

where || is concatenation and MD5 is the MD5 hash function.

What would be sufficient condition(s) for MD5 for these constructions to satisfy existential unforgeability under chosen message attack? Does MD5 satisfy these conditions?

This question isn’t really well posed because you don’t have a formal treatment of hash functions – and you likely don’t want to shoehorn one into this lecture. Still I think it may be worth asking to get students thinking about what might go wrong with these unfortunately exceedingly common constructions.

Thanks, David. I am going to talk about (keyed) hash functions either today or Tuesday, so reasoning about such a scheme could be a good exercise problem.