1 \section{The Wrestlers Protocol
}
2 \frame{\tableofcontents[currentsection
]}
4 \subsection{Identification using Diffie-Hellman
}
6 \begin{frame
}{Identification using Diffie-Hellman: properties
}
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'
16 \begin{frame
}{Identification using Diffie-Hellman: basic setting
}
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$
27 \begin{frame
}{Identification using Diffie-Hellman: protocols
}
29 %% 1 - basic setup (alice's keys)
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
38 %% 9 - bob computes check hash and sends it
39 %% 10 - alice verifies the hash
42 %% 13 - check subgroup membership
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
}$ \\
53 \node [bob, thoughts
] at (
0,
4)
54 {{$u
\getsr \Nupto{q
}$; \\
56 \action<
5->
{$Y
\gets u A$;
} \\
57 \action<
9-| alert@
9-
11>
{$
58 h
\gets H(
\cookie{check
},
60 \action<alert@
14-
15| only@
14-
15>
{Y
})
62 \action<
17-| alert@
17->
{
68 \path [message, ->
] (
0,
10) -- node
[above
]
71 \only<
9-
16>
{$U,
\alert<
9-
11>
{h
}$
}
72 \only<
17->
{$U,
\alert<
17->
{c
}$
} }}
76 \node [alice, thoughts
] at (
0,
10)
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
})
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$; \\
90 \path [message, <-
] (
0,
14) -- node
[above
] {$Y'$
} +(
1,
0);
93 \node [bob, thoughts
] at (
0,
14)
{Check $Y = Y'$;
};
96 \par\vskip-
\bigskipamount
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$.
108 \subsection{Key exchange
}
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$
};
115 \node [bob, thoughts
] at (
0,
3)
116 {{ $u
\getsr \Nupto{q
}$; \\
119 \path [message, ->
] (
0,
5.5) -- node
[above
]
120 {$U, u
\xor H(
\cookie{check
}, U, Y_B$)
}
123 \node [alice, thoughts
] at (
0,
8)
124 {{ $Y'_B
\gets a U$;
}};
125 \path [message, <-
] (
0,
9) -- node
[above
]
130 \node [bob, other, thoughts
] at (
0,
2)
131 {\footnotesize Private $b$; public $B = b P$
};
133 \node [alice, other, thoughts
] at (
0,
3)
134 {{ $v
\getsr \Nupto{q
}$; \\
137 \path [message, other, <-
] (
0,
7) -- node
[above
]
138 {$V, v
\xor H(
\cookie{check
}, V, Y_A$)
}
141 \node [bob, other, thoughts
] at (
0,
8)
142 {{ $Y'_A
\gets b V$;
}};
143 \path [message, other, ->
] (
0,
10.5) -- node
[above
]
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$;
};
152 \par\vskip-
\bigskipamount
154 \item<
3-> We can do ephemeral Diffie-Hellman with the challenges!
155 \item<
4-> Unfortunately, it's not secure.
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
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'.
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
177 \item Bob's private key is $b
\inr \Nupto{q
}$; his public key is $B = b
179 \item Symmetric IND-CCA encryption scheme $
\E = (
\kappa, E, D)$.
180 \item Assume computational Diffie-Hellman problem hard in $G$.
184 \begin{frame
}{Key exchange: protocols
}
186 %% 1 - original broken protocol
187 %% 2 - encrypt responses
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$
};
194 \node [bob, thoughts
] at (
0,
3)
195 {{ $u
\getsr \Nupto{q
}$; \\
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
},
}
207 \node [alice, thoughts
] at (
0,
11)
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
}}(
}
216 \action<only@
2-| alert@
2>
{)
}$
}
219 \node [bob, other, thoughts
] at (
0,
1.5)
220 {\footnotesize Private $b$; public $B = b P$
};
222 \node [alice, other, thoughts
] at (
0,
3)
223 {{ $v
\getsr \Nupto{q
}$; \\
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
},
}
236 \node [bob, other, thoughts
] at (
0,
11)
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
}}(
}}
245 {\action<only@
2-| alert@
2>
{)
}}$
}
247 \node [bob, thoughts
] at (
0,
15.5)
{Use key $K$;
};
248 \node [alice, thoughts
] at (
0,
15.5)
{Use key $K$;
};
256 \head{Key exchange
\seq: broken first attempt
}
257 \topic{protocol design
}
261 (Private key $a$, public key $A = a P$) &
262 \other (Private key $b$, public key $B = b P$)
264 \other $u_A
\getsr \Nupto{q
}$; & $u
\getsr \Nupto{q
}$; \\
265 \other $U_A
\gets u_A P$ & $U
\gets u P$; \\
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$
279 \head{Key exchange
\seq: solution -- encrypt responses
}
283 (Private key $a$, public key $A = a P$) &
284 \other (Private key $b$, public key $B = b P$)
286 \other $u_A
\getsr \Nupto{q
}$; & $u
\getsr \Nupto{q
}$; \\
287 \other $U_A
\gets u_A P$ & $U
\gets u P$; \\
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$
302 \head{Key exchange
\seq: multiple sessions
}
306 (Private key $a$, public key $A = a P$) &
307 \other (Private key $b$, public key $B = b P$)
309 \other $u_A
\getsr \Nupto{q
}$; & $u
\getsr \Nupto{q
}$; \\
310 \other $U_A
\gets u_A P$ & $U
\gets u P$; \\
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$
328 \head{Key exchange
\seq: proof sketch
}
331 \item $
\G0$ is SK-security game.
332 \item In $
\G1$, stop game unless all parties have distinct public keys
334 \item In $
\G2$, use extractor to answer challenges other than from matching
336 \item In $
\G3$, stop game if adversary queries $H(
\cookie{key
}, u_A u P)$
338 \item In $
\G4$, stop game if session accepts response except from matching
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$.
350 \head{Key exchange
\seq: security result
}
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}}.
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)$
373 \head{Key exchange
\seq: fully deniable variant
}
377 (Private key $a$, public key $A = a P$) &
378 \other (Private key $b$, public key $B = b P$)
380 \other $u_A
\getsr \Nupto{q
}$; & $u
\getsr \Nupto{q
}$; \\
381 \other $U_A
\gets u_A P$ & $U
\gets u P$; \\
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$
397 %%% TeX-master: "wrslides"