Message Authentication Codes

Get access to whole semester resourcesSemester Pass

Chapter Forty-Four

Syllabus topic Module 1, "Message Authentication and Hash Functions: Message Authentication Codes"

Pages 265 to 270 of 678

In one line

A short tag computed from the message and a shared secret key, which anybody holding the key can recompute and check. It proves the message came from a key holder and was not altered, and it proves nothing to anybody else.

In the wording a student can write in an examination: a message authentication code, or MAC, also called a cryptographic checksum, is a small fixed-size block of data generated from a message and a secret key, MAC = C(K, M). The sender appends it to the message; the receiver recomputes it with the same key and compares. If they match, the receiver is assured that the message has not been altered, that it is from the alleged sender, and, if the message includes a sequence number, that the sequence is correct.

What a MAC must satisfy

Three requirements, and the third is the one an examination asks about.

1. Given a message and its MAC, it must be infeasible to construct a different message with the same MAC. This is the forgery requirement.

2. The MAC values must be uniformly distributed, so that for two randomly chosen messages the chance of equal MACs is 2 to the power minus n, where n is the number of bits in the MAC.

3. The MAC must depend equally on all bits of the message. If some bits influence the tag less than others, an attacker who knows the message can change those bits with a better than random chance of the tag still matching.

Requirement 3 is the one that distinguishes a MAC from a simple checksum. A cyclic redundancy check satisfies 2 and fails 1 and 3 completely, and that is why a CRC is not a MAC however long it is.

The three things a MAC is not

# A message authentication code, and the forgery that plain CBC-MAC allows.

import hashlib, hmac as _hmac

KEY = b"a shared secret key"

def mac(key, message):
    """A MAC built on a hash, which is what HMAC does properly."""
    return _hmac.new(key, message, hashlib.sha256).digest()[:8]

msg = b"PAY 0500 TO VENDOR 8817"
tag = mac(KEY, msg)
print("message :", msg.decode())
print("tag     :", tag.hex(), "(8 bytes, truncated from SHA-256)")
print()
print("the receiver recomputes and compares:")
print("   recomputed:", mac(KEY, msg).hex(), " matches:", mac(KEY, msg) == tag)
print()
print("alter one character and the tag no longer matches:")
bad = b"PAY 0500 TO VENDOR 9999"
print("   altered   :", bad.decode())
print("   its tag   :", mac(KEY, bad).hex())
print("   matches the original tag:", mac(KEY, bad) == tag)
print()

print("a MAC is NOT reversible. Many messages share one tag, by construction:")
print("   tag is 8 bytes, so 2 to the power 64 possible tags")
print("   messages of 23 bytes: 2 to the power 184 of them")
print("   so on average 2 to the power 120 messages share each tag.")
print("   The tag does not contain the message and cannot be inverted.")
print()

print("and why a MAC is not a signature. Both parties hold KEY, so BHARAT")
print("could have produced this tag himself:")
print("   Bharat computes the same tag :", mac(KEY, msg).hex())
print("   identical to Asha's          :", mac(KEY, msg) == tag)
print("   A third party cannot tell which of them made it. No non-repudiation.")
print()

print("PLAIN CBC-MAC, and the forgery it allows on variable-length messages.")
print("Built on a small block cipher so the blocks are readable:")

def block_cipher(block, key):
    x = int.from_bytes(block, "big")
    for r in range(4):
        x = (x * 0x2545 + key + r) & 0xFFFFFFFF
        x = ((x << 9) | (x >> 23)) & 0xFFFFFFFF
        x ^= (key >> (8 * r)) & 0xFFFFFFFF
    return x.to_bytes(4, "big")

def xor(a, b):
    return bytes(p ^ q for p, q in zip(a, b))

def cbc_mac(message, key):
    prev = bytes(4)
    for i in range(0, len(message), 4):
        prev = block_cipher(xor(prev, message[i:i + 4]), key)
    return prev

K = 0x2B7E1516
one = b"PAY1"
t1 = cbc_mac(one, K)
print("   MAC of %r            = %s" % (one.decode(), t1.hex()))
two = one + xor(t1, b"PAY1")
t2 = cbc_mac(two, K)
print("   MAC of the forged two-block message = %s" % t2.hex())
print("   which equals the one-block MAC      :", t1 == t2)
print("   The attacker built a LONGER message with the SAME tag, knowing only")
print("   one message and its tag. No key was needed.")
print()
print("   The fix is to include the LENGTH, or to use a different final key:")
print("   CMAC (SP 800-38B) and HMAC (FIPS 198-1) both do this correctly.")

