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

   1 %%% -*-latex-*-
   2 %%%
   3 %%% $Id: rand.tex,v 1.1 1999/09/03 08:41:13 mdw Exp $
   4 %%%
   5 %%% Description of Catacomb's random number generator
   6 %%%
   7 %%% (c) 1999 Straylight/Edgeware
   8 %%%
   9
  10 %%%----- Licensing notice ---------------------------------------------------
  11 %%%
  12 %%% This file is part of Catacomb.
  13 %%%
  14 %%% Catacomb is free software; you can redistribute it and/or modify
  15 %%% it under the terms of the GNU Library General Public License as
  16 %%% published by the Free Software Foundation; either version 2 of the
  17 %%% License, or (at your option) any later version.
  18 %%%
  19 %%% Catacomb is distributed in the hope that it will be useful,
  20 %%% but WITHOUT ANY WARRANTY; without even the implied warranty of
  21 %%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22 %%% GNU Library General Public License for more details.
  23 %%%
  24 %%% You should have received a copy of the GNU Library General Public
  25 %%% License along with Catacomb; if not, write to the Free
  26 %%% Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27 %%% MA 02111-1307, USA.
  28
  29 %%%----- Revision history ---------------------------------------------------
  30 %%%
  31 %%% $Log: rand.tex,v $
  32 %%% Revision 1.1  1999/09/03 08:41:13  mdw
  33 %%% Initial import.
  34 %%%
  35
  36 %%%----- Header -------------------------------------------------------------
  37
  38 \documentclass[a4paper, article, 10pt, notitlepage, numbering]{strayman}
  39 \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
  40 \usepackage{mdwtab, mathenv}
  41 \usepackage[T1]{fontenc}
  42 \usepackage{cmtt, url}
  43 \usepackage[tpic, all]{xy}
  44 \usepackage{mathbbol}
  45 % \usepackage{crypto}
  46
  47 \def\mdw{{\normalfont[{\bfseries\itshape mdw}]}}
  48 \urlstyle{tt}
  49 \def\email{\begingroup\urlstyle{rm}\Url}
  50 \urldef\myemail\email{mdw@nsict.org}
  51 \def\Z{\mathbb{Z}}
  52 \let\assign\leftarrow
  53 \let\xor\oplus
  54 \let\bigxor\bigoplus
  55
  56 \title{The Catacomb random number generator}
  57 \author{Mark Wooding, \myemail}
  58
  59 %%%----- The main document --------------------------------------------------
  60
  61 \begin{document}
  62
  63 \maketitle
  64
  65 \begin{abstract}
  66   The author describes the random number generator used in the
  67   Straylight/\-Edgeware `Catacomb' library.  While the generator is
  68   superficially similar to (for example) the Linux and OpenBSD random number
  69   generators, it introduces a number of its own innovations which improve
  70   both security and performance.
  71
  72   The Catacomb generator uses an optional secret key, which can provide
  73   additional security against forward state compromise extension.  It uses a
  74   catastrophic reseeding operation to prevent a compromise yielding
  75   information about past generator states.  This operation works on
  76   arbitrary-sized blocks of data, so the generator's output buffer can be
  77   large.  This minimizes the effect of the reseeding overhead.
  78 \end{abstract}
  79
  80 \tableofcontents
  81
  82
  83 \section{The one-way transformation}
  84
  85 The most novel part of the generator\footnote{I believe this construction to
  86 be novel.  If I'm wrong, let me know.} is the one-way transformation which is
  87 used to allow pooled input data to affect the output buffer.
  88
  89 Let $H$ be some collision-resistant hash function, and let $E_k$ be a
  90 symmetric cipher with key $k$.  Then I can define the one-way transformation
  91 $T$ by
  92 \[ T(x) = E_{H(x)}(x) \]
  93
  94 I believe, although formal proof seems difficult, that an adversary in
  95 posession of $T(x)$ and a portion of the original $x$ cannot reconstruct the
  96 remainder of $x$ without breaking one of the cryptographic primitives (which
  97 I assume is `difficult') or performing an exhaustive search of one of: the
  98 space of the unknown portion of $x$, the range of the hash function $H$, or
  99 the keyspace of the cipher $E$.
 100
 101 A similar feat of cryptanalysis or exhaustive search seems necessary to work
 102 in a forwards direction: given partial knowledge of both $x$ and $T(x)$, the
 103 adversary cannot work out the remainder of either without trying every
 104 possibility for one or the other unknown portions, or working through the
 105 hash- or keyspace.
 106
 107 A keyed version of $T$ may be defined, given a keyed hash (or MAC) $H_k$:
 108 \[ T_k(x) = E_{H_k(x)}(x) \]
 109 If this is done, the adversary cannot work forwards even with \emph{complete}
 110 knowledge of $B$, or performing one of the obvious exhaustive searches.
 111
 112
 113 \section{Description of the generator}
 114
 115 The generator is divided into two parts: an \emph{input pool} which
 116 accumulates random input data from the environment, and an \emph{output
 117 buffer} which contains data to be passed to clients of the generator on
 118 request.
 119
 120 New information is contributed to the generator by mixing it with the input
 121 pool, using a mixing function derived from the Linux random number generator
 122 \cite{linux:devrandom}.  The mixing function views the input pool as eight
 123 parallel shift registers.  Input data is added one octet at a time.  Each bit
 124 of an input octet is mixed with a different shift register.
 125
 126 Formally, let $I$ be the input pool, with size $n_I$ bytes; let $P(x) = a_0 +
 127 a_1 x + a_2 x^2 + \cdots + a_{n_I} x^{n_I}$ be a primitive polynomial in
 128 $\mathrm{GF}(2^{n_I})$ with degree $n_I$; let $i$ be an integer such that $0
 129 \le i < n_I$, and $r$ be an integer such that $0 \le r < 8$; and let $x$ be
 130 an input byte.  The result of mixing $x$ with the pool $I$ is calculated as
 131 follows:
 132 \begin{eqlines*}
 133   \begin{spliteqn*}
 134     I'[8j + b] =
 135     \begin{cases}
 136       x\bigl[(r + b) \bmod 8\bigr] \xor
 137         \bigxor_{0 \le k < n_I}
 138           a_k I\bigl[8\bigl((j + k) \bmod n_I\bigr) + b\bigr] & if $i = j$ \\
 139       I[j + b] & otherwise
 140     \end{cases} \\
 141     \textrm{for all integers $j$ and $b$ where $0 \le j < n_I$ and
 142       $0 \le b < 8$}
 143   \end{spliteqn*}
 144   \\
 145   I \assign I' \qquad
 146   i \assign (i + 1) \bmod n_I \qquad
 147   r \assign (r + 5) \bmod 8
 148 \end{eqlines*}
 149 Initially, $i$ and $r$ are both zero.  The use of 8-bit bytes above is
 150 arbitrary.
 151
 152 Newly added data doesn't affect the output buffer until a `gating' operation
 153 is performed.  This uses the one-way transformation described earlier over
 154 the entire generator state.
 155
 156 Data requested by clients of the generator is read from the output buffer
 157 $O$.  Initially the buffer contains zeroes.
 158
 159 \begin{thebibliography}{99}
 160
 161 \bibitem{cp:rand}
 162   J.~Kelsey, B.~Schneier, D.~Wagner, and C.~Hall, ``Cryptographic Attacks on
 163   Pseudorandom Number Generators'', \emph{Fast Software Encryption, Fifth
 164   International Workshop Proceedings (March 1998)}, Springer-Verlag, 1998,
 165   pp. 168--188, \url{http://www.counterpane.com/pseudorandom_number.html}
 166
 167 \bibitem{linux:devrandom}
 168   T.~Ts'o, ``A string random number generator'', Linux sources,
 169   \path{drivers/char/random.c}.
 170
 171 \bibitem{mdw:devrandom}
 172   M.~Wooding, ``Linux \path{/dev/random} generator security'', Usenet article
 173   posted to \mtt{sci.crypt}, July 1998.
 174
 175 \end{thebibliography}
 176
 177 %%%----- That's all, folks --------------------------------------------------
 178
 179 \end{document}