chiark - git - mdw - become/blob - src/rand.c

   1 /* -*-c-*-
   2  *
   3  * $Id: rand.c,v 1.3 1998/01/12 16:46:23 mdw Exp $
   4  *
   5  * Random number generation
   6  *
   7  * (c) 1998 EBI
   8  */
   9
  10 /*----- Licencing notice --------------------------------------------------*
  11  *
  12  * This file is part of Become.
  13  *
  14  * Become is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU General Public License as published by
  16  * the Free Software Foundation; either version 2 of the License, or
  17  * (at your option) any later version.
  18  *
  19  * Become 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 General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with `become'; if not, write to the Free Software Foundation,
  26  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  27  */
  28
  29 /*----- Revision history --------------------------------------------------*
  30  *
  31  * $Log: rand.c,v $
  32  * Revision 1.3  1998/01/12 16:46:23  mdw
  33  * Fix copyright date.
  34  *
  35  * Revision 1.2  1997/08/07 09:47:07  mdw
  36  * Fix address of the FSF.
  37  *
  38  * Revision 1.1  1997/08/07 09:46:05  mdw
  39  * New source file added to maintain a randomness pool.
  40  *
  41  */
  42
  43 /*----- Header files ------------------------------------------------------*/
  44
  45 /* --- ANSI headers --- */
  46
  47 #include <ctype.h>
  48 #include <errno.h>
  49 #include <stdio.h>
  50 #include <stdlib.h>
  51 #include <string.h>
  52 #include <time.h>
  53
  54 /* --- Local headers --- */
  55
  56 #include "become.h"
  57 #include "config.h"
  58 #include "icrypt.h"
  59 #include "md5.h"
  60 #include "rand.h"
  61 #include "tx.h"
  62 #include "utils.h"
  63
  64 /*----- Magic numbers -----------------------------------------------------*/
  65
  66 #define rand__seedBits 512              /* Number of random seed bits */
  67
  68 /*----- Persistant state --------------------------------------------------*/
  69
  70 static unsigned char rand__pool[rand__seedBits / 8]; /* Entropy pool */
  71 static size_t rand__i = 0;              /* Index into entropy pool */
  72 static size_t rand__r = 0;              /* Rotation to apply to next byte */
  73
  74 /*----- Main code ---------------------------------------------------------*/
  75
  76 /* --- @rand_read@ --- *
  77  *
  78  * Arguments:   @FILE *fp@ = pointer to file to read from
  79  *
  80  * Returns:     ---
  81  *
  82  * Use:         Reads a random number seed from the stream.
  83  */
  84
  85 void rand_read(FILE *fp)
  86 {
  87   tx_getBits(rand__pool, rand__seedBits, fp);
  88   rand__i = 0;
  89   rand__r = 0;
  90   T( traceblk(TRACE_RAND, "rand: loaded randomness pool",
  91               rand__pool, sizeof(rand__pool)); )
  92 }
  93
  94 /* --- @rand_write@ --- *
  95  *
  96  * Arguments:   @FILE *fp@ = pointer to file to write on
  97  *
  98  * Returns:     ---
  99  *
 100  * Use:         Writes a random number seed back to the stream.
 101  */
 102
 103 void rand_write(FILE *fp)
 104 {
 105   rand_churn();
 106   tx_putBits(rand__pool, rand__seedBits, fp);
 107 }
 108
 109 /* --- @rand_clear@ --- *
 110  *
 111  * Arguments:   ---
 112  *
 113  * Returns:     ---
 114  *
 115  * Use:         Clears the random number pool.
 116  */
 117
 118 void rand_clear(void)
 119 {
 120   memset(rand__pool, 0, sizeof(rand__pool));
 121   T( trace(TRACE_RAND, "rand: cleared randomness pool"); )
 122   rand__i = 0;
 123   rand__r = 0;
 124 }
 125
 126 /* --- @rand_encrypt@ --- *
 127  *
 128  * Arguments:   @icrypt_job *j@ = pointer to an encryption job to apply
 129  *
 130  * Returns:     ---
 131  *
 132  * Use:         Encrypts the randomness pool with a given key.  This should
 133  *              be done before use, in case the pool gets compromised.
 134  */
 135
 136 void rand_encrypt(icrypt_job *j)
 137 {
 138   icrypt_encrypt(j, rand__pool, rand__pool, sizeof(rand__pool));
 139   rand__i = 0;
 140   rand__r = 0;
 141   T( traceblk(TRACE_RAND, "encrypted randomness pool",
 142               rand__pool, sizeof(rand__pool)); )
 143 }
 144
 145 /* --- @rand_add@ --- *
 146  *
 147  * Arguments:   @const void *p@ = pointer to some data
 148  *              @size_t sz@ = size of the data in bytes
 149  *
 150  * Returns:     ---
 151  *
 152  * Use:         Adds entropy to the pool.
 153  */
 154
 155 void rand_add(const void *p, size_t sz)
 156 {
 157   /* --- Method --- *
 158    *
 159    * Entropy is inserted byte-by-byte.  The method used is derived from
 160    * Linux's `drivers/char/random.c', which is in turn appears to be inspired
 161    * by SHA-1.
 162    *
 163    * Imagine the randomness pool as 8 parallel shift registers.  To insert
 164    * a byte into the pool, XOR it with bytes picked according to a primitive
 165    * polynomial mod 2, and rotate one place to the left.  (The rotation is
 166    * from SHA-1; it introduces some interaction between the registers.)
 167    */
 168
 169   size_t i = rand__i;
 170   const unsigned char *cp = p;
 171   size_t mask = (rand__seedBits / 8) - 1;
 172   size_t r = rand__r;
 173   unsigned int x;
 174
 175   /* --- Ensure the polynomial is valid --- *
 176    *
 177    * The current polynomal is %$x^{64} + x^4 + x^3 + x + 1$% (picked from
 178    * Schneier's excellent book).  If the pool size changes, though, I'll
 179    * need another polynomial.
 180    */
 181
 182 #if rand__seedBits / 8 != 64
 183 #  error Change the polynomal in rand_add
 184 #endif
 185
 186   T( traceblk(TRACE_RAND, "rand: incoming entropy", p, sz); )
 187
 188   /* --- Add values to the entropy pool --- */
 189
 190   while (sz) {
 191     x = *cp++ & 0xffu;
 192     if (r)
 193       x = ((x << r) | (x >> (8 - r)));
 194     x ^= (rand__pool[i] ^
 195           rand__pool[(i + 1) & mask] ^
 196           rand__pool[(i + 3) & mask] ^
 197           rand__pool[(i + 4) & mask]);
 198     rand__pool[i] = ((x << 1) | (x >> 7)) & 0xffu;
 199     sz--;
 200     i = (i + 1) & mask;
 201     r = (r + 3) & 7;
 202   }
 203
 204   /* --- Update the global counters --- */
 205
 206   rand__r = r;
 207   rand__i = i;
 208
 209   T( traceblk(TRACE_RAND, "rand: added some entropy",
 210               rand__pool, sizeof(rand__pool)); )
 211 }
 212
 213 /* --- @rand_extract@ --- *
 214  *
 215  * Arguments:   @unsigned char *b@ = pointer to output buffer
 216  *              @size_t sz@ = number of bytes wanted
 217  *
 218  * Returns:     ---
 219  *
 220  * Use:         Produces a number of random bytes.
 221  */
 222
 223 void rand_extract(unsigned char *b, size_t sz)
 224 {
 225   /* --- Method --- *
 226    *
 227    * Hash the buffer with a secure hash (or, in this case, with MD5 and hope
 228    * for the best...).  If this gives us enough bytes, fill the output
 229    * buffer; otherwise copy the whole hash out.  The contribute the hash back
 230    * into the randomness pool with @rand_add@ to provide some feedback.
 231    *
 232    * The secure hash gives us good mixing over the whole of the randomness
 233    * pool, and attempts to ensure that an attacker receiving our random
 234    * numbers can't predict any numbers we don't actually give him.
 235    */
 236
 237   size_t c;
 238   unsigned char mdbuf[MD5_HASHSIZE];
 239   md5 md;
 240
 241   T( trace(TRACE_RAND, "rand: extracting entropy"); )
 242
 243   while (sz) {
 244     c = (sz >= sizeof(mdbuf)) ? sizeof(mdbuf) : sz;
 245     md5_init(&md);
 246     md5_buffer(&md, rand__pool, sizeof(rand__pool));
 247     md5_final(&md, mdbuf);
 248     memcpy(b, mdbuf, c);
 249     rand_add(mdbuf, c);
 250     b += c; sz -= c;
 251   }
 252   burn(mdbuf); burn(md);
 253
 254   T( trace(TRACE_RAND, "rand: finished extracting entropy"); )
 255 }
 256
 257 /* --- @rand_churn@ --- *
 258  *
 259  * Arguments:   ---
 260  *
 261  * Returns:     ---
 262  *
 263  * Use:         Churns the randomness pool completely.  The pool is replaced
 264  *              by repeated MD5-ings of itself.
 265  */
 266
 267 void rand_churn(void)
 268 {
 269   md5 md;
 270   unsigned char mdbuf[MD5_HASHSIZE];
 271   size_t sz = sizeof(rand__pool);
 272   size_t c;
 273
 274   T( trace(TRACE_RAND, "rand: churning pool"); )
 275
 276   rand__i = 0;
 277   rand__r = 0;
 278
 279   while (sz) {
 280     c = (sz >= sizeof(mdbuf)) ? sizeof(mdbuf) : sz;
 281     md5_init(&md);
 282     md5_buffer(&md, rand__pool, sizeof(rand__pool));
 283     md5_final(&md, mdbuf);
 284     rand_add(mdbuf, c);
 285     sz -= c;
 286   }
 287
 288   rand__i = 0;
 289   rand__r = 0;
 290
 291   burn(mdbuf); burn(md);
 292
 293   T( trace(TRACE_RAND, "rand: finished churning pool"); )
 294 }
 295
 296 /*----- That's all, folks -------------------------------------------------*/