| 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} |