Cryptography

CS 555
Week 3:
• Building CPA-Secure Encryption Schemes
• Pseudorandom Functions/Permutations
• Block Ciphers + Modes of Operation
• CCA-Security (definition)
• Message Authentication Codes [time permitting]

Readings: Katz and Lindell Chapter 3.5-3.7

Reminder: Homework 3 is due on Thursday at 11:59PM on Gradescope

Spring 2021 1
Recap
• Using PRGs to achieve Semantic Security (Single Message Eavesdropping)

• Multiple Message Eavesdropping Experiment

• Impossible to achieve with stateless/deterministic encryption scheme

• Chosen Plaintext Attacks and CPA-Security

• PRF Security: )

where is a truly random function and PRF key k is picked randomly

2
Recap CPA-Security
• Defend against eavesdropping attacker’s ability to influence messages that honest
party encrypts
• More powerful than known plaintext attacks (knows vs controls encrypted message)

• Historical Importance: Battle of Midway

• CPA-Security Equivalence
• Multiple vs Single Encryption Game

• Limitations of Threat Model

• Passive vs Active Attacker
• What if attacker can get honest party to (partially) decrypt some messages?
3
Chosen Plaintext Attacks (Examples)
• CPA-attacker influences messages that honest party encrypts

• Eve sends Bob a document/e-mail expecting that Bob will encrypt it and forward
it to Alice

• Eve registers herself in a database expecting that Bob (employee) will forward
the encrypted database to her boss.

• Eve generate important news that Bob will encrypt and pass on to Alice
• Plant objects at specific GPS coordinates
• Broadcast Message (Battle of Midway)
4
 Week 3: Topic 1:
Pseudorandom Functions
and CPA-Security

5
PRF Security
Definition 3.25: A keyed function is a pseudorandom function if for all
PPT distinguishers D there is a negligible function s.t.

Notes:
• the first probability is taken over the uniform choice of as well as the
randomness of D.
• the second probability is taken over uniform choice of f Funcnas well as
the randomness of D.
• D is not given the secret k in the first probability (otherwise easy to
distinguish…how?)
11
PRF-Security as a Game
m1
r1
m2
r2
m3
r3

b’ …
Random bit b

Truly random func R

ri = FK(mi) if b=1
R(mi) o.w 12
PRF Security Concrete Version
Definition 3.25: A keyed function is a -secure pseudorandom function if
for all distinguishers D running in time at most and making at most
queries we have

13
Reminder: CPA-Security (Single
Message)
m0,m1
c = EncK(mb)
m2
c2 = EncK(m2)
m3
c3 = EncK(m3)

b’ …
Random bit b

14
CPA-Secure Encryption
• Gen: on input 1n pick uniform
• Enc: Input and
Output for uniform

• Dec: Input and How to begin proof?

Output

Theorem: If F is a pseudorandom function, then (Gen,Enc,Dec) is a CPA-

secure encryption scheme for messages of length n.
15
 Breaking CPA-Security (Single
Message)
m0,m1
⟨ 𝑟 , 𝐹 𝑘 ( 𝑟 ) ⨁ 𝑚𝑏⟩
m2
m3
⟨ 𝑟 2 , 𝐹 𝑘 ( 𝑟 2 ) ⨁ 𝑚2 ⟩
⟨ 𝑟 3 , 𝐹 𝑘 ( 𝑟 3 ) ⨁ 𝑚3 ⟩
b’ …
Random bit b

