![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to random.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [PGP] / pgp / src|
Return to random.c CVS log | Up to [PGP] / pgp / src |
1.1.1.7 root 1: /*
2: * True and cryptographic random number generation.
3: *
4: * (c) Copyright 1990-1994 by Philip Zimmermann. All rights reserved.
5: * The author assumes no liability for damages resulting from the use
6: * of this software, even if the damage results from defects in this
7: * software. No warranty is expressed or implied.
8: *
9: * Note that while most PGP source modules bear Philip Zimmermann's
10: * copyright notice, many of them have been revised or entirely written
11: * by contributors who frequently failed to put their names in their
12: * code. Code that has been incorporated into PGP from other authors
13: * was either originally published in the public domain or is used with
14: * permission from the various authors.
15: *
16: * PGP is available for free to the public under certain restrictions.
17: * See the PGP User's Guide (included in the release package) for
18: * important information about licensing, patent restrictions on
19: * certain algorithms, trademarks, copyrights, and export controls.
20: *
21: * Written by Colin Plumb.
22: */
23:
24: #include <stdlib.h>
25: #include <stdio.h>
26: #include <string.h>
27: #include <assert.h>
28: #include <signal.h> /* For SIGINT */
29: #include <time.h>
30:
31: #include "system.h" /* For ttycbreak, getch, etc. */
32: #include "idea.h"
33: #include "md5.h"
34: #include "noise.h"
35: #include "language.h"
36: #include "random.h"
37: #include "fileio.h" /* For FOPRBIN */
38: #include "pgp.h" /* For globalRandseedName */
39: #include "randpool.h"
40:
1.1.1.8 ! root 41: /*
! 42: * As of PGP 2.6.2, the randseed.bin file has been expanded. An explanation
! 43: * of how the whole thing works in in order, as people are always suspiscious
! 44: * of the random number generator. (After the xorbytes bug in 2.6, perhaps
! 45: * you should be.) There are two random number generators in PGP. One
! 46: * is the "cryptRand" family, which is based on X9.17, but uses IDEA instead
! 47: * of 2-key EDE triple-DES. This is the generator with a lot of peer review.
! 48: * The implementation is in idea.c.
! 49: * The second is the "trueRand" family, which attempt to accurately measure
! 50: * the entropy available from keyboard I/O. It keeps a lot more state.
! 51: * The implementation of this is in randpool.c.
! 52: * Originally, the trueRand generator was only used for generating primes,
! 53: * and the cryptRand for generating IDEA session keys. But things have
! 54: * become a bit more complex. In particular, the X9.17 specification
! 55: * wants a source of high-resolution time-of-day information, as a source
! 56: * of some "true" randomness to throw in. So we use the trueRand pool
! 57: * for that.
! 58: * The cryptRand functions keep a state file around, usually named
! 59: * randseed.bin, for a seed, as the X9.17 generator requires 24 bytes of
! 60: * known initial information.
! 61: * This data in this file is carefully "washed" before and after use to
! 62: * help ensure that if the file is captured or altered, the keys will
! 63: * not be too vulnerable. A washing consists of an encryption in PGP's
! 64: * usual CFB mode of the material coming from or being written to the
! 65: * randseed.bin file on disk. Assuming the cipher is strong, the effects
! 66: * of the wash are as difficult to predict as the key that is used is
! 67: * difficult to guess.
! 68: * Beforehand, we use the MD5 of the file being encrypted as an additional
! 69: * source of randomness (on the theory that an attacker trying to break
! 70: * a session key probably doesn't have the plaintext, or he wouldn't need
! 71: * to bother), and use that as an IDEA key (with a fixed IV of zero)
! 72: * to encrypt the randseed.bin data.
! 73: * After generating an IDEA key and IV, some more random bytes are generated
! 74: * to reinitialize randseed.bin, and these are encrypted in the same manner
! 75: * as the PGP message before being written to disk, on the assumption that
! 76: * if an attacker can decrypt that, they can decrypt the message directly
! 77: * and not bother attacking the randseed.bin file.
! 78: * The previous code only saved the 24 bytes needed by the X9.17 algorithm.
! 79: * But in 2.6.2, we decided to make the randseed.bin file substantially
! 80: * larger to hold more information that a would-be attacker must guess.
! 81: * There are two reasons for this:
! 82: * - Every time you run PGP, especially when responding to one of PGP's
! 83: * prompts, PGP samples the keystrokes for use as random numbers.
! 84: * It is a shame to throw this entropy (randomness) away just because
! 85: * there is no need for it in the current invocation of PGP.
! 86: * - A feature was added to 2.6.2 to generate files full of random bytes
! 87: * for other programs to use as key material. In this case, we haven't
! 88: * got a message we're encrypting to take some entropy from, and we may
! 89: * be asked to generate more than 24 random bytes, so there should be
! 90: * more than 24 bytes of seed material to work from.
! 91: * The implementation is added on to the previous one, to offer assurance
! 92: * that it is no weaker.
! 93: * When the cryptRand generator is opened, the file is washed (if possible)
! 94: * and the first 24 bytes are fed to the cryptographic RNG, while the
! 95: * remainder is added to the trueRand random number pool.
! 96: * When saving, the randseed.bin file is refilled with newly generated
! 97: * bytes, again washed if possible. It turns out (if you study the
! 98: * X9.17 RNG) that each of the 2^64 possible timestamp information
! 99: * values used in generating each 8 bytes of output generates a output
! 100: * value, so the entropy in the trueRand pool is put to good use; this
! 101: * is not just generating more data from 24 bytes of seed.
! 102: * The random pool is opened and saved with a washing key when
! 103: * generating a session key (see make_random_ideakey in crypto.c),
! 104: * but it is also opened (harmless if alreasy open) and saved
! 105: * (harmless if already saved) without a washing key in the exitPGP routine,
! 106: * to mix in any entropy collected in this invocation of PGP even if
! 107: * a session key was not generated.
! 108: */
! 109:
! 110: /*
! 111: * The new randseed size, big enough to hold the full context of the cryptRand
! 112: * and trueRand generators. With the current RANDPOOLBITS of 3072 (384 bytes),
! 113: * that's 408 bytes. It's useless to make it any larger, although if
! 114: * RANDPOOLBITS is increased, it might be an idea to keep this smaller than
! 115: * one disk block on all systems (512 bytes is a good figure to use)
! 116: * so we don't change the space requirements for randseed.bin.
! 117: */
! 118: #define RANDSEED_BYTES (RANDPOOLBITS/8 + 24)
! 119: /* Have we read in the randseed.bin file? */
! 120: static boolean randSeedOpen = 0;
1.1.1.7 root 121: static struct IdeaRandContext randContext;
122:
123: /*
124: * Load the RNG state from the randseed.bin file on disk.
125: * Returns 0 on success, <0 on error.
1.1.1.8 ! root 126: *
! 127: * If cfb is non-zero, prewashes the data by encrypting with it.
1.1.1.7 root 128: */
129: int
1.1.1.8 ! root 130: cryptRandOpen(struct IdeaCfbContext *cfb)
1.1.1.7 root 131: {
1.1.1.8 ! root 132: byte buf[256];
1.1.1.7 root 133: int len;
134: FILE *f;
135:
1.1.1.8 ! root 136: if (randSeedOpen)
! 137: return 0; /* Already open */
1.1.1.7 root 138:
139: f = fopen(globalRandseedName, FOPRBIN);
140: if (!f)
141: return -1;
1.1.1.8 ! root 142:
! 143: /* First get the bare minimum 24 bytes we need for the IDEA RNG */
1.1.1.7 root 144: len = fread((char *)buf, 1, 24, f);
1.1.1.8 ! root 145: if (cfb)
! 146: ideaCfbEncrypt(cfb, buf, buf, 24);
1.1.1.7 root 147: ideaRandInit(&randContext, buf, buf+16);
1.1.1.8 ! root 148: randSeedOpen = TRUE;
! 149: if (len != 24) { /* Error */
! 150: fclose(f);
! 151: return -1;
! 152: }
! 153:
! 154: /* Read any extra into the random pool */
! 155: for (;;) {
! 156: len = fread((char *)buf, 1, sizeof(buf), f);
! 157: if (len <= 0)
! 158: break;
! 159: if (cfb)
! 160: ideaCfbEncrypt(cfb, buf, buf, len);
! 161: randPoolAddBytes(buf, len);
! 162: }
1.1.1.7 root 163:
1.1.1.8 ! root 164: fclose(f);
! 165: burn(buf);
! 166: return 0;
1.1.1.7 root 167: }
168:
1.1.1.8 ! root 169: /* Create a new state from the output of trueRandByte */
1.1.1.7 root 170: void
1.1.1.8 ! root 171: cryptRandInit(struct IdeaCfbContext *cfb)
1.1.1.7 root 172: {
1.1.1.8 ! root 173: byte buf[24];
1.1.1.7 root 174: int i;
175:
1.1.1.8 ! root 176: for (i = 0; i < sizeof(buf); i++)
! 177: buf[i] = trueRandByte();
! 178: if (cfb)
! 179: ideaCfbEncrypt(cfb, buf, buf, sizeof(buf));
1.1.1.7 root 180:
1.1.1.8 ! root 181: ideaRandInit(&randContext, buf, buf+16);
! 182: randSeedOpen = TRUE;
! 183: burn(buf);
! 184: }
1.1.1.7 root 185:
1.1.1.8 ! root 186: byte
! 187: cryptRandByte(void)
! 188: {
! 189: if (!randSeedOpen)
! 190: cryptRandOpen((struct IdeaCfbContext *)0);
! 191: return ideaRandByte(&randContext);
1.1.1.7 root 192: }
193:
194: /*
1.1.1.8 ! root 195: * Write out a file of random bytes. If cfb is defined, wash it with the
! 196: * cipher.
1.1.1.7 root 197: */
1.1.1.8 ! root 198: int
! 199: cryptRandWriteFile(char const *name, struct IdeaCfbContext *cfb, unsigned bytes)
1.1.1.7 root 200: {
1.1.1.8 ! root 201: byte buf[256];
! 202: FILE *f;
! 203: int i, len;
1.1.1.7 root 204:
1.1.1.8 ! root 205: f = fopen(name, FOPWBIN);
! 206: if (!f)
! 207: return -1;
1.1.1.7 root 208:
1.1.1.8 ! root 209: while (bytes) {
! 210: len = (bytes < sizeof(buf)) ? bytes : sizeof(buf);
! 211: for (i = 0; i < len; i++)
! 212: buf[i] = ideaRandByte(&randContext);
! 213: if (cfb)
! 214: ideaCfbEncrypt(cfb, buf, buf, len);
! 215: i = fwrite(buf, 1, len, f);
! 216: if (i < len)
! 217: break;
! 218: bytes -= len;
! 219: }
! 220:
! 221: return (fclose(f) != 0 || bytes != 0) ? -1 : 0;
1.1.1.7 root 222: }
223:
224: /*
1.1.1.8 ! root 225: * Create a new RNG state, encrypt it with the supplied key, and save it
! 226: * out to disk.
1.1.1.7 root 227: *
1.1.1.8 ! root 228: * When we encrypt a file, the saved data is "postwashed" using the
! 229: * same key and initial vector (including the repeated check bytes and
! 230: * everything) that is used to encrypt the user's message.
1.1.1.7 root 231: * The hope is that this "postwash" renders it is at least as hard to
232: * derive old session keys from randseed.bin as it is to crack the the
233: * message directly.
234: *
235: * The purpose of using EXACTLY the same encryption is to make sure that
236: * there isn't related, but different data floating around that can be
237: * used for cryptanalysis.
1.1.1.8 ! root 238: *
! 239: * This function is always called by exitPGP, without a washing encryption,
! 240: * so this function ignores that call if it has previously been called
! 241: * to save washed bytes.
1.1.1.7 root 242: */
243: void
1.1.1.8 ! root 244: cryptRandSave(struct IdeaCfbContext *cfb)
1.1.1.7 root 245: {
1.1.1.8 ! root 246: static boolean savedwashed = FALSE;
1.1.1.7 root 247:
1.1.1.8 ! root 248: if (!randSeedOpen)
! 249: return; /* Do nothing */
1.1.1.7 root 250:
1.1.1.8 ! root 251: if (cfb)
! 252: savedwashed = TRUE;
! 253: else if (savedwashed)
! 254: return; /* Don't re-save if it's already been saved washed. */
! 255:
! 256: (void)cryptRandWriteFile(globalRandseedName, cfb, RANDSEED_BYTES);
1.1.1.7 root 257: }
258:
259: /*
260: * True random bit handling
261: */
262:
263: /*
264: * Because these truly random bytes are so unwieldy to accumulate,
265: * they can be regarded as a precious resource. Unfortunately,
266: * cryptographic key generation algorithms may require a great many
267: * random bytes while searching about for large random prime numbers.
268: * Fortunately, they need not all be truly random. We only need as
269: * many truly random bits as there are bits in the large prime we
270: * are searching for. These random bytes can be recycled and modified
271: * via pseudorandom numbers until the key is generated, without losing
272: * any of the integrity of randomness of the final key.
273: *
274: * The technique used is a pool of random numbers, which bytes are
275: * taken from successively and, when the end is reached, the pool
276: * is stirred using an irreversible hash function. Some (64 bytes)
277: * of the pool is not returned to ensure the sequence is not predictible
278: * from the values retriefed from trueRandByte(). To be precise,
279: * MD5Transform is used as a block cipher in CBC mode, and then the
280: * "key" (i.e. what is usually the material to be hashed) is overwritten
281: * with some of the just-generated random bytes.
282: *
283: * This is implemented in randpool.c; see that file for details.
284: *
285: * An estimate of the number of bits of true (Shannon) entropy in the
286: * pool is kept in trueRandBits. This is incremented when timed
287: * keystrokes are available, and decremented when bits are explicitly
288: * consumed for some purpose (such as prime generation) or another.
289: *
290: * trueRandFlush is called to obliterate traces of old random bits after
291: * prime generation is completed. (Primes are the most carefully-guarded
292: * values in PGP.)
293: */
294:
295: static unsigned trueRandBits = 0; /* Bits of entropy in pool */
296:
297: /* trueRandPending is bits to add to next accumulation request */
298: static unsigned trueRandPending = 0;
299:
300: /*
301: * Destroys already-used random numbers. Ensures no sensitive data
302: * remains in memory that can be recovered later. This is called
303: * after RSA key generation, so speed is not critical, but security is.
304: * RSA key generation takes long enough that interrupts and other
305: * tasks are likely to have used a measurable and difficult-to-predict
306: * amount of real time, so there is some virtue in sampling the clocks
307: * with noise().
308: */
309: void
310: trueRandFlush(void)
311: {
312: noise();
313: randPoolStir(); /* Destroy evidence of what primes were generated */
314: randPoolStir();
315: randPoolStir();
316: randPoolStir(); /* Make *really* certain */
317: }
318:
319: /*
320: * "Consumes" count bits worth of entropy from the true random pool for some
321: * purpose, such as prime generation.
322: *
323: * Note that something like prime generation can end up calling trueRandByte
324: * more often than is implied by the count passed to trueRandClaim; this
325: * may happen if the random bit consumer is not perfectly efficient in its
326: * use of random bits. For example, if a search for a suitable prime fails,
327: * the easiest thing to do is to get another load of random bits and try
328: * again. It is perfectly acceptable if these bits are correlated with the
329: * bits used in the failed attempt, since they are discarded.
330: */
331: void
332: trueRandConsume(unsigned count)
333: {
334: assert (trueRandBits >= count);
335: trueRandBits -= count;
336: }
337:
338: /*
339: * Returns a truly random byte if any are available. It degenerates to
340: * a pseudorandom value if there are none. It is not an error to call
341: * this if none are available. For example, it is called when generating
342: * session keys to add to other sources of cryptographic random numbers.
343: *
344: * This forces an accumulation if any extra random bytes are pending.
345: */
346: int
347: trueRandByte(void)
348: {
349: if (trueRandPending)
350: trueRandAccum(0);
351:
352: return randPoolGetByte();
353: }
354:
355: /*
356: * Given an event (typically a keystroke) coded by "event"
357: * at a random time, add all randomness to the random pool,
358: * compute a (conservative) estimate of the amount, add it
359: * to the pool, and return the amount of randomness.
360: * (The return value is just for informational purposes.)
361: *
362: * Double events are okay, but three in a row is considered
363: * suspiscous and the randomness is counted as 0.
364: */
365: unsigned
366: trueRandEvent(int event)
367: {
368: static int event1 = 0, event2 = 0;
369: word32 delta;
370: unsigned cbits;
371:
372: delta = noise();
373: randPoolAddBytes((byte *)&event, sizeof(event));
374:
375: if (event == event1 && event == event2) {
376: cbits = 0;
377: } else {
378: event2 = event1;
379: event1 = event;
380:
381: for (cbits = 0; delta; cbits++)
382: delta >>= 1;
383:
384: /* Excessive paranoia? */
385: if (cbits > 8)
386: cbits = 8;
387: }
388:
389: trueRandBits += cbits;
390: if (trueRandBits > RANDPOOLBITS)
391: trueRandBits = RANDPOOLBITS;
392:
393: return cbits;
394: }
395:
396:
397: /*
398: * Since getting random bits from the keyboard requires user attention,
399: * we buffer up requests for them until we can do one big request.
400: */
401: void
402: trueRandAccumLater(unsigned bitcount)
403: {
404: trueRandPending += bitcount; /* Wow, that was easy! :-) */
405: }
406:
407: static void flush_input(void);
408:
409: /*
410: * Performs an accumulation of random bits. As long as there are fewer bits
411: * in the buffer than are needed (the number passed, plus pending bits),
412: * prompt for more.
413: */
414: void
415: trueRandAccum(unsigned count) /* Get this many random bits ready */
416: {
417: int c;
418: #if defined(MSDOS) || defined(__MSDOS__)
419: time_t timer;
420: #endif
421:
422: count += trueRandPending; /* Do deferred accumulation now */
423: trueRandPending = 0;
424:
425: if (count > RANDPOOLBITS)
426: count = RANDPOOLBITS;
427:
428: if (trueRandBits >= count)
429: return;
430:
431: fprintf(stderr,
432: LANG("\nWe need to generate %u random bits. This is done by measuring the\
433: \ntime intervals between your keystrokes. Please enter some random text\
434: \non your keyboard until you hear the beep:\n"), count-trueRandBits);
435:
436: ttycbreak();
437:
438: do {
439: /* display counter to show progress */
440: fprintf(stderr,"\r%4d ", count-trueRandBits);
441: fflush(stderr); /* assure screen update */
442:
443: flush_input(); /* If there's no delay, we can't use it */
444: c = getch(); /* always wait for input */
445: #ifdef MSDOS
446: if (c == 3)
447: breakHandler(SIGINT);
448: if (c == 0)
449: c = getch() + 256;
450: #endif
451: /* Print flag indicating acceptance (or not) */
452: putc(trueRandEvent(c) ? '.' : '?' , stderr);
453: } while (trueRandBits < count);
454:
455: fputs("\r 0 *", stderr);
456: fputs(LANG("\007 -Enough, thank you.\n"), stderr);
457:
458: #if defined(MSDOS) || defined(__MSDOS__)
459: /* Wait until one full second has passed without keyboard input */
460: do {
461: flush_input();
462: sleep(1);
463: } while (kbhit());
464: #else
465: sleep(1);
466: flush_input();
467: #endif
468:
469: ttynorm();
470: }
471:
472: #define BS 8
473: #define LF 10
474: #define CR 13
475: #define DEL 127
476:
477: #ifdef VMS
478: int putch(int);
479: #else
480: #define putch(c) putc(c, stderr)
481: #endif
482:
483: int
484: getstring(char *strbuf, unsigned maxlen, int echo)
485: /* Gets string from user, with no control characters allowed.
486: * Also accumulates random numbers.
487: * maxlen is max length allowed for string.
488: * echo is TRUE iff we should echo keyboard to screen.
489: * Returns null-terminated string in strbuf.
490: */
491: {
492: unsigned i;
493: char c;
494:
495: ttycbreak();
496:
497: #ifdef AMIGA
498: aecho = (int)echo;
499: echo = FALSE; /* echo is done in getch */
500: #endif /* AMIGA */
501:
502: fflush(stdout);
503: i=0;
504: for (;;) {
505: #ifndef VMS
506: fflush(stderr);
507: #endif /* VMS */
508: c = getch();
509: trueRandEvent(c);
510: #ifdef VMS
511: if (c == 25) { /* Control-Y detected */
512: ttynorm();
513: breakHandler(SIGINT);
514: }
515: #endif /* VMS */
516: #if defined(MSDOS) || defined (__MSDOS__)
517: if (c == 3)
518: breakHandler(SIGINT);
519: #endif
520: if (c==BS || c==DEL) {
521: if (i) {
522: if (echo) {
523: putch(BS);
524: putch(' ');
525: putch(BS);
526: }
527: i--;
1.1.1.8 ! root 528: } else {
! 529: putch('\007');
1.1.1.7 root 530: }
531: continue;
532: }
533: if (c < ' ' && c != LF && c != CR) {
534: putch('\007');
535: #if defined(MSDOS) || defined (__MSDOS__)
536: if (c == 3)
537: breakHandler(SIGINT);
538: if (c == 0)
539: getch(); /* Skip extended key codes */
540: #endif
541: continue;
542: }
543: if (echo)
544: putch(c);
545: if (c==CR) {
546: if (echo)
547: putch(LF);
548: break;
549: }
550: if (c==LF)
551: break;
552: if (c=='\n')
553: break;
554: strbuf[i++] = c;
555: if (i >= maxlen) {
556: fputs("\007*\n", stderr); /* -Enough! */
557: #if 0
558: while (kbhit())
559: getch(); /* clean up any typeahead */
560: #endif
561: break;
562: }
563: }
564: strbuf[i] = '\0'; /* null termination of string */
565:
566: ttynorm();
567:
568: return(i); /* returns string length */
569: } /* getstring */
570:
571:
572: static void
573: flush_input(void)
574: { /* on unix ttycbreak() will flush the input queue */
575: #if defined(MSDOS) || defined (__MSDOS__)
576: while (kbhit()) /* flush typahead buffer */
577: getch();
578: #endif
579: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.