Cryptography

CS 555
Week 4:
• Message Authentication Codes
• CBC-MAC
• Authenticated Encryption + CCA Security

Readings: Katz and Lindell Chapter 4.1-4.4

Homework 1 Solutions Released
Homework 2 Released: Due Feb 18 @11:59PM on Gradescope

Spring 2021 2
Recap
• Chosen Plaintext Attacks/Chosen Ciphertext Attacks
• CPA vs CCA-security

• Blockciphers and Modes of Operation

• Message Authentication Codes

• Confidentiality vs Integrity
• Canonical Verification and Timing Side Channel

Current Goal:
• Build a Secure MAC
• Key tool in Construction of CCA-Secure Encryption Schemes
3
 Week 4: Topic 1:
Constructing Message
Authentication Codes

5
Message Authentication Code
Syntax
Definition 4.1: A message authentication code (MAC) consists of three
algorithms
• (Key-generation algorithm)
• Input: security parameter 1n (unary) and random bits R
• Output: Secret key
• (Tag Generation algorithm)
• Input: Secret key and message and random bits R
• Output: a tag t
• (Verification algorithm)
• Input: Secret key a message m and a tag t
• Output: a bit b (b=1 means “valid” and b=0 means “invalid”)
Security Goal (Informal): Attacker should not be able to forge a valid tag t’ for new
message m’ that s/he wants to send. 6
General vs Fixed Length MAC

versus

21
Strong MAC Construction (Fixed
Length)
Simply uses a secure PRF F

Question: How to verify the a MAC?

Canonical Verification Algorithm…

22
Strong MAC Authentication ()
m1
t1 = MacK(m1)
m2
t2 = MacK (m2)

…
mq
tq = MacK(mq)
s.t
Mac s forge 𝐴 , Π (𝑛)=Vrfy k (𝑚, 𝑡) K = Gen(.)

23
Concrete Version: -secure MAC
m1
t1 = MacK(m1)
m2
t2 = MacK (m2)

…
mq
tq = MacK(mq)
s.t
Mac s forge 𝐴 , Π (𝑛)=Vrfy k (𝑚, 𝑡) K = Gen(.)

24
Strong MAC Construction (Fixed
Length)

Theorem 4.6: If F is a PRF then this is a secure (fixed-length) MAC for

messages of length n.
Proof: Start with attacker who breaks MAC security and build an
attacker who breaks PRF security (contradiction!)
Sufficient to start with attacker who breaks regular MAC security (why?)
25
Breaking MAC Security ()
m1
𝒕 𝟏 =𝑭 𝑲 ( 𝒎𝟏 )
m2
𝒕 𝟐 =𝑭 𝑲 ( 𝒎𝟐 )

…
mq
𝒕 𝒒=𝑭 𝑲 ( 𝒎𝒒 )
s.t
Macforge 𝐴 , Π (𝑛)=Vrfy k (𝑚 , 𝑡) K = Gen(.)

26
 A Similar Game ()
m1 Why? Because f(m) is
t1 = f(m1) distributed uniformly
m2 in {0,1}n so Pr[f(m)=t]=2-n
t2 = f (m2)

…
mq
tq = f(mq)
s.t
Macforge 𝐴 , ~Π (𝑛)=Vrfy k (𝑚 , 𝑡) Truly Random Function
f Funcn
Claim:
27
PRF Distinguisher D
• Given oracle O (either FK or truly random f)
• Run PPT Macforge adversary A
• When adversary queries with message m, respond with O(m)
• Output 1 if attacker wins (otherwise 0)

• If O = f then

• If O=FK then

28
PRF Distinguisher D
• If O = f then

• If O=FK then

Advantage:

Note that is non-negligible and D runs in PPT if A does.

29
Strong MAC Construction (Fixed
Length)

Theorem 4.6: If F is a PRF then this is a secure (fixed-length) MAC for

messages of length n.

30
 Strong MAC Construction (Fixed
Length)

Theorem (Concrete): If F is a -secure PRF then the above construction is

a -secure MAC for (messages of length n).
Example: F is a -secure PRF- the above MAC construction is
-secure

31
 Strong MAC Construction (Fixed
Length)

Theorem (Concrete): If F is a -secure PRF then the above construction is a -

