Commit | Line | Data |
---|---|---|
de14f3b0 MW |
1 | =udpkey= Protocol Analysis |
2 | ||
3 | \begin{abstract} | |
4 | This note describes and analyses the cryptographic protocol used by | |
5 | \texttt{udpkey}. The analysis is fairly formal and quantitative; but | |
6 | this note probably isn't up to full academic standards. | |
7 | \end{abstract} | |
8 | ||
9 | ||
10 | * Introduction | |
11 | ||
12 | The =udpkey= program transports a secret -- a short-ish binary string -- | |
13 | from a /server/ which knows it to a /client/ which needs it for some | |
14 | reason. In the particular use case it was written for, the client is a | |
15 | server in a lights-out datacentre which is booting and needs a key to | |
16 | decrypt its disk. | |
17 | ||
18 | ** Preliminaries | |
19 | ||
20 | We work in a cyclic group $G = \langle P\rangle$, of order $p$, written | |
21 | additively. We consider $G$ as a vector space over $\gf{p}$. We say | |
22 | that an algorithm $\mathcal{A}$ can $(t, q, \epsilon)$-/break/ $G$ if | |
23 | $\mathcal{A}$ takes at most time $t$, issues at most $q$ oracle queries, | |
24 | and | |
25 | \[ \Pr[\textrm{$a^* \getsr \gf{p}$; | |
26 | $b^* \getsr \gf{p}$; | |
27 | $Z^* \gets a^* b^* P$; | |
28 | $Z \gets | |
29 | \mathcal{A}^{a^*(\cdot)\stackrel?=(\cdot)} | |
30 | (a^* P, b^* P)$} : | |
31 | Z = Z^*] \ge \epsilon \] | |
32 | ||
33 | Let $\Sigma = \{0, 1\}$; $\Sigma^*$ is the set of binary strings. If | |
34 | $x$ and $y$ are strings then $x \cat y$ is their concatenation. If $x$ | |
35 | is a string then $\ell(x)$ its length; i.e., $x \in \Sigma^{\ell(x)}$. | |
36 | We assume that sequences of strings, integers, and elements of $\gf{p}$ | |
37 | and $G$ can be encoded as unambiguously as strings, and denote this | |
38 | encoding using $[\cdots]$. | |
39 | ||
40 | We need a symmetric encryption scheme $\mathcal{E} = (\kappa, E, D)$. | |
41 | Here, $\kappa$ is the (nonnegative integer) /key length/; $E$ is | |
42 | the /encryption algorithm/, which takes as input a /key/ $K \in | |
43 | \Sigma^\kappa$ and a /message/ $m \in \Sigma^*$, and outputs a | |
44 | /ciphertext/ $c = E_K(m) \in \Sigma^*$; and $D$ is the /decryption | |
45 | algorithm/, which takes as input a key $K \in \Sigma^\kappa$ and a | |
46 | (purported) ciphertext $c \in \Sigma^*$, and outputs $m' = D_K(c) \in | |
47 | \Sigma^* \cup \{\bot\}$, where $\bot \notin \Sigma^*$ is a symbol | |
48 | indicating failure. We require that $D_K(c) = m$ whenever $E_K(m) = | |
49 | c$. We say that an algorithm $\mathcal{A}$ can $(t, q_E, q_D, | |
50 | \epsilon)$-/break/ $\mathcal{E}$ if $\mathcal{A}$ takes at most | |
51 | time $t$, issues at most $q_E$ (resp.\ $q_D$) encryption | |
52 | (resp.\ decryption) queries, and | |
53 | \[ 2 \Pr[\textrm{$K \getsr \Sigma^\kappa$; | |
54 | $b \getsr \{0, 1\}$; | |
55 | $b' \gets \mathcal{A}^ | |
56 | {E_K(w_b(\cdot, \cdot)), D_K(\cdot)}$} : | |
57 | b = b'] - 1 \ge \epsilon \] | |
58 | where $w_b(m_0, m_1) = m_b$, whenever $\mathcal{A}$ queries its | |
59 | encryption oracle on a pair of messages $m_0, m_1$ then $\ell(m_0) = | |
60 | \ell(m_1)$, and $\mathcal{A}$ never queries its decryption oracle on a | |
61 | ciphertext which was previously produced by the encryption oracle. | |
62 | ||
63 | We use the random oracle model, and assume the existence of a randomly | |
64 | chosen mapping $H\colon \Sigma^* \to \Sigma^\kappa$. | |
65 | ||
66 | ** Communication model | |
67 | ||
68 | In this section we describe the security property we want from our | |
69 | protocol. The model is fairly standard: after some initialization, an | |
70 | adversary is invoked; the rest of the game unfolds according to the | |
71 | adversary's queries. | |
72 | ||
73 | We consider a number of /clients/ $C_j$ and /servers/ $S_i$, for $0 \le | |
74 | i, j < n$. There is no especial relationship between like-numbered | |
75 | clients and servers. The clients and servers don't communicate | |
76 | directly: rather, communication occurs between client and server | |
77 | /sessions/, which are established by the adversary. | |
78 | ||
79 | A protocol $\Pi = (\lambda, \textsf{init}, \textsf{msg})$ consists of an | |
80 | integer /secret length/ parameter $\lambda$, and two (possibly | |
81 | randomized) algorithms: | |
82 | ||
83 | + Initialization (\textsf{init}) :: Given $n$, return: two vectors of | |
84 | /private inputs/ $\mathbf{I}^C$ and $\mathbf{I}^S$ for the clients | |
85 | and servers, respectively; and a /common input/ $J$. | |
86 | ||
87 | + Activate client (\textsf{activate-client}) :: Given a client private | |
88 | input $I$, and the common input $J$, output a new /session state/ | |
89 | $\sigma'$. | |
90 | ||
91 | + Activate server (\textsf{activate-server}) :: Given a server private | |
92 | input $I$, a secret $s \in \Sigma^\lambda$, and the common input | |
93 | $J$, output a new /session state/ $\sigma'$ and a /message/ $m \in | |
94 | \Sigma^*$. | |
95 | ||
96 | + Client (server) message (\textsf{client-msg}, \textsf{server-msg}) :: | |
97 | Given a client (server) state $\sigma$, a server (client) index $i$, | |
98 | and a message $m \in \Sigma^*$, output a /new state/ $\sigma'$, a | |
99 | /response/ message $m' \in \Sigma^* \cup \{\bot\}$, and an output | |
100 | $o$. If $m' = \bot$ then we say that the session has /finished/: if | |
101 | $o = \bot$ then it has /failed/; otherwise it has /succeeded/ with | |
102 | output $o$. If $m' \ne bot$ then we require $o = \bot$. | |
103 | ||
104 | The game proceeds as follows. | |
105 | ||
106 | 1. *Initialization*. Run $\textsf{init}(n)$ to find initial private | |
107 | inputs $\mathbf{I}^C$ and $\mathbf{I}^S$, and common input $J$. | |
108 | Choose a random bit $b \inr \{0, 1\}$, and a /secret/ $s_i \inr | |
109 | \Sigma^\lambda$ for each server $S_i$. | |
110 | ||
111 | 2. *Invoke the adversary*. The adversary is given the common input | |
112 | $J$. It may make the following queries. | |
113 | ||
114 | + Random oracle :: Given a string $s \in \Sigma^*$, return the | |
115 | output of the random oracle $H(s)$ to the adversary. | |
116 | ||
117 | + Activate client :: Given a client index $i$ and a session index | |
118 | $k \in \N$, set $(\sigma^C_{i,k}, m) \gets | |
119 | \textsf{activate-client}(I^C_i, J)$, and return $m$ to the | |
120 | adversary. | |
121 | ||
122 | + Activate server :: Given a server index $j$ and a session index | |
123 | $k \in \N$, set $\sigma^S_{j,k} \gets | |
124 | \textsf{activate-server}(I^S_j, s_j, J)$. | |
125 | ||
126 | + Deliver message to client :: Given a client index $i$, a | |
127 | session index $k$, a server index $j$, and a message $m$, set | |
128 | $(\sigma^C_{i,k}, m', o) \gets | |
129 | \textsf{client-msg}(\sigma^C_{i,k}, j, m)$, and return $m'$ to | |
130 | the adversary. | |
131 | ||
132 | + Deliver message to server :: Given a server index $j$, a | |
133 | session index $k$, a server index $i$, and a message $m$, set | |
134 | $(\sigma^S_{i,k}, m', o) \gets | |
135 | \textsf{server-msg}(\sigma^S_{j,k}, i, m)$, and return $m'$ to | |
136 | the adversary. If server $i$ is the /challenge server/ | |
137 | (described below) then client $j$ must not be /corrupt/ | |
138 | (below). | |
139 | ||
140 | + Corrupt client :: Given a client index $i$, mark client $i$ as | |
141 | /corrupt/ and return $I^C_i$ to the adversary. | |
142 | ||
143 | + Corrupt server :: Given a server index $j$, mark server $j$ as | |
144 | /corrupt/ and return $(I^S_j, s_j)$ to the adversary. Server | |
145 | $j$ must not be the /challenge server/. | |
146 | ||
147 | + Challenge :: Given a server index $j$, mark server $j$ as being | |
148 | the /challenge server/. If $b = 1$ then set $s^* \gets s_j$; | |
149 | otherwise choose $s^* \getsr \Sigma^\lambda$ at random. Return | |
150 | $s^*$ to the adversary. The adversary must not have issued a | |
151 | challenge query before; server $j$ must not be corrupt; and | |
152 | server $j$ must not have been delivered a message (apparently) | |
153 | from a client which was, at that time, corrupt. | |
154 | ||
155 | Eventually, the adversary terminates and outputs a bit $b'$. | |
156 | ||
157 | The adversary wins the game if $b = b'$. We say that the adversary $(t, | |
158 | q_M, q_H, \epsilon)$-breaks protocol $\Pi$ if the adversary completes | |
159 | within time $t$, delivers at most $q_M$ messages, issues at most $q_H$ | |
160 | random-oracle queries, and $2 \Pr[b = b'] - 1 \ge \epsilon$. | |
161 | ||
162 | There is a /correctness/ constraint on protocols. Let | |
163 | $\mathcal{B}_{i,j}$ be the following `benign' adversary. | |
164 | ||
165 | 1. Activate session $0$ of server $j$. | |
166 | ||
167 | 2. Activate session $0$ of client $i$, receiving message $m$. | |
168 | ||
169 | 3. Deliver message $m$ from client $i$ to session $0$ of server $j$, | |
170 | receiving message $m'$. | |
171 | ||
172 | 4. Deliver message $m$ from server $i$ to session $0$ of client $j$, | |
173 | receiving message $m$. | |
174 | ||
175 | 5. If $m \ne \bot$ then go back to step 3. | |
176 | ||
177 | 6. Output $b' = 1$. | |
178 | ||
179 | We require that $\mathcal{B}_{i,j}$ complete in finite time, and that | |
180 | client $i$ successfully output the secret $s_j$. | |
181 | ||
182 | Notice that our definition excludes trivial protocols because the | |
183 | initialization procedure prepares the inputs for the clients and servers | |
184 | before the secrets $s_j$ are chosen. | |
185 | ||
186 | Also, we impose no requirements on a client's output in the face of | |
187 | adversarial interference. Instead, we expect clients to be able to | |
188 | distinguish the correct secret in some manner (e.g., by checking its | |
189 | hash against a reference). Modelling this as part of the protocol is | |
190 | tricky, though, because whatever the client uses to check a secret can | |
191 | also be used by an adversary to distinguish between a proper secret and | |
192 | a fake random one in the security game. | |
193 | ||
194 | ||
195 | * The original =v0= protocol | |
196 | ||
197 | This section describes and analyses =udpkey='s original =v0= protocol. | |
198 | ||
199 | The client knows a /private key/ $x \in \gf{p}$. The server knows a | |
200 | /secret/ $s \in \Sigma^\sigma$, and the client's /public key/ $X = x P | |
201 | \in G$. The protocol works as follows. | |
202 | ||
203 | + Client :: $u \getsr \gf{p}$; $U \gets u P$. Send $[U]$ to the | |
204 | server. | |
205 | ||
206 | + Server :: $v \getsr \gf{p}$; $V \gets v P$; $r \getsr \gf{p}$; $R | |
207 | \gets r P$; $W \gets R - v U$; $K \gets H([R, r X])$; $c \gets | |
208 | E_K(s)$. Send $[V, W, c]$ to the client. | |
209 | ||
210 | + Client :: $R \gets W + u V$; $K \gets H([R, x R])$; $s \gets | |
211 | D_K(c)$. | |
212 | ||
213 | This basically splits into a DHIES encryption $(R, c)$ of $\sigma$, made | |
214 | with the client's long-term public key $X$, but the clue $R$ is | |
215 | ElGamal-encrypted using an ephemeral public key $U$. | |
216 | ||
217 | The =v0= protocol is not forward-secure: an active attacker can acquire | |
218 | information which, combined with the result of compromising a client, | |
219 | can reveal a server's secret. The attack is simple: | |
220 | ||
221 | 1. Activate session $0$ of server $0$. | |
222 | ||
223 | 2. Choose $u \inr \gf{p}$ and send $U = u P$ to session $0$ of server | |
224 | $0$, apparently from client $0$. Receive $(V, W, c)$. | |
225 | ||
226 | 3. Corrupt client $0$; recover the client's private key $x$. | |
227 | ||
228 | 4. Challenge server $0$, receiving the challenge secret $s^*$. | |
229 | ||
230 | 5. Compute $R = W + u V$, $K = H([R, x R])$, and $s = D_K(c)$. | |
231 | ||
232 | 6. If $s = s^*$ then output $b' = 1$; otherwise output $b' = 0$. | |
233 | ||
234 | This adversary, then, $(t, 1, 1, 1)$-breaks =v0=, for some appropriately | |
235 | small constant $t$. | |
236 | ||
237 | We shall show that the =v0= protocol is secure if clients are not | |
238 | corrupted; and, separately, if the adversary is `passive' -- i.e., | |
239 | restricts itself to delivering messages honestly. | |
240 | ||
241 | ** Security in the absence of corruption | |
242 | ||
243 | If clients are not corrupted, then their private keys $x$ are secret | |
244 | from the adversary. | |
245 | ||
246 | This proof considers a sequence of games, played with the same adversary | |
247 | $\mathcal{A}$. In each game $\G{i}$, we let $P_i$ be the probability | |
248 | that $\mathcal{A}$. | |
249 | ||
250 | Let $\G0$ be the full attack game, with the =v0= protocol, as described | |
251 | above, where the adversary makes no $\textsf{corrupt-client}$ requests. | |
252 | ||
253 | Game $\G1$ is like $\G0$, except that we guess a server $j^* \inr \{0, | |
254 | 1, \ldots, n - 1\}$ at random, in the hope that this is the challenge | |
255 | server. If the guess is wrong (i.e., the adversary chooses a challenge | |
256 | server $j \ne j^*$) then we immediately abandon the game, and credit the | |
257 | adversary with a win. Then | |
258 | \[ |P_1 - P_0| \le \frac{1}{n} \] | |
259 | ||
260 | Game $\G2$ is like $\G1$, except that we compute the private and public | |
261 | keys differently, and encryption works differently. | |
262 | ||
263 | + Initially we choose $a^* \inr \gf{p}$ and $b^* \inr \gf{p}$. Let | |
264 | $A^* = a^* P$ and $B^* = b^* P$, and $Z^* = a^* b^* P$. For each | |
265 | client $i$, let $x'_i = x_i - a^*$, and $X'_i = x'_i P = X_i - A^*$. | |
266 | Initialize a function $\mathcal{R}\colon G \to \gf{p} \cup \{\bot\}$ | |
267 | so that $\mathcal{R}(Q) = \bot$ for all $Q \in G$. | |
268 | ||
269 | + When a session $k$ of server $j^*$ receives a message $U$ from | |
270 | client $i$: we select $r' \inr \gf{P}$, and set $r = r' + b^*$; then | |
271 | $R = r' P + B^*$, and $Z = r' X_i + x'_i B^* + Z^*$. Set | |
272 | $\mathcal{R}(R) \gets r'$. | |
273 | ||
274 | + When a session $k$ of client $i$ receives a message $(V, W, c)$ from | |
275 | server $j^*$: recover $R = W + u V$ as usual; then, if $r' = | |
276 | \mathcal{R}(R) \ne \bot$ then set $Z = r' (A^* + X'_i) + x'_i R + | |
277 | Z^*$; otherwise, if $r' = \bot$, and the adversary has previously | |
278 | issued a random-oracle query for a pair $[R, Z']$ with $Z' = x'_i | |
279 | R + a^* R$, then set $Z = Z'$; otherwise ignore the message. | |
280 | ||
281 | It is clear that $\G2$ proceeds exactly as $\G1$ except that a client | |
282 | might ignore a message which previously it accepted. In this case, | |
283 | then, the client would have chosen $K = H([R, x_i R])$; but the random | |
284 | oracle has not previously been queried at $[R, x_i R]$, so $K$ is | |
285 | freshly random. A standard hybrid argument allows us to construct an | |
286 | adversary which $(t + O(q), 1, q, \epsilon)$-breaks $\mathcal{E}$, such | |
287 | that | |
288 | \[ |P_2 - P_1| \le q \epsilon \] | |
289 | Specifically: | |
290 | ||
291 | + In the $m$th hybrid, we focus on the $m$th message delivered to a | |
292 | client from server $j$. | |
293 | ||
294 | Game $\G3$ is like $\G2$, except that we modify encryption and | |
295 | decryption further. | |
296 | ||
297 | + At the start of the game, | |
298 | ||
299 | + When a session $k$ of server $j$ receives a message from client $i$: | |
300 | if $\mathcal{R}( | |
301 | ||
302 | initialization procedure now chooses $x^* \inr \gf{p}$, and sets $X^* = | |
303 | x^* P$. Each client $i$ gets $x_i \inr \gf{p}$ and $x^*$; and the | |
304 | public input contains $X^*$ (for the adversary's benefit), and $X_i = | |
305 | x_i P + X^*$ for each client $i$. The client computes $K$ as $H([R, | |
306 | (x_i + x^*) R])$. None of this affects the probability distribution at | |
307 | all, so $P_2 = P_1$. | |
308 | ||
309 | . | |
310 | ||
311 | Game $\G3$ is like $\G2$, except that we choose $K$ at random rather | |
312 | than computing it via the random oracle. Specifically: | |
313 | ||
314 | + Initialize a partial function $\mathcal{K}_i\colon G \to | |
315 | \Sigma^\kappa$. | |
316 | ||
317 | + If a session of server $j^*$ receives a message $[U]$, apparently | |
318 | from client $i$ then we choose $K \getsr \Sigma^\kappa$ rather than | |
319 | consulting the random oracle. If $R \in \dom \mathcal{R}_i$ then we | |
320 | abort the game; otherwise, set $\mathcal{R}_i \gets \mathcal{R}_i | |
321 | \cup \{R \mapsto K\}$. The server computes $c \gets E_K(s_{j^*})$ | |
322 | and returns $[V, W, c]$ as before. | |
323 | ||
324 | + If a session of a client receives a message $[V', W', c']$, | |
325 | apparently from server $j^*$, then we calculate $R' = W' + u V'$ as | |
326 | before; then, if $R' \in \dom\mathcal{R}_i$ set $K' = | |
327 | \mathcal{R}_i(R')$; otherwise set $K' = H([R, (x_i + x^*) R])$ as | |
328 | usual. | |
329 | ||
330 | ||
331 | we abandon the game, and credit | |
332 | the adversary with a win, if the adversary ever issues a random-oracle | |
333 | query $H([R, x R])$ for an $R$ output by a session of server $j^*$. | |
334 | ||
335 | ||
336 | ||
337 | ||
338 | ||
339 | ||
340 | ||
341 | ||
342 | ||
343 | ||
344 | ||
345 | ||
346 | ||
347 | ||
348 | ||
349 | ||
350 | ||
351 | ||
352 | ||
353 | ||
354 | ||
355 | ||
356 | ||
357 | ||
358 | ||
359 | ||
360 | ||
361 | ** Communication model and security definition | |
362 | ||
363 | We consider a (probabilistic) adversary, and play a game $\G0$. The | |
364 | game is initialized as follows. | |
365 | ||
366 | + Choose a random bit $b \in \{0, 1\}$. | |
367 | ||
368 | + For each $i \in N$, select $s_i \inr \Sigma^\sigma$. | |
369 | ||
370 | + For each $j \in \N$, select $x_j \inr \gf{p}$, and set $X_j = x_j | |
371 | P$. | |
372 | ||
373 | + For each $(j, k) \in \N^2$, select $u_{j,k} \inr \gf{p}$. | |
374 | ||
375 | The adversary may make the following kinds of queries. | |
376 | ||
377 | \begin{description} | |
378 | \item[\normalfont $\textsf{begin}(j, k)$] | |
379 | The adversary is given $U_{j,k} = u_{j,k} P$. | |
380 | ||
381 | \item[\normalfont $\textsf{fetch}(U, i, j)$] | |
382 | If server $i$ is the challenge server, then the adversary must not | |
383 | have corrupted client $j$. Choose $r \getsr \gf{p}$ and $v \getsr | |
384 | \gf{p}$; compute $R \gets r P$, $K \gets H([R, r X_j])$, and $c \gets | |
385 | E_K(s_i)$. The adversary is given $(R - v U, c)$. | |
386 | ||
387 | \item[\normalfont $\textsf{corrupt-server}(i)$] | |
388 | Server $i$ must not be the challenge server. Server $i$ is marked as | |
389 | \emph{corrupt}. The adversary is given $s_i$. | |
390 | ||
391 | \item[\normalfont $\textsf{corrupt-client}(j)$] | |
392 | Client $j$ is marked as \emph{corrupt}. The adversary is given $x_j$. | |
393 | ||
394 | \item[\normalfont $\textsf{challenge}(i)$] | |
395 | The adversary is permitted at most one \textsf{challenge} query. The | |
396 | server $i$ -- the \emph{challenge server} -- must not be corrupt, a | |
397 | query $\textsf{fetch}(U, i, j)$ must not have been made for any client | |
398 | $j$ which was corrupt at the time. If $b = 0$ then $s^* = s_i$; | |
399 | otherwise $s^* \inr \Sigma^\sigma$ is chosen at random. The adversary | |
400 | is given $s^*$. | |
401 | \end{description} | |
402 | ||
403 | Finally, the adversary outputs a single bit $b'$. The adversary /wins/ | |
404 | this game if $b' = b$. Note that it is permitted for the adversary to | |
405 | corrupt a client | |
406 | ||
407 | ||
408 | * COMMENT Emacs cruft | |
409 | #+LaTeX_CLASS: strayman |