Assumption: PPT
16
Security Reduction
• Step 1: Assume for contraction that we have a PPT attacker A that breaks CPA-Security.
• Step 2: Construct a PPT distinguisher D which breaks PRF security.
• Distinguisher DO (oracle O --- either f or Fk)
• Simulate A
• Whenever A queries its encryption oracle on a message m
• Select random r and query O(r)
• Return
• Whenever A outputs messages m0,m1 Analysis: Suppose that O = f then
• Select random r and bit b
• Return
• Whenever A outputs b’ Suppose that O = f then
• Output 1 if b=b’
• Output 0 otherwise
where denotes the encryption scheme in which Fk
is replaced by truly random f. 17
Security Reduction
• Step 1: Assume for contraction that we have a PPT attacker A that breaks CPA-Security.
• Step 2: Construct a PPT distinguisher D which breaks PRF security.
• Distinguisher DO (oracle O --- either f or Fk)
• Simulate A
• Whenever A queries its encryption oracle on a message m
• Select random r and query O(r)
• Return
Analysis: By PRF security, for some negligible function we
• Whenever A outputs messages m0,m1
have
• Select random r and bit b
• Return
• Whenever A outputs b’
• Output 1 if b=b’ Implies:
• Output 0 otherwise

18
Security Reduction
• Fact: -

• Claim: For any attacker A making at most q(n) queries we have

Conclusion: For any attacker A making at most q(n) queries we have

where is negligible.
19
Finishing Up
Claim: For any attacker A making at most q(n) queries we have

Proof: Let m0,m1 denote the challenge messages and let r* denote the
random string used to produce the challenge ciphertext

And let denote the random strings used to produce the other
ciphertexts .
If then then c leaks no information about b (information theoretically).

20
Finishing Up
Claim: For any attacker A making at most q(n) queries we have

Proof: If then then c leaks no information about b (information

theoretically). We have

21
Conclusion

PRF Security

For any attacker A making at most q(n) queries we have

Suggested Exercise: Work out concrete version of security proof 22

Are PRFs or PRGs more Powerful?
• Easy to construct a secure PRG from a PRF
G(s) = Fs(1)|…|Fs()

• Construct a PRF from a PRG?

• Tricky, but possible… (Katz and Lindell Section 7.5)

23
 PRFs from PRGs
Theorem: Suppose that there is a PRG G with
expansion factor Then there is a secure PRF.

Let G(x) = G0(x)||G1(x) (first/last n bits of output)

Theorem: If G is a PRG then Fk is a PRF

24
 PRFs from PRGs
Theorem: Suppose that there is a PRG G with
expansion factor Then there is a secure PRF.
1
0 k Fk(011)=G1(G1(G0(k)))

G0(k) G1(k)
0 1
1
0

G0(G0(k)) 1 G1(G0(k)) G0(G1(k)) G1(G1(k))

0 1 0 1 1
0 0
… … … …
… … … … 25
Stream Ciphers Modes
• What if we don’t know the length of the message to be encrypted a priori?
• Stream Cipher: outputs n pseudorandom bits as follows
• Initial State: st0 = Initialize(s)
• Repeat
• (yi,sti)=GetBits(sti-1)
• Output yi

• Synchronized Mode
• Message sequence: m1,m2,…
• Ciphertext sequence: ci = mi yi (same length as ciphertext!)
• “CPA-like” security follows from cipher security (must stop after n-bits)
• Deterministic encryption, what gives???
• Requires both parties to maintain state (not good for sporadic communication)
27
Stream Ciphers Modes
• What if we don’t want to keep state?
• Unsynchronized Mode
• Message sequence: m1,m2,…
• Ciphertext sequence:
• CPA-Secure if Fk(IV) is a (weak) PRF.
• No shared state, but longer ciphertexts….

28
 Week 3: Topic 2: Modes of
Encryption, The Penguin and CCA
security

29
Pseudorandom Permutation
A keyed function , which is invertible and “looks
random” without the secret key k.

• Similar to a PRF, but

• Computing Fk(x) and is efficient (polynomial-time)

Definition 3.28: A keyed function is a strong pseudorandom

permutation if for all PPT distinguishers D there is a negligible function
s.t.
30
Pseudorandom Permutation
Definition 3.28: A keyed function is a strong pseudorandom permutation if for all
PPT distinguishers D there is a negligible function s.t.

Notes:
• the first probability is taken over the uniform choice of as well as the randomness
of D.
• the second probability is taken over uniform choice of f Permnas well as the
randomness of D.
• D is never given the secret k
• However, D is given oracle access to (keyed) permutation and inverse
• Strong pseudorandom permutation: attacker doesn’t get oracle access to inverse
• Can build strong pseudorandom permutation given pseudorandom function 31
 Electronic Code Book (ECB) Mode
