Found in crybaby's working tree.

[udpkey] / protocol.org

=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