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

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