• Uses strong PRP Fk(x) and
• Enck
• Input: m1,…,m
• Output:
• How to decrypt?
• Is this secure?
• Hint: Encryption is deterministic.
• Implication: Not CPA-Secure
• But, it gets even worse
32
ECB Mode (A Failed Approach)

33
The Penguin Principle
If you can still see the penguin after
“encrypting” the image something is very
very wrong with the encryption scheme.

34
Cipher Block Chaining
• CBC-Mode (below) is CPA-secure if Ek is a PRP

IV
Reduces bandwidth!

Message: 3n bits
Ciphertext: 4n bits
IV

How to decrypt? (Hint: Can be done in parallel) 35

Recap
• PRFs/PRPs

• CPA-Secure Encryption + Security Reduction

Reminder: HW Due Tonight
11:59PM on Gradescope

• ECB Mode + Penguin Principle

• CBC Mode (CPA Secure)
• Chained CBC-Mode

36
 Chained CBC-Mode

m4 m5 m6

IV
c3

IV c4 c5 c6

• First glance: seems similar to CBC-Mode and reduces bandwidth

• Vulnerable to CPA-Attack! (Set and c4=c1 iff m1=m1’)
• Moral: Be careful when tweaking encryption scheme!
37
Counter Mode

• Input: m1,…,mn
• Output: c = (ctr, c1,c2,…,cn) where ctr is chosen uniformly at random
• Theorem: If Ek is PRF (or PRP) then counter mode is CPA-Secure
• Advantages: Parallelizable encryption/decryption
39
 Galois Counter Mode (GCM)
Input: plaintexts 1 & 2

• AES-GCM is CCA-secure (> CPA-security)

• Bonus: Authentication Encryption with
Associated Data
• Ensure integrity of ciphertext
• Attacker cannot even generate new/valid
ciphertext!
• Ensures attacker cannot tamper with
associated packet data
• Source IP
• Destination IP
• Why can’t these values be encrypted?
• Encryption is largely parallelizable!
Outputs: iv, ciphertexts 1 & 2,
40
authentication tag
Week 3: Topic 3:
CCA-Security

42
Chosen Ciphertext Attacks
• Sometimes an attacker has ability to obtain (partial) decryptions of
ciphertexts of its choice.
• CPA-Security does not model this ability.
Examples:
• An attacker may learn that a ciphertext corresponds to an ill-formed
plaintext based on the reaction (e.g., server replies with “invalid
message”).
• Monitor enemy behavior after receiving an encrypted message.
• Authentication Protocol: Send Enck(r) to recipient who authenticates by
responding with r.
43
CCA-Security (Ind-CCA2)
We could set m = m or m = m etc…0 -1 1 -2

m-1
c-1 = EncK(m-1)
c-2
m-2 = DecK(c-2)

…
m0,m1
However, we could still flip 1 bit of
c = EncK(mb) c and ask challenger to decrypt
m2
c2 = EncK(m2)
c3 Random bit b
m3 = DecK(c3) K = Gen(.)
c4 =c
…

“No Way!”
b’ 44
CCA-Security
1. Challenger generates a secret key k and a bit b
2. Adversary (A) is given oracle access to Enck and Deck
3. Adversary outputs m0,m1
4. Challenger sends the adversary c=Enck(mb).
5. Adversary maintains oracle access to Enck and Deck ,however the adversary is
not allowed to query Deck(c).
6. Eventually, Adversary outputs b’.

CCA-Security: For all PPT A exists a negligible function negl(n) s.t.

45
CCA-Security
Definition 3.33: An encryption scheme is CCA-secure if for all PPT A
there is a negligible function negl(n) such that

46
CPA-Security doesn’t imply CCA-
Security

Attacker: Selects m0 = 0n and m1 = 1n

Attacker Receives:
Attacker Queries: Deck(c’) for

Attacker Receives:

