--- /dev/null
+=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
~mdw / udpkey / blobdiff