secure MAC for (messages of length n).
Limitation: What if we want to authenticate a longer message?

32
 MACs for Arbitrary Length Messages
• Building Block ’=(Mac’,Vrfy’), a secure MAC for length n messages

First: A few failed attempts

“I love you”
Let m = m1,…,md where each mi is n bits and let

“I will never say that”

“you are stupid”
What is wrong?
Block-reordering attack
33
 MACs for Arbitrary Length Messages
• Building Block ’=(Mac’,Vrfy’), a secure MAC for length n messages

Attempt 2
Let m = m1,…,md where each mi is n bits and let

Suppose
Addresses block-reordering attack. “I don’t like you. I LOVE you!”
Any other concerns?
Truncation attack!
34
 MACs for Arbitrary Length Messages
• Building Block ’=(Mac’,Vrfy’), a secure MAC for length n messages

Attempt 3
Let m = m1,…,md where each mi is n bits and m has length
Let

Addresses truncation.
Any other concerns?
Mix and Match Attack!
35
 MACs for Arbitrary Length Messages
Let m = m1,…,md where each mi is n bits and m has length
Let m’ = m’1,…,m’d where each m’i is n bits and m has length

Let and

Mix and Match Attack!

36
“What will I say to Eve?” “Dear Alice”
“You are evil and vile.” “You are wonderful.”
“Please leave me alone!” “I can’t wait to see you!”
“Your sworn enemy - BOB” “XOXOXOXOXO - BOB”

“Dear Alice”
“You are evil and vile.”
“Please leave me alone!”
“Your sworn enemy - BOB”

37
MACs for Arbitrary Length Messages
• A non-failed approach 
• Building Block ’=(Mac’,Vrfy’), a secure MAC for length n messages
• Let m = m1,…,md where each mi is n/4 bits and m has length

MacK(m)=
• Select random bit nonce
• Let for i=1,…,d
• (Note: encode i and as bit strings)
• Output
38
MACs for Arbitrary Length Messages
MacK(m)=
• Select random n/4 bit string r
• Let for i=1,…,d
• (Note: encode i and as n/4 bit strings)
• Output

Theorem 4.8: If is a secure MAC for messages of fixed length n, above

construction is secure MAC for arbitrary length messages.

39
 Caveat: Tricky Padding Issues arise if
CBC-MAC |m| is not a multiple of the block-
length. See textbook.
𝑚1 𝑚2 𝑚3
|𝑚|❑ We will see a simpler MAC
construction using hash functions
⨁ ⨁ ⨁ soon.

F K (.) F K (.) F K (.) F K (.) 𝜏= Mac K ( 𝑚 )

Advantages over Previous Solution

• Both MACs are secure for i=1,…,d
• Works for unbounded length messages
• Canonical Verification (encode i and as n/4 bit strings)
• Short Authentication tag Output
40
• Parallelizable
Coming Soon
• CBC-MAC and Authenticated Encryption
• Read Katz and Lindell 4.4-4.5

41
 Week 4
Topics 2&3: Authenticated Encryption + CCA-Security

42
Recap
• Message Authentication Codes
• Secrecy vs Confidentiality

Today’s Goals:
• Authenticated Encryption
• Build Authenticated Encryption Scheme with CCA-Security

43
Authenticated Encryption
Encryption: Hides a message from the attacker

Message Authentication Codes: Prevents attacker from

tampering with message

44
Unforgeable Encryption Experiment ()
m1
c1 = EncK(m1)
m2
c2 = EncK (m2)

…
mq
cq = EncK(mq)
s.t
E nc forge 𝐴 , Π ( 𝑛 )=1 if Deck ( 𝑐 ) ≠ ⊥ K = Gen(.)

45
Unforgeable Encryption Experiment ()
m1
c1 = EncK(m1)
m2
c2 = EncK (m2)

…
Call an authenticated
mq
encryption scheme if it is
CCA-secure
cq = EncK(mq) Game is very
s.t and any PPT similar to MAC-
attacker wins Encforge
E nc forge 𝐴 , Π ( 𝑛 )=1 if Deck ( 𝑐 ) ≠ ⊥ K = Gen(.)
Forge game
with negligible probability

46
Building Authenticated Encryption
Attempt 1: Let be a CPA-Secure encryption scheme and let be a
secure MAC

Any problems?

