git.samba.org - gd/nettle/blob - yarrow256.c

   1 /* yarrow256.c
   2
   3    The yarrow pseudo-randomness generator.
   4
   5    Copyright (C) 2001, 2008, 2013 Niels Möller
   6
   7    This file is part of GNU Nettle.
   8
   9    GNU Nettle is free software: you can redistribute it and/or
  10    modify it under the terms of either:
  11
  12      * the GNU Lesser General Public License as published by the Free
  13        Software Foundation; either version 3 of the License, or (at your
  14        option) any later version.
  15
  16    or
  17
  18      * the GNU General Public License as published by the Free
  19        Software Foundation; either version 2 of the License, or (at your
  20        option) any later version.
  21
  22    or both in parallel, as here.
  23
  24    GNU Nettle is distributed in the hope that it will be useful,
  25    but WITHOUT ANY WARRANTY; without even the implied warranty of
  26    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  27    General Public License for more details.
  28
  29    You should have received copies of the GNU General Public License and
  30    the GNU Lesser General Public License along with this program.  If
  31    not, see http://www.gnu.org/licenses/.
  32 */
  33
  34 #if HAVE_CONFIG_H
  35 # include "config.h"
  36 #endif
  37
  38 #include <assert.h>
  39 #include <stdlib.h>
  40 #include <string.h>
  41
  42 #include "yarrow.h"
  43
  44 #include "macros.h"
  45
  46 #ifndef YARROW_DEBUG
  47 #define YARROW_DEBUG 0
  48 #endif
  49
  50 #if YARROW_DEBUG
  51 #include <stdio.h>
  52 #endif
  53
  54 /* Parameters */
  55
  56 /* An upper limit on the entropy (in bits) in one octet of sample
  57  * data. */
  58 #define YARROW_MULTIPLIER 4
  59
  60 /* Entropy threshold for reseeding from the fast pool */
  61 #define YARROW_FAST_THRESHOLD 100
  62
  63 /* Entropy threshold for reseeding from the fast pool */
  64 #define YARROW_SLOW_THRESHOLD 160
  65
  66 /* Number of sources that must exceed the threshold for slow reseed */
  67 #define YARROW_SLOW_K 2
  68
  69 /* The number of iterations when reseeding, P_t in the yarrow paper.
  70  * Should be chosen so that reseeding takes on the order of 0.1-1
  71  * seconds. */
  72 #define YARROW_RESEED_ITERATIONS 1500
  73
  74 /* Entropy estimates sticks to this value, it is treated as infinity
  75  * in calculations. It should fit comfortably in an uint32_t, to avoid
  76  * overflows. */
  77 #define YARROW_MAX_ENTROPY 0x100000
  78
  79 /* Forward declarations */
  80 static void
  81 yarrow_gate(struct yarrow256_ctx *ctx);
  82
  83 void
  84 yarrow256_init(struct yarrow256_ctx *ctx,
  85                unsigned n,
  86                struct yarrow_source *s)
  87 {
  88   unsigned i;
  89
  90   sha256_init(&ctx->pools[0]);
  91   sha256_init(&ctx->pools[1]);
  92
  93   ctx->seeded = 0;
  94
  95   /* Not strictly necessary, but it makes it easier to see if the
  96    * values are sane. */
  97   memset(ctx->counter, 0, sizeof(ctx->counter));
  98
  99   ctx->nsources = n;
 100   ctx->sources = s;
 101
 102   for (i = 0; i<n; i++)
 103     {
 104       ctx->sources[i].estimate[YARROW_FAST] = 0;
 105       ctx->sources[i].estimate[YARROW_SLOW] = 0;
 106       ctx->sources[i].next = YARROW_FAST;
 107     }
 108 }
 109
 110 void
 111 yarrow256_seed(struct yarrow256_ctx *ctx,
 112                size_t length,
 113                const uint8_t *seed_file)
 114 {
 115   assert(length > 0);
 116
 117   sha256_update(&ctx->pools[YARROW_FAST], length, seed_file);
 118   yarrow256_fast_reseed(ctx);
 119 }
 120
 121 /* FIXME: Generalize so that it generates a few more blocks at a
 122  * time. */
 123 static void
 124 yarrow_generate_block(struct yarrow256_ctx *ctx,
 125                       uint8_t *block)
 126 {
 127   unsigned i;
 128
 129   aes256_encrypt(&ctx->key, sizeof(ctx->counter), block, ctx->counter);
 130
 131   /* Increment counter, treating it as a big-endian number. This is
 132    * machine independent, and follows appendix B of the NIST
 133    * specification of cipher modes of operation.
 134    *
 135    * We could keep a representation of the counter as 4 32-bit values,
 136    * and write entire words (in big-endian byteorder) into the counter
 137    * block, whenever they change. */
 138   for (i = sizeof(ctx->counter); i--; )
 139     {
 140       if (++ctx->counter[i])
 141         break;
 142     }
 143 }
 144
 145 static void
 146 yarrow_iterate(uint8_t *digest)
 147 {
 148   uint8_t v0[SHA256_DIGEST_SIZE];
 149   unsigned i;
 150
 151   memcpy(v0, digest, SHA256_DIGEST_SIZE);
 152
 153   /* When hashed inside the loop, i should run from 1 to
 154    * YARROW_RESEED_ITERATIONS */
 155   for (i = 0; ++i < YARROW_RESEED_ITERATIONS; )
 156     {
 157       uint8_t count[4];
 158       struct sha256_ctx hash;
 159
 160       sha256_init(&hash);
 161
 162       /* Hash v_i | v_0 | i */
 163       WRITE_UINT32(count, i);
 164       sha256_update(&hash, SHA256_DIGEST_SIZE, digest);
 165       sha256_update(&hash, sizeof(v0), v0);
 166       sha256_update(&hash, sizeof(count), count);
 167
 168       sha256_digest(&hash, SHA256_DIGEST_SIZE, digest);
 169     }
 170 }
 171
 172 /* NOTE: The SHA-256 digest size equals the AES key size, so we need
 173  * no "size adaptor". */
 174
 175 void
 176 yarrow256_fast_reseed(struct yarrow256_ctx *ctx)
 177 {
 178   uint8_t digest[SHA256_DIGEST_SIZE];
 179   unsigned i;
 180
 181 #if YARROW_DEBUG
 182   fprintf(stderr, "yarrow256_fast_reseed\n");
 183 #endif
 184
 185   /* We feed two block of output using the current key into the pool
 186    * before emptying it. */
 187   if (ctx->seeded)
 188     {
 189       uint8_t blocks[AES_BLOCK_SIZE * 2];
 190
 191       yarrow_generate_block(ctx, blocks);
 192       yarrow_generate_block(ctx, blocks + AES_BLOCK_SIZE);
 193       sha256_update(&ctx->pools[YARROW_FAST], sizeof(blocks), blocks);
 194     }
 195
 196   sha256_digest(&ctx->pools[YARROW_FAST], sizeof(digest), digest);
 197
 198   /* Iterate */
 199   yarrow_iterate(digest);
 200
 201   aes256_set_encrypt_key(&ctx->key, digest);
 202   ctx->seeded = 1;
 203
 204   /* Derive new counter value */
 205   memset(ctx->counter, 0, sizeof(ctx->counter));
 206   aes256_encrypt(&ctx->key, sizeof(ctx->counter), ctx->counter, ctx->counter);
 207
 208   /* Reset estimates. */
 209   for (i = 0; i<ctx->nsources; i++)
 210     ctx->sources[i].estimate[YARROW_FAST] = 0;
 211 }
 212
 213 void
 214 yarrow256_slow_reseed(struct yarrow256_ctx *ctx)
 215 {
 216   uint8_t digest[SHA256_DIGEST_SIZE];
 217   unsigned i;
 218
 219 #if YARROW_DEBUG
 220   fprintf(stderr, "yarrow256_slow_reseed\n");
 221 #endif
 222
 223   /* Get digest of the slow pool*/
 224   sha256_digest(&ctx->pools[YARROW_SLOW], sizeof(digest), digest);
 225
 226   /* Feed it into the fast pool */
 227   sha256_update(&ctx->pools[YARROW_FAST], sizeof(digest), digest);
 228
 229   yarrow256_fast_reseed(ctx);
 230
 231   /* Reset estimates. */
 232   for (i = 0; i<ctx->nsources; i++)
 233     ctx->sources[i].estimate[YARROW_SLOW] = 0;
 234 }
 235
 236 int
 237 yarrow256_update(struct yarrow256_ctx *ctx,
 238                  unsigned source_index, unsigned entropy,
 239                  size_t length, const uint8_t *data)
 240 {
 241   enum yarrow_pool_id current;
 242   struct yarrow_source *source;
 243
 244   assert(source_index < ctx->nsources);
 245
 246   if (!length)
 247     /* Nothing happens */
 248     return 0;
 249
 250   source = &ctx->sources[source_index];
 251
 252   if (!ctx->seeded)
 253     /* While seeding, use the slow pool */
 254     current = YARROW_SLOW;
 255   else
 256     {
 257       current = source->next;
 258       source->next = !source->next;
 259     }
 260
 261   sha256_update(&ctx->pools[current], length, data);
 262
 263   /* NOTE: We should be careful to avoid overflows in the estimates. */
 264   if (source->estimate[current] < YARROW_MAX_ENTROPY)
 265     {
 266       if (entropy > YARROW_MAX_ENTROPY)
 267         entropy = YARROW_MAX_ENTROPY;
 268
 269       if ( (length < (YARROW_MAX_ENTROPY / YARROW_MULTIPLIER))
 270            && (entropy > YARROW_MULTIPLIER * length) )
 271         entropy = YARROW_MULTIPLIER * length;
 272
 273       entropy += source->estimate[current];
 274       if (entropy > YARROW_MAX_ENTROPY)
 275         entropy = YARROW_MAX_ENTROPY;
 276
 277       source->estimate[current] = entropy;
 278     }
 279
 280   /* Check for seed/reseed */
 281   switch(current)
 282     {
 283     case YARROW_FAST:
 284 #if YARROW_DEBUG
 285       fprintf(stderr,
 286               "yarrow256_update: source_index = %d,\n"
 287               "            fast pool estimate = %d\n",
 288               source_index, source->estimate[YARROW_FAST]);
 289 #endif
 290       if (source->estimate[YARROW_FAST] >= YARROW_FAST_THRESHOLD)
 291         {
 292           yarrow256_fast_reseed(ctx);
 293           return 1;
 294         }
 295       else
 296         return 0;
 297
 298     case YARROW_SLOW:
 299       {
 300         if (!yarrow256_needed_sources(ctx))
 301           {
 302             yarrow256_slow_reseed(ctx);
 303             return 1;
 304           }
 305         else
 306           return 0;
 307       }
 308     default:
 309       abort();
 310     }
 311 }
 312
 313 static void
 314 yarrow_gate(struct yarrow256_ctx *ctx)
 315 {
 316   uint8_t key[AES256_KEY_SIZE];
 317   unsigned i;
 318
 319   for (i = 0; i < sizeof(key); i+= AES_BLOCK_SIZE)
 320     yarrow_generate_block(ctx, key + i);
 321
 322   aes256_set_encrypt_key(&ctx->key, key);
 323 }
 324
 325 void
 326 yarrow256_random(struct yarrow256_ctx *ctx, size_t length, uint8_t *dst)
 327 {
 328   assert(ctx->seeded);
 329
 330   while (length >= AES_BLOCK_SIZE)
 331     {
 332       yarrow_generate_block(ctx, dst);
 333       dst += AES_BLOCK_SIZE;
 334       length -= AES_BLOCK_SIZE;
 335     }
 336   if (length)
 337     {
 338       uint8_t buffer[AES_BLOCK_SIZE];
 339
 340       assert(length < AES_BLOCK_SIZE);
 341       yarrow_generate_block(ctx, buffer);
 342       memcpy(dst, buffer, length);
 343     }
 344   yarrow_gate(ctx);
 345 }
 346
 347 int
 348 yarrow256_is_seeded(struct yarrow256_ctx *ctx)
 349 {
 350   return ctx->seeded;
 351 }
 352
 353 unsigned
 354 yarrow256_needed_sources(struct yarrow256_ctx *ctx)
 355 {
 356   /* FIXME: This is somewhat inefficient. It would be better to
 357    * either maintain the count, or do this loop only if the
 358    * current source just crossed the threshold. */
 359   unsigned k, i;
 360
 361   for (i = k = 0; i < ctx->nsources; i++)
 362     if (ctx->sources[i].estimate[YARROW_SLOW] >= YARROW_SLOW_THRESHOLD)
 363       k++;
 364
 365 #if YARROW_DEBUG
 366   fprintf(stderr,
 367           "yarrow256_needed_sources: source_index = %d,\n"
 368           "                    slow pool estimate = %d,\n"
 369           "     number of sources above threshold = %d\n",
 370           source_index, source->estimate[YARROW_SLOW], k);
 371 #endif
 372
 373   return (k < YARROW_SLOW_K) ? (YARROW_SLOW_K - k) : 0;
 374 }