Rearrange the file tree.

[u/mdw/catacomb] / papers / rand.tex

%%% -*-latex-*-
%%%
%%% Description of Catacomb's random number generator
%%%
%%% (c) 1999 Straylight/Edgeware
%%%

%%%----- Licensing notice ---------------------------------------------------
%%%
%%% This file is part of Catacomb.
%%%
%%% Catacomb is free software; you can redistribute it and/or modify
%%% it under the terms of the GNU Library General Public License as
%%% published by the Free Software Foundation; either version 2 of the
%%% License, or (at your option) any later version.
%%%
%%% Catacomb 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 Library General Public License for more details.
%%%
%%% You should have received a copy of the GNU Library General Public
%%% License along with Catacomb; if not, write to the Free
%%% Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
%%% MA 02111-1307, USA.

%%%----- Header -------------------------------------------------------------

\documentclass[a4paper, article, 10pt, notitlepage, numbering]{strayman}
\usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
\usepackage{mdwtab, mathenv}
\usepackage[T1]{fontenc}
\usepackage{cmtt, url}
\usepackage[tpic, all]{xy}
\usepackage{mathbbol}
% \usepackage{crypto}

\def\mdw{{\normalfont[{\bfseries\itshape mdw}]}}
\urlstyle{tt}
\def\email{\begingroup\urlstyle{rm}\Url}
\urldef\myemail\email{mdw@nsict.org}
\def\Z{\mathbb{Z}}
\let\assign\leftarrow
\let\xor\oplus
\let\bigxor\bigoplus
\def\cat{\mathbin{\|}}

\title{The Catacomb random number generator}
\author{Mark Wooding, \myemail}

%%%----- The main document --------------------------------------------------

\begin{document}

\maketitle

\begin{abstract}
  The author describes the random number generator used in the
  Straylight/\-Edgeware `Catacomb' library.  While the generator is
  superficially similar to (for example) the Linux and OpenBSD random number
  generators, it introduces a number of its own innovations which improve
  both security and performance.

  The Catacomb generator uses an optional secret key, which can provide
  additional security against forward state compromise extension.  It uses a
  catastrophic reseeding operation to prevent a compromise yielding
  information about past generator states.  This operation works on
  arbitrary-sized blocks of data, so the generator's output buffer can be
  large.  This minimizes the effect of the reseeding overhead.
\end{abstract}

\tableofcontents


\section{The one-way transformation}
\label{sec:oneway}

The most novel part of the generator\footnote{I believe this construction to
be novel.  If I'm wrong, let me know.} is the one-way transformation which is
used to allow pooled input data to affect the output buffer.

Let $H$ be some collision-resistant hash function, and let $E_k$ be a
symmetric cipher with key $k$.  Then I can define the one-way transformation
$T$ by
\[ T(x) = E_{H(x)}(x) \]

I believe, although formal proof seems difficult, that an adversary in
posession of $T(x)$ and a portion of the original $x$ cannot reconstruct the
remainder of $x$ without breaking one of the cryptographic primitives (which
I assume is `difficult') or performing an exhaustive search of one of: the
space of the unknown portion of $x$, the range of the hash function $H$, or
the keyspace of the cipher $E$.

A similar feat of cryptanalysis or exhaustive search seems necessary to work
in a forwards direction: given partial knowledge of both $x$ and $T(x)$, the
adversary cannot work out the remainder of either without trying every
possibility for one or the other unknown portions, or working through the
hash- or keyspace.

A keyed version of $T$ may be defined, given a keyed hash (or MAC) $H_k$:
\[ T_k(x) = E_{H_k(x)}(x) \]
If this is done, the adversary cannot work forwards even with \emph{complete}
knowledge of $B$, or performing one of the obvious exhaustive searches.


\section{Abstract description of the generator}

The generator is divided into two parts: an \emph{input pool} which
accumulates random input data from the environment, and an \emph{output
buffer} which contains data to be passed to clients of the generator on
request.

\subsection{The input pool and mixing function}

New information is contributed to the generator by mixing it with the input
pool, using a mixing function derived from the Linux random number generator
\cite{linux:devrandom}.  The mixing function views the input pool as eight
parallel shift registers.  Input data is added one octet at a time.  Each bit
of an input octet is mixed with a different shift register.

