Rearrange the file tree.

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

diff --git a/papers/rand.tex b/papers/rand.tex
index eda970e..a82387b 100644 (file)
--- a/papers/rand.tex
+++ b/papers/rand.tex
@@ -1,7 +1,5 @@
 %%% -*-latex-*-
 %%%
-%%% $Id: rand.tex,v 1.2 1999/10/12 21:00:34 mdw Exp $
-%%%
 %%% Description of Catacomb's random number generator
 %%%
 %%% (c) 1999 Straylight/Edgeware
@@ -15,27 +13,17 @@
 %%% 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.
 
-%%%----- Revision history ---------------------------------------------------
-%%%
-%%% $Log: rand.tex,v $
-%%% Revision 1.2  1999/10/12 21:00:34  mdw
-%%% Updated.  Almost finished, in fact. ;-)
-%%%
-%%% Revision 1.1  1999/09/03 08:41:13  mdw
-%%% Initial import.
-%%%
-
 %%%----- Header -------------------------------------------------------------
 
 \documentclass[a4paper, article, 10pt, notitlepage, numbering]{strayman}
@@ -72,7 +60,7 @@
   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
@@ -141,8 +129,8 @@ follows:
     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$ \\
+       \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
@@ -200,16 +188,27 @@ The Catacomb implementation of the generator uses the following parameters:
 \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 also 128 bytes.  The size $N_S$ of the secret part of the output buffer
+  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.  
+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
@@ -228,4 +227,4 @@ primitives.
 
 %%%----- That's all, folks --------------------------------------------------
 
-\end{document}
\ No newline at end of file
+\end{document}