git.distorted.org.uk Git - u/mdw/catacomb/blob - papers/rand.tex

   1 %%% -*-latex-*-
   2 %%%
   3 %%% Description of Catacomb's random number generator
   4 %%%
   5 %%% (c) 1999 Straylight/Edgeware
   6 %%%
   7
   8 %%%----- Licensing notice ---------------------------------------------------
   9 %%%
  10 %%% This file is part of Catacomb.
  11 %%%
  12 %%% Catacomb is free software; you can redistribute it and/or modify
  13 %%% it under the terms of the GNU Library General Public License as
  14 %%% published by the Free Software Foundation; either version 2 of the
  15 %%% License, or (at your option) any later version.
  16 %%%
  17 %%% Catacomb is distributed in the hope that it will be useful,
  18 %%% but WITHOUT ANY WARRANTY; without even the implied warranty of
  19 %%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20 %%% GNU Library General Public License for more details.
  21 %%%
  22 %%% You should have received a copy of the GNU Library General Public
  23 %%% License along with Catacomb; if not, write to the Free
  24 %%% Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25 %%% MA 02111-1307, USA.
  26
  27 %%%----- Header -------------------------------------------------------------
  28
  29 \documentclass[a4paper, article, 10pt, notitlepage, numbering]{strayman}
  30 \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
  31 \usepackage{mdwtab, mathenv}
  32 \usepackage[T1]{fontenc}
  33 \usepackage{cmtt, url}
  34 \usepackage[tpic, all]{xy}
  35 \usepackage{mathbbol}
  36 % \usepackage{crypto}
  37
  38 \def\mdw{{\normalfont[{\bfseries\itshape mdw}]}}
  39 \urlstyle{tt}
  40 \def\email{\begingroup\urlstyle{rm}\Url}
  41 \urldef\myemail\email{mdw@nsict.org}
  42 \def\Z{\mathbb{Z}}
  43 \let\assign\leftarrow
  44 \let\xor\oplus
  45 \let\bigxor\bigoplus
  46 \def\cat{\mathbin{\|}}
  47
  48 \title{The Catacomb random number generator}
  49 \author{Mark Wooding, \myemail}
  50
  51 %%%----- The main document --------------------------------------------------
  52
  53 \begin{document}
  54
  55 \maketitle
  56
  57 \begin{abstract}
  58   The author describes the random number generator used in the
  59   Straylight/\-Edgeware `Catacomb' library.  While the generator is
  60   superficially similar to (for example) the Linux and OpenBSD random number
  61   generators, it introduces a number of its own innovations which improve
  62   both security and performance.
  63
  64   The Catacomb generator uses an optional secret key, which can provide
  65   additional security against forward state compromise extension.  It uses a
  66   catastrophic reseeding operation to prevent a compromise yielding
  67   information about past generator states.  This operation works on
  68   arbitrary-sized blocks of data, so the generator's output buffer can be
  69   large.  This minimizes the effect of the reseeding overhead.
  70 \end{abstract}
  71
  72 \tableofcontents
  73
  74
  75 \section{The one-way transformation}
  76 \label{sec:oneway}
  77
  78 The most novel part of the generator\footnote{I believe this construction to
  79 be novel.  If I'm wrong, let me know.} is the one-way transformation which is
  80 used to allow pooled input data to affect the output buffer.
  81
  82 Let $H$ be some collision-resistant hash function, and let $E_k$ be a
  83 symmetric cipher with key $k$.  Then I can define the one-way transformation
  84 $T$ by
  85 \[ T(x) = E_{H(x)}(x) \]
  86
  87 I believe, although formal proof seems difficult, that an adversary in
  88 posession of $T(x)$ and a portion of the original $x$ cannot reconstruct the
  89 remainder of $x$ without breaking one of the cryptographic primitives (which
  90 I assume is `difficult') or performing an exhaustive search of one of: the
  91 space of the unknown portion of $x$, the range of the hash function $H$, or
  92 the keyspace of the cipher $E$.
  93
  94 A similar feat of cryptanalysis or exhaustive search seems necessary to work
  95 in a forwards direction: given partial knowledge of both $x$ and $T(x)$, the
  96 adversary cannot work out the remainder of either without trying every
  97 possibility for one or the other unknown portions, or working through the
  98 hash- or keyspace.
  99
 100 A keyed version of $T$ may be defined, given a keyed hash (or MAC) $H_k$:
 101 \[ T_k(x) = E_{H_k(x)}(x) \]
 102 If this is done, the adversary cannot work forwards even with \emph{complete}
 103 knowledge of $B$, or performing one of the obvious exhaustive searches.
 104
 105
 106 \section{Abstract description of the generator}
 107
 108 The generator is divided into two parts: an \emph{input pool} which
 109 accumulates random input data from the environment, and an \emph{output
 110 buffer} which contains data to be passed to clients of the generator on
 111 request.
 112
 113 \subsection{The input pool and mixing function}
 114
 115 New information is contributed to the generator by mixing it with the input
 116 pool, using a mixing function derived from the Linux random number generator
 117 \cite{linux:devrandom}.  The mixing function views the input pool as eight
 118 parallel shift registers.  Input data is added one octet at a time.  Each bit
 119 of an input octet is mixed with a different shift register.
 120
 121 Formally, let $I$ be the input pool, with size $N_I$ bytes; let $P(x) = a_0 +
 122 a_1 x + a_2 x^2 + \cdots + a_{N_I} x^{N_I}$ be a primitive polynomial in
 123 $\mathrm{GF}(2^{N_I})$ with degree $N_I$; let $i$ be an integer such that $0
 124 \le i < N_I$, and $r$ be an integer such that $0 \le r < 8$; and let $x$ be
 125 an input byte.  The result of mixing $x$ with the pool $I$ is calculated as
 126 follows:
 127 \begin{eqlines*}
 128   \begin{spliteqn*}
 129     I'[8j + b] =
 130     \begin{cases}
 131       x\bigl[(r + b) \bmod 8\bigr] \xor
 132         \bigxor_{0 \le k < N_I}
 133           a_k I\bigl[8\bigl((j + k) \bmod N_I\bigr) + b\bigr] & if $i = j$ \\
 134       I[j + b] & otherwise
 135     \end{cases} \\
 136     \textrm{for all integers $j$ and $b$ where $0 \le j < N_I$ and
 137       $0 \le b < 8$}
 138   \end{spliteqn*}
 139   \\
 140   I \assign I' \qquad
 141   i \assign (i + 1) \bmod N_I \qquad
 142   r \assign (r + 5) \bmod 8
 143 \end{eqlines*}
 144 Initially, $i$ and $r$ are both zero.  The use of 8-bit bytes above is
 145 arbitrary but convenient for modern computers.
 146
 147 The mixing function isn't intended to be cryptographically strong.  Its
 148 purpose is just to hold data without letting too much of the randomness get
 149 away.
 150
 151 \subsection{The output buffer}
 152
 153 Newly added data doesn't affect the output buffer until a `gating' operation
 154 is performed.  This uses the one-way transformation described earlier over
 155 the entire generator state.
 156
 157 Data requested by clients of the generator is read from the output buffer
 158 $O$.  Initially the buffer contains zeroes.  The output buffer is large
 159 enough for $N_O$ bits.
 160
 161 When the generator estimates that there's enough entropy in the input pool, a
 162 \emph{gating} operation is performed, using the one-way function described in
 163 section~\ref{sec:oneway}.  Hash both the input pool and output buffer, and
 164 then encrypt both using the hash as the key:
 165 \begin{eqlines*}
 166   h = H(I \cat O) \\
 167   I \assign E_h(I) \qquad O \assign E_h(O)
 168 \end{eqlines*}
 169 If the output buffer is exhausted before the next gating operation, it is
 170 \emph{stretched} using the one-way function: $O \assign E_{H(O)}(O)$.
 171
 172 \subsection{Other tweaks}
 173
 174 The first $N_S$ bits of this buffer take part in the output transformation
 175 but are never actually output.  They're there to make predicting further
 176 output from the generator difficult.
 177
 178 Also, optionally, the one-way functions can be keyed.  This does, of course,
 179 beg the question as to where the key comes from.  This might be one of those
 180 things best done the old-fashioned way with a bunch of coins or dice or
 181 something.
 182
 183
 184 \section{The actual implementation}
 185
 186 The Catacomb implementation of the generator uses the following parameters:
 187 \begin{itemize}
 188 \item The hash function used in the one-way transformation is RIPEMD-160
 189   \cite{rmd160}; the block cipher is Blowfish, using a 160-bit key.
 190 \item The input pool size $N_I$ is 128 bytes.  The output buffer size $N_O$
 191   is 512 bytes.  The size $N_S$ of the secret part of the output buffer
 192   is 160 bits (20 bytes).
 193 \item The polynomial $P(x)$ used for mixing in new input is
 194   $1 + x + x^2 + x^7 + x^{128}$.
 195 \end{itemize}
 196 The hash and block cipher are well-known and respected cryptographic
 197 primitives.
 198
 199 The input pool is rater larger than it strictly needs to be to contain
 200 `enough' entropy to bring the generator up to the strength of its
 201 cryptographic primitives.  The pool is large to reduce the effect of
 202 asymptotic behaviour in the amount of entropy in the pool.
 203
 204 The output buffer is large simply to improve performance: Blowfish has a
 205 heavy key schedule, so it pays to perform fewer rekeyings per byte of data.
 206 The precise size of 512 bytes was chosen empirically as being about where the
 207 performance improvement stops being linear with the buffer size on my
 208 machine.
 209
 210 \begin{thebibliography}{99}
 211
 212 \bibitem{cp:rand}
 213   J.~Kelsey, B.~Schneier, D.~Wagner, and C.~Hall, ``Cryptographic Attacks on
 214   Pseudorandom Number Generators'', \emph{Fast Software Encryption, Fifth
 215   International Workshop Proceedings (March 1998)}, Springer-Verlag, 1998,
 216   pp. 168--188, \url{http://www.counterpane.com/pseudorandom_number.html}
 217
 218 \bibitem{linux:devrandom}
 219   T.~Ts'o, ``A string random number generator'', Linux sources,
 220   \path{drivers/char/random.c}.
 221
 222 \bibitem{mdw:devrandom}
 223   M.~Wooding, ``Linux \path{/dev/random} generator security'', Usenet article
 224   posted to \mtt{sci.crypt}, July 1998.
 225
 226 \end{thebibliography}
 227
 228 %%%----- That's all, folks --------------------------------------------------
 229
 230 \end{document}