Scribed by Mark Landry
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 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. We still are guaranteed that any message we see was sent at some time by the right party. To protect against replay attacks, we could include a timestamp with the message, and reject messages that are too old. We’ll assume that replay attacks are handled at a higher level and will not worry about them.
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.
Proof: First, let be a truly random function, and
an algorithm with oracle access to
and complexity at most
. Then
Now, define an algorithm that returns 1 iff
, where
are the values computed by
. Then
Where the last inequality is due to the definition of a pseudo-random function. From this it follows that
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. Here are some examples:
Example 1
. This authentication scheme allows the advisary to rearrange, repeate, or remove blocks of the message. Therefore it is insecure.
Example 2
. This authentication scheme prevents the advisary from reordering blocks of the message, but it still allows the advisary to truncate the message or to interleave blocks from two previously seen messages.
Example 3
. This scheme adds a randomized message identifier, and it prevents interleaving blocks from different messages, but it still fails to protect the message from being truncated by the advisary.
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
- Pick a random
-
:
- Output
if and only if
- Output
Theorem 4 If
is
-secure, the above scheme is
-secure.
Proof: Define as the authentication scheme above. Define
in the same way, except using a truly random function
in place of
. Let A be an algorithm of complexity at most
.
Consider . Note that A can make at most
oracle queries. Define
as the event in which
never queries
, and produces a tag
for which
. Define
as the event in which, for two different oracle queries,
receives tags with same
.
Now,
Consider the event . Suppose our oracle queries, and the resulting random strings, were:
Then we know . Now, the algorithm outputs message
with a valid tag
Then there are the following cases:
- Case1:
. Then the algorithm computed
without having seen it before.
- Case2:
was seen before, so it occured exactly once, in the Tag for the
query.
- Case 2a:
. Then we computed
without having seen it before.
- Case 2b:
. We know
, so
. thus we computed
without having seen it before
- Case 2a:
Thus, in the event , we constructed some
without sending
to the oracle. Since R is truely random, this can only occur with prbability
.
Now,
So finally we have