Formally, let $I$ be the input pool, with size $N_I$ bytes; let $P(x) = a_0 +
a_1 x + a_2 x^2 + \cdots + a_{N_I} x^{N_I}$ be a primitive polynomial in
$\mathrm{GF}(2^{N_I})$ with degree $N_I$; let $i$ be an integer such that $0
\le i < N_I$, and $r$ be an integer such that $0 \le r < 8$; and let $x$ be
an input byte.  The result of mixing $x$ with the pool $I$ is calculated as
follows:
\begin{eqlines*}
  \begin{spliteqn*}
    I'[8j + b] =
    \begin{cases}
      x\bigl[(r + b) \bmod 8\bigr] \xor
	\bigxor_{0 \le k < N_I}
	  a_k I\bigl[8\bigl((j + k) \bmod N_I\bigr) + b\bigr] & if $i = j$ \\
      I[j + b] & otherwise
    \end{cases} \\
    \textrm{for all integers $j$ and $b$ where $0 \le j < N_I$ and
      $0 \le b < 8$}
  \end{spliteqn*}
  \\
  I \assign I' \qquad
  i \assign (i + 1) \bmod N_I \qquad
  r \assign (r + 5) \bmod 8
\end{eqlines*}
Initially, $i$ and $r$ are both zero.  The use of 8-bit bytes above is
arbitrary but convenient for modern computers.

The mixing function isn't intended to be cryptographically strong.  Its
purpose is just to hold data without letting too much of the randomness get
away.

\subsection{The output buffer}

Newly added data doesn't affect the output buffer until a `gating' operation
is performed.  This uses the one-way transformation described earlier over
the entire generator state.

Data requested by clients of the generator is read from the output buffer
$O$.  Initially the buffer contains zeroes.  The output buffer is large
enough for $N_O$ bits.

When the generator estimates that there's enough entropy in the input pool, a
\emph{gating} operation is performed, using the one-way function described in
section~\ref{sec:oneway}.  Hash both the input pool and output buffer, and
then encrypt both using the hash as the key:
\begin{eqlines*}
  h = H(I \cat O) \\
  I \assign E_h(I) \qquad O \assign E_h(O)
\end{eqlines*}
If the output buffer is exhausted before the next gating operation, it is
\emph{stretched} using the one-way function: $O \assign E_{H(O)}(O)$.

\subsection{Other tweaks}

The first $N_S$ bits of this buffer take part in the output transformation
but are never actually output.  They're there to make predicting further
output from the generator difficult.

Also, optionally, the one-way functions can be keyed.  This does, of course,
beg the question as to where the key comes from.  This might be one of those
things best done the old-fashioned way with a bunch of coins or dice or
something.


\section{The actual implementation}

The Catacomb implementation of the generator uses the following parameters:
\begin{itemize}
\item The hash function used in the one-way transformation is RIPEMD-160
  \cite{rmd160}; the block cipher is Blowfish, using a 160-bit key.
\item The input pool size $N_I$ is 128 bytes.  The output buffer size $N_O$
  is 512 bytes.  The size $N_S$ of the secret part of the output buffer
  is 160 bits (20 bytes).
\item The polynomial $P(x)$ used for mixing in new input is
  $1 + x + x^2 + x^7 + x^{128}$.
\end{itemize}
The hash and block cipher are well-known and respected cryptographic
primitives.

The input pool is rater larger than it strictly needs to be to contain
`enough' entropy to bring the generator up to the strength of its
cryptographic primitives.  The pool is large to reduce the effect of
asymptotic behaviour in the amount of entropy in the pool.

The output buffer is large simply to improve performance: Blowfish has a
heavy key schedule, so it pays to perform fewer rekeyings per byte of data.
The precise size of 512 bytes was chosen empirically as being about where the
performance improvement stops being linear with the buffer size on my
machine.

\begin{thebibliography}{99}

\bibitem{cp:rand}
  J.~Kelsey, B.~Schneier, D.~Wagner, and C.~Hall, ``Cryptographic Attacks on
  Pseudorandom Number Generators'', \emph{Fast Software Encryption, Fifth
  International Workshop Proceedings (March 1998)}, Springer-Verlag, 1998,
  pp. 168--188, \url{http://www.counterpane.com/pseudorandom_number.html}

\bibitem{linux:devrandom}
  T.~Ts'o, ``A string random number generator'', Linux sources,
  \path{drivers/char/random.c}.

\bibitem{mdw:devrandom}
  M.~Wooding, ``Linux \path{/dev/random} generator security'', Usenet article
  posted to \mtt{sci.crypt}, July 1998.

\end{thebibliography}

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

\end{document}