47
Building Authenticated Encryption
Attempt 1:

CPA-Attack:
• Intercept ciphertext c

• Ask to encrypt r

48
Building Authenticated Encryption
Attempt 1: Let be a CPA-Secure encryption scheme and let be a
secure MAC

Attack exploited fact

that same secret key
used for MAC’/Enc’

49
Independent Key Principle

“different instances of cryptographic

primitives should always use
independent keys”

50
Building Authenticated Encryption
Attempt 2: (Encrypt-and-Authenticate) Let be a CPA-Secure
encryption scheme and let be a secure MAC. Let then

Any problems?

51
Building Authenticated Encryption
Attempt 2: (Encrypt-and-Authenticate)

CPA-Attack:
• Select ,
• Obtain ciphertext c

• Ask to encrypt

52
Building Authenticated Encryption
Attempt 2: (Encrypt-and-Authenticate)

CPA-Attack:
• Select ,
• Obtain ciphertext c Encrypt and
Authenticate
Paradigm does
• Ask to encrypt
not work in
general

53
Building Authenticated Encryption
Attempt 2: (Encrypt-and-Authenticate) Let be a CPA-Secure
encryption scheme and let be a secure MAC. Let then

Problem: MAC security

definition doesn’t
This is what SSL does 
promise to hide m!
54
 Building Authenticated Encryption
Attempt 3: (Authenticate-then-encrypt) Let be a CPA-Secure encryption
scheme and let be a secure MAC. Let then

- Used in SSL/TLS
- Not generically secure (Hugo Krawczyk)
- Easy to make mistakes when implementing (e.g., Lucky13 attack on TLS)

The Order of Encryption and Authentication for Protecting Communications (or: How Secu 55
re Is SSL?)
Authenticate-then-Encrypt: A Bad
Case
Attempt 3: (Authenticate-then-encrypt)

(Contrived? Plausible?) bad case:

Error Correcting Code

Return

56
Authenticate-then-Encrypt: A Bad
Case
Attempt 3: (Authenticate-then-encrypt)

(Contrived? Plausible?) bad case:

Error Correcting Code

Ties?
Return

57
 Authenticate-then-Encrypt: A Bad
Case Error Correcting Code
Can learn tag
Attempt 3: and message bit
(Authenticate-then-encrypt)
by bit by repeatedly querying
(Contrived? Plausible?) bad case:
decryption oracle!

1. Attacker obtains
2. Attacker asks for decryption of
• What happens if last bit of was a zero?
• Answer: decryption error since !

Return 3. What happens if last bit of is a one?

• Answer: Valid!

58
Building Authenticated Encryption
Attempt 4: (Encrypt-then-authenticate) Let be a CPA-Secure
encryption scheme and let be a strongly secure MAC. Let then

Secure?

59
 Recap
• MACs for Unbounded Length Messages
• Reordering/Truncation/Block Swapping Attacks
• Nonce Based Construction
• CBC MAC
• Authenticated Encryption = CCA-Secure + Unforgeable Encryptions
• Independent Key Principle
• Encrypt and Authenticate
• Not generically secure
• Authenticate then Encrypt
• Not generically secure
• Encrypt then Authenticate
• Always secure given CPA-Secure encryption + strongly secure MAC

Announcement: Quiz 2 Released today due by Saturday at 11:30PM on Brightspace

60
Building Authenticated Encryption
Theorem: (Encrypt-then-authenticate) Let be a CPA-Secure encryption scheme and
let be a strongly secure MAC. Then the following construction is an authenticated
encryption scheme.

Proof?
Two Tasks:

CCA-Security

61
Building Authenticated Encryption
Theorem: (Encrypt-then-authenticate) Let be a CPA-Secure encryption scheme and
let be a strongly secure MAC. Then the following construction is an authenticated
encryption scheme.

Proof Intuition: Suppose that we have already shown that any PPT attacker wins
with negligible probability.
Why does CCA-Security now follow from CPA-Security?
CCA-Attacker has decryption oracle, but cannot exploit it! Why?
Always sees “invalid ciphertext” when he query with unseen ciphertext
62
Encryption Forgery Attacker ()
m1
c1 =
m2
c2 =

