### CIS 5371 Cryptography

```CIS 5371 Cryptography
4. Message Authentication Codes
Based on: Jonathan Katz and Yehuda Lindell Introduction to Modern Cryptography
1
Message Authentication
Codes
Encryption vs message authentication
• Different functionalities
• Encryption does not provide message
authentication!
• Encryption with stream ciphers
• For  ≔ () one just needs to flip a bit of
the ciphertext.
• Encryption with block ciphers
• Same attack (flipping bits) works, only this
time blocks are affected.
2
Definition 4.1
Message Authentication Code
A message authentication code (MAC) is a tuple
(Gen, Mac, Vrfy) such that:
•
Gen takes input the security parameter 1 and
outputs a key  with || ≥ .
•
Mac takes as input a key  and a message  ∈ {0,1}∗
and outputs a tag .
We write:   Mac ().
•
Vrfy takes as input a key , a message  ∈ {0,1}∗
and a tag  and outputs a bit :  = 1 means valid,
while  = 0 means .
We write,  :=Vrfy(, ).
3
Message authentication experiment
Mac-forge(A,) ()
1.
2.
3.
A random key  is generated running Gen 1 .
The adversary  is given input 1 and oracle access
to Ma ∙ .
The adversary eventually outputs a pair ,  .
Let Q be the set of all queries of A asked to its oracle.
The output of the experiment i 1 if and only if
a.
Vrf ,  = 1, and
b. ..
4
Definition 4.2 -- Secure MAC
A message authentication code = (Gen, Mac, Vrfy)
is existentially unforgeable under adaptive chosen
message attack, or just secure, if for all probabilistic
polynomial-time adversaries , there exists a
negligible function negl such that:
Pr[Mac-forge(A,)  = 1] ≤ negl.
5
Construction 4.3
A fixed length MAC from any PRF
Let  be a pseudorandom function. Define a fixed
length MAC on messages of length  as follows:
• Gen: on input 1 choose   {0,1} uniformly at
random.
• Mac: on input a key   {0,1} and a message
{0,1} , output tag
≔   .
(If  ≠ || then output nothing.)
• Vrfy: on input a key   {0,1} and a message
{0,1} , output 1 if and only if  =   .
(If  ≠ || then output 0.)
6
Theorem 4.4
Let  be a pseudorandom function.
Then Construction 4.3 is a fixed-length MAC
for messages of length n that is existentially
unforgeable under an adaptive chosen message
attack.
7
A secure fixed length MAC
Proof
Let A be a probabilistic polynomial time adversary.
Define:
≝ Pr[Mac-forge(A,)  = 1]
Let  be a MAC that is the same as
= (Gen, Mac, Vrfy) except that a truly random
function  is used instead of a PRF  .
Then
Pr[Mac-forge(A, )  = 1] ≤ 2− .
8
Distinguisher D
O ∶ {0,1} → ∶ {0,1}
1. Run (1 ): whenever  queries its MAC oracle on a
•
Query O with  to get response . Return t to A.
2. When A outputs (, ) at the end of its execution do:
a) Query O with  to get ′.
b) If  ′ =  and A never queried its MAC oracle with
then output 1; else output 0.
9
Distinguisher D
If  oracle is a PRF then,
Pr
∙
1 = 1 = Pr[Mac−forge A, )  = 1 = ()
If the oracle is a random function - then,
Pr
∙
1
= 1 = Pr[Mac-forge ,   = 1] ≤
1
2
Therefore,
|Pr
∙
1
= 1 − Pr
∙
1
1
=1 |   +
2
10
Distinguisher D
Since  is a PRF it follows that there is a negligible
function negl with
+ 2− = negl  .
and so   is negligible.
11
Replay attacks
MACs do not protect against replay attacks.
This is because the definition of a MAC does not
incorporate any notion of state in the verification
algorithm.
• Two common techniques for preventing replay attacks
involve the use of   and  .
12
Construction 4.5
A variable length MAC
Let ′ = (Gen′, Mac′, Vrfy′) be fixed length MAC for messages
of length .
• Gen’: identical to Gen.
• Mac’: on input a key   {0,1} and a message {0,1}∗
of length  < 2 /4 parse  = 1     into blocks of
length /4 and choose a random identifier  in {0,1}/4 .
Compute  ← MAC ′ |  ||| , for  = 1, … , , and
output  ≔ (, 1 , … ,  )
• Vrfy: parse  into  blocks and re-compute the MAC.
Output 1 if and only if the answer is the same for all
||
13
Theorem 4.6
If ’ is a secure fixed length MAC for messages of
length , then Construction 4.6 is a MAC that is
existentially unforgeable under an adaptive chosen
message attack.
14
Construction 4.9 CBC-MAC
Let  be a pseudorandom function. Fix a length function .
The CBC-MAC construction is as follows:
• Gen: on input 1 choose   {0,1} uniformly at random.
• Mac: on input a key {0,1} and message {0,1}
∙
1. Parse  = 1 ∙∙∙  into blocks of length , and set 0 ≔ 0 .
2. Compute  ←  −1   , for  = 1, … ,  .
Output  ≔
• Vrfy: on input a key {0,1} , a message {0,1} ,
and a tag  output 1 if and only if  = MAC  .
15
Theorem 4.10
Let  be a polynomial.
If F is a pseudorandom function then Construction 4.9
is a fixed length MAC for messages of length () ∙
that is existentially unforgeable under an adaptive
chosen message attack.
16
CBC-MAC vs CBC-mode encryption
1. CBC-mode encryption uses a random IV.
If we use a random IV for CBS-MAC then we lose
security.
2. In CBC-mode encryption all encrypted blocks
are output as part of the ciphertext.
This is not the case with CBC-MAC.
If we do so we loose security.
17
Variable length CBC-MAC
1

2
3



18
Secure CBC-MAC for variable
length messages – three options
1. Apply the pseudorandom function to the length  of the
input message  to get a key , e.g. set  ≔  (). Then
compute the CBC-MAC with this key.
2. Prepend the message  with length || and then
compute the basic CBC-MAC.
If we append  instead of prepending it we lose
security.
2. Choose two keys 1 , 2 . Compute the CBC-MAC with the
first key to get . The tag is  ≔ 2 ().
19
Variable length CBC-MAC
||

1
2
3




20
```