diff options
author | Gregor Kleen <gkleen@yggdrasil.li> | 2017-10-24 15:33:07 +0200 |
---|---|---|
committer | Gregor Kleen <gkleen@yggdrasil.li> | 2017-10-24 15:33:07 +0200 |
commit | 162df3190c4e179ef968b0a467ddd4951faba336 (patch) | |
tree | 3c9628cf1abf259e1b897ac14b006e2b448cff27 /ss2017/cryptography/Notes16.txt | |
parent | 92ed41381f40c97b52b0e96f0eaeaa9025091411 (diff) | |
download | uni-162df3190c4e179ef968b0a467ddd4951faba336.tar uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.gz uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.bz2 uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.xz uni-162df3190c4e179ef968b0a467ddd4951faba336.zip |
Notes on cryptography
Diffstat (limited to 'ss2017/cryptography/Notes16.txt')
-rw-r--r-- | ss2017/cryptography/Notes16.txt | 318 |
1 files changed, 318 insertions, 0 deletions
diff --git a/ss2017/cryptography/Notes16.txt b/ss2017/cryptography/Notes16.txt new file mode 100644 index 0000000..f75607d --- /dev/null +++ b/ss2017/cryptography/Notes16.txt | |||
@@ -0,0 +1,318 @@ | |||
1 | 16 Chosen ciphertext and random oracles | ||
2 | - - - - - - - - - - - - - - - - - - - - | ||
3 | |||
4 | Many public key schemes including the ones using the RSA assumption | ||
5 | presented earlier make use of an unkeyed hash function to scramble | ||
6 | ciphertext and thus to enhance security, thus in particular preventing | ||
7 | chosen-ciphertext attacks. In this chapter, we will formulate these | ||
8 | attacks, remedies against them, and a semi-rigorous method for proving | ||
9 | there relative security. | ||
10 | |||
11 | |||
12 | Chosen ciphertext attacks | ||
13 | - - - - - - - - - - - - - | ||
14 | |||
15 | Chosen ciphertext attacks (CCA) model scenarios where the attacker can | ||
16 | request the decryption of ciphertexts of its choice. This is relevant | ||
17 | in a number of practical scenarios, where cryptosystems are used as | ||
18 | building blocks in larger protocols. Here a "man in the middle" can | ||
19 | intercept message and assume the role of one of the participants. The | ||
20 | messages it fabricates will then---at least up to a point---be | ||
21 | decrypted by the honest parties. | ||
22 | |||
23 | None of the schemes presented to far is secure against CCA. Consider | ||
24 | for example a symmetric key encryption given by Enc_k(m) = | ||
25 | (r,F_k(r)+m) where r is a random nonce and F_k() is a PRF. | ||
26 | |||
27 | Consider an attacker who wishes to distinguishes encryptions of m0 = | ||
28 | 000...0 and m1 = 1111..1 as in the PrivK^eav experiment. If the | ||
29 | attacker is given (r,c) being the encryption of either m0 or m1 all it | ||
30 | has to do is to request the decryption of the chosen ciphertext (r,c') | ||
31 | where c' is c with the first bit flipped. Clearly, this will be | ||
32 | 1000..000 or 0111...111 according to whether m0 or m1 has been | ||
33 | encrypted and hence the attacker wins. | ||
34 | |||
35 | The situation is similar in the public key setting. Suppose for | ||
36 | instance that (c1,c2) is an ElGamal encryption of some message | ||
37 | m. Then, as we know, c1=g^y and c2=h^y*m where y is random but private | ||
38 | and h=g^x is public. Now, for any m' we have that (c1,c2*m') is a | ||
39 | valid encryption of m*m'. It is clear that this allows an adversary to | ||
40 | win the PubK^eav experiment: Given (c1,c2), the adversary can request | ||
41 | the decryption of (c1,c2*g). The adversary thus obtains m*g and can compute | ||
42 | m by multiplication with g^(-1). A similar argument can be made for | ||
43 | various cryptosytems based on RSA. | ||
44 | |||
45 | The property of the cryptosystems making that form of attack possible | ||
46 | is known as *malleability*. From a given ciphertext it is possible to | ||
47 | produce another one that corresponds to a known transformation of the | ||
48 | plaintext. | ||
49 | |||
50 | We now define security against chosen ciphertext attacks formally in | ||
51 | the public key setting. The corresponding definition for private keys | ||
52 | is analogous. | ||
53 | |||
54 | Let A be a ppt adversary and Pi be a public key cryptosystem. The experiment | ||
55 | PubK^cca_{A,Pi}(n) is defined as follows. | ||
56 | |||
57 | 1. (pk,sk)<-Gen(n) | ||
58 | 2. A is given n, the public key pk, and access to a decryption oracle Dec_sk() | ||
59 | /* in the private key setting A also gets access to an encryption oracle like in CPA security */ | ||
60 | A outputs two messages m0,m1 | ||
61 | 3. b<-{0,1} | ||
62 | 4. c<-Enc_pk(m_b) is given to A | ||
63 | 5. A continues to have access to the decryption oracle but may, of course, not | ||
64 | request the decryption of c itself. Any other ciphertext is allowed. | ||
65 | 6. A outputs a bit b' and the outcome is 1 if b=b', 0 otherwise. | ||
66 | |||
67 | The cryptosystem is deemed CCA-secure if the success probability in | ||
68 | this experiment is 1/2+negl(n). | ||
69 | |||
70 | |||
71 | CCA secure private key cryptography using MACs | ||
72 | - - - - - - - - - - - - - - - - - - - - - - - - | ||
73 | |||
74 | In the private key case such CCA-secure schemes can be constructed by | ||
75 | combining a CPA-secure system PiE with a secure MAC PiM as follows: | ||
76 | |||
77 | A key pair (k1,k2) is generated, k1 for PiE and k2 for the MAC PiM. | ||
78 | |||
79 | The encryption of m under (k1,k2) is given by (c,t) where | ||
80 | c<-Enc_{k1}(m) and t<-Mac_{k2}(c). Thus, we authenticate the | ||
81 | ciphertext so as to prevent any modification. | ||
82 | |||
83 | To decrypt (c,t) we first check that Mac_{k2}(c)=t and only then | ||
84 | return Dec_{k1}(c). If Mac_{k2}(c) is different from t we return a | ||
85 | default value _|_. | ||
86 | |||
87 | One can now show that---assuming PiE and PiM are themselves | ||
88 | secure---this scheme achieves CCA security. The proof idea is that | ||
89 | assuming PiM is secure the probability that the adversary makes a | ||
90 | query which is answered with a value different from _|_ is | ||
91 | negligible. We can therefore assume that all queries are answered with | ||
92 | _|_ and in this case the experiment degrades to a PrivK^cpa experiment | ||
93 | against which PiE is assumed secure. For details see KL4.8. | ||
94 | |||
95 | |||
96 | CCA-secure public key cryptography using hash functions | ||
97 | - - - - - - - - - - - - - - - - - - - - - - - - - - - - | ||
98 | |||
99 | Building CCA-secure public key systems is more difficult and typically | ||
100 | uses hybrid encryption with a CCA-secure private key system and, | ||
101 | additionally, a "cryptographic hash function" H(). Here we show one such | ||
102 | system using RSA, which at the same time gives an example of a | ||
103 | security proof based on the RSA assumption. | ||
104 | |||
105 | Assume thus that Pi0=(Enc0,Dec0) is a CCA-secure private key | ||
106 | cryptosystem which uses uniformly distributed keys from {0,1}^n (so | ||
107 | there is no "Gen0"). Assume further that H:{0,1}^n->{0,1}^n is a | ||
108 | "cryptographic hash function". We will later discuss what this should | ||
109 | mean formally in this context. We will need stronger properties than | ||
110 | just the collision-resistance that we have required of hash functions | ||
111 | before. | ||
112 | |||
113 | Finally, assume that GenRSA() is an RSA key generator for which the | ||
114 | RSA hardness assumption holds. | ||
115 | |||
116 | We then construct a public key cryptosystem Pi=(Gen,Enc,Dec) as follows. | ||
117 | |||
118 | |||
119 | Gen(n): | ||
120 | (N,d,e)<- GenRSA(n) | ||
121 | pk = (N,e), sk=(N,d) | ||
122 | return (pk,sk) | ||
123 | |||
124 | Enc_{(N,e)}(m): | ||
125 | 1. r <- {0,1}^n | ||
126 | 2. k = H(r) | ||
127 | 3. return (r^e mod N, Enc0_k(m)) | ||
128 | |||
129 | Dec_{(N,d)}(c1,c2): | ||
130 | 1. r = c1^d mod N | ||
131 | 2. k = H(r) | ||
132 | 3. return Dec0_k(c2) | ||
133 | |||
134 | Why should this scheme be CCA secure? Intuitively, given the RSA-assumption, | ||
135 | the attacker has no way of recovering r, hence the likelihood | ||
136 | that it applies (the publicly known function) H() to r is negligible | ||
137 | and as a result all H()-values it sees would look random to it. Thus, | ||
138 | the key used in the private key encryption of the actual message is as | ||
139 | good as random so that the security assumption on Pi2 applies and the | ||
140 | entire scheme is secure. | ||
141 | |||
142 | We need the function H to make the key k look random. It may be tempting | ||
143 | to just try to use r as the encryption key. But the RSA-assumption gives | ||
144 | us only that the attacker cannot recover r fully. It does not rule out | ||
145 | that the attacker obtains a few bits of r. If we used r as key, then | ||
146 | it would not be fully random and the security assumption on Pi2 could | ||
147 | not be used. | ||
148 | |||
149 | |||
150 | The random oracle model | ||
151 | - - - - - - - - - - - - | ||
152 | |||
153 | The question is under what assumptions on H() the above argument can | ||
154 | be made rigorous. Assuming H() to be a PRF does not work because those | ||
155 | always require a secret key. Once you know the key there is nothing | ||
156 | random about a PRF. Taking a PRG also does not work, as its output | ||
157 | looks random only if the input is random as well. | ||
158 | Assuming that H() is merely a secure hash function does not suffice | ||
159 | either because nothing prevents a good hash function from, for example, | ||
160 | producing hash strings which contain predictable portions. | ||
161 | E.g. if H0() is a secure hash function so is H(x) = 0.....0 H0(x). | ||
162 | |||
163 | Unfortunately, there have not been found any plausible assumptions on | ||
164 | the function H() under which schemes like the above could be proved | ||
165 | secure. A possible way out is the random oracle model which we now describe. | ||
166 | |||
167 | In this model, one instantiates H() with a function that is randomly | ||
168 | chosen at the beginning of each experiment, i.e., the probabilities | ||
169 | are taken over uniform random choices of H() which is therefore called | ||
170 | *random oracle*. All participants in the experiment get access to H. | ||
171 | It would be possible to actually implement this by using a trusted | ||
172 | party, e.g. an internet server which must called for any evaluation of | ||
173 | H(). It can either precompute the entire value table of H() (finite | ||
174 | for a given security parameter) using random choices or alternatively, | ||
175 | fill this table on demand, i.e. regurgitate H-values on previously | ||
176 | requested arguments and make random choices for new requests. | ||
177 | |||
178 | In practice, however, this approach is unfeasible, and so the random | ||
179 | oracle, for which schemes like the above one *can be proved secure*, | ||
180 | is replaced with a cryptographic hash function such as SHA-2. Whether | ||
181 | or not the security proof in the random oracle model has any bearing | ||
182 | on this instantiation remains open. | ||
183 | |||
184 | In fact, it has been shown that there exist contrived cryptographic | ||
185 | schemes which are secure in the random oracle model but insecure with | ||
186 | any concrete instantiation. Nevertheless, a proof in the random oracle | ||
187 | model consists strong evidence as to the security of a scheme and | ||
188 | perhaps even more importantly, failure to prove a system secure in the | ||
189 | random oracle model might point out actual flaws of a scheme. KL | ||
190 | contains a longer discussion of the metamathematical or epistemic | ||
191 | implications of the random oracle model without however being able to | ||
192 | get over the central issue that a proof in the random oracle model | ||
193 | does not imply anything---in the rigorous mathematical sense---about | ||
194 | the "standard model" which is used in actual practice. | ||
195 | |||
196 | |||
197 | |||
198 | Secure hash functions and pseudorandom functions in the random oracle model | ||
199 | - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - | ||
200 | |||
201 | As a warmup let us see how random oracles can be used to construct | ||
202 | secure hash functions and pseudo random functions. | ||
203 | |||
204 | We fix a length function l(n), e.g. l(n)=n or l(n)=n/2 and let H : | ||
205 | {0,1}^n->{0,1}^{l(n)} be a random function. | ||
206 | |||
207 | We now show that H() itself is a secure hash function. Consider a ppt | ||
208 | adversary A who gets oracle access to H() and conduct the Hash-coll | ||
209 | experiment from Chapter 11 with random H(): | ||
210 | |||
211 | 1. Choose H() at random | ||
212 | 2. Adversary A gets oracle access to H() and outputs values x,x':{0,1}^n | ||
213 | such that x != x'. | ||
214 | 3. The outcome of the experiment is 1 iff H(x)=H(x') | ||
215 | |||
216 | Theorem: | ||
217 | |||
218 | The success probability of this experiment, taken over uniform random | ||
219 | choice of H and the random choices that A might make is a negligible | ||
220 | function of the security parameter. | ||
221 | |||
222 | Proof. Let x1...xk be the sequence of values that A queries of H prior to | ||
223 | outputting x,x'. Clearly, k is polynomial in the security parameter n | ||
224 | due to the polynomial time bound on the computation time of A. The | ||
225 | probability that H(xi)=H(xj) for some i!=j is therefore | ||
226 | negligible. Notice that we can assume that H-values are selected "on | ||
227 | demand". Thus, when x,x' are among the x1..xk the success probability | ||
228 | is negligible. If, however, A chooses at least one of them afresh | ||
229 | then, again, the success probability is negligible because only a | ||
230 | negligible portion of the possible H-values is favourable. QED | ||
231 | |||
232 | Notice that, in a way, the earlier account of hash functions in | ||
233 | Chapter 11 was also based on some kind of random oracle in that we | ||
234 | assumed a uniformly random selection of the seed which also does not | ||
235 | happen in practice. | ||
236 | |||
237 | |||
238 | A pseudorandom function from a random oracle | ||
239 | - - - - - - - - - - - - - - - - - - - - - - - | ||
240 | |||
241 | The random oracle can be used to obtain a PRF as follows: | ||
242 | |||
243 | Theorem: Let l(n)=n/2 and define F_k(x) = H(k || x). Notice that for | ||
244 | k,x:{0,1}^n we have F_k(x):{0,1}^n. Now, F_k() is a PRF in the | ||
245 | following sense. Let D be a ppt distinguisher with oracle access to a | ||
246 | function g():{0,1}^n->{0,1}^n *and* the random function H(). We write | ||
247 | this as D^{g(),H()}(n). We then have | ||
248 | |||
249 | | Pr[ D^{F_k(),H()}(n)=1 ] - Pr[ D^{f(),H()}(n)=1 ] | = negl(n) | ||
250 | |||
251 | with probabilities taken over a random function f(), the key k and the | ||
252 | random function H() appearing in F_k(). | ||
253 | |||
254 | Proof: As before, we can condition on the queries made to H() by D | ||
255 | during its computation. So long as these are disjoint from those made | ||
256 | as part of evaluations of F_k() we are in the situation of the | ||
257 | previous theorem. But then the probability for such a coincidence is | ||
258 | negligible by the randomization over k. The details are left as an | ||
259 | exercise. QED | ||
260 | |||
261 | It is now also possible to show that the abovedescribed hybrid | ||
262 | encryption system is CCA secure; however, for simplicity, we only show | ||
263 | its CPA security which is already nontrivial. Also, we have not | ||
264 | seen any provably secure RSA-based cryptosystem so far. | ||
265 | |||
266 | Theorem: Let Pi0 be a CPA-secure private key system and let | ||
267 | Pi be the hybrid system as described above. Then for any ppt adversary, which | ||
268 | is given additional access to the random oracle H(), one has | ||
269 | |||
270 | Pr[ PubK^eav_{Pi,A^{H()}}(n) = 1 ] = 1/2 + negl(n) | ||
271 | |||
272 | with probabilities taken over random choice of H(), the random steps | ||
273 | taken within A, and those in the PubK^eav experiment. | ||
274 | |||
275 | Proof sketch: For convenience we recall the steps of the experiment. | ||
276 | |||
277 | 1. H() is chosen at random. | ||
278 | 2. (N,e,d) <- GenRSA(n); pk=(N,e); sk=(N,d) | ||
279 | 3. A is given access to pk and H() | ||
280 | 4. A outputs messages m0, m1. | ||
281 | 5. r<-{0,1}^n; k=H(r) | ||
282 | 6. b<-{0,1} | ||
283 | 7. c1<-r^e mod N | ||
284 | 8. c2<-Enc0_k(m_b) | ||
285 | 9. A is given (c1,c2) and returns b' | ||
286 | 10. Outcome is 1 iff b=b' | ||
287 | |||
288 | The encryption and decryption algorithms that A is given oracle access | ||
289 | to essentially follow lines 5-9 and are not repeated here. | ||
290 | |||
291 | Let us call QUERY the event that A queries H() on one of the random | ||
292 | nonces r used either in line 5 or as part of its queries to the | ||
293 | encryption oracle. | ||
294 | |||
295 | The idea is that since---assuming as we do---GenRSA satisfies the RSA | ||
296 | hardness assumption, the probability of QUERY is negligible. | ||
297 | This is because we can use A to construct an adversary in the RSA-inv | ||
298 | experiment as follows. We use A as a subroutine and run it according | ||
299 | to protocol. We monitor all queries of A to H() and for each one of | ||
300 | those, call it r_q, check whether r_q^e mod N is correct. If this is | ||
301 | the case, then we output r_q. By the RSA hardness assumption, this | ||
302 | adversary can output the correct r only with negligible probability, | ||
303 | which means that the probability of QUERY must be negligible. | ||
304 | |||
305 | Once we know that QUERY is a negligible event we can assume without | ||
306 | loss of generality that it does not occur, i.e., oracle access to H() | ||
307 | returns random values that are completely unrelated to the experiment. | ||
308 | We can thus assume that A does not get access to H() at all and then | ||
309 | the CPA-secure scheme Pi0 is secure by assumption. | ||
310 | |||
311 | We refer to KL Theorem 13.1 for details and to KL Theorem 13.5 for a | ||
312 | proof that the hybrid scheme even yields CCA security assuming Pi0 is | ||
313 | CCA secure. | ||
314 | |||
315 | We also remark that the deterministic version of RSA used to encrypt | ||
316 | the symmetric key can be replaced by an arbitrary so-called key | ||
317 | encapsulation mechanism (KEM), without essentially changing the | ||
318 | proof. See KL, 2nd ed for details. | ||