| 1 | \section{The Wrestlers Protocol} |
| 2 | \frame{\tableofcontents[currentsection]} |
| 3 | |
| 4 | \subsection{Identification using Diffie-Hellman} |
| 5 | |
| 6 | \begin{frame}{Identification using Diffie-Hellman: properties} |
| 7 | \begin{itemize}[<+->] |
| 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} |
| 14 | \end{frame} |
| 15 | |
| 16 | \begin{frame}{Identification using Diffie-Hellman: basic setting} |
| 17 | \begin{itemize}[<+->] |
| 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} |
| 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 | } |
| 95 | \end{protocol} |
| 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 | } |
| 151 | \end{protocol} |
| 152 | \par\vskip-\bigskipamount |
| 153 | \begin{itemize} |
| 154 | \item<3-> We can do ephemeral Diffie-Hellman with the challenges! |
| 155 | \item<4-> Unfortunately, it's not secure. |
| 156 | \end{itemize} |
| 157 | \end{frame} |
| 158 | |
| 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} |
| 169 | |
| 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$. |
| 175 | \item Alice's private key is $a \inr \Nupto{q}$; her public key is $A = a |
| 176 | P$. |
| 177 | \item Bob's private key is $b \inr \Nupto{q}$; his public key is $B = b |
| 178 | P$. |
| 179 | \item Symmetric IND-CCA encryption scheme $\E = (\kappa, E, D)$. |
| 180 | \item Assume computational Diffie-Hellman problem hard in $G$. |
| 181 | \end{itemize} |
| 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} |
| 251 | |
| 252 | \endinput |
| 253 | |
| 254 | |
| 255 | \begin{frame} |
| 256 | \head{Key exchange \seq: broken first attempt} |
| 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] |
| 264 | \other $u_A \getsr \Nupto{q}$; & $u \getsr \Nupto{q}$; \\ |
| 265 | \other $U_A \gets u_A P$ & $U \gets u P$; \\ |
| 266 | \\ |
| 267 | \\ |
| 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)} |
| 274 | Key is $Z$ & Key is $Z$ |
| 275 | \end{protocol} |
| 276 | \end{frame} |
| 277 | |
| 278 | \begin{frame} |
| 279 | \head{Key exchange \seq: solution -- encrypt responses} |
| 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] |
| 286 | \other $u_A \getsr \Nupto{q}$; & $u \getsr \Nupto{q}$; \\ |
| 287 | \other $U_A \gets u_A P$ & $U \gets u P$; \\ |
| 288 | \\ |
| 289 | \\ |
| 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)$})} |
| 297 | Key is $K_1$ & Key is $K_1$ |
| 298 | \end{protocol} |
| 299 | \end{frame} |
| 300 | |
| 301 | \begin{frame} |
| 302 | \head{Key exchange \seq: multiple sessions} |
| 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] |
| 309 | \other $u_A \getsr \Nupto{q}$; & $u \getsr \Nupto{q}$; \\ |
| 310 | \other $U_A \gets u_A P$ & $U \gets u P$; \\ |
| 311 | \\ |
| 312 | \\ |
| 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))} |
| 322 | Key is $K_1$ & Key is $K_1$ |
| 323 | \end{protocol} |
| 324 | (Session id is $s$) |
| 325 | \end{frame} |
| 326 | |
| 327 | \begin{frame} |
| 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. |
| 336 | \item In $\G3$, stop game if adversary queries $H(\cookie{key}, u_A u P)$ |
| 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$). |
| 342 | \item In $\G6$, encrypt $1^{|Y|}$ instead of $Y = x U$ (IND-CCA of $\E$). |
| 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} |
| 347 | \end{frame} |
| 348 | |
| 349 | \begin{frame} |
| 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} |
| 370 | \end{frame} |
| 371 | |
| 372 | \begin{frame} |
| 373 | \head{Key exchange \seq: fully deniable variant} |
| 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] |
| 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))} |
| 391 | Key is $K_1$ & Key is $K_1$ |
| 392 | \end{protocol} |
| 393 | \end{frame} |
| 394 | |
| 395 | %%% Local Variables: |
| 396 | %%% mode: latex |
| 397 | %%% TeX-master: "wrslides" |
| 398 | %%% TeX-PDF-mode: t |
| 399 | %%% End: |