yarrow256.c 8.94 KB
Newer Older
1
/* yarrow256.c
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

   The yarrow pseudo-randomness generator.

   Copyright (C) 2001, 2008, 2013 Niels Möller

   This file is part of GNU Nettle.

   GNU Nettle is free software: you can redistribute it and/or
   modify it under the terms of either:

     * the GNU Lesser General Public License as published by the Free
       Software Foundation; either version 3 of the License, or (at your
       option) any later version.

   or

     * the GNU General Public License as published by the Free
       Software Foundation; either version 2 of the License, or (at your
       option) any later version.

   or both in parallel, as here.

   GNU Nettle is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received copies of the GNU General Public License and
   the GNU Lesser General Public License along with this program.  If
   not, see http://www.gnu.org/licenses/.
*/
33

34 35 36
#if HAVE_CONFIG_H
# include "config.h"
#endif
37

38
#include <assert.h>
39
#include <stdlib.h>
40 41
#include <string.h>

42 43 44 45
#include "yarrow.h"

#include "macros.h"

46 47 48 49 50
#ifndef YARROW_DEBUG
#define YARROW_DEBUG 0
#endif

#if YARROW_DEBUG
Niels Möller's avatar
Niels Möller committed
51 52 53
#include <stdio.h>
#endif

54 55 56 57 58 59
/* Parameters */

/* An upper limit on the entropy (in bits) in one octet of sample
 * data. */
#define YARROW_MULTIPLIER 4

60 61 62 63 64 65 66 67 68
/* Entropy threshold for reseeding from the fast pool */
#define YARROW_FAST_THRESHOLD 100

/* Entropy threshold for reseeding from the fast pool */
#define YARROW_SLOW_THRESHOLD 160

/* Number of sources that must exceed the threshold for slow reseed */
#define YARROW_SLOW_K 2

69 70 71 72 73
/* The number of iterations when reseeding, P_t in the yarrow paper.
 * Should be chosen so that reseeding takes on the order of 0.1-1
 * seconds. */
#define YARROW_RESEED_ITERATIONS 1500

74 75 76 77 78
/* Entropy estimates sticks to this value, it is treated as infinity
 * in calculations. It should fit comfortably in an uint32_t, to avoid
 * overflows. */
#define YARROW_MAX_ENTROPY 0x100000

79 80 81 82
/* Forward declarations */
static void
yarrow_gate(struct yarrow256_ctx *ctx);

83 84
void
yarrow256_init(struct yarrow256_ctx *ctx,
85
	       unsigned n,
86 87
	       struct yarrow_source *s)
{
88 89
  unsigned i;

90 91
  sha256_init(&ctx->pools[0]);
  sha256_init(&ctx->pools[1]);
92
  
93 94
  ctx->seeded = 0;

95
  /* Not strictly necessary, but it makes it easier to see if the
96 97 98
   * values are sane. */
  memset(ctx->counter, 0, sizeof(ctx->counter));
  
99 100
  ctx->nsources = n;
  ctx->sources = s;
101 102 103 104 105 106 107 108 109

  for (i = 0; i<n; i++)
    {
      ctx->sources[i].estimate[YARROW_FAST] = 0;
      ctx->sources[i].estimate[YARROW_SLOW] = 0;
      ctx->sources[i].next = YARROW_FAST;
    }
}

110 111
void
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 122
}

/* FIXME: Generalize so that it generates a few more blocks at a
 * time. */
123 124 125 126 127
static void
yarrow_generate_block(struct yarrow256_ctx *ctx,
		      uint8_t *block)
{
  unsigned i;
Niels Möller's avatar
Niels Möller committed
128

129
  aes256_encrypt(&ctx->key, sizeof(ctx->counter), block, ctx->counter);
130 131 132 133 134

  /* Increment counter, treating it as a big-endian number. This is
   * machine independent, and follows appendix B of the NIST
   * specification of cipher modes of operation.
   *
135
   * We could keep a representation of the counter as 4 32-bit values,
136 137 138 139 140 141 142
   * and write entire words (in big-endian byteorder) into the counter
   * block, whenever they change. */
  for (i = sizeof(ctx->counter); i--; )
    {
      if (++ctx->counter[i])
	break;
    }
143 144
}