Message Authentication Codes

message : PAY 0500 TO VENDOR 8817
tag     : 33308090dac16738 (8 bytes, truncated from SHA-256)

the receiver recomputes and compares:
   recomputed: 33308090dac16738  matches: True

alter one character and the tag no longer matches:
   altered   : PAY 0500 TO VENDOR 9999
   its tag   : 8b0a5a9075cfdeb0
   matches the original tag: False

a MAC is NOT reversible. Many messages share one tag, by construction:
   tag is 8 bytes, so 2 to the power 64 possible tags
   messages of 23 bytes: 2 to the power 184 of them
   so on average 2 to the power 120 messages share each tag.
   The tag does not contain the message and cannot be inverted.

and why a MAC is not a signature. Both parties hold KEY, so BHARAT
could have produced this tag himself:
   Bharat computes the same tag : 33308090dac16738
   identical to Asha's          : True
   A third party cannot tell which of them made it. No non-repudiation.

PLAIN CBC-MAC, and the forgery it allows on variable-length messages.
Built on a small block cipher so the blocks are readable:
   MAC of 'PAY1'            = 881fa296
   MAC of the forged two-block message = 881fa296
   which equals the one-block MAC      : True
   The attacker built a LONGER message with the SAME tag, knowing only
   one message and its tag. No key was needed.

   The fix is to include the LENGTH, or to use a different final key:
   CMAC (SP 800-38B) and HMAC (FIPS 198-1) both do this correctly.

Message Authentication Codes

Read four things out of that run.

It works, and an alteration is caught. One character changed and the tag is entirely different, because the underlying hash has the avalanche property.

A MAC is not reversible, and the counting shows why. The tag is 8 bytes, so there are 2 to the power 64 possible tags; a 23-byte message has 2 to the power 184 possibilities; so on average 2 to the power 120 messages share each tag. The tag does not contain the message. Many students describe a MAC as "encryption that cannot be decrypted", which is the wrong picture: it is a many-to-one function, not an encryption at all.

A MAC is not a signature, and the run demonstrates it. Bharat computes the identical tag, because he holds the same key. A third party shown the message and the tag cannot say which of the two produced it. This is the services chapter's argument, made concrete.

And plain CBC-MAC is forgeable on variable-length messages. Given one message PAY1 and its tag, the attacker constructs a two-block message whose tag is the same, by appending the tag exclusive-ored with the first block. No key was used. That is why plain CBC-MAC must never be used on messages of varying length, and why SP 800-38B's CMAC applies a different final key and HMAC uses a nested hash.

Why the forgery works, in one paragraph

CBC-MAC computes T = E(K, M1) for a one-block message. Now consider the two-block message whose first block is M1 and whose second block is T XOR M1. The MAC of that is E(K, (T XOR M1) XOR E(K, M1)), which is E(K, (T XOR M1) XOR T), which is E(K, M1), which is T. So the longer message has the same tag, and the attacker needed only M1 and T. The fix is to make the computation depend on the length, which CMAC does by using a different key for the final block.

The alternatives, and which to use

	Plain CBC-MAC	CMAC	HMAC
Built on	a block cipher	a block cipher	a hash function
Specified in	older standards	SP 800-38B	FIPS 198-1, RFC 2104
Safe for variable-length messages	no	yes	yes
How it fixes the length problem	it does not	a different key for the final block	the nested construction
Speed	a cipher pass	a cipher pass	a hash pass, usually faster in software
Use it	never	where a block cipher is already present	the default choice

Message Authentication Codes

Worked example: where a MAC is the right answer and where it is not

Case 1: two college offices exchanging marks, sharing a key. A MAC is exactly right. Both hold the key, neither needs to convince a third party, and a MAC is far cheaper than a signature.

Case 2: a college publishing a timetable for two thousand students. A MAC is wrong. The key would have to be given to all two thousand, and then any one of them could forge a timetable. A signature is the answer.

Case 3: a bank needing to prove which college authorised a payment. A MAC is wrong, because the bank holds the key too and could have produced the tag. A signature is the answer.

Case 4: a protocol authenticating each packet of a live connection, thousands per second. A MAC is right. The two endpoints already share a session key from the handshake, no third party is involved, and a signature per packet would be far too slow.

The step that carries the marks. The test is always the same: is there a third party who must be convinced, and is the key held by more than the parties whose word is at stake? If either answer is yes, a MAC will not do.

