=udpkey= Protocol Analysis \begin{abstract} This note describes and analyses the cryptographic protocol used by \texttt{udpkey}. The analysis is fairly formal and quantitative; but this note probably isn't up to full academic standards. \end{abstract} * Introduction The =udpkey= program transports a secret -- a short-ish binary string -- from a /server/ which knows it to a /client/ which needs it for some reason. In the particular use case it was written for, the client is a server in a lights-out datacentre which is booting and needs a key to decrypt its disk. ** Preliminaries We work in a cyclic group $G = \langle P\rangle$, of order $p$, written additively. We consider $G$ as a vector space over $\gf{p}$. We say that an algorithm $\mathcal{A}$ can $(t, q, \epsilon)$-/break/ $G$ if $\mathcal{A}$ takes at most time $t$, issues at most $q$ oracle queries, and \[ \Pr[\textrm{$a^* \getsr \gf{p}$; $b^* \getsr \gf{p}$; $Z^* \gets a^* b^* P$; $Z \gets \mathcal{A}^{a^*(\cdot)\stackrel?=(\cdot)} (a^* P, b^* P)$} : Z = Z^*] \ge \epsilon \] Let $\Sigma = \{0, 1\}$; $\Sigma^*$ is the set of binary strings. If $x$ and $y$ are strings then $x \cat y$ is their concatenation. If $x$ is a string then $\ell(x)$ its length; i.e., $x \in \Sigma^{\ell(x)}$. We assume that sequences of strings, integers, and elements of $\gf{p}$ and $G$ can be encoded as unambiguously as strings, and denote this encoding using $[\cdots]$. We need a symmetric encryption scheme $\mathcal{E} = (\kappa, E, D)$. Here, $\kappa$ is the (nonnegative integer) /key length/; $E$ is the /encryption algorithm/, which takes as input a /key/ $K \in \Sigma^\kappa$ and a /message/ $m \in \Sigma^*$, and outputs a /ciphertext/ $c = E_K(m) \in \Sigma^*$; and $D$ is the /decryption algorithm/, which takes as input a key $K \in \Sigma^\kappa$ and a (purported) ciphertext $c \in \Sigma^*$, and outputs $m' = D_K(c) \in \Sigma^* \cup \{\bot\}$, where $\bot \notin \Sigma^*$ is a symbol indicating failure. We require that $D_K(c) = m$ whenever $E_K(m) = c$. We say that an algorithm $\mathcal{A}$ can $(t, q_E, q_D, \epsilon)$-/break/ $\mathcal{E}$ if $\mathcal{A}$ takes at most time $t$, issues at most $q_E$ (resp.\ $q_D$) encryption (resp.\ decryption) queries, and \[ 2 \Pr[\textrm{$K \getsr \Sigma^\kappa$; $b \getsr \{0, 1\}$; $b' \gets \mathcal{A}^ {E_K(w_b(\cdot, \cdot)), D_K(\cdot)}$} : b = b'] - 1 \ge \epsilon \] where $w_b(m_0, m_1) = m_b$, whenever $\mathcal{A}$ queries its encryption oracle on a pair of messages $m_0, m_1$ then $\ell(m_0) = \ell(m_1)$, and $\mathcal{A}$ never queries its decryption oracle on a ciphertext which was previously produced by the encryption oracle. We use the random oracle model, and assume the existence of a randomly chosen mapping $H\colon \Sigma^* \to \Sigma^\kappa$. ** Communication model In this section we describe the security property we want from our protocol. The model is fairly standard: after some initialization, an adversary is invoked; the rest of the game unfolds according to the adversary's queries. We consider a number of /clients/ $C_j$ and /servers/ $S_i$, for $0 \le i, j < n$. There is no especial relationship between like-numbered clients and servers. The clients and servers don't communicate directly: rather, communication occurs between client and server /sessions/, which are established by the adversary. A protocol $\Pi = (\lambda, \textsf{init}, \textsf{msg})$ consists of an integer /secret length/ parameter $\lambda$, and two (possibly randomized) algorithms: + Initialization (\textsf{init}) :: Given $n$, return: two vectors of /private inputs/ $\mathbf{I}^C$ and $\mathbf{I}^S$ for the clients and servers, respectively; and a /common input/ $J$. + Activate client (\textsf{activate-client}) :: Given a client private input $I$, and the common input $J$, output a new /session state/ $\sigma'$. + Activate server (\textsf{activate-server}) :: Given a server private input $I$, a secret $s \in \Sigma^\lambda$, and the common input $J$, output a new /session state/ $\sigma'$ and a /message/ $m \in \Sigma^*$. + Client (server) message (\textsf{client-msg}, \textsf{server-msg}) :: Given a client (server) state $\sigma$, a server (client) index $i$, and a message $m \in \Sigma^*$, output a /new state/ $\sigma'$, a /response/ message $m' \in \Sigma^* \cup \{\bot\}$, and an output $o$. If $m' = \bot$ then we say that the session has /finished/: if $o = \bot$ then it has /failed/; otherwise it has /succeeded/ with output $o$. If $m' \ne bot$ then we require $o = \bot$. The game proceeds as follows. 1. *Initialization*. Run $\textsf{init}(n)$ to find initial private inputs $\mathbf{I}^C$ and $\mathbf{I}^S$, and common input $J$. Choose a random bit $b \inr \{0, 1\}$, and a /secret/ $s_i \inr \Sigma^\lambda$ for each server $S_i$. 2. *Invoke the adversary*. The adversary is given the common input $J$. It may make the following queries. + Random oracle :: Given a string $s \in \Sigma^*$, return the output of the random oracle $H(s)$ to the adversary. + Activate client :: Given a client index $i$ and a session index $k \in \N$, set $(\sigma^C_{i,k}, m) \gets \textsf{activate-client}(I^C_i, J)$, and return $m$ to the adversary. + Activate server :: Given a server index $j$ and a session index $k \in \N$, set $\sigma^S_{j,k} \gets \textsf{activate-server}(I^S_j, s_j, J)$. + Deliver message to client :: Given a client index $i$, a session index $k$, a server index $j$, and a message $m$, set $(\sigma^C_{i,k}, m', o) \gets \textsf{client-msg}(\sigma^C_{i,k}, j, m)$, and return $m'$ to the adversary. + Deliver message to server :: Given a server index $j$, a session index $k$, a server index $i$, and a message $m$, set $(\sigma^S_{i,k}, m', o) \gets \textsf{server-msg}(\sigma^S_{j,k}, i, m)$, and return $m'$ to the adversary. If server $i$ is the /challenge server/ (described below) then client $j$ must not be /corrupt/ (below). + Corrupt client :: Given a client index $i$, mark client $i$ as /corrupt/ and return $I^C_i$ to the adversary. + Corrupt server :: Given a server index $j$, mark server $j$ as /corrupt/ and return $(I^S_j, s_j)$ to the adversary. Server $j$ must not be the /challenge server/. + Challenge :: Given a server index $j$, mark server $j$ as being the /challenge server/. If $b = 1$ then set $s^* \gets s_j$; otherwise choose $s^* \getsr \Sigma^\lambda$ at random. Return $s^*$ to the adversary. The adversary must not have issued a challenge query before; server $j$ must not be corrupt; and server $j$ must not have been delivered a message (apparently) from a client which was, at that time, corrupt. Eventually, the adversary terminates and outputs a bit $b'$. The adversary wins the game if $b = b'$. We say that the adversary $(t, q_M, q_H, \epsilon)$-breaks protocol $\Pi$ if the adversary completes within time $t$, delivers at most $q_M$ messages, issues at most $q_H$ random-oracle queries, and $2 \Pr[b = b'] - 1 \ge \epsilon$. There is a /correctness/ constraint on protocols. Let $\mathcal{B}_{i,j}$ be the following `benign' adversary. 1. Activate session $0$ of server $j$. 2. Activate session $0$ of client $i$, receiving message $m$. 3. Deliver message $m$ from client $i$ to session $0$ of server $j$, receiving message $m'$. 4. Deliver message $m$ from server $i$ to session $0$ of client $j$, receiving message $m$. 5. If $m \ne \bot$ then go back to step 3. 6. Output $b' = 1$. We require that $\mathcal{B}_{i,j}$ complete in finite time, and that client $i$ successfully output the secret $s_j$. Notice that our definition excludes trivial protocols because the initialization procedure prepares the inputs for the clients and servers before the secrets $s_j$ are chosen. Also, we impose no requirements on a client's output in the face of adversarial interference. Instead, we expect clients to be able to distinguish the correct secret in some manner (e.g., by checking its hash against a reference). Modelling this as part of the protocol is tricky, though, because whatever the client uses to check a secret can also be used by an adversary to distinguish between a proper secret and a fake random one in the security game. * The original =v0= protocol This section describes and analyses =udpkey='s original =v0= protocol. The client knows a /private key/ $x \in \gf{p}$. The server knows a /secret/ $s \in \Sigma^\sigma$, and the client's /public key/ $X = x P \in G$. The protocol works as follows. + Client :: $u \getsr \gf{p}$; $U \gets u P$. Send $[U]$ to the server. + Server :: $v \getsr \gf{p}$; $V \gets v P$; $r \getsr \gf{p}$; $R \gets r P$; $W \gets R - v U$; $K \gets H([R, r X])$; $c \gets E_K(s)$. Send $[V, W, c]$ to the client. + Client :: $R \gets W + u V$; $K \gets H([R, x R])$; $s \gets D_K(c)$. This basically splits into a DHIES encryption $(R, c)$ of $\sigma$, made with the client's long-term public key $X$, but the clue $R$ is ElGamal-encrypted using an ephemeral public key $U$. The =v0= protocol is not forward-secure: an active attacker can acquire information which, combined with the result of compromising a client, can reveal a server's secret. The attack is simple: 1. Activate session $0$ of server $0$. 2. Choose $u \inr \gf{p}$ and send $U = u P$ to session $0$ of server $0$, apparently from client $0$. Receive $(V, W, c)$. 3. Corrupt client $0$; recover the client's private key $x$. 4. Challenge server $0$, receiving the challenge secret $s^*$. 5. Compute $R = W + u V$, $K = H([R, x R])$, and $s = D_K(c)$. 6. If $s = s^*$ then output $b' = 1$; otherwise output $b' = 0$. This adversary, then, $(t, 1, 1, 1)$-breaks =v0=, for some appropriately small constant $t$. We shall show that the =v0= protocol is secure if clients are not corrupted; and, separately, if the adversary is `passive' -- i.e., restricts itself to delivering messages honestly. ** Security in the absence of corruption If clients are not corrupted, then their private keys $x$ are secret from the adversary. This proof considers a sequence of games, played with the same adversary $\mathcal{A}$. In each game $\G{i}$, we let $P_i$ be the probability that $\mathcal{A}$. Let $\G0$ be the full attack game, with the =v0= protocol, as described above, where the adversary makes no $\textsf{corrupt-client}$ requests. Game $\G1$ is like $\G0$, except that we guess a server $j^* \inr \{0, 1, \ldots, n - 1\}$ at random, in the hope that this is the challenge server. If the guess is wrong (i.e., the adversary chooses a challenge server $j \ne j^*$) then we immediately abandon the game, and credit the adversary with a win. Then \[ |P_1 - P_0| \le \frac{1}{n} \] Game $\G2$ is like $\G1$, except that we compute the private and public keys differently, and encryption works differently. + Initially we choose $a^* \inr \gf{p}$ and $b^* \inr \gf{p}$. Let $A^* = a^* P$ and $B^* = b^* P$, and $Z^* = a^* b^* P$. For each client $i$, let $x'_i = x_i - a^*$, and $X'_i = x'_i P = X_i - A^*$. Initialize a function $\mathcal{R}\colon G \to \gf{p} \cup \{\bot\}$ so that $\mathcal{R}(Q) = \bot$ for all $Q \in G$. + When a session $k$ of server $j^*$ receives a message $U$ from client $i$: we select $r' \inr \gf{P}$, and set $r = r' + b^*$; then $R = r' P + B^*$, and $Z = r' X_i + x'_i B^* + Z^*$. Set $\mathcal{R}(R) \gets r'$. + When a session $k$ of client $i$ receives a message $(V, W, c)$ from server $j^*$: recover $R = W + u V$ as usual; then, if $r' = \mathcal{R}(R) \ne \bot$ then set $Z = r' (A^* + X'_i) + x'_i R + Z^*$; otherwise, if $r' = \bot$, and the adversary has previously issued a random-oracle query for a pair $[R, Z']$ with $Z' = x'_i R + a^* R$, then set $Z = Z'$; otherwise ignore the message. It is clear that $\G2$ proceeds exactly as $\G1$ except that a client might ignore a message which previously it accepted. In this case, then, the client would have chosen $K = H([R, x_i R])$; but the random oracle has not previously been queried at $[R, x_i R]$, so $K$ is freshly random. A standard hybrid argument allows us to construct an adversary which $(t + O(q), 1, q, \epsilon)$-breaks $\mathcal{E}$, such that \[ |P_2 - P_1| \le q \epsilon \] Specifically: + In the $m$th hybrid, we focus on the $m$th message delivered to a client from server $j$. Game $\G3$ is like $\G2$, except that we modify encryption and decryption further. + At the start of the game, + When a session $k$ of server $j$ receives a message from client $i$: if $\mathcal{R}( initialization procedure now chooses $x^* \inr \gf{p}$, and sets $X^* = x^* P$. Each client $i$ gets $x_i \inr \gf{p}$ and $x^*$; and the public input contains $X^*$ (for the adversary's benefit), and $X_i = x_i P + X^*$ for each client $i$. The client computes $K$ as $H([R, (x_i + x^*) R])$. None of this affects the probability distribution at all, so $P_2 = P_1$. . Game $\G3$ is like $\G2$, except that we choose $K$ at random rather than computing it via the random oracle. Specifically: + Initialize a partial function $\mathcal{K}_i\colon G \to \Sigma^\kappa$. + If a session of server $j^*$ receives a message $[U]$, apparently from client $i$ then we choose $K \getsr \Sigma^\kappa$ rather than consulting the random oracle. If $R \in \dom \mathcal{R}_i$ then we abort the game; otherwise, set $\mathcal{R}_i \gets \mathcal{R}_i \cup \{R \mapsto K\}$. The server computes $c \gets E_K(s_{j^*})$ and returns $[V, W, c]$ as before. + If a session of a client receives a message $[V', W', c']$, apparently from server $j^*$, then we calculate $R' = W' + u V'$ as before; then, if $R' \in \dom\mathcal{R}_i$ set $K' = \mathcal{R}_i(R')$; otherwise set $K' = H([R, (x_i + x^*) R])$ as usual. we abandon the game, and credit the adversary with a win, if the adversary ever issues a random-oracle query $H([R, x R])$ for an $R$ output by a session of server $j^*$. ** Communication model and security definition We consider a (probabilistic) adversary, and play a game $\G0$. The game is initialized as follows. + Choose a random bit $b \in \{0, 1\}$. + For each $i \in N$, select $s_i \inr \Sigma^\sigma$. + For each $j \in \N$, select $x_j \inr \gf{p}$, and set $X_j = x_j P$. + For each $(j, k) \in \N^2$, select $u_{j,k} \inr \gf{p}$. The adversary may make the following kinds of queries. \begin{description} \item[\normalfont $\textsf{begin}(j, k)$] The adversary is given $U_{j,k} = u_{j,k} P$. \item[\normalfont $\textsf{fetch}(U, i, j)$] If server $i$ is the challenge server, then the adversary must not have corrupted client $j$. Choose $r \getsr \gf{p}$ and $v \getsr \gf{p}$; compute $R \gets r P$, $K \gets H([R, r X_j])$, and $c \gets E_K(s_i)$. The adversary is given $(R - v U, c)$. \item[\normalfont $\textsf{corrupt-server}(i)$] Server $i$ must not be the challenge server. Server $i$ is marked as \emph{corrupt}. The adversary is given $s_i$. \item[\normalfont $\textsf{corrupt-client}(j)$] Client $j$ is marked as \emph{corrupt}. The adversary is given $x_j$. \item[\normalfont $\textsf{challenge}(i)$] The adversary is permitted at most one \textsf{challenge} query. The server $i$ -- the \emph{challenge server} -- must not be corrupt, a query $\textsf{fetch}(U, i, j)$ must not have been made for any client $j$ which was corrupt at the time. If $b = 0$ then $s^* = s_i$; otherwise $s^* \inr \Sigma^\sigma$ is chosen at random. The adversary is given $s^*$. \end{description} Finally, the adversary outputs a single bit $b'$. The adversary /wins/ this game if $b' = b$. Note that it is permitted for the adversary to corrupt a client * COMMENT Emacs cruft #+LaTeX_CLASS: strayman