| 1 | \xcalways\section{The Wrestlers Protocol}\x |
| 2 | |
| 3 | \xcalways\subsection{Identification using Diffie-Hellman}\x |
| 4 | |
| 5 | \begin{slide} |
| 6 | \resetseq |
| 7 | \head{Identification using Diffie-Hellman \seq: Properties} |
| 8 | \topic{properties} |
| 9 | |
| 10 | \begin{itemize} |
| 11 | \item Simple -- easy to remember, analyse and implement |
| 12 | \item Practical -- two scalar multiplications for each party |
| 13 | \item Secure -- under Computational Diffie-Hellman assumption |
| 14 | \item Zero-knowledge -- statistical ZK |
| 15 | \item Proofs in random oracle model -- but without `programming' |
| 16 | \end{itemize} |
| 17 | \end{slide} |
| 18 | |
| 19 | \begin{slide} |
| 20 | \head{Identification using Diffie-Hellman \seq: Basic setting} |
| 21 | \topic{setting} |
| 22 | |
| 23 | \begin{itemize} |
| 24 | \item Cyclic group $(G, +)$ |
| 25 | \item $|G| = q$ is prime |
| 26 | \item $P$ generates $G$ |
| 27 | \item Alice's private key is $a \inr \Nupto{q}$ |
| 28 | \item Alice's public key is $A = a P$ |
| 29 | \item Assume computational Diffie-Hellman problem hard in $G$ |
| 30 | \end{itemize} |
| 31 | \end{slide} |
| 32 | |
| 33 | \begin{slide} |
| 34 | \head{Identification using Diffie-Hellman \seq: Na\"\i ve attempt} |
| 35 | \topic{protocol design} |
| 36 | |
| 37 | \begin{protocol} |
| 38 | Alice & Bob \\ |
| 39 | (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$) |
| 40 | \\[\medskipamount] |
| 41 | & $r \getsr \Nupto{q}$; \\ |
| 42 | & $R \gets r P$; \\ |
| 43 | \\ |
| 44 | \\ |
| 45 | \\ |
| 46 | \send{<-}{R} |
| 47 | $Y \gets a R$; \\ |
| 48 | \\ |
| 49 | \\ |
| 50 | \\ |
| 51 | \send{->}{Y} |
| 52 | & \textbf{Check} $Y = r A$ |
| 53 | \end{protocol} |
| 54 | \end{slide} |
| 55 | |
| 56 | \begin{slide} |
| 57 | \head{Identification using Diffie-Hellman \seq: Fix it with a hash} |
| 58 | \protocolskip0pt |
| 59 | |
| 60 | \begin{protocol} |
| 61 | Alice & Bob \\ |
| 62 | (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$) |
| 63 | \\[\medskipamount] |
| 64 | & $r \getsr \Nupto{q}$; \\ |
| 65 | & $R \gets r P$; \\ |
| 66 | & $Y \gets r A$; \\ |
| 67 | & \diff $h \gets H(\cookie{check}, R, Y)$; \\ |
| 68 | & \\ |
| 69 | \send{<-}{(R, \hbox{\diff $h$})} |
| 70 | $Y \gets a R$; \\ |
| 71 | \\ |
| 72 | \\ |
| 73 | \diff \textbf{Check} $h = H(\cookie{check}, R, Y)$ \\ |
| 74 | \send{->}{Y} |
| 75 | & \textbf{Check} $Y$ |
| 76 | \end{protocol} |
| 77 | \dots but there are still small-subgroup attacks |
| 78 | \end{slide} |
| 79 | |
| 80 | \begin{slide} |
| 81 | \head{Identification using Diffie-Hellman \seq: Stinson-Wu [SW06]} |
| 82 | \protocolskip0pt |
| 83 | |
| 84 | \begin{protocol} |
| 85 | Alice & Bob \\ |
| 86 | (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$) |
| 87 | \\[\medskipamount] |
| 88 | & $r \getsr \Nupto{q}$; \\ |
| 89 | & $R \gets r P$; \\ |
| 90 | & $Y \gets r A$; \\ |
| 91 | & $h \gets H(\cookie{check}, R, Y)$; \\ |
| 92 | & \\ |
| 93 | \send{<-}{(R, h)} |
| 94 | $Y \gets a R$; \\ |
| 95 | \\ |
| 96 | \diff \textbf{Check} $q R = 0$; \\ |
| 97 | \textbf{Check} $h = H(\cookie{check}, R, Y)$ \\ |
| 98 | \send{->}{Y} |
| 99 | & \textbf{Check} $Y$ |
| 100 | \end{protocol} |
| 101 | \dots and apply the Knowledge of Exponent assumption |
| 102 | \end{slide} |
| 103 | |
| 104 | \begin{slide} |
| 105 | \head{Identification using Diffie-Hellman \seq: The Wrestlers Protocol |
| 106 | $\Wident$} |
| 107 | |
| 108 | \begin{protocol} |
| 109 | Alice & Bob \\ |
| 110 | (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$) |
| 111 | \\[\medskipamount] |
| 112 | & $r \getsr \Nupto{q}$; \\ |
| 113 | & $R \gets r P$; \\ |
| 114 | & $Y \gets r A$; \\ |
| 115 | & $h \gets H(\cookie{check}, R, Y)$; \\ |
| 116 | & \diff $c \gets h \xor r$; \\ |
| 117 | \send{<-}{(R, \hbox{\diff $c$})} |
| 118 | $Y \gets a R$; \\ |
| 119 | $h \gets H(\cookie{check}, R, Y)$; \\ |
| 120 | \diff $r \gets c \xor h$; \\ |
| 121 | \diff \textbf{Check} $R = r P$ \\ |
| 122 | \send{->}{Y} |
| 123 | & \textbf{Check} $Y$ |
| 124 | \end{protocol} |
| 125 | \end{slide} |
| 126 | |
| 127 | \begin{slide} |
| 128 | \head{Identification using Diffie-Hellman \seq: Identification-based |
| 129 | $\Wident$} |
| 130 | |
| 131 | \begin{protocol} |
| 132 | Alice & Bob \\ |
| 133 | (Private key $K_A = t I_A$) & |
| 134 | (Public key $I_A = H(\cookie{id}, \text{Alice})$) |
| 135 | \\[\medskipamount] |
| 136 | & $r \getsr \Nupto{q}$; \\ |
| 137 | & $R \gets r P$; \\ |
| 138 | & \diff $Y \gets \hat{e}(T, I_A)^r$; \\ |
| 139 | & $h \gets H(\cookie{check}, R, Y)$; \\ |
| 140 | & $c \gets h \xor r$; \\ |
| 141 | \send{<-}{(R, c)} |
| 142 | \diff $Y \gets \hat{e}(R, K_A)$; \\ |
| 143 | $h \gets H(\cookie{check}, R, Y)$; \\ |
| 144 | $r \gets c \xor h$; \\ |
| 145 | \textbf{Check} $R = r P$ \\ |
| 146 | \send{->}{Y} |
| 147 | & \textbf{Check} $Y$ |
| 148 | \end{protocol} |
| 149 | (Trusted authority's private key $t \inr \Nupto{q}$; public key $T = t P$) |
| 150 | \end{slide} |
| 151 | |
| 152 | \xcalways\subsection{Key exchange}\x |
| 153 | |
| 154 | \begin{slide} |
| 155 | \resetseq |
| 156 | \head{Mutual identification \seq: Bob identifies Alice} |
| 157 | \topic{mutual identification} |
| 158 | |
| 159 | \begin{protocol} |
| 160 | Alice & Bob \\ |
| 161 | (Private key $a$, public key $A = a P$) |
| 162 | \\[\medskipamount] |
| 163 | & $r_B \getsr \Nupto{q}$; \\ |
| 164 | & $R_B \gets r_B P$; \\ |
| 165 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} |
| 166 | \\ |
| 167 | $Y_B \gets a R_B$; \\ |
| 168 | \\ |
| 169 | \send{->}{Y_B} |
| 170 | \end{protocol} |
| 171 | \end{slide} |
| 172 | |
| 173 | \begin{slide} |
| 174 | \head{Mutual identification \seq: Alice identifies Bob too} |
| 175 | |
| 176 | \begin{protocol} |
| 177 | Alice & Bob \\ |
| 178 | (Private key $a$, public key $A = a P$) & |
| 179 | \other (Private key $b$, public key $B = b P$) |
| 180 | \\[\medskipamount] |
| 181 | \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ |
| 182 | \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ |
| 183 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} |
| 184 | \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))} |
| 185 | $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ |
| 186 | \\ |
| 187 | \send{->}{Y_B} |
| 188 | \send{<-}{\other Y_A} |
| 189 | \end{protocol} |
| 190 | \end{slide} |
| 191 | |
| 192 | \begin{slide} |
| 193 | \head{Mutual identification \seq: Key exchange?} |
| 194 | |
| 195 | \begin{protocol} |
| 196 | Alice & Bob \\ |
| 197 | (Private key $a$, public key $A = a P$) & |
| 198 | \other (Private key $b$, public key $B = b P$) |
| 199 | \\[\medskipamount] |
| 200 | \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ |
| 201 | \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ |
| 202 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} |
| 203 | \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))} |
| 204 | $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ |
| 205 | \\ |
| 206 | \send{->}{Y_B} |
| 207 | \send{<-}{\other Y_A} |
| 208 | \diff $Z \gets r_A R_B$; & \diff $Z \gets r_B R_A$; |
| 209 | \end{protocol} |
| 210 | \bigskip |
| 211 | Unfortunately it's not secure. |
| 212 | \end{slide} |
| 213 | |
| 214 | \begin{slide} |
| 215 | \resetseq |
| 216 | \head{Key exchange \seq: Properties} |
| 217 | \topic{properties} |
| 218 | |
| 219 | \begin{itemize} |
| 220 | \item Simple -- symmetrical; based on mutual identification |
| 221 | \item Practical -- three, four or five flows; four multiplications by each |
| 222 | party |
| 223 | \item Secure -- provides SK-security in model of [CK01] |
| 224 | \item Deniable -- simulator can produce convincing transcripts |
| 225 | \item Proofs in random oracle model -- again without `programming' |
| 226 | \end{itemize} |
| 227 | \end{slide} |
| 228 | |
| 229 | \begin{slide} |
| 230 | \head{Key exchange \seq: Setting} |
| 231 | \topic{setting} |
| 232 | |
| 233 | \begin{itemize} |
| 234 | \item Cyclic group $(G, +)$ |
| 235 | \item $|G| = q$ is prime |
| 236 | \item $P$ generates $G$ |
| 237 | \item Alice's private key is $a \inr \Nupto{q}$; her public key is $A = a |
| 238 | P$ |
| 239 | \item Bob's private key is $b \inr \Nupto{q}$; his public key is $B = b |
| 240 | P$ |
| 241 | \item Symmetric IND-CCA encryption scheme $\E = (\kappa, E, D)$ |
| 242 | \item Assume computational Diffie-Hellman problem hard in $G$ |
| 243 | \end{itemize} |
| 244 | \end{slide} |
| 245 | |
| 246 | \begin{slide} |
| 247 | \head{Key exchange \seq: Broken first attempt} |
| 248 | \topic{protocol design} |
| 249 | |
| 250 | \begin{protocol} |
| 251 | Alice & Bob \\ |
| 252 | (Private key $a$, public key $A = a P$) & |
| 253 | \other (Private key $b$, public key $B = b P$) |
| 254 | \\[\medskipamount] |
| 255 | \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ |
| 256 | \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ |
| 257 | \\ |
| 258 | \\ |
| 259 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} |
| 260 | \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))} |
| 261 | $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ |
| 262 | $Z \gets r_A R_B$; & $Z \gets r_B R_A$; \\ |
| 263 | \send{->}{(R_A, Y_B)} |
| 264 | \send{<-}{\other (R_B, Y_A)} |
| 265 | Key is $Z$ & Key is $Z$ |
| 266 | \end{protocol} |
| 267 | \end{slide} |
| 268 | |
| 269 | \begin{slide} |
| 270 | \head{Key exchange \seq: Solution -- encrypt responses} |
| 271 | |
| 272 | \begin{protocol} |
| 273 | Alice & Bob \\ |
| 274 | (Private key $a$, public key $A = a P$) & |
| 275 | \other (Private key $b$, public key $B = b P$) |
| 276 | \\[\medskipamount] |
| 277 | \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ |
| 278 | \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ |
| 279 | \\ |
| 280 | \\ |
| 281 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} |
| 282 | \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))} |
| 283 | $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ |
| 284 | \diff $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; & |
| 285 | \diff $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\ |
| 286 | \send{->}{(R_A, \hbox{\diff $E_{K_0}(Y_B)$})} |
| 287 | \send{<-}{\other (R_B, \hbox{\diff $E_{K_0}(Y_A)$})} |
| 288 | Key is $K_1$ & Key is $K_1$ |
| 289 | \end{protocol} |
| 290 | \end{slide} |
| 291 | |
| 292 | \begin{slide} |
| 293 | \head{Key exchange \seq: Multiple sessions} |
| 294 | |
| 295 | \begin{protocol} |
| 296 | Alice & Bob \\ |
| 297 | (Private key $a$, public key $A = a P$) & |
| 298 | \other (Private key $b$, public key $B = b P$) |
| 299 | \\[\medskipamount] |
| 300 | \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ |
| 301 | \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ |
| 302 | \\ |
| 303 | \\ |
| 304 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, |
| 305 | \hbox{\diff $B$}, \hbox{\diff $s$}, R_B, Y_B))} |
| 306 | \send{->}{\other (R_A, r_A \xor H(\cookie{check}, |
| 307 | \hbox{\diff $A$}, \hbox{\diff $s$}, R_A, Y_A))} |
| 308 | $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ |
| 309 | $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; & |
| 310 | $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\ |
| 311 | \send{->}{(R_A, E_{K_0}(Y_B))} |
| 312 | \send{<-}{\other (R_B, E_{K_0}(Y_A))} |
| 313 | Key is $K_1$ & Key is $K_1$ |
| 314 | \end{protocol} |
| 315 | (Session id is $s$) |
| 316 | \end{slide} |
| 317 | |
| 318 | \begin{slide} |
| 319 | \head{Key exchange \seq: Fully deniable variant} |
| 320 | |
| 321 | \begin{protocol} |
| 322 | Alice & Bob \\ |
| 323 | (Private key $a$, public key $A = a P$) & |
| 324 | \other (Private key $b$, public key $B = b P$) |
| 325 | \\[\medskipamount] |
| 326 | \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ |
| 327 | \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ |
| 328 | \send{->}{\diff R_A} |
| 329 | \send{<-}{\diff R_B} |
| 330 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, B, s, \hbox{\diff $R_A$}, R_B, Y_B))} |
| 331 | \send{->}{\other (R_A, r_A \xor H(\cookie{check}, A, s, \hbox{\diff $R_B$}, R_A, Y_A))} |
| 332 | $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ |
| 333 | $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; & |
| 334 | $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\ |
| 335 | \send{->}{(R_A, E_{K_0}(Y_B))} |
| 336 | \send{<-}{\other (R_B, E_{K_0}(Y_A))} |
| 337 | Key is $K_1$ & Key is $K_1$ |
| 338 | \end{protocol} |
| 339 | \end{slide} |
| 340 | |
| 341 | \endinput |
| 342 | |
| 343 | %%% Local Variables: |
| 344 | %%% mode: latex |
| 345 | %%% TeX-master: "wrslides" |
| 346 | %%% End: |