Message Authentication Code

25 September, 2024
MAC
A message authentication code (MAC) is defined by a function of the form
H :K×M→T.
I Parametrized by a key k ∈ K, the MAC function is usually expressed
as Hk .
I Each function Hk should be efficiently computable.
I t = Hk (m) is called the MAC or MAC-tag of m.

Applications: data integrity and data origin authentication.

Definition

MAC is formally defined by 3 algorithms:

1. Key-Gen: Returns a key k ∈R K.
2. MAC-Gen: Given k ∈ K and m ∈ M, returns t = Hk (m).
3. MAC-Verify: Given (k, m, t), return 1 if t = Hk (m), else 0.
I Correctness: A properly generated MAC should always be accepted
as valid.
I Security:
Definition

MAC is formally defined by 3 algorithms:

1. Key-Gen: Returns a key k ∈R K.
2. MAC-Gen: Given k ∈ K and m ∈ M, returns t = Hk (m).
3. MAC-Verify: Given (k, m, t), return 1 if t = Hk (m), else 0.
I Correctness: A properly generated MAC should always be accepted
as valid.
I Security: An adversarially generated MAC should not be accepted as
valid.
Application of MAC

I How to achieve data integrity and data origin authentication?

1. Alice and Bob share a secret key k ∈ {0, 1}` .
2. Alice computes tag = Hk (m) and sends (m, tag) to Bob.
3. Bob accepts m as a valid message originating from Alice only if
tag = Hk (m).
I Attacker shouldn’t be able to produce a valid tag for some “new”
message.
Application of MAC

I How to achieve data integrity and data origin authentication?

1. Alice and Bob share a secret key k ∈ {0, 1}` .
2. Alice computes tag = Hk (m) and sends (m, tag) to Bob.
3. Bob accepts m as a valid message originating from Alice only if
tag = Hk (m).
I Attacker shouldn’t be able to produce a valid tag for some “new”
message.
I Replay attack: An adversary can replay a valid (x, tag) pair!
I Prevention: add a timestamp, or sequence number to the message.
Application of MAC

I How to achieve data integrity and data origin authentication?

