PSEUDO-RANDOM FUNCTIONS Mihir Bellare UCSD 1 Recall We studied security of a block cipher against key recovery. But we saw that security against key recovery is not sufficient to ensure that natural usages of a block cipher are secure. We want to answer the question: What is a good block cipher? where “good” means that natural uses of the block cipher are secure. We could try to define “good” by a list of necessary conditions: • Key recovery is hard • Recovery of M from C = EK (M) is hard • ... But this is neither necessarily correct nor appealing. Mihir Bellare UCSD 2 Turing Intelligence Test Q: What does it mean for a program to be “intelligent” in the sense of a human? Possible answers: • It can be happy • It recognizes pictures • It can multiply • But only small numbers! • • Clearly, no such list is a satisfactory answer to the question. Mihir Bellare UCSD 3 Turing Intelligence Test Q: What does it mean for a program to be “intelligent” in the sense of a human? Turing’s answer: A program is intelligent if its input/output behavior is indistinguishable from that of a human. Mihir Bellare UCSD 4 Turing Intelligence Test Behind the wall: • Room 1: The program P • Room 0: A human Mihir Bellare UCSD 5 Turing Intelligence Test Game: • Put tester in room 0 and let it interact with object behind wall • Put tester in rooom 1 and let it interact with object behind wall • Now ask tester: which room was which? The measure of “intelligence” of P is the extent to which the tester fails. Mihir Bellare UCSD 6 Real versus Ideal Notion Intelligence PRF Mihir Bellare Real object Program Block cipher UCSD Ideal object Human ? 7 Real versus Ideal Notion Intelligence PRF Mihir Bellare Real object Program Block cipher UCSD Ideal object Human Random function 8 Random functions Game RandR // here R is a set procedure Fn(x) $ if T[x] = ⊥ then T[x] ← R return T[x] Adversary A • Make queries to Fn • Eventually halts with some output We denote by h i Pr RandA ⇒ d R the probability that A outputs d Mihir Bellare UCSD 9 Random functions Game Rand{0,1}3 procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}3 return T[x] adversary A y ← Fn(01) return (y = 000) h i Pr RandA ⇒ true = 3 {0,1} Mihir Bellare UCSD 10 Random functions Game Rand{0,1}3 procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}3 return T[x] adversary A y ← Fn(01) return (y = 000) h i Pr RandA ⇒ true = 2−3 3 {0,1} Mihir Bellare UCSD 11 Random function Game Rand{0,1}3 procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}3 return T[x] adversary A y1 ← Fn(00) y2 ← Fn(11) return (y1 = 010 ∧ y2 = 011) h i Pr RandA ⇒ true = 3 {0,1} Mihir Bellare UCSD 12 Random function Game Rand{0,1}3 procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}3 return T[x] adversary A y1 ← Fn(00) y2 ← Fn(11) return (y1 = 010 ∧ y2 = 011) h i Pr RandA ⇒ true = 2−6 3 {0,1} Mihir Bellare UCSD 13 Random function Game Rand{0,1}3 procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}3 return T[x] adversary A y1 ← Fn(00) y2 ← Fn(11) return (y1 ⊕ y2 = 101) h i Pr RandA ⇒ true = 3 {0,1} Mihir Bellare UCSD 14 Random function Game Rand{0,1}3 procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}3 return T[x] adversary A y1 ← Fn(00) y2 ← Fn(11) return (y1 ⊕ y2 = 101) h i Pr RandA ⇒ true = 2−3 3 {0,1} Mihir Bellare UCSD 15 Function families A family of functions F : Keys(F ) × Dom(F ) → Range(F ) is a two-argument map. For K ∈ Keys(F ) we let FK : Dom(F ) → Range(F ) be defined by ∀x ∈ Dom(F ) : FK (x) = F (K , x) Examples: • DES: Keys(F ) = {0, 1}56 , Dom(F ) = Range(F ) = {0, 1}64 • Any block cipher: Dom(F ) = Range(F ) and each FK is a permutation Mihir Bellare UCSD 16 Real versus Ideal Notion PRF Real object Family of functions (eg. a block cipher) Ideal object Random function F is a PRF if the input-output behavior of FK looks to a tester like the input-output behavior of a random function. Tester does not get the key K ! Mihir Bellare UCSD 17 Games defining prf advantage of an adversary against F Let F : Keys(F ) × Dom(F ) → Range(F ) be a family of functions. Game RealF Game RandRange(F ) procedure Initialize $ K ← Keys(F ) procedure Fn(x) $ if T[x] = ⊥ then T[x] ← Range(F ) Return T[x] procedure Fn(x) Return FK (x) Associated to F , A are the probabilities h h i i Pr RandA ⇒1 Pr RealA F ⇒1 Range(F ) that A outputs 1 in each world. The advantage of A is h i h i A A Advprf (A) = Pr Real ⇒1 − Pr Rand ⇒1 F Range(F ) F Mihir Bellare UCSD 18 PRF advantage A’s output d 1 0 Intended meaning: I think I am in game Real Random Advprf F (A) ≈ 1 means A is doing well and F is not prf-secure. Advprf F (A) ≈ 0 (or ≤ 0) means A is doing poorly and F resists the attack A is mounting. Mihir Bellare UCSD 19 PRF security Adversary advantage depends on its • strategy • resources: Running time t and number q of oracle queries Security: F is a (secure) PRF if Advprf F (A) is “small” for ALL A that use “practical” amounts of resources. Example: 80-bit security could mean that for all n = 1, . . . , 80 we have −n Advprf F (A) ≤ 2 for any A with time and number of oracle queries at most 280−n . Insecurity: F is insecure (not a PRF) if we can specify an A using “few” resources that achieves “high” advantage. Mihir Bellare UCSD 20 Example Define F : {0, 1}` × {0, 1}` → {0, 1}` by FK (x) = K ⊕ x for all K , x ∈ {0, 1}` . Is F a secure PRF? Game RealF Game Rand{0,1}` procedure Initialize $ K ← Keys(F ) procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}` Return T[x] procedure Fn(x) Return K ⊕ x So we are asking: Can we design a low-resource A so that h i h i A A Advprf (A) = Pr Real ⇒1 − Pr Rand ⇒1 ` F F {0,1} is close to 1? Mihir Bellare UCSD 21 Example Define F : {0, 1}` × {0, 1}` → {0, 1}` by FK (x) = K ⊕ x for all K , x ∈ {0, 1}` . Is F a secure PRF? Game RealF Game Rand{0,1}` procedure Initialize $ K ← Keys(F ) procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}` Return T[x] procedure Fn(x) Return K ⊕ x So we are asking: Can we design a low-resource A so that h i h i A A Advprf (A) = Pr Real ⇒1 − Pr Rand ⇒1 ` F F {0,1} is close to 1? Exploitable weakness of F : For all K we have FK (0` ) ⊕ FK (1` ) = (K ⊕ 0` ) ⊕ (K ⊕ 1` ) = 1` Mihir Bellare UCSD 22 Example: The adversary F : {0, 1}` × {0, 1}` → {0, 1}` is defined by FK (x) = K ⊕ x. adversary A if Fn(0` ) ⊕ Fn(1` ) = 1` then return 1 else return 0 Mihir Bellare UCSD 23 Example: Real game analysis F : {0, 1}` × {0, 1}` → {0, 1}` is defined by FK (x) = K ⊕ x. adversary A if Fn(0` ) ⊕ Fn(1` ) = 1` then return 1 else return 0 Game RealF procedure Initialize $ K ← Keys(F ) procedure Fn(x) Return K ⊕ x h i Pr RealA ⇒1 = F Mihir Bellare UCSD 24 Example: Real game analysis F : {0, 1}` × {0, 1}` → {0, 1}` is defined by FK (x) = K ⊕ x. adversary A if Fn(0` ) ⊕ Fn(1` ) = 1` then return 1 else return 0 Game RealF procedure Initialize $ K ← Keys(F ) procedure Fn(x) Return K ⊕ x h i Pr RealA ⇒1 =1 F because Fn(0` ) ⊕ Fn(1` ) = FK (0` ) ⊕ FK (1` ) = (K ⊕ 0` ) ⊕ (K ⊕ 1` ) = 1` Mihir Bellare UCSD 25 Example: Rand game analysis F : {0, 1}` × {0, 1}` → {0, 1}` is defined by FK (x) = K ⊕ x. adversary A if Fn(0` ) ⊕ Fn(1` ) = 1` then return 1 else return 0 Game Rand{0,1}` procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}` Return T[x] h i Pr RandA ⇒1 = ` {0,1} Mihir Bellare UCSD 26 Example: Rand game analysis F : {0, 1}` × {0, 1}` → {0, 1}` is defined by FK (x) = K ⊕ x. adversary A if Fn(0` ) ⊕ Fn(1` ) = 1` then return 1 else return 0 Game Rand{0,1}` procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}` Return T[x] h i h i ` ` ` Pr RandA ⇒1 = Pr Fn(1 ) ⊕ Fn(0 ) = 1 = ` {0,1} Mihir Bellare UCSD 27 Example: Rand game analysis F : {0, 1}` × {0, 1}` → {0, 1}` is defined by FK (x) = K ⊕ x. adversary A if Fn(0` ) ⊕ Fn(1` ) = 1` then return 1 else return 0 Game Rand{0,1}` procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}` Return T[x] h i h i ` ` ` Pr RandA ⇒1 = Pr Fn(1 ) ⊕ Fn(0 ) = 1 = 2−` ` {0,1} because Fn(0` ), Fn(1` ) are random `-bit strings. Mihir Bellare UCSD 28 Example: Conclusion F : {0, 1}` × {0, 1}` → {0, 1}` is defined by FK (x) = K ⊕ x. adversary A if Fn(0` ) ⊕ Fn(1` ) = 1` then return 1 else return 0 Then 2−` 1 }| z h }| i{ z h i{ prf A A AdvF (A) = Pr RealF ⇒1 − Pr Rand{0,1}` ⇒1 = 1 − 2−` and A is efficient . Conclusion: F is not a secure PRF. Mihir Bellare UCSD 29 Exercise Define the family of functions F : {0, 1}128 × {0, 1}128 → {0, 1}128 by F (K , M) = AES(M, K ). Assuming AES is a secure PRF, is F a secure PRF? If so, explain why. If not, present the best attack (with analysis) that you can. If you give an attack it should be presented in the format of the above examples, with an adversary clearly specified in pseudo-code, a claim about its advantage, and a succinct proof of the claim. Avoid long textual descriptions. Mihir Bellare UCSD 30 Exercise Let F : {0, 1}k × D → {0, 1}n be a family of functions and A an adversary. Prove that Advprf F (A) 6= 1 . Mihir Bellare UCSD 31 Birthday Problem We have q people 1, . . . , q with birthdays y1 , . . . , yq ∈ {1 . . . , 365}. Assume each person’s birthday is a random day of the year. Let C (365, q) = Pr [2 or more persons have same birthday] = Pr [y1 , . . . , yq are not all different] • What is the value of C (365, q)? • How large does q have to be before C (365, q) is at least 1/2? Mihir Bellare UCSD 32 Birthday Problem We have q people 1, . . . , q with birthdays y1 , . . . , yq ∈ {1 . . . , 365}. Assume each person’s birthday is a random day of the year. Let C (365, q) = Pr [2 or more persons have same birthday] = Pr [y1 , . . . , yq are not all different] • What is the value of C (365, q)? • How large does q have to be before C (365, q) is at least 1/2? Naive intuition: • C (365, q) ≈ q/365 • q has to be around 365 Mihir Bellare UCSD 33 Birthday Problem We have q people 1, . . . , q with birthdays y1 , . . . , yq ∈ {1 . . . , 365}. Assume each person’s birthday is a random day of the year. Let C (365, q) = Pr [2 or more persons have same birthday] = Pr [y1 , . . . , yq are not all different] • What is the value of C (365, q)? • How large does q have to be before C (365, q) is at least 1/2? Naive intuition: • C (365, q) ≈ q/365 • q has to be around 365 The reality • C (365, q) ≈ q 2 /365 • q has to be only around 23 Mihir Bellare UCSD 34 Birthday collision bounds C (365, q) is the probability that some two people have the same birthday in a room of q people with random birthdays q 15 18 20 21 23 25 27 30 35 40 50 Mihir Bellare C (365, q) 0.253 0.347 0.411 0.444 0.507 0.569 0.627 0.706 0.814 0.891 0.970 UCSD 35 Birthday Problem $ Pick y1 , . . . , yq ← {1, . . . , N} and let C (N, q) = Pr [y1 , . . . , yq not all distinct] Birthday setting: N = 365 Mihir Bellare UCSD 36 Birthday Problem $ Pick y1 , . . . , yq ← {1, . . . , N} and let C (N, q) = Pr [y1 , . . . , yq not all distinct] Birthday setting: N = 365 Fact: C (N, q) ≈ Mihir Bellare q2 2N UCSD 37 Birthday collisions formula $ Let y1 , . . . , yq ← {1, . . . , N}. Then 1 − C (N, q) = Pr [y1 , . . . , yq all distinct] N − (q − 1) N −1 N −2 · · ··· · N N N q−1 Y i = 1− N = 1· i=1 so C (N, q) = 1 − q−1 Y 1− i=1 Mihir Bellare UCSD i N 38 Birthday bounds Let C (N, q) = Pr [y1 , . . . , yq not all distinct] Fact: Then q(q − 1) q(q − 1) ≤ C (N, q) ≤ 0.5 · N N √ where the lower bound holds for 1 ≤ q ≤ 2N. 0.3 · Mihir Bellare UCSD 39 Block ciphers as PRFs Let E : {0, 1}k × {0, 1}` → {0, 1}` be a block cipher. Game RealE Game Rand{0,1}` procedure Initialize $ K ← {0, 1}k procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}` Return T[x] procedure Fn(x) Return EK (x) Can we design A so that h i h i A A Advprf (A) = Pr Real ⇒1 − Pr Rand ⇒1 E E {0,1}` is close to 1? Mihir Bellare UCSD 40 Block ciphers as PRFs Defining property of a block cipher: EK is a permutation for every K So if x1 , . . . , xq are distinct then • Fn = EK ⇒ Fn(x1 ), . . . , Fn(xq ) distinct • Fn random ⇒ Fn(x1 ), . . . , Fn(xq ) not necessarily distinct This leads to the following attack: adversary A Let x1 , . . . , xq ∈ {0, 1}` be distinct for i = 1, . . . , q do yi ← Fn(xi ) if y1 , . . . , yq are all distinct then return 1 else return 0 Mihir Bellare UCSD 41 Real world analysis Let E : {0, 1}k × {0, 1}` → {0, 1}` be a block cipher Game RealE procedure Initialize $ K ← {0, 1}k procedure Fn(x) Return EK (x) Then Mihir Bellare adversary A Let x1 , . . . , xq ∈ {0, 1}` be distinct for i = 1, . . . , q do yi ← Fn(xi ) if y1 , . . . , yq are all distinct then return 1 else return 0 h i Pr RealA ⇒1 = E UCSD 42 Real world analysis Let E : {0, 1}k × {0, 1}` → {0, 1}` be a block cipher Game RealE procedure Initialize $ K ← {0, 1}k procedure Fn(x) Return EK (x) Then adversary A Let x1 , . . . , xq ∈ {0, 1}` be distinct for i = 1, . . . , q do yi ← Fn(xi ) if y1 , . . . , yq are all distinct then return 1 else return 0 h i Pr RealA ⇒1 =1 E because y1 , . . . , yq will be distinct because EK is a permutation. Mihir Bellare UCSD 43 Rand world analysis Let E : {0, 1}K × {0, 1}` → {0, 1}` be a block cipher Game Rand{0,1}` procedure Fn(x) $ if T[x] = ⊥ then T[x] ← {0, 1}` Return T[x] adversary A Let x1 , . . . , xq ∈ {0, 1}` be distinct for i = 1, . . . , q do yi ← Fn(xi ) if y1 , . . . , yq are all distinct then return 1 else return 0 Then h i Pr RandA ⇒1 = Pr [y1 , . . . , yq all distinct] = 1 − C (2` , q) ` {0,1} because y1 , . . . , yq are randomly chosen from {0, 1}` . Mihir Bellare UCSD 44 Birthday attack on a block cipher E : {0, 1}k × {0, 1}` → {0, 1}` a block cipher adversary A Let x1 , . . . , xq ∈ {0, 1}` be distinct for i = 1, . . . , q do yi ← Fn(xi ) if y1 , . . . , yq are all distinct then return 1 else return 0 1−C (2` ,q) 1 z h }| }| i{ z h i{ prf A A AdvE (A) = Pr RealE ⇒1 − Pr Rand{0,1}` ⇒1 = C (2` , q) ≥ 0.3 · q(q − 1) 2` so q ≈ 2`/2 ⇒ Advprf E (A) ≈ 1 . Mihir Bellare UCSD 45 Birthday attack on a block cipher Conclusion: If E : {0, 1}k × {0, 1}` → {0, 1}` is a block cipher, there is an attack on it as a PRF that succeeds in about 2`/2 queries. Depends on block length, not key length! DES, 2DES, 3DES3 AES Mihir Bellare ` 64 128 UCSD 2`/2 232 264 Status Insecure Secure 46 KR-security versus PRF-security We have seen two possible metrics of security for a block cipher E • KR-security: It should be hard to find a key consistent with input-output examples of a hidden target key. • PRF-security: It should be hard to distinguish the input-output behavior of EK from that of a random function. Fact: PRF-security of E implies • KR-security of E • Many other security attributes of E This is a validation of the choice of PRF security as our main metric. Mihir Bellare UCSD 47 If E is PRF-secure then it is KR-secure Proposition: Let E : {0, 1}k × {0, 1}` → {0, 1}` be a blockcipher. Given a kr-adversary B making q (distinct!) oracle queries, we can construct a PRF adversary A making q oracle queries such that prf k−q` Advkr . E (B) ≤ AdvE (A) + 2 The running time of A is that of B plus O(q`). Interpretation: E is PRF secure ⇒ Advprf E (A) is small ⇒ Advkr E (B) is small ⇒ E is KR-secure. Example: If E = AES and q = 2 then 2k−q` = 2−128 . Our first example of a reduction and a proof by reduction! Mihir Bellare UCSD 48 Game defining kr-advantage of an adversary B against E Game KRE procedure Initialize $ K ← {0, 1}k ; i ← 0 procedure Fn(M) i ← i + 1; Mi ← M Ci ← E (K , Mi ) Return Ci procedure Finalize(K 0 ) win ← true For j = 1, . . . , i do If E (K 0 , Mj ) 6= Cj then win ← false If Mj ∈ {M1 , . . . , Mj−1 } then win ← false Return win The kr-advantage of B is B Advkr E (B) = Pr[KRE ⇒ true] Mihir Bellare UCSD 49 Games defining prf-advantage of an adversary A against E Game RealE Game Rand{0,1}` procedure Initialize $ K ← {0, 1}k procedure Fn(M) $ if T[M] = ⊥ then T[M] ← {0, 1}` Return T[M] procedure Fn(M) Return E (K , M) The prf-advantage of A is h i h i A A Advprf (A) = Pr Real ⇒1 − Pr Rand ⇒1 E E {0,1}` Mihir Bellare UCSD 50 Proof of Proposition Given B we build A as follows: adversary A i ← 0; d ← 1 K 0 ← B FnKRSim For j = 1, . . . , i do If (E (K 0 , Mj ) 6= Cj ) then d ← 0 Return d subroutine FnKRSim(M) i ← i + 1; Mi ← M Ci ← Fn(Mi ) return Ci A runs B, simulating B’s oracle via a subroutine that in turn invokes A’s own Fn oracle. When B returns a key K 0 , adversary A returns 1 if K 0 is consistent with the input-output examples, and 0 otherwise. Mihir Bellare UCSD 51 Real game analysis Game RealE procedure Initialize $ K ← {0, 1}k procedure Fn(M) Return EK (M) When A is executed in game RealE , subroutine FnKRSim(M) will return Fn(M), which equals EK (M). So B is getting the same responses it would in game KRE . So K 0 will be consistent with (M1 , C1 ), . . . , (Mq , Cq ) with probability the kr-advantage of B. So h i Pr RealA ⇒1 = Advkr E E (B) . Mihir Bellare UCSD 52 Rand game analysis Game Rand{0,1}` procedure Fn(x) $ if T[M] = ⊥ then T[M] ← {0, 1}` Return T[M] When A is executed in game Rand{0,1}` , subroutine FnKRSim(M) will return Fn(M), which is a random `-bit string. So B is getting back a sequence of q random, independent `-bit strings. So K 0 will be consistent with (M1 , C1 ), . . . , (Mq , Cq ) with probability at most 2k /2q` , because there are 2k choices for K 0 and 2q` choices for (C1 , . . . , Cq ). So h i Pr RandA ⇒1 ≤ 2k−q` . ` {0,1} Mihir Bellare UCSD 53 Closer look There is a lot going on in this proof! Look over it slowly, checking each step. In particular: So K 0 will be consistent with (M1 , C1 ), . . . , (Mq , Cq ) with probability at most 2k /2q` , because there are 2k choices for K 0 and 2q` choices for (C1 , . . . , Cq ). This is subtle because B picks K 0 as a function of C1 , . . . , Cq . The claim is justified by a counting argument. There are 2q` sequences (C1 , . . . , Cq ), but for only 2k of them does there even exist a K 0 which is consistent with (M1 , C1 ), . . . , (Mq , Cq ). We will do many such proofs, and you will be asked to do them on quizzes, so spend the time to understand this one! Ask now if you have doubts! Mihir Bellare UCSD 54 Our Assumptions DES, AES are good block ciphers in the sense that they are PRF-secure up to the inherent limitations of the birthday attack and known key-recovery attacks. You can assume this in designs and analyses. But beware that the future may prove these assumptions wrong! Mihir Bellare UCSD 55 Exercise: Setup Let F : {0, 1}k × {0, 1}l → {0, 1}L be a family of functions where l, L ≥ 128. Consider the following game G: procedure Initialize $ $ K ← {0, 1}k ; b ← {0, 1} procedure LR(x0 , x1 ) Ret F (K , xb ) procedure Finalize(b 0 ) Ret (b = b 0 ) We define h i B Advlr (B) = 2 · Pr G ⇒ true −1. F Let (x01 , x11 ), . . . , (x0q , x1q ) be the queries that B makes to its oracle. (Each query is a pair of l-bit strings, and there are q queries in all.) We say that B is legitimate if x01 , . . . , x0q are all distinct, and also x11 , . . . , x1q are all distinct. We say that F is LR-secure if Advlr F (B) is “small” for every legitimate B of “practical” resources. Mihir Bellare UCSD 56 Exercise: Questions 1. Show that the legitimacy condition is necessary for LR-security to be “interesting” by showing that if F is a block cipher then there is an efficient, illegitimate B such that Advlr F (B) = 1. 2. Let B be a legitimate lr-adversary that makes q oracle queries and has time-complexity t. Specify a prf-adversary A, also making q oracle queries and having time-complexity close to t, such that prf Advlr F (B) ≤ 2 · AdvF (A) . Explain why this reduction shows that if F is a secure PRF then it is LR-secure. 3. Is the converse true? Namely, if F is LR-secure, then is it a secure PRF? Answer YES or NO. If you say YES, justify this via a reduction, and, if NO, via a counter-example. Mihir Bellare UCSD 57

© Copyright 2020