145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
static void
yarrow_iterate(uint8_t *digest)
{
  uint8_t v0[SHA256_DIGEST_SIZE];
  unsigned i;
  
  memcpy(v0, digest, SHA256_DIGEST_SIZE);
  
  /* When hashed inside the loop, i should run from 1 to
   * YARROW_RESEED_ITERATIONS */
  for (i = 0; ++i < YARROW_RESEED_ITERATIONS; )
    {
      uint8_t count[4];
      struct sha256_ctx hash;
  
      sha256_init(&hash);

      /* Hash v_i | v_0 | i */
      WRITE_UINT32(count, i);
      sha256_update(&hash, SHA256_DIGEST_SIZE, digest);
      sha256_update(&hash, sizeof(v0), v0);
      sha256_update(&hash, sizeof(count), count);

      sha256_digest(&hash, SHA256_DIGEST_SIZE, digest);
    }
}

172
/* NOTE: The SHA-256 digest size equals the AES key size, so we need
173
 * no "size adaptor". */
174

175 176
void
yarrow256_fast_reseed(struct yarrow256_ctx *ctx)
177 178 179
{
  uint8_t digest[SHA256_DIGEST_SIZE];
  unsigned i;
180
  
181
#if YARROW_DEBUG
182
  fprintf(stderr, "yarrow256_fast_reseed\n");
Niels Möller's avatar
Niels Möller committed
183 184
#endif
  
185 186 187 188 189 190 191 192 193 194 195
  /* We feed two block of output using the current key into the pool
   * before emptying it. */
  if (ctx->seeded)
    {
      uint8_t blocks[AES_BLOCK_SIZE * 2];
      
      yarrow_generate_block(ctx, blocks);
      yarrow_generate_block(ctx, blocks + AES_BLOCK_SIZE);
      sha256_update(&ctx->pools[YARROW_FAST], sizeof(blocks), blocks);
    }
  
196
  sha256_digest(&ctx->pools[YARROW_FAST], sizeof(digest), digest);
197 198 199 200

  /* Iterate */
  yarrow_iterate(digest);

201
  aes256_set_encrypt_key(&ctx->key, digest);
202
  ctx->seeded = 1;
203 204 205

  /* Derive new counter value */
  memset(ctx->counter, 0, sizeof(ctx->counter));
206
  aes256_encrypt(&ctx->key, sizeof(ctx->counter), ctx->counter, ctx->counter);
207 208 209 210 211 212
  
  /* Reset estimates. */
  for (i = 0; i<ctx->nsources; i++)
    ctx->sources[i].estimate[YARROW_FAST] = 0;
}

213 214
void
yarrow256_slow_reseed(struct yarrow256_ctx *ctx)
215 216 217 218
{
  uint8_t digest[SHA256_DIGEST_SIZE];
  unsigned i;

219
#if YARROW_DEBUG
220
  fprintf(stderr, "yarrow256_slow_reseed\n");
Niels Möller's avatar
Niels Möller committed
221 222
#endif

223 224 225 226
  /* Get digest of the slow pool*/
  sha256_digest(&ctx->pools[YARROW_SLOW], sizeof(digest), digest);

  /* Feed it into the fast pool */
227
  sha256_update(&ctx->pools[YARROW_FAST], sizeof(digest), digest);
228

229
  yarrow256_fast_reseed(ctx);
230 231 232 233 234 235
  
  /* Reset estimates. */
  for (i = 0; i<ctx->nsources; i++)
    ctx->sources[i].estimate[YARROW_SLOW] = 0;
}

236
int
237 238
yarrow256_update(struct yarrow256_ctx *ctx,
		 unsigned source_index, unsigned entropy,
239
		 size_t length, const uint8_t *data)