Example Shows: CPA-Security doesn’t imply CCA Security (Why?)

47
Attacks in the Wild
• Padding Oracle Attack
• Length of plaintext message must be multiple of block length (e.g., 16 bytes)
• Popular fix PKCS #5 padding
• 1 bytes of padding (0x01)
• 2 bytes of padding (0x0202)
• 3 bytes of padding (0x030303)
• 4 bytes of padding (0x04040404)
• Invalid: (0x020303)
• “Bad Padding Error”
• Adversary submits ciphertext(s) and waits to if this error is produced
• Attacker can repeatedly modify ciphertext to reveal original plaintext piece by piece!
48
Example
M=“hello…please keep this message secret”+0x030303

Ask to decrypt C’
• If we added 3 bytes of padding?
•  C’ can be decrypted (Looks like the message M’ = M + 0x0301 with 1 byte padding).
• If we added 3 (or < 3) bytes of padding?
• We will get a decryption error (bad padding)!

Once we know we have three bits of padding we can set

If C’’ decrypts then we can infer the byte t s.t. since .

49
Example
M=“hello…please keep this message secret”+0x030303

Once we know we have three bits of padding we can set

If C’’ decrypts then we can infer the byte t s.t. since .

Question: How do we infer the next byte t’?

Answer: Set
if decryption is successful then
50
CCA-Security
• CCA-Security is strictly stronger than CPA-Security
• Note: If a scheme has indistinguishable encryptions under one chosen-ciphertext attack
then it has indistinguishable multiple encryptions under chosen-ciphertext attacks.
• None of the encryption schemes we have considered so far are CCA-Secure 
• Achieving CCA-Security?
• Useful to guarantee integrity of the ciphertext
• Idea: If attacker cannot generate valid new ciphertext c’ (distinct from ciphertext obtained via
eavesdropping) then ability to query decryption oracle is useless!
• CCA-Security requires non-malleability.
• Intuition: if attacker tampers with ciphertext c then c’ is either invalid or m’ is unrelated to m
• Let Suppose attacker could generate a new valid ciphertext such that is related to the but not
message
• How can the attacker win the CCA-Security game?
• Ask for decryption of c’ and check if is related to or
51
 Week 3: Topic 4:
Message Authentication Codes
(Part 1)

52
What Does It Mean to “Secure
Information”
• Confidentiality (Security/Privacy)
• Only intended recipient can see the communication

53
 What Does It Mean to “Secure
Information”
• Confidentiality (Security/Privacy)
• Only intended recipient can see the communication
• Integrity (Authenticity)
• The message was actually sent by the alleged sender

I love you We need to

Alice… - Bob break up -Bob Alice
Bob 54
Message Authentication Codes
• CPA-Secure Encryption: Focus on Secrecy
• But does not promise integrity

• Message Authentication Codes: Focus on Integrity

• But does not promise secrecy

• CCA-Secure Encryption: Requires Integrity and Secrecy

55
 What Does It Mean to “Secure
Information”
• Integrity (Authenticity)
• The message was actually sent by the alleged sender
• And the received message matches the original

Pay robot Pay robot

devil $50 devil $5,000 Alice
Bob 56
Error Correcting Codes?
• Tool to detect/correct a small number of random errors in transmission

• Examples: Parity Check, Reed-Solomon Codes, LDPC, Hamming Codes …

• Provides no protection against a malicious adversary who can introduce

an arbitrary number of errors

• Still useful when implementing crypto in the real world (Why?)

57
Modifying Ciphertexts

If attacker knows original message he can forge c’ to decrypt to any message

he wants.
Even if attacker doesn’t know message he may find it advantageous to flip
certain bits (e.g., decimal places)
58
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”)
• Invariant?
59
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”)
• Invariant?
60
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. 61
MAC Authentication Game ()
m1
t1 = MacK(m1)
m2
t2 = MacK (m2)

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

