%%% -*-LaTeX-*-
%%%
%%% $Id: become.tex,v 1.3 1997/08/07 09:37:44 mdw Exp $
%%%
%%% Documentation for `become'
%%%
%%% (c) 1997 EBI
%%%

%%%----- Licencing notice ---------------------------------------------------
%%% 
%%% This file is part of `become'
%%% 
%%% `Become' is free software; you can redistribute it and/or modify
%%% it under the terms of the GNU General Public License as published by
%%% the Free Software Foundation; either version 2 of the License, or
%%% (at your option) any later version.
%%% 
%%% `Become' is distributed in the hope that it will be useful,
%%% but WITHOUT ANY WARRANTY; without even the implied warranty of
%%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%%% GNU General Public License for more details.
%%% 
%%% You should have received a copy of the GNU General Public License
%%% along with `become'; if not, write to the Free Software
%%% Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

%%%----- Revision history ---------------------------------------------------
%%%
%%% $Log: become.tex,v $
%%% Revision 1.3  1997/08/07 09:37:44  mdw
%%% Updated to reflect new `become' version.  Included description of multiple
%%% server support, netgroup handling, larger random seed file, and so on.
%%%
%%% Revision 1.2  1997/08/04 10:24:20  mdw
%%% Sources placed under CVS control.
%%%
%%% Revision 1.1  1997/07/21  13:47:54  mdw
%%% Initial revision
%%%

%%%----- Document preamble --------------------------------------------------


%% --- Document class and packages ---

\documentclass[a4paper, 10pt]{article}
\usepackage{array, tabularx}
\usepackage[rounded]{syntax}

\newif\ifxypic
% \IfFileExists{xy.sty}{\usepackage[all]{xy}\xypictrue}{\xypicfalse}

\IfFileExists{mdwfonts.sty}{\usepackage{mdwfonts}}{}


%% --- Macros and things ---

