4. Message Authentication Codes
Message authentication codes (MAC) were designed to provide message integrity. Bob receives a message from Alice and wants to know if this message was not modified during transmission. For MACs, the message itself does not have to be secret. For example, when we download a file the file itself does not have to be protected, but we need a way to verify that the file was not modified.
Note that MAC is different from error correcting codes (ECC). ECC fixes accidental errors. For example, the Ethernet protocol uses CRC32, which is keyless. Keyless integrity mechanisms are designed to detect and fix random transmission errors, and the adversary can easily modify the data since there is no key and the algorithm is publicly known.
On the other hand, MAC fixes data that is tampered in purpose. We will also require a key so that the adversary cannot easily modify the message. We assume that the secret key is shared between two parties, in advance.
Message Authentication Code
Definition. A MAC system
defined over is a pair of efficient algorithms and where is a signing algorithm and is a verification algorithm.
is a probabilistic algorithm that outputs for some key and message . The output is called a tag, and is the tag space. is a deterministic algorithm that computes and outputs ( ) or ( ) . - It is required that
.
When
Canonical Verification
This is called canonical verification. All real-world MACs use canonical verification.
Secure MAC: Unforgeability
In the security definition of MACs, we allow the attacker to request tags for arbitrary messages of its choice, called chosen-message attacks. This assumption will allow the attacker to collect a bunch of valid
- Attacker is given
for of his choice.- Attacker has a signing oracle.
- Attacker’s goal is existential forgery.
- MAC: generate a new valid message-tag pair
such that and . - Strong MAC: generate a new valid message-tag pair
and .
- MAC: generate a new valid message-tag pair
For strong MACs, the attacker only has to change the tag for the attack to succeed.
Definition. Let
be a MAC system defined over . Given an adversary , the security game goes as follows.
- The challenger picks a random
. queries the challenger times.
- The
-th signing query is a message , and receives . outputs a new forged pair that is not among the queried pairs.
(for strong MAC)
wins if is a valid pair under . Let this event be . The MAC advantage with respect to is defined as and a MAC
is secure if the advantage is negligible for any efficient . In this case, we say that is existentially unforgeable under a chosen message attack.
If a MAC is secure, the attacker learns almost nothing from the
MAC Security with Verification Queries
The above definition can be modified to include verification queries, where the adversary
It can be shown that for strong MACs, these two definitions are equivalent. See Theorem 6.1.1 For (just) MACs, these are not equivalent. See Exercise 6.7.1
Since these two definition are equivalent, security proofs are easier when we use the definition without verification queries.
Notes on the Security Definition
Replay Attacks
The definition requires that the adversary generate a new message-tag pair. In the real world, there are replay attacks that send the same message multiple times. For example, intercepting a bank transaction message and sending it several times can be critical. Replay attacks should be handled differently, by using sequence numbers in messages or by appending a timestamp.
Secure MAC with Canonical Verification
A secure MAC with canonical verification is strongly secure, since
MAC Constructions from PRFs
Block ciphers were actually PRPs, but we have a large message space, so by the PRF switching lemma, we can use block ciphers as PRFs and construct other systems!
Let
be a PRF. Define a MAC scheme over as
if and otherwise.
This MAC is derived from
Theorem. Let
be a secure PRF. If is sufficiently large, then is a secure MAC. For every efficient MAC adversary
against , there exists an efficient PRF adversary such that
Proof. See Theorem 6.2.1
The above construction uses a PRF, so it is restricted to messages of fixed size. We also need a MAC for longer messages.
MAC Constructions for Fixed Length Messages
CBC-MAC
Definition. For any message
, let .
Theorem. If
is a secure PRF, then for a fixed , CBC-MAC is secure for messages .
The following modifications show some of the ways that CBC-MAC could become insecure.
Using Shorter Messages is Insecure (Extension Attack)
For any messages shorter than
To see this, consider the following extension attack.
- Pick an arbitrary
. - Request the tag
. - Set
and output and as the tag.
Then the verification works since
Random IV is Insecure
If we use random IV instead of
- Pick an arbitrary
. - Request the tag
. ( ) - Send
and tag .
Then the verification works since
Disclosing Intermediate Values is Insecure
If CBC-MAC outputs all intermediate values of
- Pick an arbitrary
. - Request the computed values
, where and . - Send
and tag .
Then the verification works since
The lesson is that cryptographic constructions should be implemented exactly as it was specified, without any unproven variations.
CBC-MAC for Messages of Arbitrary Length
We can extend CBC-MAC for arbitrary length messages. First, assume that all messages have lengths divisible by
Length Prepending
We can prepend the length of message
However, this cannot be used if the length of the message is not known in advance. Also, only prepending works since appending the length is not secure. See Exercise 6.8.1
Proposition. Appending the length of the message in CBC-MAC is insecure.
Proof. Let
Now forge a message-tag pair
which equals
Encrypt Last Block (ECBC-MAC)
Since CBC-MAC is vulnerable to extension attacks, we encrypt the last block again. Choose a second key
ECBC-MAC doesn’t require us to know the message length in advance, but it is relatively expensive in practice, since a block cipher has to be initialized with a new key.
Theorem. Let
be a secure PRF. Then for any , is a secure PRF. For any efficient
-query PRF adversary against , there exists an efficient PRF adversary such that
Thus ECBC-MAC is secure as long as
Extendable PRF
Definition. Let
be a PRF defined over . is extendable if for all , and ,
It is easy to see that (E)CBC is an extendable PRF.
Attacking ECBC with Messages
- Make
queries using random messages and obtain . - With a high probability, there is a collision
for . - Query for
and receive the tag . - Return a forged pair
.
This works because ECBC is an extendable PRF.
So ECBC becomes insecure after signing
Bit-wise PRF Using Block-wise PRF
Now we construct a bitwise PRF, that enables us to sign messages of arbitrary length. We pad the messages so that they can be signed block-wise.
Specifically, pad with
Other Constructions
- CMAC (OMAC)
- Simplified version of ECBC-MAC
- Uses only one key
- NIST standard
- Parallelizable MAC (PMAC)
- Uses two keys.
- Better than ECBC, since it is parallelizable.
- Each message block is XORed with a easy-to-compute function, then it is encrypted.
- All encrypted blocks are XORed, and finally encrypted again.
- PMAC is incremental: the tag can be easily updated when a message block changes.
- Hash-MAC (HMAC)