← Back to branch summary

~zulcss/samba/server-dailies-3.4

« back to all changes in this revision

Viewing changes to source4/heimdal/lib/hcrypto/rand-fortuna.c

  • Committer: Chuck Short
  • Date: 2010-09-28 20:38:39 UTC
  • Revision ID: zulcss@ubuntu.com-20100928203839-pgjulytsi9ue63x1
Initial version

Show diffs side-by-side

added added

removed removed

Lines of Context:
source4/heimdal/lib/hcrypto/rand-fortuna.c
 
1
/*
 
2
 * fortuna.c
 
3
 *              Fortuna-like PRNG.
 
4
 *
 
5
 * Copyright (c) 2005 Marko Kreen
 
6
 * All rights reserved.
 
7
 *
 
8
 * Redistribution and use in source and binary forms, with or without
 
9
 * modification, are permitted provided that the following conditions
 
10
 * are met:
 
11
 * 1. Redistributions of source code must retain the above copyright
 
12
 *        notice, this list of conditions and the following disclaimer.
 
13
 * 2. Redistributions in binary form must reproduce the above copyright
 
14
 *        notice, this list of conditions and the following disclaimer in the
 
15
 *        documentation and/or other materials provided with the distribution.
 
16
 *
 
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 
18
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
19
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 
20
 * ARE DISCLAIMED.      IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 
21
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 
22
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 
23
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 
24
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 
25
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 
26
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 
27
 * SUCH DAMAGE.
 
28
 *
 
29
 * $PostgreSQL: pgsql/contrib/pgcrypto/fortuna.c,v 1.8 2006/10/04 00:29:46 momjian Exp $
 
30
 */
 
31
 
 
32
#ifdef HAVE_CONFIG_H
 
33
#include <config.h>
 
34
#endif
 
35
 
 
36
RCSID("$Id$");
 
37
 
 
38
#include <stdio.h>
 
39
#include <stdlib.h>
 
40
#include <rand.h>
 
41
 
 
42
#include <roken.h>
 
43
 
 
44
#include "randi.h"
 
45
#include "aes.h"
 
46
#include "sha.h"
 
47
 
 
48
/*
 
49
 * Why Fortuna-like: There does not seem to be any definitive reference
 
50
 * on Fortuna in the net.  Instead this implementation is based on
 
51
 * following references:
 
52
 *
 
53
 * http://en.wikipedia.org/wiki/Fortuna_(PRNG)
 
54
 *       - Wikipedia article
 
55
 * http://jlcooke.ca/random/
 
56
 *       - Jean-Luc Cooke Fortuna-based /dev/random driver for Linux.
 
57
 */
 
58
 
 
59
/*
 
60
 * There is some confusion about whether and how to carry forward
 
61
 * the state of the pools.      Seems like original Fortuna does not
 
62
 * do it, resetting hash after each request.  I guess expecting
 
63
 * feeding to happen more often that requesting.   This is absolutely
 
64
 * unsuitable for pgcrypto, as nothing asynchronous happens here.
 
65
 *
 
66
 * J.L. Cooke fixed this by feeding previous hash to new re-initialized
 
67
 * hash context.
 
68
 *
 
69
 * Fortuna predecessor Yarrow requires ability to query intermediate
 
70
 * 'final result' from hash, without affecting it.
 
71
 *
 
72
 * This implementation uses the Yarrow method - asking intermediate
 
73
 * results, but continuing with old state.
 
74
 */
 
75
 
 
76
 
 
77
/*
 
78
 * Algorithm parameters
 
79
 */
 
80
 
 
81
#define NUM_POOLS               32
 
82
 
 
83
/* in microseconds */
 
84
#define RESEED_INTERVAL 100000  /* 0.1 sec */
 
85
 
 
86
/* for one big request, reseed after this many bytes */
 
87
#define RESEED_BYTES    (1024*1024)
 
88
 
 
89
/*
 
90
 * Skip reseed if pool 0 has less than this many
 
91
 * bytes added since last reseed.
 
92
 */
 
93
#define POOL0_FILL              (256/8)
 
94
 
 
95
/*
 
96
 * Algorithm constants
 
97
 */
 
98
 
 
99
/* Both cipher key size and hash result size */
 
100
#define BLOCK                   32
 
101
 
 
102
/* cipher block size */
 
103
#define CIPH_BLOCK              16
 
104
 
 
105
/* for internal wrappers */
 