\newcommand{\become}{\textsf{become}}
\newcommand{\path}[1]{\texttt{#1}}
\def\<#1>{\synt{#1}}
\newcommand{\xor}{\oplus}
\newcommand{\ror}{\mathbin{>\mskip-6mu>\mskip-6mu>}}


%% --- eqalign, from Plain TeX, LaTeXified ---

\makeatletter
\def\eqalign{%
  \null\,\vcenter\bgroup\openup\jot\m@th%
  \ialign\bgroup%
    \strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil\crcr%
}
\def\endeqalign{
    \crcr%
  \egroup\egroup%
  \,%
}
\makeatother


%% --- Other layout preferences ---

\setlength{\grammarindent}{1in}
\renewcommand{\arraystretch}{1.2}
\addtolength{\textwidth}{0.6in}
\addtolength{\oddsidemargin}{-0.3in}
\sloppy

\begin{document}


%%%----- Introductory matter ------------------------------------------------


%% --- Title and some `brief' acknowledgements ---

\title{The \become\ program}
\author{Mark Wooding\thanks{
    The program contains nontrivial pieces of code owned by the European
    Bioinformatics Institute, Mark Wooding and Straylight (even though I
    actually wrote it all).  Thanks also to the Free Software Foundation for
    Autoconf; to Ron Rivest for the MD5 message digest algorithm; to Xuejia
    Lai and James Massey for the IDEA cipher; and to Bruce Schneier, for
    writing \emph{Applied Cryptography}, which explained why I'd written the
    first version of all this code wrong.} \\
  \texttt{mdw@ebi.ac.uk}}

\maketitle


%% --- Abstract ---

\begin{abstract}
  This document describes a system for allowing users to `become' other users
  in a secure and controlled way under Unix.  The idea is to allow users to
  maintain programs and other resources which require their own accounts
  while removing the need for such accounts to have passwords (which can be
  disclosed, forgotten or otherwise abused in ways that passwords for user
  accounts don't tend to be).

  The \become\ program will look up the user's identity, the identity of the
  user he or she wishes to `become', the name of the program which is to be
  executed, and the identity of the current host, consult a configuration
  file, and decide whether the request is permitted before granting it.  The
  novel idea is that the table doesn't need to be on the local machine --
  \become\ will send a request to a server, asking it for permission,
  allowing the information to be held centrally, and making maintenance more
  convenient.  Cryptographic protocols are used to ensure the authenticity of
  the server's responses.
\end{abstract}


%% --- Contents ---

\tableofcontents


%%%--------------------------------------------------------------------------
\section{User guide}


\subsection{Introduction}

Running \become\ lets you `become' another user.  What this really means is
that it lets you execute a process with the permissions of another user.
Which users you're allowed to `become', and exactly what processes you're
allowed to execute as those users is determined by the people that installed
\become.


\subsection{Invoking \become}

Invoking the \become\ program is impressively simple.  There are essentially
two forms of invocation:
\begin{syntdiag}
  `become' <user-name> \[ <program> \[ \< <argument> \> \] \]
\end{syntdiag}
and
\begin{syntdiag}
  `become' `-c' <shell-command> <user-name>
\end{syntdiag}
The first variant allows you to execute any \<program> as user \<user-name>,
as limited by your site's configuration.  The second variant simply passes
the \<shell-command> to \path{/bin/sh}, so you must have permission to
execute the shell as \<user-name>.  The latter form doesn't actually allow
you to do anything the former doesn't: it is in fact entirely equivalent to
saying `\syntax{"become" <user-name> "/bin/sh -c" <shell-command>}', but
slightly more compact.


%%%--------------------------------------------------------------------------
\section{Installation and configuration}


\subsection{Unpacking and compiling}

Before you begin, there are some prerequisites you should check:
\begin{itemize}
\item You need the Free Software Foundation's gzip program to unpack the
  distribution archive.
\item You need an ANSI-conformant C~compiler and library to correctly compile
  the source code.  No effort at all has been made to support nonstandard
  C~implementations.\footnote{
    The ANSI~C standard was ratified in 1989.  It is now 1997.  If your
    system vendor hasn't bothered to comply with an eight year old standard,
    you ought to firstly complain to your vendor, and secondly install the
    GNU~C compiler.}
\item You'll probably need GNU flex and bison to rebuild the scanner and
  parser.  However, prebuilt C~source for these components is provided, and
  will probably work.
\item A recent version of \LaTeX\ is required for formatting the manual.  For
  those without \LaTeX, a formatted version of the manual is supplied, in
  PostScript form.
\end{itemize}

The \become\ software is distributed as a gzipped tape archive: saying
\begin{verbatim}
    $ gunzip -c become-1.2.tar.gz | tar xvf -
\end{verbatim}
will decompress and unpack the source code into a directory
\path{become-1.2}.

The software must be configured prior to compilation.  The author has used
the Free Software Foundation's Autoconf system which will (with luck)
configure \become\ correctly for the host platform.  The simplest way to do
this is to change into the unpacked source directory and say
\begin{verbatim}
    $ ./configure
\end{verbatim}
If you're compiling for several architectures, you can keep the object files
for each in a separate directory.  To do this, create a directory for each
one, e.g., by saying something like
\begin{verbatim}
    $ mkdir linux solaris
\end{verbatim}
Then make the appropriate directory current, and run the configure script
from the parent directory:
\begin{verbatim}
    $ cd linux
    $ ../configure
\end{verbatim}

Without any arguments, the configure script will attempt to deduce all it
needs to know about your platform, and it will choose default places to
install files.  You can change the configure script's ideas about where to
put the files by passing it command line arguments.  By default, all of
\become's files are placed relative to a \emph{prefix} directory (so binaries
go in \emph{prefix}\path{/bin} and so on).  The prefix directory is usually
\path{/usr/local}, although you can change this by using the
\texttt{--prefix} option, e.g.,
\begin{verbatim}
    $ ./configure --prefix=/usr/local/become-1.1
\end{verbatim}
(This will keep all of \become's files in a subdirectory of
\path{/usr/local}, which you may find makes maintenance easier.)

You can also choose different locations for various types of file.  Most
importantly, \become's configuration files are put into a `system
configuration' directory, which by default is \emph{prefix}\path{/etc}.  You
can change it using the \texttt{--sysconfdir} option, e.g.,
\begin{verbatim}
    $ ./configure --sysconfdir=/etc/become
\end{verbatim}
If you're planning to use \become\ in a centralised installation (see
section~\ref{sec:become.inst-type} on page~\pageref{sec:become.inst-type})
then the system configuration directory \emph{must not} be on a remote
filesystem because cryptographic keys are stored in this directory and
putting them on a remote filesystem will make them visible on the network.

A complete list of options accepted by the configure script may be displayed
by passing the \texttt{--help} option:
\begin{verbatim}
    $ ./configure --help
\end{verbatim}

You can now build the programs by invoking make.

Finally, you can install the various files to their correct directories by
saying
\begin{verbatim}
    $ make install
\end{verbatim}
(again, using GNU make, so maybe it's not called `\texttt{make}' at your
site).

Congratulations: \become\ is now compiled.  The easy part is now done.


\subsection{Different installation types}
\label{sec:become.inst-type}

There are two types of installation for \become, and which one you choose
depends on how you want to maintain the configuration file, which contains
the rules describing who is allowed to become whom:
\begin{itemize}
\item a \emph{standalone} installation, where the configuration is stored
  locally, and
\item a \emph{centralised} installation, where the configuration is stored on
  a central trusted server.
\end{itemize}
The difference is basically how you want to maintain the configuration.  In
the standalone case, you have to ensure that the configuration file is copied
to each participating host each time it gets changed.  In the centralised
case, you only have one copy of the configuration file, and have a different
problem concerning key distribution.


\subsection{The configuration file}

The configuration file for \become is called \path{become.conf}, and it's
stored in the system configuration directory you set up when compiling the
program.  It defines a set of records, each containing four fields:
\begin{itemize}
\item a \emph{from} field, identifying a class of users;
\item a \emph{to} field, identifying a (possibly different) class of users;
\item a \emph{commands} field, describing a class of commands; and
\item a \emph{hosts} field, describing a class of hosts.
\end{itemize}
Such a record permits any user in the \emph{from} class to run a command
contained in the \emph{commands} class as any user in the \emph{to} class, on
any host in the \emph{hosts} class.  If any class fails to match, permission
is denied.

The configuration file can contain comments, which start with a \lit{\#}
character and extend to the end of the line; this is the only time when
newlines are significant in the configuration file.

\subsubsection{Allow records}

A record like the one described above is represented in the configuration
file by an \emph{allow record}.  It has the following syntax:
\begin{grammar}

<allow>         ::= \[[
  `allow'
    \[ `[' <host-class> `]' \]
    <user-class> `->' \[ <user-class> \]
    \[ `:' <command-class> \]
  `;'
\]]

\end{grammar}
The items \<host-class>, \<user-class> and \<command-class> are all
\emph{class expressions}.  If you omit one of the classes, then it will match
all requests.  So saying
\begin{verbatim}
    allow EVILHACKER -> ;
\end{verbatim}
allows anyone in the `EVILHACKER' class to become anyone they like,
everywhere, and do anything.

\subsubsection{Class expressions}

Class expressions allow you to define classes of users, hosts and commands
conveniently.

All class expressions have the same high-level syntax, and it's fairly easy
to understand.  It looks a little bit like set notation: you can obtain the
union of two classes using the \lit{|} character (or), take intersections
using \lit{\&} (and), and subtract classes using \lit{-}.  Finally, you can
list several classes by separating them with commas \lit{,}.  The order of
precedence, from lowest to highest, is \lit{,}, \lit{-}, \lit{|} and
\lit{\&}.\footnote{
  Actually, the \lit{,} and \lit{|} operators do exactly the same thing.  The
  only difference is their relative precedence.  It probably helps if you
  think of them as being conceptually different, though.}
You can override the precedence rules by using parentheses.

The whole syntax looks like this:
\begin{grammar}

<class-expr>    ::= \[[
  \[ \< <class-minus-expr> \\ `,' \> \] <class-minus-expr>
 \]]

<class-minus-expr> ::= \[[
  \[ \< <class-or-expr> \\ `-' \> \] <class-or-expr>
\]]

<class-or-expr> ::= \[[
  \[ \< <class-and-expr> \\ `|' \> \] <class-and-expr>
\]]

<class-and-expr> ::= \[[
  \[ \< <class-primary> \\ `&' \> \] <class-primary>
\]]

<class-primary> ::= \[[
  \( `(' <class-expr> `)' \\ <class-name> \\ <explicit-item> \)
\]]

\end{grammar}

\subsubsection{Naming classes}

To save repetition, you can give names to classes, using one of the three
assignment statements:
\begin{grammar}

<user-assign>   ::= \[[ `user' <name> `=' <user-class> `;' \]]

<host-assign>   ::= \[[ `host' <name> `=' <host-class> `;' \]]

<command-assign> ::= \[[ `command' <name> `=' <command-class> `;' \]]

\end{grammar}

Classes can be defined in terms of themselves: saying
\begin{verbatim}
    user HACKERS = HACKERS | "mdw";
\end{verbatim}
says to add `mdw' to the class of hackers, for example.  The configuration
file is read strictly top-to-bottom, and an allow record already given
doesn't change its meaning just because you later redefine of the classes it
refers to.

\subsubsection{Naming users, hosts and commands}

Right: you now know how to define classes in terms of other classes, but
you've got to start somewhere.  Each type of class has its own way of
identifying members.
\begin{itemize}
\item A user may be identified either by writing the user's name in double
  quotes (e.g, \texttt{"mdw"}) or by giving the integer user id (e.g.,
  \texttt{272}).
\item A host may be specified by giving, in quotes, either the host's
  \emph{fully qualified} name (e.g., \texttt{"excessus.hacker.org"}), or its
  IP~address, (e.g., \texttt{"158.152.170.219"}).  Note that the IP~address
  must be quoted too: this is slightly unusual.  Either form may contain
  wildcards: \lit{?} matches any character, and \lit{*} matches zero or more
  characters.  For example, I can name all hosts at hacker.org by saying
  \texttt{"*.hacker.org"}.  \emergencystretch=10pt
\item A command may be specified by giving its \emph{full pathname} in quotes
  (e.g., \texttt{"/sbin/shutdown"}).  Again, wildcards can be used to specify
  lots of commands at the same time.
\end{itemize}

\subsubsection{Predefined names}

Before reading the configuration file, \become\ predefines a collection of
classes:
\begin{itemize}
\item For every user $u$, a class `$u$' is created containing that user.
\item For every group $g$, a class `$g$' is created containing all members of
  that group.
\item For each netgroup $n$ read from the NIS server, a class `\lit*{u_}$n$'
  is created containing all the users listed in the netgroup, and a class
  `\lit{h_}$n$' containing the IP address of all the hosts listed in the
  netgroup.\footnote{
    Netgroups don't fit in particularly well with \become's way of thinking.
    The netgroup idea tries to bind users and hosts together in tight little
    bundles, which doesn't help here.  The current behaviour of splitting
    the tight little host--user--domain bundles into separate lists of users
    and hosts is, to the author's knowledge, the cleanest way of making
    netgroups useful.

    It should probably be pointed out that, in general, NIS should be
    considered insecure.  Nothing too terrible should happen if you run your
    \become\ server on the NIS master machine.}
\end{itemize}
User and group names can contain characters (e.g., dashes or dots) which
aren't allowed in \become\ class names; \become\ automatically translates
any non-alphanumeric characters into underscores.

Note that by the end of this process, each class contains the \emph{union} of
all the things which are automatically put there.  So if your system has a
`root' group, then the class \lit{root} ends up containing the root user
together with all members of the root group.  You can be sure of referring to
a single user by enclosing the user name in quotes.  Hence
\begin{verbatim}
  allow HACKERS -> rcs;
\end{verbatim}
lets your syshacks become anyone in the rcs group, whereas
\begin{verbatim}
  allow HACKERS -> "rcs";
\end{verbatim}
lets them become the rcs user only.


\subsection{Configuring standalone installations}

That's it, really.  Make sure that \become\ can find the configuration file
on each host.  If \become\ can't find a server to talk to (which it can't
because you haven't configured one) it will parse the local configuration
file and decide for itself whether to grant the user's request.

If you're only interested in setting up a standalone installation, then
you're finished, and can get on with doing something interesting.
Alternatively, read on, and see all the work you don't have to do.  You
should probably note, however, that reading a configuration file for a
reasonable-sized site takes quite a long while, though; doing this in a
central server will make your users happier, as well as being less work for
you.


\subsection{Keys and random numbers}

Because \become\ uses cryptographic methods for communicating with its
server, you must set up some encryption keys for it to use.  You need to set
up two files, both in \become's system configuration directory:
\begin{itemize}
\item The file \path{become.key} contains \become's `master' key.  Someone
  who knows the master key can fake responses from the server, and grant
  themselves any privileges they like.
\item The file \path{become.random} contains a `random number seed' which is
  used (together with the master key) to generate random numbers (e.g.,
  session keys).  Someone who knows the random numbers can fake responses
  from the server, and grant themselves any privileges they like.  It's
  difficult to actually predict random numbers given the random number seed
  file, although it's not a good idea to leave the seed lying around.
\end{itemize}
Both of these files should be stored on a local filesystem, and they should
be readable only by the super-user.

The key contains a 128-bit number; the random number file contains a 512-bit
number.  Both numbers are written in hexadecimal.  To make the thing more
readable, you may insert dashes in the number between each chunk of eight digits.\footnote{
  Actually, you can insert dashes wherever you like in the number, but this
  is only because the parser is rather primitive.  The author recommends that
  you stick with every eight digits.}
Here's an example of a possible key file:
\begin{verbatim}
    4fda99b0-fcbd8bcb-d1bcf951-e1ed04c9
\end{verbatim}

You should generate 128 genuinely random bits for the key file.  It is
\emph{not} good enough to use a computer random number generator.  A program
will be supplied later which will examine key timings as a source for random
numbers.  Also, don't use the number printed above.  That would be really
silly.  To help you do this, a program `keygen' is provided.  It uses timings
of keypresses to generate random numbers.  To use the program to generate
the key file, type
\begin{verbatim}
    $ keygen -o become.key
\end{verbatim}
Keygen will report the number of bits which still need to be generated.  Keep
typing until it says `done'.  The program automatically ensures that its
output file, if it doesn't already exist, is readable only by its owner.  The
command line arguments to keygen are simple:
\begin{syntdiag}
`keygen' \< \[ `--bits' <number> \\ `--output' <file-name> \] \>
\end{syntdiag}
If you don't specify a \<number> of bits, a default of 128 random bits are
generated, which is correct for IDEA keys.  If you omit the \<file-name>, the
random key is written to standard output.

The random number file can be generated by saying
\begin{verbatim}
  keygen -o become.random -b 512
\end{verbatim}
However, \become\ will generate a random number file if it can't find one.
Note that its randomness acquisition isn't completely wonderful yet; the
author recommends that you \emph{do} generate a seed file.


\subsection{Setting up the server and clients}

As of version 1.2, the \become\ client is capable of sending its request to
multiple servers, which makes it more resilient to server failures.

You don't need a separate program to run as a \become\ server: the normal
\become\ is quite capable of behaving as a server all by itself.  However,
before you start the server up, you need to decide on a port to which it will
listen.  The author uses port 9876 for testing purposes, and there's not much
reason why you couldn't do the same.

There are three ways you can inform \become\ of your choice of port:
\begin{itemize}
\item You can pass the port number on the command line, using the
  \texttt{--port} option.
\item You can add a line saying `\syntax{"port" <number> ";"}' to the
  configuration file.
\item You can add an entry to your \path{/etc/services} file (or NIS map),
  binding your chosen port number to the name `become'.\footnote{
    Actually, \become\ searches for the port using the filename with which
    it was invoked, so if you call the \become\ binary \path{splat}, then
    \become will look for a service labelled `splat'.}
\end{itemize}
If \become\ still has no idea which port to use, it refuses to start up as a
server and reports an error message to you.

You can also choose a different key file to use, by writing a line of the
form `\syntax{"key" <filename> ";"}' in \path{become.conf}.  The client won't
listen to this -- only the server does that.

To make \become\ run as a server, say
\begin{verbatim}
    $ become --daemon
\end{verbatim}
(or to use an explicit port number, say something like
\begin{verbatim}
    $ become --daemon --port=9876
\end{verbatim}
replacing \texttt{9876} in the example with your chosen port).  You can also
run the daemon with a different configuration file, by using the
\texttt{--config-file} option, e.g.,
\begin{verbatim}
    $ become --daemon --config-file=/etc/become/server.conf
\end{verbatim}

Now to configure the clients.  All they need is a file saying where to find
the server or servers.  This has the syntax:
\begin{syntdiag}
  \< <host-name> \[ `:' <port> \] \>
\end{syntdiag}
The \<port> can be either a number (which is used directly) or a service
name, which is looked up in the system's services database (typically
\texttt{/etc/services}).  If you omit the port number, then \become\ looks in
the services database for a service with the name used to invoke it.  This
usage isn't recommended, however.\footnote{
  It's not actually a security risk, because even though a user could
  potentially make the client send its request to a different server, the
  server would only be able to build a valid reply if it knew the correct
  key.}

The server wakes up every half an hour to rescan its configuration and
encryption key.  Thus, it should react fairly quickly to changes to the user
database or to its configuration.  However, you can always force the server
to refetch its configuration files by sending it a SIGHUP signal.  To help
you do this, the server stores its process id in a file \path{become.pid}
within its system configuration directory.


\subsection{Maintaining \become}

There's not much to it really, apart from updating the configuration file
when your requirements change.

The only other thing you really ought to do is to periodically change the
master key.  This should be done about once a week, I'd suspect.  The
difficult part is distributing the keys over the network: you don't really
want to trust the old keys.  I'd recommend that you investigate `ssh' for key
distribution.


\subsection{Summary of \become\ configuration}

\subsubsection{Table of the configuration files}

\begin{tabularx}{\textwidth}{@{} >{\ttfamily}l X @{}}
  \multicolumn{1}{@{}l}{\textbf{File name}} &
  \multicolumn{1}{l@{}}{\textbf{Contents}} \\
  become.conf	& Main configuration file.  See the syntax below for the
		  complete reference \\
  become.key	& Master encryption key.  Should contain a 128-bit random
		  number. \\
  become.pid	& Server's process id (so that you can kill it).  The server
		  creates this file all by itself. \\
  become.random & Random number seed for generating session keys.  Should
		  also contain a 128-bit random number.  Don't be surprised
		  if the number keeps changing -- it's meant to. \\
  become.server	& Tells the \become\ client where to find the server. \\
\end{tabularx}

\subsubsection{Definitive syntax for \path{become.conf}}

The syntax for \path{become.conf} files is shown below.  This mainly reprises
the syntax shown earlier, but in a different order, and without all the
explanatory text getting in the way.

Firstly, the lexical grammar is as follows:

\begin{grammar}

<comment>	::= \[[
  `#' \< \tok{any character other than <new-line>} \> <new-line>
\]]

<name>		::= \[[
  \tok{letter or `_'} \< \( \tok{letter or `_'} \\ \tok{digit} \) \>
\]]

<integer>	::= \[[ \< \tok{digit} \> \]]

<string>	::= \[[
  `"' \< \( \tok{any character other than `"', <new-line> or `\\'} \\
            `\\' \tok{any character other than <new-line>} \) \> `"'
\]]

\end{grammar}

All \<comment>s and whitespace are ignored entirely.  What's left is parsed
as follows:

\begin{grammar}

<become-conf>	::= \[[ \< <statement> \> \]]

<statement>	::= \[[
  \( \( `user' \\ `command' \\ `host' \) <name> `=' <class-expr> `;' \\
     `allow' <allow-spec> `;' \\
     `port' <integer> `;' \\
     `key' <string> `;' \)
\]]

<allow-spec>	::= \[[
   \[ `[' <host-class> `]' \]
  <user-class> `->' \[ <user-class> \]
  \[ `:' <command-class> \]
\]]

<class-expr>    ::= \[[
  \[ \< <class-minus-expr> \\ `,' \> \] <class-minus-expr>
 \]]

<class-minus-expr> ::= \[[
  \[ \< <class-or-expr> \\ `-' \> \] <class-or-expr>
\]]

<class-or-expr> ::= \[[
  \[ \< <class-and-expr> \\ `|' \> \] <class-and-expr>
\]]

<class-and-expr> ::= \[[
  \[ \< <class-primary> \\ `&' \> \] <class-primary>
\]]

<class-primary> ::= \[[
  \( `(' <class-expr> `)' \\ <name> \\ <integer> \\ <string> \)
\]]

\end{grammar}


%%%--------------------------------------------------------------------------
\section{Cryptographic trivia}


\subsection{Design requirements}

The way the system works is that the \become\ client program builds a
\emph{request block} containing all the information needed to decide whether
the user's request is valid.  It then sends this to a server, asking it
whether this request should be granted.  If the server replies `yes', then
\become\ changes its uid, and runs the user's program.

The really important point is that the client must be able to trust the
responses it gets from the server: the final decision over whether to grant
the request lies only with the client.  The server doesn't really need to
worry too much about whether it trusts a request -- it's not going to do
anything with them anyway except send a reply back.


\subsection{Notation}

Some slightly weird mathematical notation is used in the following sections.
\begin{description}
\item [$a \xor b$] denotes the exclusive-or (XOR) operation (bitwise addition
  mod 2).
\item [$(a, b, c)$] denotes concatenation of the quantities $a$, $b$ and $c$.
\item [$a[x : y]$] denotes bits $x$ up to $y$ of $a$, including bit~$x$ but
  \emph{not} bit~$y$.  For example, $a[32:64]$ is a 32-bit quantity.  The
  bits are labelled starting from the left at zero, and increasing to the
  right.
\item [$E_{k, IV}(a)$] denotes encryption of $a$, using the key $k$ and
  initialisation vector $IV$.
\item [$D_{k, IV}(a)$] denotes decryption of $a$, using the key $k$ and
  initialisation vector $IV$.
\end{description}
Encryption is performed using the IDEA algorithm, in 64-bit ciphertext
feedback mode.


\subsection{The actual protocol}

The protocol \become\ uses to communicate with the server is as follows:
\begin{enumerate}

\item The client and server share a secret key~$k$.

\item The client calculates the following:
  \begin{description}
  \item [$F$] is the `from' user id;
  \item [$T$] is the `to' user id;
  \item [$C$] is the command the user wishes to execute;
  \item [$t$] is the current time, as returned from \texttt{time}(2); and
  \item [$p$] is the client's process id.
  \end{description}
  The fields $t$ and~$p$ are to ensure that the client doesn't get confused
  by replies to the wrong requests.

\item The client generates a session key~$s$ and initialisation vector~$IV$.
  It then calculates a checksum
  \[ X = MD5(F, T, C, t, p)[0:32] \]
  and sends the server a message
  \[ \bigl(IV, E_{k, IV}(s), E_{s, IV'}(F, T, C, t, p, X)\bigr) \]
  where $IV'$ is $E_{k, IV}(s)[64:128]$ (i.e., the last block of ciphertext
  after encrypting the session key, so the whole message is encrypted as one
  ciphertext feedback job, with a key change part-way).

\item The server decrypts the message, and checks it to make sure it's valid:
  \begin{itemize}
  \item It checks that $X$ is the correct checksum.
  \item It ensures that the difference between $t$ and the true time is
    acceptable.  (The current implementation allows $t$ to be 15 seconds
    out.)
  \end{itemize}
  If either of these checks fails, the request is rejected without
  acknowledgement.

\item The server decides whether to grant the request.  If it gives its
  permission, it sets $a = 1$; otherwise it sets $a = 0$.  It calculates a
  checksum
  \[ Y = MD5(t, p, a)[0:32] \]
  and sends the client a message
  \[ \bigl(IV'', E_{s, IV''}(t, p, a, Y)\bigr) \]
  where $IV''$ is the last 64~bits of ciphertext received from the client,
  continuing the ciphertext feedback again.  (Later versions of \become\
  might use a different method for deciding on the initialisation vector.)

\item The client decrypts the reply, and verifies it:
  \begin{itemize}
  \item It checks that $Y$ is a valid checksum.
  \item It checks that the $t$ and $p$ values received match the ones in the
    original request.
  \end{itemize}
  If either fail to match, the reply is discarded, and the client continues
  to wait for a valid reply (possibly timing out).

\item The client accepts the reply.  If $a = 1$ it changes uid and executes
  the named process~$C$.

\end{enumerate}

The encryption makes it hard for an attacker to alter the data being
transmitted in any meaningful way; the 32-bit checksum means that an altered
message has a $2^{-32}$ probability of not being noticed.

The use of ciphertext feedback mode attempts to prevent chosen-plaintext
attacks, even though the user can make the client send arbitrary messages.


\subsection{The `keygen' program}

The `keygen' program attempts to take advantage of the variations in time
between your keystrokes to generate random numbers.  It's not perfect.  It
may help a little if you know exactly how it works.

Keygen keeps track of the interval between keypresses.  It exclusive-ors
adjacent interval times together, and strips off leading and trailing
sequences of one- or zero-bits.  What's left is shifted into the accumulator.
The aim of all this complexity is to measure the variation in key timings,
and then discard any uninteresting bits from the result.

This method works best on machines with very high-resolution clocks
(preferably with microsecond granularity), although even on the author's
Linux machine, which uses a clock with centisecond granularity, the number of
keystrokes required is acceptable.


\subsection{How to break \become's security}

The author can't see any obvious weaknesses in the protocol used.  Here are
some possibilities which might occur to an attacker, though:
\begin{itemize}

\item Forge a server reply packet and send it to the client.  Intercept the
  request packet and discard it before it reaches the real server.  The
  required contents of the reply packet can be guessed.  However, encrypting
  it requires knowledge of the session key sent by the client.  Obtaining
  this means you need to break the IDEA cipher, which (to the author's
  knowledge) isn't practical.

\item Send another packet to the server at the same time, altering the sender
  address so that the server replies to the wrong host or port.  This won't
  work, because the client will attempt to decrypt the fake reply with the
  wrong session key and will reject the packet when it finds that the
  checksum is incorrect.

\item Find some other back door into the client host, to become root.  Read
  the secret key file, and use that to decrypt requests and send back
  replies.  If you can already become the super-user, why bother cracking
  \become?

\item Feed the client program bad input to overflow a fixed-size buffer.  The
  bad input contains executable code which gives the attacker a privileged
  shell.  The author isn't aware of any buffers which might overflow as a
  result of user-supplied data, and has checked the source rather carefully.

\end{itemize}

The above assumes that \become\ has been set up correctly.  The following
attacks rely on misconfiguration:
\begin{itemize}

\item Watch new secret keys being transmitted over the network when the
  administrator replaces them.  Now you can decrypt request packets and send
  back replies.  Make sure that the original server's responses are
  corrupted so that the client rejects them.

\item Watch the client or server reading the secret key from a remote
  filesystem.

\item Clobber the configuration file when the server re-reads it from a
  remote filesystem, so that it gives your user account permission to become
  anyone.

\end{itemize}


%%%----- That's all, folks --------------------------------------------------

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
