From 74eb47db34cb72d98808afb40caced375f348f11 Mon Sep 17 00:00:00 2001 Message-Id: <74eb47db34cb72d98808afb40caced375f348f11.1715556687.git.mdw@distorted.org.uk> From: Mark Wooding Date: Fri, 16 Feb 2001 21:43:33 +0000 Subject: [PATCH] Initial versions of documentation. Organization: Straylight/Edgeware From: mdw --- doc/tripe.8 | 252 ++++++++++++++++++++++++++++++++++++++++++++++ doc/wrestlers.tex | 252 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 504 insertions(+) create mode 100644 doc/tripe.8 create mode 100644 doc/wrestlers.tex diff --git a/doc/tripe.8 b/doc/tripe.8 new file mode 100644 index 00000000..4c031500 --- /dev/null +++ b/doc/tripe.8 @@ -0,0 +1,252 @@ +.\" -*-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, diff --git a/doc/wrestlers.tex b/doc/wrestlers.tex new file mode 100644 index 00000000..d71e4306 --- /dev/null +++ b/doc/wrestlers.tex @@ -0,0 +1,252 @@ +%%% -*-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]