| 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 |