Distinctions that carry marks

	MAC	Digital signature
Key	one, shared	a private key to make, a public key to check
Who can produce it	anybody holding the key	only the private key holder
Who can verify it	anybody holding the key	anybody at all
Non-repudiation	no	yes
Speed	fast	slow, so it signs a digest
Length	8 to 32 bytes typically	as long as the modulus

	MAC	Hash
Key	yes	no
Authenticates on its own	yes	no
Same input, same output	yes, given the key	yes
Reversible	no, and many messages share a tag	no

	MAC	Encryption
Output length	fixed and short	as long as the message
Reversible	no	yes
Provides confidentiality	no	yes
Provides integrity	yes	not by itself

What beginners get wrong here

Calling a MAC "encryption that is not decrypted". It is a many-to-one function. Many messages share a tag, by construction, and the tag does not contain the message.

Claiming a MAC gives non-repudiation. It does not, and the run shows Bharat producing Asha's tag.

Using a CRC as a MAC. A CRC has no key and is linear, so an attacker alters the message and fixes up the CRC. Length is irrelevant.

Message Authentication Codes

Using plain CBC-MAC on variable-length messages. The forgery is in this chapter. Use CMAC or HMAC.

Comparing tags with an ordinary equality test. A comparison that stops at the first difference leaks how many bytes matched, and the timing recovers the tag. Use a constant-time comparison.

Quick revision

MAC = C(K, M): a short fixed-length tag from the message and a shared key, appended and checked by recomputation.
Three requirements: infeasible to find another message with the same tag; uniformly distributed tags, so a chance collision is 2 to the power minus n; and dependence on all bits equally.
A MAC is not reversible: with an 8-byte tag and a 23-byte message about 2 to the power 120 messages share each tag.
A MAC is not a signature: the verifier holds the key and could have produced the tag, so there is no non-repudiation.
Plain CBC-MAC is forgeable on variable-length messages: from M1 and its tag T, the two-block message M1 || (T XOR M1) has the same tag. Performed in this chapter.
Use CMAC (SP 800-38B) where a block cipher is present, or HMAC (FIPS 198-1) as the default.
A CRC is not a MAC: no key, and linear.
Compare tags in constant time.

Test yourself

1. Define a message authentication code and state the three requirements on it. A fixed-length value computed from a message and a secret key, MAC = C(K, M), appended to the message and verified by recomputation. It must be infeasible, given a message and its MAC, to construct a different message with the same MAC; the MAC values must be uniformly distributed, so that two random messages collide with probability 2 to the power minus n; and the MAC must depend equally on all bits of the message.

2. Why is a MAC not reversible, and why is that not a defect? Because it maps messages of any length to a short fixed-length tag, so it is many-to-one: with an 8-byte tag and 23-byte messages, about 2 to the power 120 messages share each tag. It is not a defect because the purpose is verification rather than recovery: the receiver already has the message and needs only to confirm it.

3. Why does a MAC not provide non-repudiation? Because the key is shared, so the verifier can compute any tag the sender can. Presented with a message and a valid tag, a third party cannot determine which of the two key holders produced it, so neither party's authorship can be proved against their denial.

4. Show how a forgery is possible against plain CBC-MAC. Let M1 be a one-block message with tag T, so T = E(K, M1). Consider the two-block message whose blocks are M1 and T XOR M1. Its CBC-MAC is E(K, (T XOR M1) XOR E(K, M1)), which is E(K, (T XOR M1) XOR T), which is E(K, M1), which is T. The attacker therefore produces a longer message with the same tag knowing only M1 and T, and no key.

Message Authentication Codes

5. Why is a cyclic redundancy check not a message authentication code? Because it has no key, so anybody can compute it, and because it is linear, so an attacker who alters the message can adjust it to make the check pass. Both failures are independent of its length.

6. Name two correct constructions and say what each is built on. CMAC, specified in NIST SP 800-38B, built on a block cipher and using a separately derived key for the final block so that the computation depends on the message length. HMAC, specified in FIPS 198-1 and RFC 2104, built on a hash function using a nested construction with two derived keys.

7. A college wants to publish a timetable that two thousand students can verify. Is a MAC suitable? No. Verification with a MAC requires the key, so every student would need it, and any of them could then forge a timetable. The correct mechanism is a digital signature: the college signs with its private key and every student verifies with the public one, which they can do without being able to produce a signature themselves.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.

Syllabus for Cyber and Information Security

Issue