sys/dev/rndpool.c

   1 /*      $NetBSD: rndpool.c,v 1.19 2005/12/11 12:20:53 christos Exp $        */
   2
   3 /*-
   4  * Copyright (c) 1997 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Michael Graff <explorer@flame.org>.  This code uses ideas and
   9  * algorithms from the Linux driver written by Ted Ts'o.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  22  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  23  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  24  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  25  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  26  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  27  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  28  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  29  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  30  * POSSIBILITY OF SUCH DAMAGE.
  31  */
  32
  33 #include <sys/cdefs.h>
  34 __KERNEL_RCSID(0, "$NetBSD: rndpool.c,v 1.19 2005/12/11 12:20:53 christos Exp $");
  35
  36 #include <sys/param.h>
  37 #include <sys/systm.h>
  38 #include <sys/sha1.h>
  39
  40 #include <sys/rnd.h>
  41
  42 /*
  43  * The random pool "taps"
  44  */
  45 #define TAP1    99
  46 #define TAP2    59
  47 #define TAP3    31
  48 #define TAP4     9
  49 #define TAP5     7
  50
  51 static inline void rndpool_add_one_word(rndpool_t *, u_int32_t);
  52
  53 void
  54 rndpool_init(rndpool_t *rp)
  55 {
  56
  57         rp->cursor = 0;
  58         rp->rotate = 1;
  59
  60         memset(&rp->stats, 0, sizeof(rp->stats));
  61
  62         rp->stats.curentropy = 0;
  63         rp->stats.poolsize = RND_POOLWORDS;
  64         rp->stats.threshold = RND_ENTROPY_THRESHOLD;
  65         rp->stats.maxentropy = RND_POOLBITS;
  66
  67         KASSERT(RND_ENTROPY_THRESHOLD*2 <= 20); /* XXX sha knowledge */
  68 }
  69
  70 u_int32_t
  71 rndpool_get_entropy_count(rndpool_t *rp)
  72 {
  73
  74         return (rp->stats.curentropy);
  75 }
  76
  77 void rndpool_get_stats(rndpool_t *rp, void *rsp, int size)
  78 {
  79
  80         memcpy(rsp, &rp->stats, size);
  81 }
  82
  83 void
  84 rndpool_increment_entropy_count(rndpool_t *rp, u_int32_t  entropy)
  85 {
  86
  87         rp->stats.curentropy += entropy;
  88         rp->stats.added += entropy;
  89         if (rp->stats.curentropy > RND_POOLBITS) {
  90                 rp->stats.discarded += (rp->stats.curentropy - RND_POOLBITS);
  91                 rp->stats.curentropy = RND_POOLBITS;
  92         }
  93 }
  94
  95 u_int32_t *
  96 rndpool_get_pool(rndpool_t *rp)
  97 {
  98
  99         return (rp->pool);
 100 }
 101
 102 u_int32_t
 103 rndpool_get_poolsize(void)
 104 {
 105
 106         return (RND_POOLWORDS);
 107 }
 108
 109 /*
 110  * The input function treats the contents of the pool as an array of
 111  * 32 LFSR's of length RND_POOLWORDS, one per bit-plane.  The LFSR's
 112  * are clocked once in parallel, using 32-bit xor operations, for each
 113  * word to be added.
 114  *
 115  * Each word to be added is xor'd with the output word of the LFSR
 116  * array (one tap at a time).
 117  *
 118  * In order to facilitate distribution of entropy between the
 119  * bit-planes, a 32-bit rotate of this result is performed prior to
 120  * feedback. The rotation distance is incremented every RND_POOLWORDS
 121  * clocks, by a value that is relativly prime to the word size to try
 122  * to spread the bits throughout the pool quickly when the pool is
 123  * empty.
 124  *
 125  * Each LFSR thus takes its feedback from another LFSR, and is
 126  * effectively re-keyed by both that LFSR and the new data.  Feedback
 127  * occurs with another XOR into the new LFSR, rather than assignment,
 128  * to avoid destroying any entropy in the destination.
 129  *
 130  * Even with zeros as input, the LFSR output data are never visible;
 131  * the contents of the pool are never divulged except via a hash of
 132  * the entire pool, so there is no information for correlation
 133  * attacks. With rotation-based rekeying, each LFSR runs at most a few
 134  * cycles before being permuted.  However, beware of initial
 135  * conditions when no entropy has been added.
 136  *
 137  * The output function also stirs the generated hash back into the
 138  * pool, further permuting the LFSRs and spreading entropy through the
 139  * pool.  Any unknown bits anywhere in the pool are thus reflected
 140  * across all the LFSRs after output.
 141  *
 142  * (The final XOR assignment into the pool for feedback is equivalent
 143  * to an additional LFSR tap of the MSB before shifting, in the case
 144  * where no rotation is done, once every 32 cycles. This LFSR runs for
 145  * at most one length.)
 146  */
 147 static inline void
 148 rndpool_add_one_word(rndpool_t *rp, u_int32_t  val)
 149 {
 150         /*
 151          * Shifting is implemented using a cursor and taps as offsets,
 152          * added mod the size of the pool. For this reason,
 153          * RND_POOLWORDS must be a power of two.
 154          */
 155         val ^= rp->pool[(rp->cursor + TAP1) & (RND_POOLWORDS - 1)];
 156         val ^= rp->pool[(rp->cursor + TAP2) & (RND_POOLWORDS - 1)];
 157         val ^= rp->pool[(rp->cursor + TAP3) & (RND_POOLWORDS - 1)];
 158         val ^= rp->pool[(rp->cursor + TAP4) & (RND_POOLWORDS - 1)];
 159         val ^= rp->pool[(rp->cursor + TAP5) & (RND_POOLWORDS - 1)];
 160         if (rp->rotate != 0)
 161                 val = ((val << rp->rotate) | (val >> (32 - rp->rotate)));
 162         rp->pool[rp->cursor++] ^= val;
 163
 164         /*
 165          * If we have looped around the pool, increment the rotate
 166          * variable so the next value will get xored in rotated to
 167          * a different position.
 168          */
 169         if (rp->cursor == RND_POOLWORDS) {
 170                 rp->cursor = 0;
 171                 rp->rotate = (rp->rotate + 7) & 31;
 172         }
 173 }
 174
 175 #if 0
 176 /*
 177  * Stir a 32-bit value (with possibly less entropy than that) into the pool.
 178  * Update entropy estimate.
 179  */
 180 void
 181 rndpool_add_uint32(rndpool_t *rp, u_int32_t  val, u_int32_t  entropy)
 182 {
 183         rndpool_add_one_word(rp, val);
 184
 185         rp->entropy += entropy;
 186         rp->stats.added += entropy;
 187         if (rp->entropy > RND_POOLBITS) {
 188                 rp->stats.discarded += (rp->entropy - RND_POOLBITS);
 189                 rp->entropy = RND_POOLBITS;
 190         }
 191 }
 192 #endif
 193
 194 /*
 195  * Add a buffer's worth of data to the pool.
 196  */
 197 void
 198 rndpool_add_data(rndpool_t *rp, void *p, u_int32_t len, u_int32_t entropy)
 199 {
 200         u_int32_t val;
 201         u_int8_t *buf;
 202
 203         buf = p;
 204
 205         for (; len > 3; len -= 4) {
 206                 val = *((u_int32_t *)buf);
 207
 208                 rndpool_add_one_word(rp, val);
 209                 buf += 4;
 210         }
 211
 212         if (len != 0) {
 213                 val = 0;
 214                 switch (len) {
 215                 case 3:
 216                         val = *buf++;
 217                 case 2:
 218                         val = val << 8 | *buf++;
 219                 case 1:
 220                         val = val << 8 | *buf++;
 221                 }
 222
 223                 rndpool_add_one_word(rp, val);
 224         }
 225
 226         rp->stats.curentropy += entropy;
 227         rp->stats.added += entropy;
 228
 229         if (rp->stats.curentropy > RND_POOLBITS) {
 230                 rp->stats.discarded += (rp->stats.curentropy - RND_POOLBITS);
 231                 rp->stats.curentropy = RND_POOLBITS;
 232         }
 233 }
 234
 235 /*
 236  * Extract some number of bytes from the random pool, decreasing the
 237  * estimate of randomness as each byte is extracted.
 238  *
 239  * Do this by hashing the pool and returning a part of the hash as
 240  * randomness.  Stir the hash back into the pool.  Note that no
 241  * secrets going back into the pool are given away here since parts of
 242  * the hash are xored together before being returned.
 243  *
 244  * Honor the request from the caller to only return good data, any data,
 245  * etc.  Note that we must have at least 64 bits of entropy in the pool
 246  * before we return anything in the high-quality modes.
 247  */
 248 u_int32_t
 249 rndpool_extract_data(rndpool_t *rp, void *p, u_int32_t len, u_int32_t mode)
 250 {
 251         u_int i;
 252         SHA1_CTX hash;
 253         u_char digest[20];      /* XXX SHA knowledge */
 254         u_int32_t remain, deltae, count;
 255         u_int8_t *buf;
 256         int good;
 257
 258         buf = p;
 259         remain = len;
 260
 261         if (mode == RND_EXTRACT_ANY)
 262                 good = 1;
 263         else
 264                 good = (rp->stats.curentropy >= (8 * RND_ENTROPY_THRESHOLD));
 265
 266         KASSERT(RND_ENTROPY_THRESHOLD*2 <= 20); /* XXX SHA knowledge */
 267
 268         while (good && (remain != 0)) {
 269                 /*
 270                  * While bytes are requested, compute the hash of the pool,
 271                  * and then "fold" the hash in half with XOR, keeping the
 272                  * exact hash value secret, as it will be stirred back into
 273                  * the pool.
 274                  *
 275                  * XXX this approach needs examination by competant
 276                  * cryptographers!  It's rather expensive per bit but
 277                  * also involves every bit of the pool in the
 278                  * computation of every output bit..
 279                  */
 280                 SHA1Init(&hash);
 281                 SHA1Update(&hash, (u_int8_t *)rp->pool, RND_POOLWORDS * 4);
 282                 SHA1Final(digest, &hash);
 283
 284                 /*
 285                  * Stir the hash back into the pool.  This guarantees
 286                  * that the next hash will generate a different value
 287                  * if no new values were added to the pool.
 288                  */
 289                 for (i = 0; i < 5; i++) {
 290                         u_int32_t word;
 291                         memcpy(&word, &digest[i * 4], 4);
 292                         rndpool_add_one_word(rp, word);
 293                 }
 294
 295                 count = min(remain, RND_ENTROPY_THRESHOLD);
 296
 297                 for (i = 0; i < count; i++)
 298                         buf[i] = digest[i] ^ digest[i + RND_ENTROPY_THRESHOLD];
 299
 300                 buf += count;
 301                 deltae = count * 8;
 302                 remain -= count;
 303
 304                 deltae = min(deltae, rp->stats.curentropy);
 305
 306                 rp->stats.removed += deltae;
 307                 rp->stats.curentropy -= deltae;
 308
 309                 if (rp->stats.curentropy == 0)
 310                         rp->stats.generated += (count * 8) - deltae;
 311
 312                 if (mode == RND_EXTRACT_GOOD)
 313                         good = (rp->stats.curentropy >=
 314                             (8 * RND_ENTROPY_THRESHOLD));
 315         }
 316
 317         memset(&hash, 0, sizeof(hash));
 318         memset(digest, 0, sizeof(digest));
 319
 320         return (len - remain);
 321 }