…
mq
cq =
s.t
E nc forge 𝐴 , Π ( 𝑛 )=1 iff Deck ( 𝑐 ) ≠ ⊥ K = Gen(.)
′
iff Verif 𝑦 𝐾 ( 𝑚 , 𝑡 ) =1
⟨ 𝑚 , 𝑡 ⟩ ∉ { ⟨ c 1′ , t 1′ ⟩ , … , ⟨ c q ′ , t q ′ ⟩ }
𝑀

MAC forgery for the key 63

Unforgeable Encryptions
Theorem: (Encrypt-then-authenticate) Let be a strongly secure MAC. Then the following construction has
unforgeable encryptions.

Reduction: MAC Attacker A’ picks key and simulates encryption forgery attacker A
Note: unforgeable property holds even if the encryption scheme is not CPA-Secure.

(Note: A’ plays the role of the challenger in the encryption forgery game).

Whenever A submits query mi to encryption oracle A’ responds by

1. computes and
2. sends to MAC challenger to get and
3. sends ci = back to A.
Whenever A outputs a forged ciphertext we output the pair (m=c’,t=t’) as our MAC
forgery
64
Unforgeable Encryptions
Reduction: MAC Attacker A’ picks key and simulates encryption forgery
attacker A
(Note: A’ plays the role of the challenger in the encryption forgery game).

Whenever A submits query mi to encryption oracle A’ responds by

1. computes and
2. sends to MAC challenger to get and
3. sends ci = back to A.
Whenever A outputs a forged ciphertext we output the pair (m=c’,t=t’) as
our MAC forgery.
Fact: A’ wins the MAC forgery game if and only if A wins the encryption
forgery game.
65
 Proof Sketch (CCA-Security)
1. Let ValidDecQuery be event that attacker submits new/valid ciphertext to
decryption oracle at any point in time

2. Show Pr[ValidDecQuery] is negl(n) for any PPT CCA attacker A

• If not then we could win encryption forgery game with probability at least
Pr[ValidDecQuery]/q where q is the number of queries to the decryption oracle
• Reduction Challenge: a priori don’t know which query i* to decryption oracle yields
encryption forgery
• Solution: Guess index i of query
• We win the encryption forgery game if the event ValidDecQuery occurs and we guessed
correctly

• If is non-negligible so is
66
Proof Sketch
1. Let ValidDecQuery be event that attacker submits new/valid
ciphertext to decryption oracle

2. Show Pr[ValidDecQuery] is negl(n) for any PPT attacker

• This also implies unforgeability (even if we gave the attacker !).

3. Show that attacker who does not issue valid decryption query wins
CCA-security game with probability ½ + negl(n)
• Key Idea: Given attacker A breaking CCA-Security we can build A’ which
breaks CPA-security of

67
Proof Sketch
3. Show that attacker who does not issue valid decryption query wins CCA-security game with probability ½ +
negl(n)
• Key Idea: Given attacker A breaking CCA-Security we can build A’ which breaks CPA-security of

Reduction: CPA attacker A’ picks MAC key and simulates CCA-Attacker A (A’ plays role of CCA challenger)
Whenever A queries encryption oracle on message m
A’ forwards encryption oracle to CPA challenger to get
A’ computes and responds with
Whenever A queries the decryption oracle on a ciphertext
If is the fresh ciphertext then respond with (failure)
(If c was produced in response to a query then simply respond with the original message m)
Finally, A’ outputs the same guess b’ as A.
Claim:
 If is non-negligible then so is
If A breaks CCA-security of our construction then A’ breaks CPA-security of
(Contradiction! is assumed to be CPA-secure) 68
Secure Communication Session
• Solution Protocol? Alice transmits c1 = EncK(m1) to Bob, who decrypts and sends Alice
c2 = EncK(m2) etc…
• Authenticated Encryption scheme is
• Stateless
• For fixed length-messages
• We still need to worry about
• Re-ordering attacks (or Truncation)

• “I love you”, “I will never say that”, “you are stupid”

• Alice sends three n-bit message to Bob as c1 = EncK(m1), c2 = EncK(m2), c3 = EncK(m3). Mallory can reorder

