Commit | Line | Data |
---|---|---|
32609df3 MW |
1 | \section{The Wrestlers Protocol} |
2 | \frame{\tableofcontents[currentsection]} | |
a6e375a6 | 3 | |
32609df3 | 4 | \subsection{Identification using Diffie-Hellman} |
a6e375a6 | 5 | |
32609df3 MW |
6 | \begin{frame}{Identification using Diffie-Hellman: properties} |
7 | \begin{itemize}[<+->] | |
a6e375a6 MW |
8 | \item Simple -- easy to remember, analyse and implement |
9 | \item Practical -- two scalar multiplications for each party | |
10 | \item Secure -- under Computational Diffie-Hellman assumption | |
11 | \item Zero-knowledge -- statistical ZK | |
12 | \item Proofs in random oracle model -- but without `programming' | |
13 | \end{itemize} | |
32609df3 | 14 | \end{frame} |
a6e375a6 | 15 | |
32609df3 MW |
16 | \begin{frame}{Identification using Diffie-Hellman: basic setting} |
17 | \begin{itemize}[<+->] | |
a6e375a6 MW |
18 | \item Cyclic group $(G, +)$ |
19 | \item $|G| = q$ is prime | |
20 | \item $P$ generates $G$ | |
21 | \item Alice's private key is $a \inr \Nupto{q}$ | |
22 | \item Alice's public key is $A = a P$ | |
23 | \item Assume computational Diffie-Hellman problem hard in $G$ | |
24 | \end{itemize} | |
32609df3 MW |
25 | \end{frame} |
26 | ||
27 | \begin{frame}{Identification using Diffie-Hellman: protocols} | |
28 | %% Overlays: | |
29 | %% 1 - basic setup (alice's keys) | |
30 | %% naïve version | |
31 | %% 2 - bob makes eqphemeral keys | |
32 | %% 3 - bob sends challenge to alice | |
33 | %% 4 - alice computes response and sends it back | |
34 | %% 5 - bob computes expected answer | |
35 | %% 6 - bob checks alice's response | |
36 | %% 7 - remark? | |
37 | %% hash fix (8) | |
38 | %% 9 - bob computes check hash and sends it | |
39 | %% 10 - alice verifies the hash | |
40 | %% 11 - remark? | |
41 | %% stinson-wu (12) | |
42 | %% 13 - check subgroup membership | |
43 | %% 14 - don't hash U | |
44 | %% 15 - remark? | |
45 | %% wrestlers (16) | |
46 | %% 17 - bob computes and sends c | |
47 | %% 18 - alice recovers and checks u | |
48 | \begin{protocol}{5}{16} | |
49 | \node [alice, thoughts] at (0, 2) | |
50 | {Private: $a \inr \Nupto{q}$ \\ | |
51 | Public: $A = a P$}; | |
52 | \uncover<2->{ | |
53 | \node [bob, thoughts] at (0, 4) | |
54 | {{$u \getsr \Nupto{q}$; \\ | |
55 | $U \gets u P$; \\ | |
56 | \action<5->{$Y \gets u A$;} \\ | |
57 | \action<9-| alert@9-11>{$ | |
58 | h \gets H(\cookie{check}, | |
59 | \only<9-13,16->{U, Y} | |
60 | \action<alert@14-15| only@14-15>{Y}) | |
61 | $;} \\ | |
62 | \action<17-| alert@17-> { | |
63 | $c \gets u \xor h$; | |
64 | } | |
65 | }}; | |
66 | } | |
67 | \uncover<3->{ | |
68 | \path [message, ->] (0, 10) -- node [above] | |
69 | {{\vphantom{$,$} | |
70 | \only<3-8>{$U$} | |
71 | \only<9-16>{$U, \alert<9-11>{h}$} | |
72 | \only<17->{$U, \alert<17->{c}$} }} | |
73 | +(1, 0); | |
74 | } | |
75 | \uncover<4->{ | |
76 | \node [alice, thoughts] at (0, 10) | |
77 | {{$Y' \gets a U$; \\ | |
78 | \action<only@10-16| alert@10-11> | |
79 | {Check $h = H(\cookie{check}, | |
80 | \only<10-13,16->{U, Y} | |
81 | \action<alert@14-15| only@14-15>{Y}) | |
82 | $; \\} | |
83 | \only<17-> | |
84 | {$h' \gets H(\cookie{check}, U, Y)$; \\} | |
85 | \action<only@13-15| alert@13-15>{Check $q U = 0$;} | |
86 | \action<only@18-| alert@18->{ | |
87 | $r' \gets h' \xor c$; \\ | |
88 | Check $r' P = U$; | |
89 | }}}; | |
90 | \path [message, <-] (0, 14) -- node [above] {$Y'$} +(1, 0); | |
91 | } | |
92 | \uncover<6->{ | |
93 | \node [bob, thoughts] at (0, 14) {Check $Y = Y'$;}; | |
94 | } | |
a6e375a6 | 95 | \end{protocol} |
32609df3 MW |
96 | \par\vskip-\bigskipamount |
97 | \begin{itemize} | |
98 | \item<only@2-7> Naïve attempt | |
99 | \only<7>{-- lots of attacks against this protocol.} | |
100 | \item<only@8-11> Fix it with a hash | |
101 | \only<11>{-- still open to small-subgroup attacks.} | |
102 | \item<only@12-15> Stinson-Wu [SW06] | |
103 | \only<15>{-- and assume Knowledge of Exponent.} | |
104 | \item<only@16-> The Wrestlers identification protocol $\Wident$. | |
105 | \end{itemize} \par | |
106 | \end{frame} | |
107 | ||
108 | \subsection{Key exchange} | |
109 | ||
110 | \begin{frame}{Mutual identification: protocol} | |
111 | \begin{protocol}{4}{14} | |
112 | \node [alice, thoughts] at (0, 2) | |
113 | {\footnotesize Private $a$; public $A = a P$}; | |
114 | ||
115 | \node [bob, thoughts] at (0, 3) | |
116 | {{ $u \getsr \Nupto{q}$; \\ | |
117 | $U \gets u P$; | |
118 | $Y_B \gets u A$; }}; | |
119 | \path [message, ->] (0, 5.5) -- node [above] | |
120 | {$U, u \xor H(\cookie{check}, U, Y_B$)} | |
121 | +(1, 0); | |
122 | ||
123 | \node [alice, thoughts] at (0, 8) | |
124 | {{ $Y'_B \gets a U$; }}; | |
125 | \path [message, <-] (0, 9) -- node [above] | |
126 | {$Y'_B$} | |
127 | +(1, 0); | |
128 | ||
129 | \only<2->{ | |
130 | \node [bob, other, thoughts] at (0, 2) | |
131 | {\footnotesize Private $b$; public $B = b P$}; | |
132 | ||
133 | \node [alice, other, thoughts] at (0, 3) | |
134 | {{ $v \getsr \Nupto{q}$; \\ | |
135 | $V \gets v P$; | |
136 | $Y_A \gets v B$; }}; | |
137 | \path [message, other, <-] (0, 7) -- node [above] | |
138 | {$V, v \xor H(\cookie{check}, V, Y_A$)} | |
139 | +(1, 0); | |
140 | ||
141 | \node [bob, other, thoughts] at (0, 8) | |
142 | {{ $Y'_A \gets b V$; }}; | |
143 | \path [message, other, ->] (0, 10.5) -- node [above] | |
144 | {$Y'_A$} | |
145 | +(1, 0); | |
146 | } | |
147 | \action<3-| alert@3->{ | |
148 | \node [bob, thoughts] at (0, 11) {$Z \gets u V = u v P$;}; | |
149 | \node [alice, thoughts] at (0, 11) {$Z \gets v U = u v P$;}; | |
150 | } | |
a6e375a6 | 151 | \end{protocol} |
32609df3 | 152 | \par\vskip-\bigskipamount |
a6e375a6 | 153 | \begin{itemize} |
32609df3 MW |
154 | \item<3-> We can do ephemeral Diffie-Hellman with the challenges! |
155 | \item<4-> Unfortunately, it's not secure. | |
a6e375a6 | 156 | \end{itemize} |
32609df3 | 157 | \end{frame} |
a6e375a6 | 158 | |
32609df3 MW |
159 | \begin{frame}{Key exchange: properties} |
160 | \begin{itemize}[<+->] | |
161 | \item Simple -- symmetrical; based on mutual identification. | |
162 | \item Practical -- three, four or five flows; four multiplications by each | |
163 | party. | |
164 | \item Secure -- provides SK-security in model of [CK01]. | |
165 | \item Deniable -- simulator can produce convincing transcripts. | |
166 | \item Proofs in random oracle model -- again without `programming'. | |
167 | \end{itemize} | |
168 | \end{frame} | |
a6e375a6 | 169 | |
32609df3 MW |
170 | \begin{frame}{Key exchange: setting} |
171 | \begin{itemize}[<+->] | |
172 | \item Cyclic group $(G, +)$. | |
173 | \item $|G| = q$ is prime. | |
174 | \item $P$ generates $G$. | |
a6e375a6 | 175 | \item Alice's private key is $a \inr \Nupto{q}$; her public key is $A = a |
32609df3 | 176 | P$. |
a6e375a6 | 177 | \item Bob's private key is $b \inr \Nupto{q}$; his public key is $B = b |
32609df3 MW |
178 | P$. |
179 | \item Symmetric IND-CCA encryption scheme $\E = (\kappa, E, D)$. | |
180 | \item Assume computational Diffie-Hellman problem hard in $G$. | |
a6e375a6 | 181 | \end{itemize} |
32609df3 MW |
182 | \end{frame} |
183 | ||
184 | \begin{frame}{Key exchange: protocols} | |
185 | %% overlays | |
186 | %% 1 - original broken protocol | |
187 | %% 2 - encrypt responses | |
188 | %% 3 - session-ids | |
189 | %% 4 - pre-challenges | |
190 | \begin{protocol}{3.9}{17} | |
191 | \node [alice, thoughts] at (0, 1.5) | |
192 | {\footnotesize Private $a$; public $A = a P$}; | |
193 | ||
194 | \node [bob, thoughts] at (0, 3) | |
195 | {{ $u \getsr \Nupto{q}$; \\ | |
196 | $U \gets u P$; | |
197 | $Y_B \gets u A$; }}; | |
198 | \only<4-> | |
199 | {\path [message, ->] (0, 6) -- node [above] {$\alert<4>{U}$} +(1, 0);} | |
200 | \path [message, ->] (0, 9) -- node [above] | |
201 | {$U, u \xor H(\cookie{check}, | |
202 | \only<3->{\alert<3>{B}, \alert<3>{s},} | |
203 | \only<4->{\alert<4>{V},} | |
204 | U, Y_B$)} | |
205 | +(1, 0); | |
206 | ||
207 | \node [alice, thoughts] at (0, 11) | |
208 | {{\strut | |
209 | \only<1>{$Z \gets v U$; \\}% | |
210 | \action<only@2-| alert@2> | |
211 | {$(K, \hat{K}) \gets H(\cookie{key}, v U)$; \\}% | |
212 | $Y'_B \gets a U$; }}; | |
213 | \path [message, <-] (0, 13.5) -- node [above] | |
214 | {$\action<only@2-| alert@2>{E_{\hat{K}}(} | |
215 | Y'_B | |
216 | \action<only@2-| alert@2>{)}$} | |
217 | +(1, 0); | |
218 | ||
219 | \node [bob, other, thoughts] at (0, 1.5) | |
220 | {\footnotesize Private $b$; public $B = b P$}; | |
221 | ||
222 | \node [alice, other, thoughts] at (0, 3) | |
223 | {{ $v \getsr \Nupto{q}$; \\ | |
224 | $V \gets v P$; | |
225 | $Y_A \gets v B$; }}; | |
226 | \only<4-> | |
227 | {\path [message, other, <-] (0, 7.5) -- | |
228 | node [above] {$\alert<4>{V}$} +(1, 0);} | |
229 | \path [message, other, <-] (0, 10.5) -- node [above] | |
230 | {$V, v \xor H(\cookie{check}, | |
231 | \only<3->{\alert<3>{A}, \alert<3>{s},} | |
232 | \only<4->{\alert<4>{U},} | |
233 | V, Y_A$)} | |
234 | +(1, 0); | |
235 | ||
236 | \node [bob, other, thoughts] at (0, 11) | |
237 | {{\strut | |
238 | \only<1>{$Z \gets u V$; \\}% | |
239 | \action<only@2-| alert@2> | |
240 | {$(K, \hat{K}) \gets H(\cookie{key}, u V)$; \\}% | |
241 | $Y'_A \gets b V$; }}; | |
242 | \path [message, other, ->] (0, 15) -- node [above] | |
243 | {${\action<only@2-| alert@2>{E_{\hat{K}}(}} | |
244 | Y'_A | |
245 | {\action<only@2-| alert@2>{)}}$} | |
246 | +(1, 0); | |
247 | \node [bob, thoughts] at (0, 15.5) {Use key $K$;}; | |
248 | \node [alice, thoughts] at (0, 15.5) {Use key $K$;}; | |
249 | \end{protocol} | |
250 | \end{frame} | |
a6e375a6 | 251 | |
32609df3 MW |
252 | \endinput |
253 | ||
254 | ||
255 | \begin{frame} | |
dff0fad2 | 256 | \head{Key exchange \seq: broken first attempt} |
a6e375a6 MW |
257 | \topic{protocol design} |
258 | ||
259 | \begin{protocol} | |
260 | Alice & Bob \\ | |
261 | (Private key $a$, public key $A = a P$) & | |
262 | \other (Private key $b$, public key $B = b P$) | |
263 | \\[\medskipamount] | |
32609df3 MW |
264 | \other $u_A \getsr \Nupto{q}$; & $u \getsr \Nupto{q}$; \\ |
265 | \other $U_A \gets u_A P$ & $U \gets u P$; \\ | |
a6e375a6 MW |
266 | \\ |
267 | \\ | |
32609df3 MW |
268 | \send{<-}{(U, u \xor H(\cookie{check}, U, Y_B))} |
269 | \send{->}{\other (U_A, u_A \xor H(\cookie{check}, U_A, Y_A))} | |
270 | $Y_B \gets a U$; & \other $Y_A \gets b U$; \\ | |
271 | $Z \gets u_A U$; & $Z \gets u U_A$; \\ | |
272 | \send{->}{(U_A, Y_B)} | |
273 | \send{<-}{\other (U, Y_A)} | |
a6e375a6 MW |
274 | Key is $Z$ & Key is $Z$ |
275 | \end{protocol} | |
32609df3 | 276 | \end{frame} |
a6e375a6 | 277 | |
32609df3 | 278 | \begin{frame} |
dff0fad2 | 279 | \head{Key exchange \seq: solution -- encrypt responses} |
a6e375a6 MW |
280 | |
281 | \begin{protocol} | |
282 | Alice & Bob \\ | |
283 | (Private key $a$, public key $A = a P$) & | |
284 | \other (Private key $b$, public key $B = b P$) | |
285 | \\[\medskipamount] | |
32609df3 MW |
286 | \other $u_A \getsr \Nupto{q}$; & $u \getsr \Nupto{q}$; \\ |
287 | \other $U_A \gets u_A P$ & $U \gets u P$; \\ | |
a6e375a6 MW |
288 | \\ |
289 | \\ | |
32609df3 MW |
290 | \send{<-}{(U, u \xor H(\cookie{check}, U, Y_B))} |
291 | \send{->}{\other (U_A, u_A \xor H(\cookie{check}, U_A, Y_A))} | |
292 | $Y_B \gets a U$; & \other $Y_A \gets b U$; \\ | |
293 | \diff $(K_0, K_1) \gets H(\cookie{key}, u_A U)$; & | |
294 | \diff $(K_0, K_1) \gets H(\cookie{key}, u U_A)$; \\ | |
295 | \send{->}{(U_A, \hbox{\diff $E_{K_0}(Y_B)$})} | |
296 | \send{<-}{\other (U, \hbox{\diff $E_{K_0}(Y_A)$})} | |
a6e375a6 MW |
297 | Key is $K_1$ & Key is $K_1$ |
298 | \end{protocol} | |
32609df3 | 299 | \end{frame} |
a6e375a6 | 300 | |
32609df3 | 301 | \begin{frame} |
dff0fad2 | 302 | \head{Key exchange \seq: multiple sessions} |
a6e375a6 MW |
303 | |
304 | \begin{protocol} | |
305 | Alice & Bob \\ | |
306 | (Private key $a$, public key $A = a P$) & | |
307 | \other (Private key $b$, public key $B = b P$) | |
308 | \\[\medskipamount] | |
32609df3 MW |
309 | \other $u_A \getsr \Nupto{q}$; & $u \getsr \Nupto{q}$; \\ |
310 | \other $U_A \gets u_A P$ & $U \gets u P$; \\ | |
a6e375a6 MW |
311 | \\ |
312 | \\ | |
32609df3 MW |
313 | \send{<-}{(U, u \xor H(\cookie{check}, |
314 | \hbox{\diff $B$}, \hbox{\diff $s$}, U, Y_B))} | |
315 | \send{->}{\other (U_A, u_A \xor H(\cookie{check}, | |
316 | \hbox{\diff $A$}, \hbox{\diff $s$}, U_A, Y_A))} | |
317 | $Y_B \gets a U$; & \other $Y_A \gets b U$; \\ | |
318 | $(K_0, K_1) \gets H(\cookie{key}, u_A U)$; & | |
319 | $(K_0, K_1) \gets H(\cookie{key}, u U_A)$; \\ | |
320 | \send{->}{(U_A, E_{K_0}(Y_B))} | |
321 | \send{<-}{\other (U, E_{K_0}(Y_A))} | |
a6e375a6 MW |
322 | Key is $K_1$ & Key is $K_1$ |
323 | \end{protocol} | |
324 | (Session id is $s$) | |
32609df3 | 325 | \end{frame} |
a6e375a6 | 326 | |
32609df3 | 327 | \begin{frame} |
dff0fad2 MW |
328 | \head{Key exchange \seq: proof sketch} |
329 | ||
330 | \begin{itemize} | |
331 | \item $\G0$ is SK-security game. | |
332 | \item In $\G1$, stop game unless all parties have distinct public keys | |
333 | (collision bound). | |
334 | \item In $\G2$, use extractor to answer challenges other than from matching | |
335 | session. | |
32609df3 | 336 | \item In $\G3$, stop game if adversary queries $H(\cookie{key}, u_A u P)$ |
dff0fad2 MW |
337 | (CDH in $G$). |
338 | \item In $\G4$, stop game if session accepts response except from matching | |
339 | session. | |
340 | \begin{itemize} | |
341 | \item In $\G5$, focus on a single session (factor of $q_S$). | |
32609df3 | 342 | \item In $\G6$, encrypt $1^{|Y|}$ instead of $Y = x U$ (IND-CCA of $\E$). |
dff0fad2 MW |
343 | \item In $\G7$, focus on a single party (factor of $n$). |
344 | \item Now if party accepts, reduce from impersonating in $\Wident$. | |
345 | \end{itemize} | |
346 | \end{itemize} | |
32609df3 | 347 | \end{frame} |
dff0fad2 | 348 | |
32609df3 | 349 | \begin{frame} |
dff0fad2 MW |
350 | \head{Key exchange \seq: security result} |
351 | \begin{spliteqn*} | |
352 | \InSec{sk}(\Wkx^{G, \E}; t, n, q_S, q_M, q_I, q_K) \le | |
353 | 2 q_S \bigl( \InSec{ind-cca}(\E; t', q_M, q_M) + {} \\ | |
354 | \InSec{mcdh}(G; t', q_K) + | |
355 | n \,\InSec{mcdh}(G; t', q_M + q_I) \bigr) + {} \\ | |
356 | \frac{n (n - 1)}{|G|} + | |
357 | \frac{2 q_M}{2^{\ell_I}}. | |
358 | \end{spliteqn*} | |
359 | \begin{multicols}{2} | |
360 | \begin{itemize} | |
361 | \item $t$ is running time of adversary | |
362 | \item $n$ is number of parties | |
363 | \item $q_S$ is number of new sessions | |
364 | \item $q_M$ is number of messages sent | |
365 | \item $q_I$ is number of $H(\cookie{check}, \cdot)$ queries | |
366 | \item $q_K$ is number of $H(\cookie{key}, \cdot)$ queries | |
367 | \item $t' = t + O(q_S) + O(q_M q_I) + O(q_K)$ | |
368 | \end{itemize} | |
369 | \end{multicols} | |
32609df3 | 370 | \end{frame} |
dff0fad2 | 371 | |
32609df3 | 372 | \begin{frame} |
dff0fad2 | 373 | \head{Key exchange \seq: fully deniable variant} |
a6e375a6 MW |
374 | |
375 | \begin{protocol} | |
376 | Alice & Bob \\ | |
377 | (Private key $a$, public key $A = a P$) & | |
378 | \other (Private key $b$, public key $B = b P$) | |
379 | \\[\medskipamount] | |
32609df3 MW |
380 | \other $u_A \getsr \Nupto{q}$; & $u \getsr \Nupto{q}$; \\ |
381 | \other $U_A \gets u_A P$ & $U \gets u P$; \\ | |
382 | \send{->}{\diff U_A} | |
383 | \send{<-}{\diff U} | |
384 | \send{<-}{(U, u \xor H(\cookie{check}, B, s, \hbox{\diff $U_A$}, U, Y_B))} | |
385 | \send{->}{\other (U_A, u_A \xor H(\cookie{check}, A, s, \hbox{\diff $U$}, U_A, Y_A))} | |
386 | $Y_B \gets a U$; & \other $Y_A \gets b U$; \\ | |
387 | $(K_0, K_1) \gets H(\cookie{key}, u_A U)$; & | |
388 | $(K_0, K_1) \gets H(\cookie{key}, u U_A)$; \\ | |
389 | \send{->}{(U_A, E_{K_0}(Y_B))} | |
390 | \send{<-}{\other (U, E_{K_0}(Y_A))} | |
a6e375a6 MW |
391 | Key is $K_1$ & Key is $K_1$ |
392 | \end{protocol} | |
32609df3 | 393 | \end{frame} |
a6e375a6 | 394 | |
32609df3 | 395 | %%% Local Variables: |
a6e375a6 MW |
396 | %%% mode: latex |
397 | %%% TeX-master: "wrslides" | |
32609df3 MW |
398 | %%% TeX-PDF-mode: t |
399 | %%% End: |