\documentclass[twocolumn]{article}
\usepackage{usenix,psfig,amsfonts,amssymb}

\newcommand{\Z}{\mathbb{Z}}	% Rich man's black board's font.
\newcommand{\F}{\mathbb{F}}
\newcommand{\R}{\mathbb{R}}
\def\QED {\hfill $\!\square$ \newline}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}[section]

\newcommand{\comment}[1]{}
\newcommand{\proof}{ \noindent {\bf Proof \ } }
\newcommand{\proofsk}{ \noindent {\bf Proof Sketch \ } }
\newcommand{\eqref}[1]{(\ref{#1})}
\newcommand{\mypar}[1]{\noindent {\bf #1}}

\newcommand{\st}{\;\;\mbox{s.t.}\;\;}
\newcommand{\half}{{1 \over 2}}
\newcommand{\xor}{\oplus}
\newcommand{\norm}{\parallel}
\newcommand{\rsa}{\mbox{\sc rsa}}
\renewcommand{\min}[1]{{#1}_{\mbox{\tiny min}}}
\newcommand{\lcat}{\langle}
\newcommand{\rcat}{\rangle}
\newcommand{\tuple}[1]{\lcat #1 \rcat}

\title{\Large \bf Building Intrusion Tolerant Applications\footnote{
	Project URL: {\tt http://www.stanford.edu/$\sim$dabo/ITTC}}}

\author{ \begin{tabular}{ccccc}
	{Thomas Wu}
		& \hspace{0.1cm} & 
	{Michael Malkin} 
		& \hspace{0.1cm} & 
	{Dan Boneh\thanks{Supported by {\sc darpa} 
		contract \#F30602-97-C-0326.}}  \\
        {\normalsize tjw@cs.stanford.edu} & &
        {\normalsize mikeym@stanford.edu} & &
        {\normalsize dabo@cs.stanford.edu}
	\end{tabular}}

\date{}

\begin{document}

\maketitle
\thispagestyle{empty}

\begin{abstract}  
The ITTC project (Intrusion Tolerance via Threshold Cryptography)
provides tools and an infrastructure for building intrusion tolerant
applications.  Rather than prevent intrusions or detect them after the
fact, the ITTC system ensures that the compromise of a few system
components does not compromise sensitive security information.  To do so we
protect cryptographic keys by distributing them across a few servers.
The keys are never reconstructed at a single location.  Our designs
are intended to simplify the integration of ITTC into existing
applications.  We give examples of embedding ITTC into the Apache web
server and into a Certification Authority (CA).  Performance
measurements on both the modified web server and the modified CA show
that the architecture works and performs well.
\end{abstract}

%\noindent {\bf Keywords:} intrusion tolerance, shared keys.

\section{Introduction} \label{intro}

To combat intrusions into a networked system one often installs intrusion
detection software to monitor system behavior.  Whenever an ``irregular''
behavior is observed the software notifies an administrator.  In this
paper we study a complementary approach we call {\em intrusion
tolerance}. Rather than prevent or detect intrusions after the fact, we
provide tools that limit the amount of damage an intruder can cause.  Our
goal is to ensure that an attacker who penetrates a few system components
cannot compromise total system security.  To defeat our system an attacker
must either penetrate multiple components in a short amount of time or
frequently penetrate a certain component.  Either way such large scale
attacks are much easier to detect than single isolated attacks.

To describe our approach we consider a web server as an example.  To
enable secure connections to the server one often stores a secret key
on the server.  Typically the key is used during SSL session key
negotiation.  An attacker who penetrates the server can expose the
private key and can then either masquerade as the server or eavesdrop
on connections to the server.  Hence, in the case of a bank's web
server a single intrusion could result in a compromise of sensitive
financial data. In contrast, our approach splits the web server into a
small number of components so that a single intrusion does not expose any
information about the server's key.  Our approach can also be used to
safeguard a Certificate Authority's (CA) private key.  By splitting the
CA into a number of components we can ensure that penetration of
a small number of components does not compromise the CA's key.

We protect an application's private key (e.g.  a web server or a CA)
by sharing the key among a number of {\em share servers}.  An attacker
who breaks into a small number of share servers cannot expose the private
key.  Our main design principle is that long term security information
should {\em never} be located in a single location.  Hence, 
there is no single point of attack at which an attacker
can expose critical security information (such as a CA's private key).
Shamir's secret sharing scheme~\cite{Shamir} is a classic approach for
distributing private keys across several sites.  Unfortunately, to use the
shared key one must reconstruct it at a single location. Thus, secret 
sharing is inappropriate for our purposes.  Instead, we use techniques of
Threshold Cryptography~\cite{G97} to distribute an application's private 
key among several share servers so that the key can be used without ever
reconstructing it.

Our system is designed to be easy to embed into existing applications.
For example, by embedding our system into the Apache web server we
built a web server whose private key is split across a number of share
servers and is never reconstructed in a single location.  Whenever the
web server receives a request for a secure connection it interacts
with the share servers to apply its private key.  As we shall see in
Section~\ref{timing} the performance penalty for doing so is small
compared to the total time to establish an SSL connection.  Consider
again the example of a bank's system. By placing the share servers in
a secure subnet and ensuring that they only accept connections from
the bank's web servers one can strengthen the security of the bank's
private key.  Furthermore, our share servers can service multiple web
servers.  Hence, a bank maintaining dozens of web servers need not
store a private key on each of them.  Instead, the private keys can be
stored (in shared form) on the share servers. This way a small number
of break-ins will not compromise any of the private keys.

As an additional benefit, our system provides high availability of
private keys.  Even if a few of the share servers crash (by accident
or as a result of an attack) and all data stored them is lost, the
remaining active share servers automatically compensate for the
corrupt ones.  Furthermore, the system can recover by redistributing valid
shares to the corrupted share servers.

The paper describes the design and implementation of our system
including the prototype applications we built.  We provide detailed
performance measurements on both the modified web server and the
modified CA to show that the architecture works and performs well.

\section{System components}

To protect private keys used by applications such as a web server or a
CA, our system distributes shares of private keys among a number of
share servers.  In this section we describe the
system components.  We refer to applications using
the share servers as {\em clients}.  Web servers and CA's are
example clients.  Figure~\ref{components} illustrates the interaction
between the various components.

\begin{figure*}[t]
\fbox{\centerline{\psfig{figure=components.eps,width=6in,height=2.5in,rwidth=6.0in,rheight=2.6in}}}
\caption{System components}  \label{components}
\end{figure*}

\mypar{Share server}  The share servers are implemented as daemons running
on different machines.  They hold shares of the private keys belonging
to the clients they serve.  These shares reveal no information about
the client's private key.  A share server can manage multiple keys and
serve a large number of clients.  We envision the total number of
share servers being less than ten.  Clearly it is desirable that an
attacker not be able to compromise the share servers.  However, the
intrusion tolerant design of our system ensures that even if a few of
the share servers are penetrated and the secrets stored on them are
exposed or corrupted there is no compromise to overall system
security.  In other words, an attacker learns nothing from penetrating
a few of the share servers.  The system identifies corrupt share
servers and can be instructed to take appropriate action to refresh
the secrets stored on them.

\mypar{Client.}  A client is any application that makes use of our
client side Threshold LiBrary (the TLB).  When a client connects to
the share servers it first authenticates itself as an authorized
client.  It then interacts with the share servers to sign a message or
decrypt a given ciphertext using the shared private key stored on the
share servers.  One concern is that an attacker can penetrate a client
and expose the client's authentication key. The attacker can then
masquerade as the client and fool the share server into applying a
shared key.  In Section~\ref{seqnum} we describe a mechanism for
detecting such an attack.  At any rate, the attacker cannot expose the
shared private key (as is the case when the private key is stored on
the client).

\mypar{Administrator.}  We provide a central administration utility
to administer all the share servers.  The administrator utility manages
the various keys stored on the share servers. It can shutdown or suspend
the servers if necessary, or instruct the servers to take appropriate
action if some of the servers have been penetrated.  The utility is provided
for convenience.  If for some reason central administration is not desired
the share servers can be controlled locally.

\mypar{Monitor.}  We built a monitor utility for
testing and demonstrating our system.  The
monitor is a single daemon that collects information from all key servers
and clients.  Essentially, the share servers and clients send data to the
monitor (via UDP) telling it what they are doing at any given moment.  For
instance, a client may tell the monitor that it is asking servers number
1, 2 and 4 to apply key number 23 to sign a message.  A moment later share
servers 1, 2 and 4 will each tell the monitor that they are applying
shares of key number 23 to generate a signature, and so on.  The monitor
collects all this information and sends it to a Java applet that
displays it in a human readable form.  During actual deployment the
monitor can be easily disabled by setting the appropriate switch in the
system's configuration file.  The administrator can still monitor system
behavior by viewing each server's log file.

\subsection{Interaction between components}

Each share server manages shares of the private key belonging to its
clients.  These shares are stored on disk encrypted using the
administrator's passphrase. When the share server is started (possibly as
part of the system's bootup script) it enters {\em suspended} mode.  In
suspended mode the share server refuses to accept any connections except a
connection from the administrator.  When all share servers are started,
the admin program can be used to activate the servers by sending the
passphrase to all of them at once.  Connections between the admin program
and share servers are always protected by SSL using mutual authentication.
Using a hash of the administrator's passphrase, each server loads all
shares available to it and enters {\em active} mode.  The server is then
ready to serve its clients.

In active mode a share server can accept connections from its clients
and the administrator.  The first step in any connection to a share
server is mutual authentication and key exchange using SSL.  The
second step is an integrity check of the peer as described in
Section~\ref{seqnum}. After a secure link is established, requests to
the share server use the following protocol:  \\[-0.6cm]
\begin{tabbing}
Request: \hspace{1cm} \= {\sc command} $\tuple{opcode}$ $\tuple{data}$ \\
Response:             \> {\sc response} $\tuple{status}$ $\tuple{data}$
\end{tabbing}
The response status is either (1) OK indicating a successful completion,
(2) SUSPENDED indicating that the share server is in suspended mode, or
(3) a detailed error-code.

To understand the interaction between the system components we describe
some of the opcodes supported by the share servers.  

\mypar{Connection from client.} Each connection from a client causes the
share servers to create a new thread (up to a specified maximum number of 
threads).  These threads last as long as the
client keeps open the connection to the share server, reducing the
overhead of repeatedly opening and closing connections.  A client can send
a number of opcodes instructing the servers to apply a shared key.  The
interaction that takes place as a result of these commands is described in
Section~\ref{usekey}. \\[-0.9cm]
\begin{description}
\item[{\sc sign.}] Instructs the share server to apply its share of the private
key for the purpose of generating a signature.  The parameters include
a digest of the message to be signed.  We note that prior to taking
part in the signing protocol described in Section~\ref{usekey} the
key-servers verify that the message to be signed follows the
PKCS1 format~\cite{PKCS}.
\item[{\sc decrypt.}] Instructs the share server to apply its share of the 
private key for the purpose of decrypting a ciphertext.
\item[{\sc hash-sign.}] Instructs the share server to apply its share of the 
private key for the purpose of generating a hash of a signature.   The
purpose of this opcode is explained in the next section.
\end{description}

\mypar{Connection from the admin.}
Some of the commands from the administrator include: \\[-0.9cm]
\begin{description}
\item[{\sc shutdown, suspend, activate.}] Manage share server
modes. Shutdown causes all share server daemons to exit. 

\item[{\sc genkey.}] The admin can instruct the share servers to
generate a new shared key.  In our system private keys are {\em never}
constructed in a single location. When an RSA key is generated it is
generated in shared form.  This uses a protocol due to Boneh and
Franklin~\cite{BF97}.  We use the implementation of shared RSA key
generation described in~\cite{MWB98}.  The shares of the new private RSA key
are stored on the share servers (encrypted with the admin password).  The
new public key is sent to the admin and is saved on the admin's machine.
Authorized clients can then connect to the share servers to generate
signatures or decrypt incoming messages using the new key.

A new public key is usually certified by a CA before it can be properly
used. To obtain a public key certificate for the new key the admin must
generate a {\em certificate request} to be sent to a CA.  The format of a
certificate request (specified in PKCS10) includes a {\em self signature}
on the request.  In other words, the newly generated {\em private} key
must be used to sign the public key certificate request.  The self
signature ensures that the entity requesting the certificate has the
corresponding private key.  Unfortunately, in our case, the admin does not
have the private key.  In fact, no one has the private key --- the private
key is {\em always} stored in shared form on the share servers.
Consequently, to generate the certificate request, the admin must connect
to the share servers {\em as a client} and ask them to sign the
request. Once the admin obtains the self signed request he can forward it
to the CA.  The CA will send back the certificate.  We provide a utility
that enables the admin to generate a self signed certificate
request, as described in Section~\ref{sec:ittcca}.

\item[{\sc refresh.}] Suppose the administrator suspects the system is
under attack and some share servers are compromised.  In this case, the
admin can instruct all share servers to {\em refresh} their shares of the
private keys.  Refreshing the shares does not change the private key.  It
simply generates a new independent {\em sharing} of the private key.
Suppose an attacker obtains the shares of a private key stored on one of
the servers. Once the admin refreshes the shares of the private key the
information in the attacker's hands becomes useless.

Refreshing is also used when shares stored on a share server are corrupted
or lost.  Corruption or loss could happen due to a denial of service
attack or a simple server crash.  Refreshing the shares causes the
uncorrupted servers to generate new valid shares for the corrupted server.
Consequently, the system gracefully tolerates corruption or loss of a few
shares.
\end{description}


\section{Key management}

We begin by explaining how one shares a private RSA key among a number of share
server so that the key can be used without ever having to reconstruct
it.  We then describe the structure and PEM format used to store these
shared keys.

\comment{
\begin{figure*}[t!]
\begin{center}
\begin{tabular}{ccc}
$\begin{array}{c} d = d_1+d_2+d_3 \\ d = d_4+d_5+d_6 \end{array}$
& \hspace{1.5cm} &
$\begin{array}{c} d = d_1+d_2+d_3=d_4+d_5=d_6+d_7 \\ 
	d_5 = d_8+d_9 = d_{10}+d_{11} \\ d_6 = d_{12}+d_{13} \end{array}$
\\[0.7cm]
\mbox{\begin{tabular}{|c||c||c||c|}
\hline
{\tiny Server} 1 & {\tiny Server} 2 & {\tiny Server} 3 & {\tiny Server} 4 \\
\hline
$d_1$ & $d_2$ & $d_3$ & $d_3$ \\
$d_4$ & $d_4$ & $d_5$ & $d_6$ \\
\hline
\end{tabular}} 
& &
\mbox{\begin{tabular}{|c||c||c||c||c|}
\hline
{\tiny Server} 1 & {\tiny Server} 2 & {\tiny Server} 3 & 
		{\tiny Server} 4 & {\tiny Server} 5 \\
\hline
$d_1$    & $d_2$    & $d_3$ & $d_4$    & $d_4$    \\
$d_7$    & $d_7$    & $d_7$ & $d_{12}$ & $d_{13}$ \\ 
$d_8$    & $d_8$    & $d_9$ &          &          \\
$d_{10}$ & $d_{11}$ &       &          &          \\
\hline
\end{tabular}}  \\[1.0cm]
3-out-of-4 sharing & & 3-out-of-5 sharing
\end{tabular}
\end{center} 
\mbox{}\vspace{-0.5cm}
\caption{Additive sharings of a private RSA key $d$.} \label{sharings}
\end{figure*}
}

\begin{figure*}[t!]
\begin{center}
\begin{tabular}{ccc}
$\begin{array}{c} d = d_1+d_2+d_3 \\ d = d_4+d_5+d_6 \end{array}$
& \hspace{1.5cm} &
$\begin{array}{c} d = d_1+d_2 \\ d = d_3+d_4 \end{array}$
\\[0.7cm]
\mbox{\begin{tabular}{|c||c||c||c|}
\hline
{\tiny Server} 1 & {\tiny Server} 2 & {\tiny Server} 3 & {\tiny Server} 4 \\
\hline
$d_1$ & $d_2$ & $d_3$ & $d_3$ \\
$d_4$ & $d_4$ & $d_5$ & $d_6$ \\
\hline
\end{tabular}} 
& &
\mbox{\begin{tabular}{|c||c||c||c|}
\hline
{\tiny Server} 1 & {\tiny Server} 2 & {\tiny Server} 3 & 
		{\tiny Server} 4 \\ 
\hline
$d_1$    & $d_1$    & $d_2$ & $d_2$    \\
$d_3$    & $d_4$    & $d_3$ & $d_4$    \\    
\hline
\end{tabular}}  \\[0.5cm]
3-out-of-4 sharing & & 2-out-of-4 sharing
\end{tabular}
\end{center} 
\mbox{}\vspace{-0.5cm}
\caption{Additive sharings of a private RSA key $d$.} \label{sharings}
\end{figure*}

\subsection{Sharing RSA keys}

Recall that an RSA private key consists of a modulus $N$ and a secret
exponent $d$.  The modulus $N$ is a product of two large primes, and $d$
is a positive integer less than $N$.  To decrypt a ciphertext $C$
one computes  $C^d \bmod N$.  Similarly to sign a message digest $M$
one computes $M^d \bmod N$.  Hence, both operations require an
exponentiation to the power $d$ modulo $N$.  Without the secret exponent $d$
it is believed to be hard to either decrypt ciphertexts or generate signatures.

We show how a private RSA key can be broken up into a number of pieces
(shares). Each share can be stored on a separate server and yet the
private key can be used without having to reconstruct the secret. The
basic idea, due to Frankel~\cite{F89}, is to pick random numbers
$d_1,d_2,d_3$ in the range $[-N,N]$ so that $d_1+d_2+d_3 = d$.  We 
then store share $d_i$ on share server number $i$, for $i=1,2,3$.  Note
that an attacker who breaks into any two of the three servers learns
nothing about the private key $d$. All three servers must be compromised
to obtain $d$.

When a client wishes to apply the key to sign a message $M$ it 
sends $M$ to all three servers.  Each server applies its
own share $d_i$ to obtain $S_i = M^{d_i} \bmod N$ and sends the result $S_i$
back to the client.   The client obtains $S_1,S_2,S_3$ from the
three servers.  It multiplies them to obtain the signature 
$S = S_1 \cdot S_2 \cdot S_3 \bmod N$. Since $d = d_1+d_2+d_3$ we have
that $S = M^d \bmod N$ as required.  Note that the private key $d$ was
never reconstructed in order to be used.  In addition, there is no
communication between the share servers.  The only interaction is between
the client and each of the servers.  

Clearly this approach generalizes to distributing a private RSA key among $k$
servers.  Even if $k-1$ of the shares are exposed, an attacker learns nothing
about the private key $d$.  Since all $k$ share servers must be involved
in applying to key we call this sharing a $k$-out-of-$k$ sharing.


\subsubsection{$t$-out-of-$k$ sharing}

There are a number of problems with the approach described above.  Most
importantly, it is not fault-tolerant.  If one of the share servers crashes
the entire system goes offline.  If one of the share servers loses its
share, the private key is lost forever.  For this reason, we use 
a $t$-out-of-$k$ sharing of the secret key; any $t$ of the share servers
can be used to apply the key.  For instance, if we use a 3-out-of-4 sharing
no harm is done if one of the share servers is taken offline.  In addition,
a break-in into any two servers reveals no information about the private key.

Typically a $t$-out-of-$k$ sharing is achieved using Shamir's classic
secret sharing~\cite{Shamir}. Unfortunately, when using Shamir's
secret sharing the keys must be reconstructed before they can be used.
This is inappropriate for our purposes. Instead, we use a
combinatorial construction to obtain a $t$-out-of-$k$ sharing of $d$
from several $t$-out-of-$t$ sharings of $d$.  We give two examples in
Figure~\ref{sharings}.  In both examples all the $d_i$'s are random
integers in the range $[-N,N]$ satisfying the stated equalities.  Each
server stores multiple $d_i$'s as indicated by the column
corresponding to that server.  Observe that in the example on the
left, any three servers can apply the key while any two servers learn
nothing about $d$.  The example on the right is more fault tolerant, but
compromising two servers reveals the key.  A compromise of a single
server reveals nothing about the key.  More generally, we implemented an
algorithm that constructs tables as above for a $t$-out-of-$k$ sharing
for any $t$ and $k$.  The algorithm
%is described in Appendix~\ref{keyshare} and 
is based on ideas from~\cite{AGY95,DDB94}.

When a client requests that the servers apply a private key, it
specifies which coalition of $t$ servers is used.  Based on the coalition,
each server locally decides which of its $d_i$'s it will use and sends the
resulting $S_i$ back to the client.  The client multiplies the $t$
responses and obtains the signature $S$.  The client then uses the public
key to check the validity of $S$ as a signature.  This is done to ensure
that all share servers responded properly. In Section~\ref{usekey} we
explain how we deal with corrupt share servers that apply their private
shares incorrectly.

\subsection{Key structures and key storage}  \label{sec:keystruct}

\begin{figure*}
\caption{Shared key file formats.} \label{keyfile}
\begin{center}
\begin{tabular}{c||c|c|c|c|c|c|c|c|c|c|}
\hline
type: & INT     & INT & INT & INT & INT & INT & INT & INT & $\cdots$ & INT \\
\hline 
data: & version & $N$ & $e$ & $k$ & $t$ & $w$ & $d_1$ & $d_2$ & $\cdots$ & 
				$d_w$ \\
\hline 
\multicolumn{11}{c}{(a) Private key file format.}
\end{tabular}
\\[0.4cm]
\begin{tabular}{c||c|c|c|c|c|c|c|c|c|c|c|}
\hline
type: & INT     & INT & INT & INT & INT & INT & INT & INT & INT & 
			$\cdots$ & INT \\
\hline
data: & version & $N$ & $e$ & $k$ & $t$ & $g$ & $u$ & $g^{d_1}$ & $g^{d_2}$ & 
			$\cdots$ & $g^{d_u}$ \\
\hline 
\multicolumn{12}{c}{(b) Public shared key file format.}
\end{tabular}
\end{center}
\end{figure*}

Our system manages three types of keys: (1) a standard RSA public key,
(2) a private share stored on each share server, and
(3) a public shared key stored on each client.  The public key stored on the
clients contains the public RSA key plus some additional public information.
We describe each of these keys below.

The SSLeay package~\cite{SSLeay} supports reading and writing both public and
private keys in PEM format.  Our private shares and public shared keys
are represented internally as extensions of the standard RSA key data
structure.  On disk, we support a PEM-encoded ASN.1 format similar to
that used for RSA keys.  \\[-0.7cm]

\begin{description}
\item[Public key] This is a standard RSA public key made up of an
RSA modulus $N$ and a public exponent $e$.  It is managed by the standard
RSA functions provided in SSLeay.  Note that an outsider communicating
with the clients is unaware that the corresponding private key is
stored in shared form.

\item[Private share] The private
share stored on each share server contains the modulus $N$ and a
number of private $d_i$'s.  For a $t$-out-of-$k$ shared key the
private share file format (as ASN.1) is shows in Figure~\ref{keyfile}a.
Each share server is given $w$ shares $d_1, \ldots, d_w$. Note that
the private share file does not contain the optional values $d \bmod p
- 1 ,\; d \bmod q - 1 $, or $q^{-1} \bmod p$, normally used to
optimize RSA computations, where $N = pq$.  After all, none of the
parties can construct these values.

\item[Public shared key]
The format of the public key file stored on each client is shown in
Figure~\ref{keyfile}b (all arithmetic is done modulo $N$).
Here $u$ is the total number of $g^{d_i}$'s stored on the client.  The
values $g$ and $g^{d_i} \bmod N$ are used to detect incorrect (or possibly
compromised) private share operations by the share servers, as discussed
in the next section.  For each share $d_i$ on each share server, there is
a $g^{d_i}$ in the public shared key. For example, in the 3-out-of-4
sharing of the previous section the public shared key contains six entries,
so $u=6$.

\end{description}


\section{Using a shared key} \label{usekey}

We are now ready to describe the interaction that takes place when a
client requests the share servers to apply a private key to a message $M$.
Throughout the interaction the client keeps two bit-vectors {\tt offline}
and {\tt corrupt}, indicating which of the share servers are currently
offline and which have been found to be corrupt.  We assume the client
wishes to use a $t$-out-of-$k$ shared key.

\begin{description}
\item[Init] The client sets {\tt offline} and {\tt corrupt} to zero.
\item[Step 1:] The client picks a {\em random} coalition of $t$ servers
(out of $k$) that are neither offline nor corrupt.
\item[Step 2:] The client sends the following message to each of the
servers in the coalition: \\[0.3cm]
\begin{tabular}{|c|c|c|c}
\hline 
{\sc command} & {\sc sign} {\small or} {\sc decrypt} & M &  \\
\hline
\end{tabular} \\[0.2cm]
\mbox{}\hspace{0.5cm}
\begin{tabular}{c|c|c|c|c|}
\hline 
& {coalition} & {key-ID} & {corrupt} & {offline} \\
\hline
\end{tabular}  \\[0.3cm]
%\begin{center}
%\begin{tabular}{|c|c|c|c|c|c|c|c|}
%\hline 
%{\sc ``command''} & $\begin{array}{c} \mbox{{\sc sign}} \\ \mbox{\small{or}} \\ 
%				\mbox{{\sc decrypt}} \end{array}$ &
%$M$ & {\tt coalition} & {\tt key-ID} & {\tt corrupt} & {\tt offline} \\
%\hline
%\end{tabular}
%\end{center}
where {\tt key-ID} is the ID of the key the servers should apply.
The {\tt key-ID} is simply a 32 bit hash of $N$ and $e$.

\item[Step 3:] Based on the coalition being used, each of the servers 
extract the appropriate $d_i$ from its private key share of {\tt key-ID}.
It then locally computes $S_i = M^{d_i} \bmod N$ and send $S_i$ back
to the client.  Note that if a signature is being requested, the client
first verifies that the message $M$ is in PKCS1 format, and rejects
the request if not.
\item[Step 4:] The client collects all the $S_i$'s and computes
$S = \prod_{i=1}^t S_i \bmod N$.  If some of the servers were found to
be offline, the {\tt offline} bit vector is updated and the process is
restarted at Step~1.
\item[Step 5:] If $S^e = \pm M \bmod N$ the key was applied correctly
and the process terminates.
\item[Step 6:] Otherwise, for each server in the coalition the client
performs a zero-knowledge test to validate the server's response.
The test is described in the next section.  All servers that
sent incorrect values are marked as corrupt and the process is restarted
at Step~1.
\end{description}

If at Step~1 there are less than $t$ servers that are neither corrupt
nor offline the process fails.  Note that the identity of corrupt
share servers is sent to {\em all} share servers.  This enables the
servers to notify the administrator, who can take appropriate action to
refresh the shares stored on the corrupt servers.

\mypar{Load balancing}
When many different clients use the same share servers, the load on the
servers may hurt overall system performance.  Fortunately, our choice
of a random coalition in Step~1 provides for {\em automatic load 
balancing} among the servers.  When a 3-out-of-5 key is used each application
of the key is likely to make use of a different set of three servers.
Furthermore, by using a sufficiently low timeout period clients can
avoid waiting for busy servers by switching to a different coalition.
Due to the load balancing effect, a 3-out-of-5 sharing will result in
a higher throughput than a 3-out-of-4 sharing.


\subsection{Identification of corrupt servers}  \label{corrupt}

It remains to show how we identify corrupt servers in Step~6. This
protocol is only used in the unlikely event one of the servers returns an
incorrect response in Step~3.  Recall that server $i$ sent $S_i =
M^{d_i} \bmod N$ back to the client where $d_i$ is its share of the
private key.  By examining its own public shared key file the client
obtains $V_i = g^{d_i} \bmod N$. To validate sever $i$'s response the
client does the following:
\begin{description}
\item[Step 6.1:] The client picks random $a$ and $b$ in the range $[1,N]$
and computes $Z = M^a g^b \bmod N$.
\item[Step 6.2:] It sends the following to server $i$:  \\[0.3cm]
\begin{tabular}{|c|c|c|c}
\hline 
{\sc command} & {\sc hash-sign} & Z &  \\
\hline
\end{tabular} \\[0.2cm]
\mbox{}\hspace{0.5cm}
\begin{tabular}{c|c|c|c|c|}
\hline 
& {coalition} & {key-ID} & {corrupt} & {offline} \\
\hline
\end{tabular}  \\[0.3cm]
\item[Step 6.3:] A legitimate server will respond with 
$A_i = H( Z^{d_i} \bmod N)$ where $H$ is a cryptographic hash function.
We use SHA-1.
\item[Step 6.4:] The client checks that $A_i = H[S_i^a V_i^b \bmod N]$.
If not, the server is declared to be corrupt.
\end{description}

The above protocol is a simplification of a protocol
from~\cite{FGMY97}.  The following lemma shows that a share server who
sends an invalid $S_i$ will be caught with overwhelming probability.
Furthermore, the protocol reveals no information about the server's
secret shares.  The lemma relies on the Small Order Assumption (SOA):
there is no efficient algorithm that, given an RSA modulus $N=pq$,
outputs an element $x$ in $\Z_N$, where $x \neq \pm 1$, so that the
order of $x$ in $\Z_N$ is less than $N^{1/2}$.

\begin{lemma} \label{zeroknow}
Assuming SOA, a server who in step~2 sends any value other than $\pm
M^{d_i} \bmod N$ will fool the above protocol with probability at most
$1/N^{1/2}$.  Furthermore, assuming the hash function used is a random
function, the protocol is zero-knowledge (i.e. the client can simulate
its interaction with the server).
\end{lemma}

%We give the proof in the full version of the paper. 
For a 1024 bit key, the
probability that a server fools the client is less than $1/2^{512}$
--- negligibly small.  The hash function is used to prevent a
malicious client from obtaining signatures on improperly formatted
messages (i.e.  not in PKCS1 format).  For example, in a CA
environment the {\sc decrypt} command is disabled.  Consequently,
the servers can only be used to generate signatures and they only 
sign properly formatted PKCS1 messages.  In this environment, the
hash function prevents the client from using the validation test to
obtain signatures on arbitrary messages.

We note that when $\gcd(p-1,q-1)=2$ the SOA assumption is equivalent
to assuming the hardness of factoring.  However, since our servers cannot
test this condition (no single server knows $p$ and $q$) we use the SOA
as the intractability assumption in Lemma~\ref{zeroknow}.

% \section{Implementation details}

\input{tjw}



% \section{Performance}

\input{performence}


\comment{
\section{Design choices}

We want to take a server offline without affecting the system.

We use robustness rather than applying all shares.

For robustness we use Moti rather than Tal.

We don't use Tal sharing so as not to reconstruct secrets.
}

\section{Related work}

Fray, Deswarte and Powel~\cite{FDP} and Deswarte, Blain and
Fabre~\cite{DBF} describe an encrypted file system where file keys are
distributed using Shamir secret sharing across several key servers.
Keys are reconstructed every time a file is accessed.  In
contrast, by using threshold RSA, the ITTC system never reconstructs
long term private keys in a single location.

The $\Omega$ system~\cite{Omega}, built at AT\&T, also uses threshold
cryptography to protect private keys.  $\Omega$ supported a
Certification Authority (CA) used at AT\&T.  It was the first system to
demonstrate the practicality of threshold cryptography.  We note that
$\Omega$ does not support distributed key generation, detection of
corrupt servers or the ability to refresh shares in case a share
server is compromised.

The proactive security toolkit~\cite{IBM} built at IBM focuses on
using proactive security applied to DSS to protect private DSS signing
keys.  The system shares a DSS key among a number of servers, and
proactively refreshes these shares once every predetermined time
period (e.g. once a day).  Interestingly, DSS and RSA have different
sharing properties. RSA keys are easy to share (so that a signature
can be generated without reconstructing the key), but are hard to
generate distributively (so that none of the participants know the
private key).  On the other hand, DSS keys are easy to generate
distributively, but are harder to use for threshold signatures.

Our particular implementation of threshold RSA is based on one of several
possible algorithms.  We chose an algorithm for threshold RSA that is
best suited to handle a small number of share servers (i.e. less
than six).  For a larger number of servers one could use a recent
algorithm due to Shoup~\cite{Shoup}.


\section{Conclusions} \label{conc}

The ITTC system enables applications to store their private keys in an
intrusion tolerant fashion.  Penetrating a few share servers reveals
no information about the private key.  Penetrating a client is
detected through our use of sequence numbers and does not expose any
shared keys.  Our system eliminates single points of failure by never
reconstructing a shared private key in a single location.  Even key
generation is done in shared form.  The system detects and corrects
offline and corrupt servers.  For instance, one of the share servers
can be taken offline for maintenance without affecting system
behavior.

ITTC is easy to embed into existing applications.  We built a web server
and a CA in which private keys are managed using ITTC. 
Our performance figures show that the cost of using ITTC is reasonable.
This is especially true in the case of a web server where session key
exchange is only a small fraction of the total work performed by the
server.  Session key exchange is not done too frequently since both
the browser and server cache session keys.

% Breaking into multiple servers is harder than breaking into one due
% to our use of diversity. 

\section*{Acknowledgments}

Research supported by DARPA/ITO.  We thank Bill Aiello and
Sivaramakrishnan Rajagopalan (Raj) for their help throughout the project.

\begin{thebibliography}{}

\bibitem{AGY95} 
N.~Alon, Z.~Galil, M.~Yung, ``Dynamic re-sharing verifiable secret
sharing against a mobile adversary'', in Proceedings of the 1995
European Symposium on Algorithms (ESA), pp. 523--537.

\bibitem{IBM} 
B. Barak, A. Herzberg, D. Naor, E. Shai, ``The proactive security
toolkit and applications'', to appear in the 6th ACM Conference on
Computer and Communications Security, 1999.

\bibitem{BF97}
D. Boneh, M. Franklin, ``Efficient generation of shared RSA keys'',
in Proceedings Crypto' 97, pp. 425--439.

%\bibitem{certco}
%CertCo, {\em Root CertAuthority}, {\tt http://www.certco.com}

\bibitem{DDB94}
Y.~Desmedt, G.~Di~Crescenzo, M.~Burmester, ``Multiplicative non-abelian 
sharing schemes and their application to threshold cryptography'',
Proceedings ASIACRYPT '94, pp. 21--32.

\bibitem{DBF}
Y. Deswarte, L. Blain, J Fabre, ``Intrusion tolerance in distributed
computing systems'', Proceedings IEEE Symposium on Security and
Privacy, Oakland, 1991, pp. 110--121.

\bibitem{F89}
Y. Frankel, ``A practical protocol for large group oriented networks",
Eurocrypt 89, pp. 56--61.

\bibitem{FGMY97}
Y. Frankel, P. Gemmel, P. MacKenzie, M. Yung, ``Optimal-resilience proactive 
public-key cryptosystems'', Proceedings FOCS '97, pp. 384--393.

\bibitem{FDP}
J. Fray, Y. Deswarte, D. Powell, ``Intrusion tolerance using fine-grain
fragmentation-scattering'', Proceedings IEEE Symposium on Security
and Privacy, Oakland, 1986, pp. 194--201.

\bibitem{G97}
P. Gemmel, ``An introduction to threshold cryptography'', in CryptoBytes, 
a technical newsletter of RSA Laboratories, Vol. 2, No. 7, 1997.

\bibitem{MWB98}
M. Malkin, T. Wu, D. Boneh, ``Experimenting with shared RSA key
generation'', Proceedings of the Internet Society's 1999 Symposium on 
Network and Distributed System Security (SNDSS), pp. 43--56

\bibitem{PKCS}
Public Key Cryptography Standards (PKCS), RSA Labs, 
available at {\tt http://www.rsa.com/rsalabs/pubs/PKCS/}

\bibitem{Omega}
M. Reiter, M. Franklin, J. Lacy, R. Wright, ``The $\Omega$ key management
service", Proceedings of the 3rd ACM conference on Computer and
Communication Security, 1996.

\bibitem{Tal}
T. Rabin, ``A simplified approach to threshold and proactive RSA'',
Proceedings of Crypto' 98.

\bibitem{Shamir}
A. Shamir, ``How to share a secret'', Comm. of the ACM, Vol. 22, 1979,
pp. 612--613.

\bibitem{Shoup}
V. Shoup, ``Practical threshold signatures'', to appear.

\bibitem{SSLeay}
E. Young, SSLeay, {\tt http://www.ssleay.org/}

\end{thebibliography}

\appendix

\comment{

\section*{Appendix A: Proof of Lemma~\ref{zeroknow}}  \label{proof}

\noindent {\bf Lemma~\ref{zeroknow}} {\em
A server who in step~2 sends any value other than $\pm M^{d_i} \bmod N$
will pass the above protocol with probability at most $1/N^{1/2}$.
Furthermore, assuming the hash function used is a random function, the
protocol is zero-knowledge (i.e. the client can simulate its interaction
with the server). }

\proofsk

\section*{Appendix B: Generating RSA key shares} \label{keyshare}

Here we explain how to generate additive sharings of RSA keys.

\section*{Appendix C: Example config file}

\input{config}

}

\end{document}