106
#define MD_CTX                  SHA256_CTX
 
107
#define CIPH_CTX                AES_KEY
 
108
 
 
109
struct fortuna_state
 
110
{
 
111
    unsigned char       counter[CIPH_BLOCK];
 
112
    unsigned char       result[CIPH_BLOCK];
 
113
    unsigned char       key[BLOCK];
 
114
    MD_CTX              pool[NUM_POOLS];
 
115
    CIPH_CTX            ciph;
 
116
    unsigned            reseed_count;
 
117
    struct timeval      last_reseed_time;
 
118
    unsigned            pool0_bytes;
 
119
    unsigned            rnd_pos;
 
120
    int                 tricks_done;
 
121
    pid_t               pid;
 
122
};
 
123
typedef struct fortuna_state FState;
 
124
 
 
125
 
 
126
/*
 
127
 * Use our own wrappers here.
 
128
 * - Need to get intermediate result from digest, without affecting it.
 
129
 * - Need re-set key on a cipher context.
 
130
 * - Algorithms are guaranteed to exist.
 
131
 * - No memory allocations.
 
132
 */
 
133
 
 
134
static void
 
135
ciph_init(CIPH_CTX * ctx, const unsigned char *key, int klen)
 
136
{
 
137
    AES_set_encrypt_key(key, klen * 8, ctx);
 
138
}
 
139
 
 
140
static void
 
141
ciph_encrypt(CIPH_CTX * ctx, const unsigned char *in, unsigned char *out)
 
142
{
 
143
    AES_encrypt(in, out, ctx);
 
144
}
 
145
 
 
146
static void
 
147
md_init(MD_CTX * ctx)
 
148
{
 
149
    SHA256_Init(ctx);
 
150
}
 
151
 
 
152
static void
 
153
md_update(MD_CTX * ctx, const unsigned char *data, int len)
 
154
{
 
155
    SHA256_Update(ctx, data, len);
 
156
}
 
157
 
 
158
static void
 
159
md_result(MD_CTX * ctx, unsigned char *dst)
 
160
{
 
161
    SHA256_CTX  tmp;
 
162
 
 
163
    memcpy(&tmp, ctx, sizeof(*ctx));
 
164
    SHA256_Final(dst, &tmp);
 
165
    memset(&tmp, 0, sizeof(tmp));
 
166
}
 
167
 
 
168
/*
 
169
 * initialize state
 
170
 */
 
171
static void
 
172
init_state(FState * st)
 
173
{
 
174
    int                 i;
 
175
 
 
176
    memset(st, 0, sizeof(*st));
 
177
    for (i = 0; i < NUM_POOLS; i++)
 
178
        md_init(&st->pool[i]);
 
179
    st->pid = getpid();
 
180
}
 
181
 
 
182
/*
 
183
 * Endianess does not matter.
 
184
 * It just needs to change without repeating.
 
185
 */
 
186
static void
 
187
inc_counter(FState * st)
 
188
{
 
189
    uint32_t   *val = (uint32_t *) st->counter;
 
190
 
 
191
    if (++val[0])
 
192
        return;
 
193
    if (++val[1])
 
194
        return;
 
195
    if (++val[2])
 
196
        return;
 
197
    ++val[3];
 
198
}
 
199
 
 
200
/*
 
201
 * This is called 'cipher in counter mode'.
 
202
 */
 
203
static void
 
204
encrypt_counter(FState * st, unsigned char *dst)
 
205
{
 
206
    ciph_encrypt(&st->ciph, st->counter, dst);
 
207
    inc_counter(st);
 
208
}
 
209
 
 
210
 
 
211
/*
 
212
 * The time between reseed must be at least RESEED_INTERVAL
 
213
 * microseconds.
 
214
 */
 
215
static int
 
216
enough_time_passed(FState * st)
 