1. Alice and Bob share a secret key k ∈ {0, 1}` .
2. Alice computes tag = Hk (m) and sends (m, tag) to Bob.
3. Bob accepts m as a valid message originating from Alice only if
tag = Hk (m).
I Attacker shouldn’t be able to produce a valid tag for some “new”
message.
I Replay attack: An adversary can replay a valid (x, tag) pair!
I Prevention: add a timestamp, or sequence number to the message.
I Can we achieve authentication through encryption?
Generic Attack: Forgery

For a generic attack, we assume Hk is a random function.

I Strategy: Guess the MAC of a message x:
I Select y ∈R {0, 1}n and return Hk (x) = y .
I Note: Guesses cannot be directly checked.
I What is the probability of attacker’s success?
Generic Attack: Forgery

For a generic attack, we assume Hk is a random function.

I Strategy: Guess the MAC of a message x:
I Select y ∈R {0, 1}n and return Hk (x) = y .
I Note: Guesses cannot be directly checked.
I What is the probability of attacker’s success? 21n .
I So this is the best security assurance one can hope for.
I Goal: realise this bound for all adversaries, even an unbounded one.
One-Time MAC
I MAC scheme is public, the secret key k is used to generate at most
one MAC tag.
I The attacker A is allowed to obtain at most one MAC tag on any
message of her choice.
One-Time MAC
I MAC scheme is public, the secret key k is used to generate at most
one MAC tag.
I The attacker A is allowed to obtain at most one MAC tag on any
message of her choice.
I Consider two attack scenario:
1. Impersonation: A does not make any MAC query.
2. Substitution: A has obtained the tag t for some m of her choice.
One-Time MAC
I MAC scheme is public, the secret key k is used to generate at most
one MAC tag.
I The attacker A is allowed to obtain at most one MAC tag on any
message of her choice.
I Consider two attack scenario:
1. Impersonation: A does not make any MAC query.
2. Substitution: A has obtained the tag t for some m of her choice.
I Goal of A: Return the tag t ∗ of any message m∗ 6= m.
I MAC-forge: (m∗ , t ∗ ) is a MAC forgery if t ∗ is a valid tag for m∗ .
One-Time MAC
I MAC scheme is public, the secret key k is used to generate at most
one MAC tag.
I The attacker A is allowed to obtain at most one MAC tag on any
message of her choice.
I Consider two attack scenario:
1. Impersonation: A does not make any MAC query.
2. Substitution: A has obtained the tag t for some m of her choice.
I Goal of A: Return the tag t ∗ of any message m∗ 6= m.
I MAC-forge: (m∗ , t ∗ ) is a MAC forgery if t ∗ is a valid tag for m∗ .
I A MAC Scheme Π = (Key-Gen, MAC-Gen, MAC-Verify) is one-time
-secure if for all (even unbounded) adversary A:

Pr[MAC-forge1-time
A,Π ]≤
Strongly Universal (Hash) Function

I Let K (resp. M) be the key and message space.

I Consider a function h : K × M → T : we write h(k, m) = hk (m) = t.
I The function h is strongly universal (or pairwise independent) if for
any two m 6= m0 , hk (m) and hk (m0 ) are uniform and independently
distributed in T when k is uniform.
I For all distinct m, m0 ∈ M and all t, t 0 ∈ T we have

Pr[hk (m) = t ∧ hk (m0 ) = t 0 ] = 1/|T |2

I The probability is over uniform choice of k ∈ K.

Example Construction

I For some prime number p, define Zp = {0, · · · , p − 1}

I We take M = T = Zp and K = Zp × Zp
I A key k is chosen as (a, b) ∈R Z2p .
I The function is ha,b (m) = a · m + b mod p
Claim: h is a strongly universal function.
Example Construction

I For some prime number p, define Zp = {0, · · · , p − 1}

I We take M = T = Zp and K = Zp × Zp
I A key k is chosen as (a, b) ∈R Z2p .
I The function is ha,b (m) = a · m + b mod p
Claim: h is a strongly universal function.
I For any distinct m, m0 and any t, t 0 , find out (a, b).
Example Construction

I For some prime number p, define Zp = {0, · · · , p − 1}

I We take M = T = Zp and K = Zp × Zp
I A key k is chosen as (a, b) ∈R Z2p .
I The function is ha,b (m) = a · m + b mod p
Claim: h is a strongly universal function.
I For any distinct m, m0 and any t, t 0 , find out (a, b).
I The key k = (a, b) is unique among |T |2 keys.
I So, the probability that hk (m) = t and hk (m0 ) = t 0 is 1/|K|.
I Hence the function ha,b is strongly universal.
One-Time MAC

I Given a strongly universal function h : K × M → T .

I MAC Π:
I Key-Gen: Choose the key as k ∈R K.
I MAC-Gen: Gievn k and m ∈ M, compute t = hk (m).
I MAC-Verify: Given (k, m, t), output 1 iff t = hk (m).
Example

Let p = 3: hk (m) = a · m + b mod 3 for any k = (a, b) ∈ Z23 .

Example

Let p = 3: hk (m) = a · m + b mod 3 for any k = (a, b) ∈ Z23 .

Authentication matrix:
key 0 1 2
(0,0) 0 0 0
(0,1) 1 1 1
(0,2) 2 2 2
(1,0) 0 1 2
(1,1) 1 2 0
(1,2) 2 0 1
(2,0) 0 2 1
(2,1) 1 0 2
(2,2) 2 1 0
Example

Let p = 3: hk (m) = a · m + b mod 3 for any k = (a, b) ∈ Z23 .

Authentication matrix:
key 0 1 2
(0,0) 0 0 0
(0,1) 1 1 1
(0,2) 2 2 2
(1,0) 0 1 2
(1,1) 1 2 0
(1,2) 2 0 1
(2,0) 0 2 1
(2,1) 1 0 2
(2,2) 2 1 0

Exercise: Analyse impersonation and substitution attack.

Security

Claim: If h : K × M → T is a strongly universal function then Π is a

1/|T |-secure One-Time MAC.
Security

Claim: If h : K × M → T is a strongly universal function then Π is a

1/|T |-secure One-Time MAC.
I We consider an unbounded adversary A.
I Suppose A makes a query on a message m and receives the
corresponding tag t.
I Then A returns a forgery (m∗ , t ∗ ).
I What’s Pr[MACk (m) = t ∧ MACk (m0 ) = t 0 ] =?
Security

Claim: If h : K × M → T is a strongly universal function then Π is a

1/|T |-secure One-Time MAC.
I We consider an unbounded adversary A.
I Suppose A makes a query on a message m and receives the
corresponding tag t.
I Then A returns a forgery (m∗ , t ∗ ).
I What’s Pr[MACk (m) = t ∧ MACk (m0 ) = t 0 ] =? 1/|T |2
I Summing over all t ∈ T will give the advantage of A in the
MAC-forge game.
Limitation of Unconditionally Secure MAC

I In our One Time MAC construction |M| = |T | = p and |K| = p 2

I How many bits do you need to represent an element of each set?
Limitation of Unconditionally Secure MAC

I In our One Time MAC construction |M| = |T | = p and |K| = p 2

I How many bits do you need to represent an element of each set?
I Claim: A One-Time MAC with  = 2−n must have keys of length at
least 2n.
Limitation of Unconditionally Secure MAC

I In our One Time MAC construction |M| = |T | = p and |K| = p 2

I How many bits do you need to represent an element of each set?
I Claim: A One-Time MAC with  = 2−n must have keys of length at
least 2n.
I Consider the case of two messages: m0 and m1 .
I How many possible tags must m0 have?
Limitation of Unconditionally Secure MAC

I In our One Time MAC construction |M| = |T | = p and |K| = p 2

I How many bits do you need to represent an element of each set?
I Claim: A One-Time MAC with  = 2−n must have keys of length at
least 2n.
I Consider the case of two messages: m0 and m1 .
I How many possible tags must m0 have? 2n .
Limitation of Unconditionally Secure MAC

I In our One Time MAC construction |M| = |T | = p and |K| = p 2

I How many bits do you need to represent an element of each set?
I Claim: A One-Time MAC with  = 2−n must have keys of length at
least 2n.
I Consider the case of two messages: m0 and m1 .
I How many possible tags must m0 have? 2n .
I Conditioned on the tag for m0 , how many possibilities should be there
for the tag of m1 ?
Limitation of Unconditionally Secure MAC

I In our One Time MAC construction |M| = |T | = p and |K| = p 2

I How many bits do you need to represent an element of each set?
I Claim: A One-Time MAC with  = 2−n must have keys of length at
least 2n.
I Consider the case of two messages: m0 and m1 .
I How many possible tags must m0 have? 2n .
I Conditioned on the tag for m0 , how many possibilities should be there
for the tag of m1 ? 2n .
Limitation of Unconditionally Secure MAC

I In our One Time MAC construction |M| = |T | = p and |K| = p 2

I How many bits do you need to represent an element of each set?
I Claim: A One-Time MAC with  = 2−n must have keys of length at
least 2n.
I Consider the case of two messages: m0 and m1 .
I How many possible tags must m0 have? 2n .
I Conditioned on the tag for m0 , how many possibilities should be there
for the tag of m1 ? 2n .
I A single key defines the tag for both m0 and m1 . So there must be at
least 2n × 2n keys.
I For `-Time MAC with  = 2−n we need keys of length at least (` + 1)n
Many Times MAC

I How do we go beyond the limitations mentioned in the previous slide?

Many Times MAC

I How do we go beyond the limitations mentioned in the previous slide?

I Consider security against computationally bounded adversary –
classical/quantum.
MAC-forge Security Game

I k: secret key shared by Alice and Bob; the MAC scheme Π is public.
I Attacker A does not know k, but is allowed to obtain (a certain
maximum number q of) tags for messages of her choice.
I A has access to a MAC oracle and can make the queries m1 , . . . , mq
adaptively.
I Goal of A: Return the tag t ∗ of any message m∗ whose tag she did
not already obtain from the MAC oracle.
I (m∗ , t ∗ ) is a MAC forgery.
Existential Unforgeability

Definition: A MAC scheme is secure if given some MAC tags Hk (xi ) for
1 ≤ i ≤ q where xi s are chosen by A, it is (computationally) infeasible to
obtain (with non-negligible probability of success) a pair (x, Hk (x)) for a
new message x.
Pr[MAC-forgeqA,Π ] ≤ ,
for some  which is negligible.
I The MAC scheme is existentially unforgeable under
chosen-message attack (EUF-CMA).
Existential Unforgeability

Definition: A MAC scheme is secure if given some MAC tags Hk (xi ) for
1 ≤ i ≤ q where xi s are chosen by A, it is (computationally) infeasible to
obtain (with non-negligible probability of success) a pair (x, Hk (x)) for a
new message x.
Pr[MAC-forgeqA,Π ] ≤ ,
for some  which is negligible.
I The MAC scheme is existentially unforgeable under
chosen-message attack (EUF-CMA).
How do we construct such a MAC scheme?
Reference

For Information Theoretic MAC

I Chapter 4.6 of Katz-Lindell
I Chapter 5.6 of Stinson-Paterson