Message Authentication Code

Security of MAC

Def. Message Authentication Code

A MAC scheme is an efficiently computable function

M: {0,1}^l x {0,1}^*→{0,1}ⁿ

written

M(k,m)=t

where k is the key, m is the message and t is the tag.
Remark. MAC schemes are used for porivding (symmetric-key) data integrity and data origin authentication.

Applications of MAC

• To provide data integrity and data origin authentication:
1. Alice and Bob establish a secret key k∈{0,1}^l
2. Alice computes t=M(k,m) and sends (m,t) to Bob
3. Bob verifies that t=M(k,m)
• To avoid reply, add a timestamp, or sequence number
• Widely used in communication protocols
• No confidentiality or non-repudiation

Def. MAC Security

Assume the adveersary knows everything about the MAC scheme except the key k. A MAC scheme is secure if
(interaction) given some number of MAC tags M(k,m_i) for messages m_i chosen adaptively by the adversary,
(computational resources) it is computationally infeasible
(goal) to compute (with non-negligible probability of success) the value of M(k,m) for any m≠m_i.

In other words, a MAC scheme is secure if it is existentially unforgeable against chosen-message attack.

Remarks. Secure MACs as of 2024:

• HMAC-SHA256
• Poly1305-ChaCha20

Generic Attacks

• Guessing the MAC of a message m:
• Select y∈{0,1}ⁿ and guess that M(k,m)=y
• Assuming that M(k,.) is a random function, the probability of success is (1/2)ⁿ
• Depending on the application where the MAC algorithm is employed, one could choose n as small as 32. In general, n≥128 is preferred.
• Exhausitive search on the key space:
• Given r known message/MAC pairs: (m₁,t¹),...,(m^r,t^r), one can check whether a guess k of the key is correct by verifying that M(k,m_i)=t_i for i=1,2,...,r
• Assuming that M(k,.) is a random function, the expected number of keys for which the tags verify is K = 2^l/2^nr
  ex) If the key is 56-bit, the output is 64-bit and we have two message/MAC pairs, then K≈1/2⁷²
• Requires ≈2^l computations
• It is infeasible if l≥128.

Constructing MACs

MACs based on Block Ciphers

1. CBC-MAC

• Let E be a n-bit block cipher with key space {0,1}^l
• To compute M(k,m):
1. Divide (padded) m into n-bit blocks m₁,...,m^r
2. Compute H₁=E(k,m₁)
3. For 2 ≤ i ≤ r, H_i=E(k,H_i-1⊕m_i)
4. M(k,m)=H_r
• e.x) DES CBC-MAC (with l=56, n=64)
• Was widely used in banking applications
• ANSI x9.9: Finanical institution message authentication (wholesale)
• ANSI x9.19: Financial institution message authentication (retail)

CBC-MAC is not secure if variable length messages are allowed.

Chosen message attack on CBC-MAC

1. Let m₁ be an n-bit block.
2. Let (m₁,t₁) be a known message/MAC pair.
3. Request the MAC t₂ of the message t₁. Then t₂ is also the MAC of the 2-block message (m₁,0) since t₂=E_k(E_k(m₁))

2. Encrypted CBC-MAC (EMAC)

• Encrypt the last block under a secret key s:

  M((k,s),m)=E_s(H_r)

  where H_r is the output of CBC-MAC.
• e.x) ANSIx9.19 specifies that

  M((k,s),m)=E_k(E_s^-1(H_r))

3. Hash-based MAC (HMAC)

Hash function