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

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