217
{
 
218
    int                 ok;
 
219
    struct timeval tv;
 
220
    struct timeval *last = &st->last_reseed_time;
 
221
 
 
222
    gettimeofday(&tv, NULL);
 
223
 
 
224
    /* check how much time has passed */
 
225
    ok = 0;
 
226
    if (tv.tv_sec > last->tv_sec + 1)
 
227
        ok = 1;
 
228
    else if (tv.tv_sec == last->tv_sec + 1)
 
229
    {
 
230
        if (1000000 + tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
 
231
            ok = 1;
 
232
    }
 
233
    else if (tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
 
234
        ok = 1;
 
235
 
 
236
    /* reseed will happen, update last_reseed_time */
 
237
    if (ok)
 
238
        memcpy(last, &tv, sizeof(tv));
 
239
 
 
240
    memset(&tv, 0, sizeof(tv));
 
241
 
 
242
    return ok;
 
243
}
 
244
 
 
245
/*
 
246
 * generate new key from all the pools
 
247
 */
 
248
static void
 
249
reseed(FState * st)
 
250
{
 
251
    unsigned    k;
 
252
    unsigned    n;
 
253
    MD_CTX              key_md;
 
254
    unsigned char       buf[BLOCK];
 
255
 
 
256
    /* set pool as empty */
 
257
    st->pool0_bytes = 0;
 
258
 
 
259
    /*
 
260
     * Both #0 and #1 reseed would use only pool 0. Just skip #0 then.
 
261
     */
 
262
    n = ++st->reseed_count;
 
263
 
 
264
    /*
 
265
     * The goal: use k-th pool only 1/(2^k) of the time.
 
266
     */
 
267
    md_init(&key_md);
 
268
    for (k = 0; k < NUM_POOLS; k++)
 
269
    {
 
270
        md_result(&st->pool[k], buf);
 
271
        md_update(&key_md, buf, BLOCK);
 
272
 
 
273
        if (n & 1 || !n)
 
274
            break;
 
275
        n >>= 1;
 
276
    }
 
277
 
 
278
    /* add old key into mix too */
 
279
    md_update(&key_md, st->key, BLOCK);
 
280
 
 
281
    /* add pid to make output diverse after fork() */
 
282
    md_update(&key_md, (const unsigned char *)&st->pid, sizeof(st->pid));
 
283
 
 
284
    /* now we have new key */
 
285
    md_result(&key_md, st->key);
 
286
 
 
287
    /* use new key */
 
288
    ciph_init(&st->ciph, st->key, BLOCK);
 
289
 
 
290
    memset(&key_md, 0, sizeof(key_md));
 
291
    memset(buf, 0, BLOCK);
 
292
}
 
293
 
 
294
/*
 
295
 * Pick a random pool.  This uses key bytes as random source.
 
296
 */
 
297
static unsigned
 
298
get_rand_pool(FState * st)
 
299
{
 
300
    unsigned    rnd;
 
301
 
 
302
    /*
 
303
     * This slightly prefers lower pools - thats OK.
 
304
     */
 
305
    rnd = st->key[st->rnd_pos] % NUM_POOLS;
 
306
 
 
307
    st->rnd_pos++;
 
308
    if (st->rnd_pos >= BLOCK)
 
309
        st->rnd_pos = 0;
 
310
 
 
311
    return rnd;
 
312
}
 
313
 
 
314
/*
 
315
 * update pools
 
316
 */
 
317
static void
 
318
add_entropy(FState * st, const unsigned char *data, unsigned len)
 
319
{
 
320
    unsigned            pos;
 
321
    unsigned char       hash[BLOCK];
 
322
    MD_CTX              md;
 
323
 
 
324
    /* hash given data */
 
325
    md_init(&md);
 
326
    md_update(&md, data, len);
 
327
    md_result(&md, hash);
 
328
 
 
329
    /*
 
330
     * Make sure the pool 0 is initialized, then update randomly.
 
331
     */
 
332
    if (st->reseed_count == 0)
 
333
        pos = 0;
 
334
    else
 
335
        pos = get_rand_pool(st);
 
336
    md_update(&st->pool[pos], hash, BLOCK);
 
337
 
 
338
    if (pos == 0)
 
339
        st->pool0_bytes += len;
 
340
 
 
341
    memset(hash, 0, BLOCK);
 
342
    memset(&md, 0, sizeof(md));
 
343
}
 
344
 
 
345
/*
 
346
 * Just take 2 next blocks as new key
 
347
 */
 
348
static void
 
349
rekey(FState * st)
 
350
{
 
351
    encrypt_counter(st, st->key);
 
352
    encrypt_counter(st, st->key + CIPH_BLOCK);
 
353
    ciph_init(&st->ciph, st->key, BLOCK);
 
354
}
 
355
 
 
356
/*
 
357
 * Hide public constants. (counter, pools > 0)
 
358
 *
 
359
 * This can also be viewed as spreading the startup
 
360
 * entropy over all of the components.
 
361
 */
 
362
static void
 
363
startup_tricks(FState * st)
 
364
{
 
365
    int                 i;
 
366
    unsigned char       buf[BLOCK];
 
367
 
 
368
    /* Use next block as counter. */
 
369
    encrypt_counter(st, st->counter);
 
370
 
 
371
    /* Now shuffle pools, excluding #0 */
 
372
    for (i = 1; i < NUM_POOLS; i++)
 
373
    {
 
374
        encrypt_counter(st, buf);
 
375
        encrypt_counter(st, buf + CIPH_BLOCK);
 
376
        md_update(&st->pool[i], buf, BLOCK);
 
377
    }
 
378
    memset(buf, 0, BLOCK);
 
379
 
 
380
    /* Hide the key. */
 
381
    rekey(st);
 
382
 
 
383
    /* This can be done only once. */
 
384
    st->tricks_done = 1;
 
385
}
 
386
 
 
387
static void
 
388
extract_data(FState * st, unsigned count, unsigned char *dst)
 
389
{
 
390
    unsigned    n;
 
391
    unsigned    block_nr = 0;
 
392
    pid_t       pid = getpid();
 
393
 
 
394
    /* Should we reseed? */
 
395
    if (st->pool0_bytes >= POOL0_FILL || st->reseed_count == 0)
 
396
        if (enough_time_passed(st))
 
397
            reseed(st);
 
398
 
 
399
    /* Do some randomization on first call */
 
400
    if (!st->tricks_done)
 
401
        startup_tricks(st);
 
402
 
 
403
    /* If we forked, force a reseed again */
 
404
    if (pid != st->pid) {
 
405
        st->pid = pid;
 
406
        reseed(st);
 
407
    }
 
408
 
 
409
    while (count > 0)
 
410
    {
 
411
        /* produce bytes */
 
412
        encrypt_counter(st, st->result);
 
413
 
 
414
        /* copy result */
 
415
        if (count > CIPH_BLOCK)
 
416
            n = CIPH_BLOCK;
 
417
        else
 
418
            n = count;
 
419
        memcpy(dst, st->result, n);
 
420
        dst += n;
 
421
        count -= n;
 
422
 
 
423
        /* must not give out too many bytes with one key */
 
424
        block_nr++;
 
425
        if (block_nr > (RESEED_BYTES / CIPH_BLOCK))
 
426
        {
 
427
            rekey(st);
 
428
            block_nr = 0;
 
429
        }
 
430
    }
 
431
    /* Set new key for next request. */
 
432
    rekey(st);
 
433
}
 
434
 
 
435
/*
 
436
 * public interface
 
437
 */
 
438
 
 
439
static FState   main_state;
 
440
static int      init_done;
 
441
static int      have_entropy;
 
442
#define FORTUNA_RESEED_BYTE     10000
 
443
static unsigned resend_bytes;
 
444
 
 
445
/*
 
446
 * Try our best to do an inital seed
 
447
 */
 
448
#define INIT_BYTES      128
 
449
 
 
450
static int
 
451
fortuna_reseed(void)
 
452
{
 
453
    int entropy_p = 0;
 
454
 
 
455
    if (!init_done)
 
456
        abort();
 
457
 
 
458
    {
 
459
        unsigned char buf[INIT_BYTES];
 
460
        if ((*hc_rand_unix_method.bytes)(buf, sizeof(buf)) == 1) {
 
461
            add_entropy(&main_state, buf, sizeof(buf));
 
462
            entropy_p = 1;
 
463
            memset(buf, 0, sizeof(buf));
 
464
        }
 
465
    }
 
466
#ifdef HAVE_ARC4RANDOM
 
467
    {
 
468
        uint32_t buf[INIT_BYTES / sizeof(uint32_t)];
 
469
        int i;
 
470
 
 
471
        for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
 
472
            buf[i] = arc4random();
 
473
        add_entropy(&main_state, (void *)buf, sizeof(buf));
 
474
        entropy_p = 1;
 
475
    }
 
476
#endif
 
477
    /*
 
478
     * Only to get egd entropy if /dev/random or arc4rand failed since
 
479
     * it can be horribly slow to generate new bits.
 
480
     */
 
481
    if (!entropy_p) {
 
482
        unsigned char buf[INIT_BYTES];
 
483
        if ((*hc_rand_egd_method.bytes)(buf, sizeof(buf)) == 1) {
 
484
            add_entropy(&main_state, buf, sizeof(buf));
 
485
            entropy_p = 1;
 
486
            memset(buf, 0, sizeof(buf));
 
487
        }
 
488
    }
 
489
    /*
 
490
     * Fall back to gattering data from timer and secret files, this
 
491
     * is really the last resort.
 
492
     */
 
493
    if (!entropy_p) {
 
494
        /* to save stackspace */
 
495
        union {
 
496
            unsigned char buf[INIT_BYTES];
 
497
            unsigned char shad[1001];
 
498
        } u;
 
499
        int fd;
 
500
 
 
501
        /* add timer info */
 
502
        if ((*hc_rand_timer_method.bytes)(u.buf, sizeof(u.buf)) == 1)
 
503
            add_entropy(&main_state, u.buf, sizeof(u.buf));
 
504
        /* add /etc/shadow */
 
505
        fd = open("/etc/shadow", O_RDONLY, 0);
 
506
        if (fd >= 0) {
 
507
            ssize_t n;
 
508
            rk_cloexec(fd);
 
509
            /* add_entropy will hash the buf */
 
510
            while ((n = read(fd, (char *)u.shad, sizeof(u.shad))) > 0)
 
511
                add_entropy(&main_state, u.shad, sizeof(u.shad));
 
512
            close(fd);
 
513
        }
 
514
 
 
515
        memset(&u, 0, sizeof(u));
 
516
 
 
517
        entropy_p = 1; /* sure about this ? */
 
518
    }
 
519
    {
 
520
        pid_t pid = getpid();
 
521
        add_entropy(&main_state, (void *)&pid, sizeof(pid));
 
522
    }
 
523
    {
 
524
        struct timeval tv;
 
525
        gettimeofday(&tv, NULL);
 
526
        add_entropy(&main_state, (void *)&tv, sizeof(tv));
 
527
    }
 
528
    {
 
529
        uid_t u = getuid();
 
530
        add_entropy(&main_state, (void *)&u, sizeof(u));
 
531
    }
 
532
    return entropy_p;
 
533
}
 
534
 
 
535
static int
 
536
fortuna_init(void)
 
537
{
 
538
    if (!init_done)
 
539
    {
 
540
        init_state(&main_state);
 
541
        init_done = 1;
 
542
    }
 
543
    if (!have_entropy)
 
544
        have_entropy = fortuna_reseed();
 
545
    return (init_done && have_entropy);
 
546
}
 
547
 
 
548
 
 
549
 
 
550
static void
 
551
fortuna_seed(const void *indata, int size)
 
552
{
 
553
    fortuna_init();
 
554
    add_entropy(&main_state, indata, size);
 
555
    if (size >= INIT_BYTES)
 
556
        have_entropy = 1;
 
557
}
 
558
 
 
559
static int
 
560
fortuna_bytes(unsigned char *outdata, int size)
 
561
{
 
562
    if (!fortuna_init())
 
563
        return 0;
 
564
    resend_bytes += size;
 
565
    if (resend_bytes > FORTUNA_RESEED_BYTE || resend_bytes < size) {
 
566
        resend_bytes = 0;
 
567
        fortuna_reseed();
 
568
    }
 
569
    extract_data(&main_state, size, outdata);
 
570
    return 1;
 
571
}
 
572
 
 
573
static void
 
574
fortuna_cleanup(void)
 
575
{
 
576
    init_done = 0;
 
577
    have_entropy = 0;
 
578
    memset(&main_state, 0, sizeof(main_state));
 
579
}
 
580
 
 
581
static void
 
582
fortuna_add(const void *indata, int size, double entropi)
 
583
{
 
584
    fortuna_seed(indata, size);
 
585
}
 
586
 
 
587
static int
 
588
fortuna_pseudorand(unsigned char *outdata, int size)
 
589
{
 
590
    return fortuna_bytes(outdata, size);
 
591
}
 
592
 
 
593
static int
 
594
fortuna_status(void)
 
595
{
 
596
    return fortuna_init() ? 1 : 0;
 
597
}
 
598
 
 
599
const RAND_METHOD hc_rand_fortuna_method = {
 
600
    fortuna_seed,
 
601
    fortuna_bytes,
 
602
    fortuna_cleanup,
 
603
    fortuna_add,
 
604
    fortuna_pseudorand,
 
605
    fortuna_status
 
606
};
 
607
 
 
608
const RAND_METHOD *
 
609
RAND_fortuna_method(void)
 
610
{
 
611
    return &hc_rand_fortuna_method;
 
612
}