240 241 242 243 244 245 246 247
{
  enum yarrow_pool_id current;
  struct yarrow_source *source;
  
  assert(source_index < ctx->nsources);

  if (!length)
    /* Nothing happens */
248
    return 0;
249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280

  source = &ctx->sources[source_index];
  
  if (!ctx->seeded)
    /* While seeding, use the slow pool */
    current = YARROW_SLOW;
  else
    {
      current = source->next;
      source->next = !source->next;
    }

  sha256_update(&ctx->pools[current], length, data);
 
  /* NOTE: We should be careful to avoid overflows in the estimates. */
  if (source->estimate[current] < YARROW_MAX_ENTROPY)
    {
      if (entropy > YARROW_MAX_ENTROPY)
	entropy = YARROW_MAX_ENTROPY;

      if ( (length < (YARROW_MAX_ENTROPY / YARROW_MULTIPLIER))
	   && (entropy > YARROW_MULTIPLIER * length) )
	entropy = YARROW_MULTIPLIER * length;

      entropy += source->estimate[current];
      if (entropy > YARROW_MAX_ENTROPY)
	entropy = YARROW_MAX_ENTROPY;

      source->estimate[current] = entropy;
    }

  /* Check for seed/reseed */
281 282 283
  switch(current)
    {
    case YARROW_FAST:
284
#if YARROW_DEBUG
Niels Möller's avatar
Niels Möller committed
285 286 287 288 289
      fprintf(stderr,
              "yarrow256_update: source_index = %d,\n"
              "            fast pool estimate = %d\n",
              source_index, source->estimate[YARROW_FAST]);
#endif
290 291
      if (source->estimate[YARROW_FAST] >= YARROW_FAST_THRESHOLD)
	{
292
	  yarrow256_fast_reseed(ctx);
293 294 295 296 297
	  return 1;
	}
      else
	return 0;

298 299
    case YARROW_SLOW:
      {
300
        if (!yarrow256_needed_sources(ctx))
301
	  {
302
	    yarrow256_slow_reseed(ctx);
303
	    return 1;
304
	  }
305 306
	else
	  return 0;
307
      }
308 309
    default:
      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 320
  for (i = 0; i < sizeof(key); i+= AES_BLOCK_SIZE)
    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 329
{
  assert(ctx->seeded);

330
  while (length >= AES_BLOCK_SIZE)
331
    {
332
      yarrow_generate_block(ctx, dst);
333 334 335 336 337
      dst += AES_BLOCK_SIZE;
      length -= AES_BLOCK_SIZE;
    }
  if (length)
    {
338 339
      uint8_t buffer[AES_BLOCK_SIZE];
      
340
      assert(length < AES_BLOCK_SIZE);
341 342
      yarrow_generate_block(ctx, buffer);
      memcpy(dst, buffer, length);
343
    }
344
  yarrow_gate(ctx);
345
}
346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374

int
yarrow256_is_seeded(struct yarrow256_ctx *ctx)
{
  return ctx->seeded;
}

unsigned
yarrow256_needed_sources(struct yarrow256_ctx *ctx)
{
  /* FIXME: This is somewhat inefficient. It would be better to
   * either maintain the count, or do this loop only if the
   * current source just crossed the threshold. */
  unsigned k, i;

  for (i = k = 0; i < ctx->nsources; i++)
    if (ctx->sources[i].estimate[YARROW_SLOW] >= YARROW_SLOW_THRESHOLD)
      k++;

#if YARROW_DEBUG
  fprintf(stderr,
          "yarrow256_needed_sources: source_index = %d,\n"
          "                    slow pool estimate = %d,\n"
          "     number of sources above threshold = %d\n",
          source_index, source->estimate[YARROW_SLOW], k);
#endif
  
  return (k < YARROW_SLOW_K) ? (YARROW_SLOW_K - k) : 0;
}