Understanding Pseudorandom Functions and Permutations in Cryptography

Cryptography Lecture 7

Pseudorandom functions

Keyed functions Let F: {0,1}*x {0,1}* {0,1}*be an efficient, deterministic algorithm Define Fk(x) = F(k, x) The first input is called the key Assume F is length preserving: F(k, x) only defined if |k|=|x|, in which case |F(k, x)| = |k| = |x| Choosing a uniform k {0,1}nis equivalent to choosing the function Fk: {0,1}n {0,1}n I.e., for fixed key length n, the algorithm F defines a distribution over functions in Funcn!

x1 f(x1) xt f(xt) f Funcn chosen uniformly at random f ?? World 0 x1 World 1 (poly-time) Fk(x1) xt Fk(xt) k {0,1}n chosen uniformly at random Fk

Pseudorandom permutations (PRPs) Let f Funcn f is a permutation if it is a bijection This means that the inverse f-1 exists Let Permn Funcn be the set of permutations What is |Permn|?

Pseudorandom permutations Let F be a length-preserving, keyed function F is a keyed permutation if Fk is a permutation for every k Fk-1 is efficiently computable (where Fk-1(Fk(x)) = x) F is a pseudorandom permutation if Fk , for uniform key k {0,1}n, is indistinguishable from a uniform permutation f Permn

Note For large enough n, a random permutation is indistinguishable from a random function So in practice, PRPs are also good PRFs Proof in the book (required!)

PRFs vs. PRGs PRF F immediately implies a PRG G: Define G(k) = Fk(0 0) | Fk(0 1) I.e., G(k) = Fk(<0>) | Fk(<1>) | Fk(<2>) | , where <i> denotes the n-bit encoding of i PRF can be viewed as a PRG with random access to exponentially long output The function Fk can be viewed as the n2n-bit string Fk(0 0) | | Fk(1 1)

Do PRFs/PRPs exist? They are a stronger primitive than PRGs though can be built from PRGs In practice, block ciphers are used

Block ciphers Block ciphers are practical constructions of pseudorandom permutations No asymptotics: F: {0,1}n x {0,1}m {0,1}m n = key length m = block length Hard to distinguish Fk from uniform f Permm even for attackers running in time 2n

AES Advanced encryption standard (AES) Standardized by NIST in 2000 based on a public, worldwide competition lasting over 3 years Block length = 128 bits Key length = 128, 192, or 256 bits Will not discuss details later in the course No real reason to use anything else

CPA-security Fix , A Define a randomized exp t PrivKCPAA, (n): 1. k Gen(1n) 2. A(1n) interacts with an encryption oracle Enck( ), and then outputs m0, m1 of the same length 3. b {0,1}, c Enck(mb), give c to A 4. A can continue to interact with Enck( ) 5. A outputs b ; A succeedsif b = b , and experiment evaluates to 1 in this case

CPA-security is secure against chosen-plaintext attacks (CPA-secure) if for all PPT attackers A, there is a negligible function such that Pr[PrivKCPAA, (n) = 1] + (n)

CPA-secure encryption Let F be a length-preserving, keyed function Gen(1n): choose a uniform key k {0, 1}n Enck(m), for |m| = |k|: Choose uniform r {0, 1}n (nonce/initialization vector) Output ciphertext < r, Fk(r) m > Deck(c1, c2): output c2 Fk(c1) Correctness is immediate

r key F pseudorandom pseudorandom ciphertext message message

Security? Theorem: if F is a pseudorandom function, then this scheme is CPA-secure

Note The key may be as long as the message but the same key can be used to safely encrypt multiple messages

Security? Theorem: if F is a pseudorandom function, then this scheme is CPA-secure Proof by reduction Let denote the scheme

PR/random m f(r) r {0,1}n m r, f(r) m D

PR/random f(r*) m0, m1 r* {0,1}n mb b {0,1} r*, f(r*) mb b if (b=b ) output 1 D

Analysis Let (n) = Pr[PrivCPAAdv, (n) = 1] Let q(n) be a bound on the number of encryption queries made by attacker If f = Fk for uniform k, then the view of Adv is exactly as in PrivCPAAdv, (n) Prk {0,1}n[DFk( ) =1] = Pr[PrivCPAAdv, (n) = 1] = (n)

Analysis If f is uniform, there are two sub-cases r* was used for some other ciphertext (call this event Repeat) r* was not used for some other ciphertext Prf[Df( )=1] Prf[Df( ) =1| Repeat] + Pr[Repeat] Pr[Repeat] q(n)/2n Prf[Df( ) =1 | Repeat] =

Analysis Since F is pseudorandom | (n) Prf[Df( )=1] | (n) (n) Prf[Df( ) =1] + (n) + q(n)/2n + (n) For any polynomial q, the term q(n)/2n is negligible Pr[PrivCPAAdv, (n) = 1] = (n) + (n) QED

Real-world security? The security bound we proved is tight What happens if a nonce r is ever reused? What is the probability that the nonce used in some challenge ciphertext is also used for some other ciphertext? What happens to the bound if the nonce is chosen non-uniformly?

CPA-secure encryption We have shown a CPA-secure encryption scheme based on any block cipher/PRF Enck(m) = <r, Fk(r) m> Drawbacks? A 1-block plaintext results in a 2-block ciphertext Only defined for encryption of n-bit messages

Encrypting long messages? Recall that CPA-security security for the encryption of multiple messages So, can encrypt the message m1, , mt as Enck(m1), Enck(m2), , Enck(mt) This is also CPA-secure!

c1 ... c1, , ct ct k k m1, , mt c1 Enck(m1) ct Enck(mt)

Drawback The ciphertext is twice the length of the plaintext I.e., ciphertext expansion by a factor of two Can we do better? Modes of operation Block-cipher modes of operation Stream-cipher modes of operation

CTR mode Enck(m1, , mt) // note: t is arbitrary Choose ctr {0,1}n, set c0 = ctr For i=1 to t: ci = mi Fk(ctr + i) Output c0, c1, , ct Decryption? Ciphertext expansion is just 1 block

CTR mode ctr ctr+1 ctr+2 ctr+t Fk Fk Fk m1 m2 mt c0 c1 c2 ct

CTR mode Theorem: If F is a pseudorandom function, then CTR mode is CPA-secure Proof sketch: The sequence Fk(ctri+ 1), , Fk(ctri + t) used to encrypt the ith message is pseudorandom Moreover, it is independent of every other such sequence unless ctri + j = ctri + j for some i, j, i , j Just need to bound the probability of that event

CBC mode Enck(m1, , mt) Choose random c0 {0,1}n (also called the IV) For i=1 to t: ci = Fk(mi ci-1) Output c0, c1, , ct // note: t is arbitrary Decryption? Requires F to be invertible Ciphertext expansion is just 1 block

CBC mode m2 mt m1 IV Fk Fk Fk c2 ct c0 c1

CBC mode Theorem: If F is a pseudorandom permutation, then CBC mode is CPA-secure Proof is more complicated than for CTR mode

ECB mode Enck(m1, , mt) = Fk(m1), , Fk(mt) Deterministic Not CPA-secure! Can tell from the ciphertext whether mi = mj Not even EAV-secure!

Not just a theoretical problem! original encrypted using ECB mode (Taken from http://en.wikipedia.org and derived from images created by Larry Ewing (lewing@isc.tamu.edu) using The GIMP.)