62
Discussion
• Is the definition too strong?
• Attacker wins if he can forge any message
• Does not necessarily attacker can forge a “meaningful message”
• “Meaningful Message” is context dependent
• Conservative Approach: Prove Security against more powerful attacker
• Conservative security definition can be applied broadly
• Replay Attacks?
• t=MacK(“Pay Bob $1,000 from Alice’s bank account”)
• Alice cannot modify message to say $10,000, but…
• She may try to replay it 10 times

63
Replay Attacks
• MACs alone do not protect against replay attacks (they
are stateless)

• Common Defenses:
• Include Sequence Numbers in Messages (requires
synchronized state)
• Can be tricky over a lossy channel
• Timestamp Messages
• Double check timestamp before taking action
64
Strong MACs
• Previous game ensures attacker cannot generate a valid tag for a new
message.
• However, attacker may be able to generate a second valid tag t’ for a
message m after observing (m,t)
• Strong MAC: attacker cannot generate second valid tag, even for a
known message

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

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

66
Deterministic MACs
• Canonical Verification Algorithm

• “All real-world MACs use canonical verification” – page 115

67
Strong MAC vs Regular MAC
Proposition 4.4: Let be a secure MAC that uses canonical verification.
Then is a strong MAC.

“All real-world MACs use canonical verification” – page 115

Should attacker have access to VrfyK(.) oracle in games?

(e.g., CPA vs CCA security for encryption)
Irrelevant if the MAC uses canonical verification!

68
Timing Attacks (Side Channel)
Naïve Canonical Verification Algorithm
Input: m,t’

t=MacK(m) Example
for i=1 to tag-length
if t[i] != t’[i] then t= 1 0 1 0 1 1 1 0 Returns 0 after 8 steps
return 0 t’= 1 0 1 0 1 1 1 1
return 1

69
Timing Attacks (Side Channel)
Naïve Canonical Verification Algorithm
Input: m,t’

t=MacK(m) Example
for i=1 to tag-length Returns 0 after 1 step
if t[i] != t’[i] then t= 1 0 1 0 1 1 1 0
return 0 t’= 0 0 1 0 1 1 1 0
return 1

70
Timing Attack
• MACs used to verify code updates for Xbox 360

• Implementation allowed different rejection times (side-channel)

• Attacks exploited vulnerability to load pirated games onto hardware

• Moral: Ensure verification is time-independent

71
Improved Canonical Verification
Algorithm
Input: m,t’

B=1
t=MacK(m) Example
for i=1 to tag-length Returns 0 after 8 steps
if t[i] != t’[i] then t= 1 0 1 0 1 1 1 0
B=0 t’= 0 0 1 0 1 0 1 0
else (dummy op)
return B
72
Side-Channel Attacks
• Cryptographic Definition
• Attacker only observes outputs of oracles (Enc, Dec, Mac) and nothing else
• When attacker gains additional information like timing (not captured by model) we
call it a side channel attack.

Other Examples
• Differential Power Analysis
• Cache Timing Attack
• Power Monitoring
• Acoustic Cryptanalysis
• …many others
73
Recap
• Data Integrity
• Message Authentication Codes
• Side-Channel Attacks
• Build Secure MACs
• Construct CCA-Secure Encryption Scheme

Current Goal:
• Build a Secure MAC
• Key tool in Construction of CCA-Secure Encryption Schemes
74
General vs Fixed Length MAC

versus

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

Question: How to verify the a MAC?

Canonical Verification Algorithm…

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

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

78
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(.)

79
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?)
80
Breaking MAC Security ()
m1
𝒕 𝟏 =𝑭 𝑲 ( 𝒎𝟏 )
m2
𝒕 𝟐 =𝑭 𝑲 ( 𝒎𝟐 )

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

81
 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:
82
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

83
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.

84
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.

85
 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

86
 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?

87
 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
88
 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!
89
 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!
90
 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!

91
“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”

92
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
93
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.

94
Recap
• CPA-Security vs. CCA-Security
• PRFs

Today’s Goals:
• Introduce Message Authentication Codes (MACs)
• Key tool in Construction of CCA-Secure Encryption Schemes
• Build Secure MACs

95