--- /dev/null
+.\" -*-nroff-*-
+.\".
+.de hP
+.IP
+\h'-\w'\fB\\$1\ \fP'u'\fB\\$1\ \fP\c
+..
+.de VS
+.sp 1
+.RS
+.nf
+.ft B
+..
+.de VE
+.ft R
+.fi
+.RE
+.sp 1
+..
+.ie t \{\
+. ds o \(bu
+. ds ss \s8\u
+. ds se \d\s0
+. if \n(.g \{\
+. fam P
+. \}
+.\}
+.el \{\
+. ds o o
+. ds ss ^
+. ds se _
+.\}
+.TH tripe 8 "10 February 2001" "Straylight/Edgeware" "TrIPE: Trivial IP Encryption"
+.SH "NAME"
+tripe \- a simple VPN daemon
+.SH "SYNOPSIS"
+.B tripe
+.RB [ \-D ]
+.RB [ \-p
+.IR port ]
+.RB [ \-T
+.IR trace-opts ]
+.RB [ \-d
+.IR dir ]
+.RB [ \-a
+.IR socket ]
+.br
+
+.RB [ \-k
+.IR priv-keyring ]
+.RB [ \-K
+.IR pub-keyring ]
+.RB [ \-t
+.IR key-tag ]
+.SH "DESCRIPTION"
+The
+.B tripe
+program is a server which can provide strong IP-level encryption and
+authentication between two co-operating hosts. The program and its
+protocol are deliberately very simple, to make analysing them easy and
+to help build trust rapidly in the system.
+.SS "Overview"
+The
+.B tripe
+server manages a number of secure connections to other `peer' hosts.
+Each daemon is given a private key of its own, and a file of public keys
+for the peers with which it is meant to communicate. It is responsible
+for negotiating sets of symmetric keys with its peers, and for
+encrypting, encapsulating and sending IP packets to its peers, and
+decrypting, checking and de-encapsulating packets it receives from
+them.
+.PP
+When the server starts, it creates a Unix-domain socket on which it
+listens for administration commands. It also logs warnings and
+diagnostic information to the programs connected to its admin socket.
+Clients connected to the socket can add new peers, and remove or find
+out about existing peers. The textual protocol used to give the
+.B tripe
+server admin commands is described in
+.BR tripe\-admin (5).
+A client program
+.BR tripectl (1)
+is provided to allow commands to be sent to the server either
+interactively or by simple scripts.
+.SS "Command-line arguments"
+If not given any command-line arguments,
+.B tripe
+will initialize by following these steps:
+.hP \*o
+It changes directory to
+.BR /var/lib/tripe .
+.hP \*o
+It acquires a UDP socket with an arbitrary kernel-selected port number.
+It will use this socket to send and receive all communications with its
+peer servers. The port chosen may be discovered by means of the
+.B PORT
+admin command (see
+.BR tripe\-admin (5)).
+.hP \*o
+It loads the private key with the tag or type name
+.B tripe\-dh
+from the Catacomb-format file
+.BR keyring ,
+and loads the file
+.B keyring.pub
+ready for extracting the public keys of peers as they're introduced.
+(The format of these files is described in
+.BR keyring (5).
+They are maintained using the program
+.BR key (1)
+provided with the Catacomb distribution.)
+.hP \*o
+It creates and listens to the Unix-domain socket
+.BR tripesock .
+.PP
+Following this, the server enters its main loop, accepting admin
+connections and obeying any administrative commands, and communicating
+with peers. It also treats its standard input and standard output
+streams as an admin connection, reading commands from standard input and
+writing responses and diagnostics messages to standard output.
+.PP
+Much of this behaviour may be altered by giving
+.B tripe
+suitable command-line options:
+.TP
+.B "\-h, \-\-help"
+Writes a brief description of the command-line options available to
+standard output and exits with status 0.
+.TP
+.B "\-v, \-\-version"
+Writes
+.BR tripe 's
+version number to standard output and exits with status 0.
+.TP
+.B "\-u, \-\-usage"
+Writes a brief usage summary to standard output and exits with status 0.
+.TP
+.B "\-D, \-\-daemon"
+Dissociates from its terminal and starts running in the background after
+completing the initialization procedure described above. If running as
+a daemon,
+.B tripe
+will not read commands from standard input or write diagnostics to
+standard output. A better way to start
+.B tripe
+in the background is with
+.BR tripectl (1).
+.TP
+.BI "\-d, \-\-directory=" dir
+Makes
+.I dir
+the current directory, instead of
+.BR /var/lib/tripe .
+Give a current directory of
+.B .
+if you don't want it to change directory at all.
+.TP
+.BI "\-p, \-\-port=" port
+Use the specified UDP port for all communications with peers, rather
+than an arbitarary kernel-assigned port.
+.TP
+.BI "\-k, \-\-priv\-keyring=" file
+Reads the private key from
+.I file
+rather than the default
+.BR keyring .
+.TP
+.BI "\-K, \-\-pub\-keyring=" file
+Reads public keys from
+.I file
+rather than the default
+.BR keyring.pub .
+This can be the same as the private keyring, but that's not recommended.
+.TP
+.BI "\-t, \-\-tag=" tag
+Uses the private key whose tag or type is
+.I tag
+rather than the default
+.BR tripe\-dh .
+.TP
+.BI "\-a, \-\-admin\-socket=" socket
+Accept admin connections to a Unix-domain socket named
+.I socket
+rather than the default
+.BR tripesock .
+.TP
+.BI "\-T, \-\-trace=" trace-opts
+Allows the enabling or disabling of various internal diagnostics. See
+below for the list of options.
+.SS "Key management"
+The TrIPE protocol requires all cooperating hosts to be using keys
+with the same group parameters. A suitable group may be created with the
+command:
+.VS
+key add \-adh\-param \-LS \-b2048 \-B256 \e
+ \-eforever \-tparam tripe\-dh\-param
+.VE
+This creates a `parameters' key labelled
+.B param
+in your keyring file: it doesn't contain any secrets. You may vary the
+security parameters
+.B \-b
+and
+.B \-B
+to taste: the ones given provide good security, at the expense of
+performance. Even so, from a cryptographic point of view, these keys
+will be the weak point in the security of the system. Generation of the
+group parameters can take a few minutes.
+.PP
+You should extract the parameters from your keyring and distribute them
+(securely) to the other administrators. The parameters may be extracted
+from your keyring with the command:
+.VS
+key extract param param
+.VE
+This may be merged into a keyring with:
+.VS
+key merge param
+.VE
+Once your keyring contains the parameters, a suitable key can be created
+with the command:
+.VS
+key add \-adh \-pparam \-e"now + 1 year" tripe\-dh
+.VE
+This creates a Diffie-Hellman key using the parameters from key
+.B param
+which expires in one year. The new key has type
+.BR tripe\-dh .
+
+.SS "About the name"
+The program's name is
+.BR tripe ,
+all in lower-case. The name of the protocol it uses is `TrIPE', with
+four capital letters and one lower-case. The name stands for `Trivial
+IP Encryption'.
+.SH "BUGS"
+It's too easy to deny service during key exchange. If both ends are
+honest, they'll notice any interference and resend their packets, but
+it's possible to delay successful negotation for as long as desired by
+sending bogus key exchange messages.
+.PP
+The code hasn't been audited. It may contain security bugs. If you
+find one, please inform the author
+.IR immediately .
+.SH "SEE ALSO"
+.BR key (1),
+.BR tripectl (1),
+.BR tripe\-admin (5).
+.PP
+.IR "The Trivial IP Encryption Protocol" ,
+.IR "The Wrestlers Protocol" .
+.SH "AUTHOR"
+Mark Wooding, <mdw@nsict.org>
--- /dev/null
+%%% -*-latex-*-
+%%%
+%%% $Id: wrestlers.tex,v 1.1 2001/02/16 21:43:33 mdw Exp $
+%%%
+%%% Description of the Wrestlers Protocol
+%%%
+%%% (c) 2001 Mark Wooding
+%%%
+
+%%%----- Revision history ---------------------------------------------------
+%%%
+%%% $Log: wrestlers.tex,v $
+%%% Revision 1.1 2001/02/16 21:43:33 mdw
+%%% Initial versions of documentation.
+%%%
+
+\documentclass{article}
+\usepackage{amssymb}
+\title{The Wrestlers Protocol}
+\author{Mark Wooding \\ Clive Jones}
+\def\from{\leftarrow}
+
+\begin{document}
+
+\maketitle
+
+\begin{abstract}
+ We present a simple key-exchange protocol with of mutual authentication and
+ perfect forward-secrecy, which doesn't leave any long-lasting evidence of
+ participation in the exchange. The protocol's security depends on the
+ intractability of the Diffie-Hellman problem (in some cyclic group), and on
+ the strength of a hash function.
+\end{abstract}
+
+\section{Introduction}
+
+Current key-agreement protocols are all very well for securing generally
+`honest' traffic (e.g., transmission of credit-card details to a merchant),
+but they're less satisfactory if you actually have something to hide.
+
+In the UK, new key exchange protocols have been particularly motivated by the
+new Regulation of Investigatory Powers Act, which allows `authorized persons'
+to intercept communications and demand long-term encryption keys.
+
+Let's suppose that Alice and Bob are shady characters, and that their
+communications are of great interest to the draconian r\'egime in which they
+live. (They might be international arms smugglers, for example, because they
+export cryptographic toolkits.)
+
+Alice could just invent a session key and transmit it to Bob, encrypted under
+his public key, each time she wanted to talk to him. However, once the
+secret police turn up at Bob's house and demand his private key, the game is
+over and all of the communications can be recovered.
+
+Alice and Bob would clearly be better off using a system which offers forward
+secrecy, for example, Diffie-Hellman. However, in order to prevent active
+attacks, the messages in the Diffie-Hellman exchange must be authenticated.
+The way this usually works is that Alice and Bob pick a group $G$ of order
+$q$ generated by $g$. When Alice and Bob want to communicate, they choose
+exponents $\alpha$ and $\beta$ respectively ($1 < \alpha, \beta < q$), Alice
+sends $S_A(g^\alpha)$ to Bob, Bob sends $S_B(g^\beta)$ to Alice, and, after
+verifying each other's signatures, they each compute a shared key $K =
+g^{\alpha \beta}$. They dispose of their secrets $\alpha$ and $\beta$
+forthwith, and destroy $K$ when the conversation finishes. Now the secret
+police can demand all they like: they still can't decrypt old sessions, and
+Alice and Bob, however badly tortured, can't help them. The secret police
+might not even be all owed to demand their long-term signing keys: for
+example, the RIPA grants special protection to authentication-only keys.
+
+This is fine, except that sending $S_A(g^\alpha)$ is a wonderful way of
+shouting `Alice was here' to all of the spooks tapping Bob's network
+connection. The Wrestlers Protocol\footnote{%
+ Named after the excellent pub in Cambridge where most of the design was
+ done.}
+fixes these problems. It provides perfect forward secrecy, just like
+Diffie-Hellman, without leaving signatures around for the spooks.
+
+
+\section{A simple authentication protocol}
+
+As a building-block, we construct a simple authentication protocol based on
+Diffie-Hellman key exchange. As before, let's use a group $G$ of order $q$
+(for some prime $q$), generated by a group element $g$.
+
+A Diffie-Hellman key exchange allows two parties to compute the same value,
+with different knowledge. We'll use this to make an authentication protocol.
+
+Alice chooses a private key $1 < a < q$. Her public key is $A = g^a$. She
+can prove her knowledge of $a$ to Bob like this:
+\begin{enumerate}
+\item Bob makes up a random $1 < \beta < q$. He sends a challenge $C =
+ g^\beta$ to Alice.
+\item Alice computes the response $R = C^a = g^{a \beta}$. This would
+ be the shared key if we were doing proper Diffie-Hellman, but we aren't.
+ Instead, she just sends $R$ back to Bob.
+\item Bob checks that $R = A^\beta$. If it is, he accepts that the person
+ he's talking to has Alice's private key, and hence is presumably Alice.
+\end{enumerate}
+
+This protocol has nice properties. It's not terribly difficult to implement,
+given the usual tools like modular exponentiation or elliptic curve
+point-addition.
+
+An eavesdropper -- let's call her Eve, for tradition's sake -- doesn't learn
+anything terribly interesting from watching the exchange. She sees $C$ going
+one way and then $C^a$ coming back. If she finds this illuminating, she can
+program her computer to generate random numbers $\gamma$ and show her pairs
+$C = g^\gamma$ and $R = A^\gamma = C^a$. So Eve learns nothing useful she
+couldn't have worked out for herself. In fact, she doesn't even learn that
+Alice is involved in the conversation! Bob can fake up an authentication
+with Alice by secretly agreeing which value of $\beta$ he's going to use with
+an accomplice.
+
+Bob's in a better position than Eve. If he computes his challenges honestly
+then he doesn't learn much except that he's talking to Alice, because as
+we've seen, she only tells him $R$, which he knew already. However, if Bob
+carefully chooses a challenge $C$ without knowing its discrete log $\beta$,
+then Alice's response might tell him useful information about her private
+key that he couldn't have worked out just by sitting at home computing
+discrete logs.
+
+We can fix this little problem easily enough if we make Bob transmit a hash
+of his expected answer. Let $H \colon \mathbb{Z} \to \{\,0, 1\,\}^n$ be a
+hash function. The property we require from $H$ is that Bob can't compute
+$H(g^{a \beta})$ given only $C = g^\beta$ and $A = g^a$ with more than
+negligible probability; a random function would fit the bill fine. This
+does, of course, also assume that the Diffie-Hellman problem is difficult.
+The new protocol looks very much like the old one:
+\begin{enumerate}
+\item Bob chooses a random $1 < \beta < q$. He computes $C = g^\beta$ and $R
+ = A^\beta$, and sends $C, H(R)$ to Alice.
+\item Alice computes $R' = C^a$ and checks that it matches the hash which Bob
+ sent. If it doesn't, he's trying to cheat, and she should refuse to
+ answer. Otherwise, she sends her response $R'$ back to Bob.
+\item Bob checks that Alice's reply matches the one he computed back in step
+ 1. If it does, he knows that he's talking to Alice.
+\end{enumerate}
+
+
+\section{The Wrestlers Protocol}
+
+We observe a useful side-effect of the authentication protocol just
+described: Bob should be convinved that Alice received his challenge $C$
+correctly. The idea of the Wrestlers Protocol is to use this to construct a
+full Diffie-Hellman key exchange with mutual authentication. We maintain the
+useful properties of the previous protocol.
+
+Before they can use the protocol, Alice and Bob must agree on a group $G$ as
+before. Alice chooses a private key $1 < a < q$, and publishes her public
+key $A = g^a$; Bob similarly chooses a private key $1 < b < q$ and publishes
+his public key $B = g^b$.
+
+Here's the actual protocol in summary:
+\begin{enumerate}
+\item $A \to B$:\quad $g^\alpha$
+\item $A \from B$:\quad $g^\beta$, $H(g^\alpha, g^\beta, g^{a \beta})$
+\item $A \to B$:\quad $g^{a \beta}$, $H(g^\beta, g^\alpha, g^{\alpha b})$
+\item $A \from B$:\quad $g^{\alpha b}$
+\end{enumerate}
+
+And now in detail:
+\begin{enumerate}
+
+\item Alice invents a temporary secret $1 < \alpha < q$. She computes her
+ challenge $C_A = g^\alpha$, and sends it to Bob.
+
+\item Bob receives the $C_A$, and stores it away. He invents a temporary
+ secret $1 < \beta < q$ of his own, and computes both his challenge $C_B =
+ g^\beta$ and the expected response $R_B = A^\beta = g^{a \beta}$. He
+ hashes both challenges (hers first) and the expected response $R_B$, and
+ sends his challenge and the hash back to Alice.
+
+\item Alice reads Bob's challenge. She computes her response $R_B' = C_B^a =
+ g^{a \beta}$ and ensures that the Bob's hash is correct. If it isn't, she
+ stops talking to Bob. If the hash matches, she sends back her response,
+ together with a hash of Bob's challenge, her original challenge from step
+ 1, and her expected response $R_A = B^\alpha = g^{\alpha b}$.
+
+\item Bob reads Alice's response. If it's wrong then he stops talking.
+ Otherwise he computes his response to Alice's challenge $R_A' = C_A^b =
+ g^{\alpha b}$ and checks Alice's hash. If the hash is wrong, he also stops
+ talking. Otherwise he sends the response back to Alice.
+
+\end{enumerate}
+Finally, Alice checks Bob's response, stopping the conversation if it's
+wrong. Then both sides compute their shared key $K = C_A^\beta = C_B^\alpha
+= g^{\alpha \beta}$, and discard their temporary secrets.
+
+The protocol is essentially symmetrical: each side sends and receives both a
+challenge and hash pair, and a response, but it doesn't look that simple
+because the hashes include both sides' challenges. Looking at it from one
+side at a time will make things clearer, so let's just take Alice's point of
+view.
+
+Alice constructs her challenge in step 1, and sends it off. She receives a
+challenge and hash in step 2. When she computes the response to the
+challenge, she verifies the hash she received. If it matches, she knows that
+\begin{itemize}
+\item whoever she's talking to hasn't attempted to cheat her by sending a
+ challenge for which he doesn't know the answer; and
+\item he has successfully received her challenge.
+\end{itemize}
+Because she's now received a challenge, she can work out her hash. She sends
+off her response to the challenge, together with the hash, and awaits the
+response.
+
+In step 4, the response arrives. If it's correct, she knows that it's from
+Bob, and that he (Bob) received her challenge OK. Tying everything else
+together is the tricky bit.
+
+If we assume that Bob is playing by the rules, the fact that he's sent his
+response means that he verified it against Alice's hash and decided that
+\begin{itemize}
+\item Alice wasn't trying to cheat him and find out about his private key;
+ and
+\item Alice correctly received his challenge.
+\end{itemize}
+Because Bob wouldn't have replied if these weren't true, Alice can therefore
+believe that she has received Bob's challenge correctly.
+
+To summarize: Alice has managed to get a challenge to Bob, and he responded;
+Alice has also received Bob's challenge correctly.
+
+What if Bob isn't honest? The only hole in the protocol which can be
+exploited by Bob is that he can send a response \emph{even though} it doesn't
+match Alice's hash. This means that the protocol will continue even if Alice
+is attempting to cheat Bob and find information about his private key: this
+is a penalty Bob has to pay for not following the rules. The protocol still
+aborts if an adversary interferes with the challenges: if Alice isn't given
+Bob's challenge accurately, her response will be wrong, and Bob can abort the
+exchange; similarly, if Bob isn't given Alice's challenge, she will detect
+this and abort the exchange.
+
+
+\section{Conclusions and further work}
+
+We have presented a new key exchange protocol based upon a novel use of
+Diffie-Hellman key exchange as a means of authentication.
+
+The arguments given in the previous section sound fairly convincing, but they
+don't provide a formal proof of the security of the Wrestlers Protocol. The
+authors are unaware of a logic system for verifying protocols which correctly
+capture the properties of hash functions.
+
+%%%----- That's all, folks --------------------------------------------------
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: "wrestlers"
+%%% End:
~mdw / tripe / commitdiff