• Replay Attacks
• Mallory intercepts ciphertext c3 = EncK(m3) and can now replay the message m3 later in the conversation
• Reflection Attack
• Attacker intercepts message c1 = EncK(m1) sent from Alice to Bob and Mallory reply's to Alice with c1
69
Secure Communication Session
• Defense
• Counters (CTRA,B,CTRB,A)
• Number of messages sent from Alice to Bob (CTRA,B) --- initially 0
• Number of messages sent from Bob to Alice (CTRB,A) --- initially 0
• Protects against Re-ordering and Replay attacks
• Directionality Bit
• bA,B = 0 and bB,A = 1 (e.g., since A < B)

• Alice: To send m to Bob, set c=EncK(bA,B CTRA,B m), send c and increment CTRA,B
• Bob: Decrypts c, (if then reject), obtain b CTR m
• If CTRCTRA,B or b then reject
• Otherwise, output m and increment CTR A,B
70
 Galois Counter Mode (GCM)
• AES-GCM is an Authenticated Encryption
Scheme
• Encrypt then Authenticate
• Only uses one symmetric key, but still secure 
• Bonus: Authentication Encryption with Associated
Data
• Associated Data incorporated into MAC
• Ensures attacker cannot tamper with associated
packet data
• Source IP
• Destination IP Direction of Message is Authenticated
• Why can’t these values be encrypted?
• Encryption is largely parallelizable! No truncation/reordering attacks possible
amongst the blocks of this message 71
Authenticated Security vs CCA-
Security
• Authenticated Encryption  CCA-Security (by definition)

• CCA-Security does not necessarily imply Authenticate Encryption

• But most natural CCA-Secure constructions are also Authenticated Encryption
Schemes
• Some constructions are CCA-Secure, but do not provide Authenticated
Encryptions, but they are less efficient.
• Conceptual Distinction
• CCA-Security the goal is secrecy (hide message from active adversary)
• Authenticated Encryption: the goal is integrity + secrecy

72
 Week 4: Topic 4:
Cryptographic Hash
Functions

73
Hash Functions

H(x)=y
Long Input: Short Output: y s.t.

74
Pigeonhole Principle

“You cannot fit 10 pigeons into 9 pigeonholes”

75
Hash Collisions

By Pigeonhole Principle there must

exist x and y s.t.

H(x) = H(y)

76
Classical Hash Function Applications
• Hash Tables
• O(1) lookup*

• “Good hash function” should yield “few collisions”

* Certain terms and conditions apply

77
Collision-Resistant Hash Function
Intuition: Hard for computationally bounded attacker to find any pair s.t.

How to formalize this intuition?

• Attempt 1: For all PPT A,

• The Problem: Let be given s.t.

• We are assuming that |x| > |H(x)|. Why?

• H(x)=x is perfectly collision resistant! (but with no compression)
78
Keyed Hash Function Syntax
• Two Algorithms
• (Key-generation algorithm)
• Input: Random Bits R
• Output: Secret key
• (Hashing Algorithm)
• Input: key and message (unbounded length)
• Output: hash value

• Fixed length hash function

• with

79
Collision Experiment ()
s
x1,x2

{
𝑠 𝑠
𝐻𝑎𝑠h𝐶𝑜𝑙𝑙 𝐴 , Π (𝑛)= 1𝑖𝑓 𝐻 ( 𝑥1 ) =𝐻 ( 𝑥2 )
0 𝑜𝑡h𝑒𝑟𝑤𝑖𝑠𝑒

s=Gen(1𝑛; 𝑅)
Definition: (Gen,H) is a collision resistant hash function
if
80
Collision Experiment ()
s
For simplicity we will
x1,x2
sometimes just say that H
(or Hs) is a collision 1𝑖𝑓 𝐻 𝑠 ( 𝑥 ) =𝐻 𝑠 ( 𝑥 ) Key is not key secret
𝐻𝑎𝑠h𝐶𝑜𝑙𝑙 𝐴 , Π (𝑛)=
{
resistant hash function 0 𝑜𝑡h𝑒𝑟𝑤𝑖𝑠𝑒
1 2
(just random)

s=Gen(1𝑛; 𝑅)
Definition: (Gen,H) is a collision resistant hash function
if
81
Theory vs Practice
• Most cryptographic hash functions used in practice are un-keyed
• Examples: MD5, SHA1, SHA2, SHA3
• Tricky to formally define collision resistance for keyless hash function
• There is a PPT algorithm to find collisions
• We just usually can’t find this algorithm 

82