Return to random.c CVS log

Up to [PGP] / pgp / src

Annotation of pgp/src/random.c, revision 1.1.1.6

1.1.1.6 ! 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: 
        !            41: static struct IdeaRandContext randContext;
        !            42: static int randInitFlag = 0;
        !            43: 
        !            44: /*
        !            45:  * Load the RNG state from the randseed.bin file on disk.
        !            46:  * Returns 0 on success, <0 on error.
        !            47:  */
        !            48: int
        !            49: cryptRandOpen(void)
        !            50: {
        !            51:        byte buf[24];
        !            52:        int len;
        !            53:        FILE *f;
        !            54: 
        !            55:        if (randInitFlag)
        !            56:                return 0;
        !            57: 
        !            58:        f = fopen(globalRandseedName, FOPRBIN);
        !            59:        if (!f)
        !            60:                return -1;
        !            61:        len = fread((char *)buf, 1, 24, f);
        !            62:        fclose(f);
        !            63:        ideaRandInit(&randContext, buf, buf+16);
        !            64:        randInitFlag = 1;
        !            65: 
        !            66:        return (len == 24) ? 0 : -1;
        !            67: }
        !            68: 
        !            69: void
        !            70: cryptRandCreate(void)
        !            71: {
        !            72:        byte randbuf[24];
        !            73:        int i;
        !            74:        FILE *f;
        !            75: 
        !            76:        for (i = 0; i < 24; i++)
        !            77:                randbuf[i] = trueRandByte();
        !            78: 
        !            79:        ideaRandInit(&randContext, (byte *)randbuf, (byte *)randbuf+16);
        !            80:        randInitFlag = 1;
        !            81: 
        !            82:        f = fopen(globalRandseedName, FOPWBIN);
        !            83:        if (f) {
        !            84:                fwrite(randbuf, 1, 24, f);
        !            85:                fclose(f);
        !            86:        }
        !            87:        return;
        !            88: }
        !            89: 
        !            90: /*
        !            91:  * Encrypt the state of the PRNG with the given key.  It is intended
        !            92:  * that this key is the md5 of the message to be encrypted, which is
        !            93:  * unpredictable to a would-be attacker who does not posess the message.
        !            94:  * This is simply a way to get some "random" bytes without a random
        !            95:  * number source.  This "prewash" attempts to reduce the value of a
        !            96:  * captured randseed.bin file.
        !            97:  */
        !            98: void
        !            99: cryptRandWash(byte const key[16])
        !           100: {
        !           101:        struct IdeaCfbContext cfb;
        !           102: 
        !           103:        if (!randInitFlag)
        !           104:                cryptRandOpen();
        !           105:        ideaCfbInit(&cfb, key);
        !           106:        ideaRandWash(&randContext, &cfb);
        !           107:        ideaCfbDestroy(&cfb);
        !           108: }
        !           109: 
        !           110: byte
        !           111: cryptRandByte(void)
        !           112: {
        !           113:        if (!randInitFlag)
        !           114:                cryptRandOpen();
        !           115:        return ideaRandByte(&randContext);
        !           116: }
        !           117: 
        !           118: /*
        !           119:  * Create a new RNG state, encrypt it with the session key, and save it
        !           120:  * out to disk.  The RNG is re-initialized with the saved parameters.
        !           121:  *
        !           122:  * This uses the same key and initial vector (including the repeated
        !           123:  * check bytes and everything) that is used to encrypt the user's message.
        !           124:  * The hope is that this "postwash" renders it is at least as hard to
        !           125:  * derive old session keys from randseed.bin as it is to crack the the
        !           126:  * message directly.
        !           127:  *
        !           128:  * The purpose of using EXACTLY the same encryption is to make sure that
        !           129:  * there isn't related, but different data floating around that can be
        !           130:  * used for cryptanalysis.
        !           131:  */
        !           132: void
        !           133: cryptRandSave(byte const key[16], byte const iv[8])
        !           134: {
        !           135:        struct IdeaCfbContext cfb;
        !           136:        byte buf[24];
        !           137:        FILE *f;
        !           138:        int i;
        !           139: 
        !           140:        /* This IV is EXACTLY the same as is used on bulk files. */
        !           141:        memcpy(buf, iv, 8);
        !           142:        buf[8] = buf[6];        /* "check bytes" */
        !           143:        buf[9] = buf[7];
        !           144: 
        !           145:        ideaCfbInit(&cfb, key);
        !           146:        ideaCfbEncrypt(&cfb, buf, buf, 10);
        !           147:        ideaCfbSync(&cfb);
        !           148:        for (i = 0; i < 24; i++)
        !           149:                buf[i] = ideaRandByte(&randContext);
        !           150:        ideaCfbEncrypt(&cfb, buf, buf, 24);
        !           151:        ideaCfbDestroy(&cfb);
        !           152:        ideaRandInit(&randContext, buf, buf+16);
        !           153: 
        !           154:        f = fopen(globalRandseedName, FOPWBIN);
        !           155:        if (f) {
        !           156:                fwrite(buf, 1, 24, f);
        !           157:                fclose(f);
        !           158:        }
        !           159: }
        !           160: 
        !           161: /*
        !           162:  * True random bit handling
        !           163:  */
        !           164: 
        !           165: /*
        !           166:  * Because these truly random bytes are so unwieldy to accumulate,
        !           167:  * they can be regarded as a precious resource.  Unfortunately,
        !           168:  * cryptographic key generation algorithms may require a great many
        !           169:  * random bytes while searching about for large random prime numbers.
        !           170:  * Fortunately, they need not all be truly random.  We only need as
        !           171:  * many truly random bits as there are bits in the large prime we
        !           172:  * are searching for.  These random bytes can be recycled and modified
        !           173:  * via pseudorandom numbers until the key is generated, without losing
        !           174:  * any of the integrity of randomness of the final key.
        !           175:  *
        !           176:  * The technique used is a pool of random numbers, which bytes are
        !           177:  * taken from successively and, when the end is reached, the pool
        !           178:  * is stirred using an irreversible hash function.  Some (64 bytes)
        !           179:  * of the pool is not returned to ensure the sequence is not predictible
        !           180:  * from the values retriefed from trueRandByte().  To be precise,
        !           181:  * MD5Transform is used as a block cipher in CBC mode, and then the
        !           182:  * "key" (i.e. what is usually the material to be hashed) is overwritten
        !           183:  * with some of the just-generated random bytes.
        !           184:  *
        !           185:  * This is implemented in randpool.c; see that file for details.
        !           186:  *
        !           187:  * An estimate of the number of bits of true (Shannon) entropy in the
        !           188:  * pool is kept in trueRandBits.  This is incremented when timed
        !           189:  * keystrokes are available, and decremented when bits are explicitly
        !           190:  * consumed for some purpose (such as prime generation) or another.
        !           191:  *
        !           192:  * trueRandFlush is called to obliterate traces of old random bits after
        !           193:  * prime generation is completed.  (Primes are the most carefully-guarded
        !           194:  * values in PGP.)
        !           195:  */
        !           196: 
        !           197: static unsigned trueRandBits = 0;      /* Bits of entropy in pool */
        !           198: 
        !           199: /* trueRandPending is bits to add to next accumulation request */
        !           200: static unsigned trueRandPending = 0;
        !           201: 
        !           202: /*
        !           203:  * Destroys already-used random numbers.  Ensures no sensitive data
        !           204:  * remains in memory that can be recovered later.  This is called
        !           205:  * after RSA key generation, so speed is not critical, but security is.
        !           206:  * RSA key generation takes long enough that interrupts and other
        !           207:  * tasks are likely to have used a measurable and difficult-to-predict
        !           208:  * amount of real time, so there is some virtue in sampling the clocks
        !           209:  * with noise().
        !           210:  */
        !           211: void
        !           212: trueRandFlush(void)
        !           213: {
        !           214:        noise();
        !           215:        randPoolStir(); /* Destroy evidence of what primes were generated */
        !           216:        randPoolStir();
        !           217:        randPoolStir();
        !           218:        randPoolStir(); /* Make *really* certain */
        !           219: }
        !           220: 
        !           221: /*
        !           222:  * "Consumes" count bits worth of entropy from the true random pool for some
        !           223:  * purpose, such as prime generation.
        !           224:  *
        !           225:  * Note that something like prime generation can end up calling trueRandByte
        !           226:  * more often than is implied by the count passed to trueRandClaim; this
        !           227:  * may happen if the random bit consumer is not perfectly efficient in its
        !           228:  * use of random bits.  For example, if a search for a suitable prime fails,
        !           229:  * the easiest thing to do is to get another load of random bits and try
        !           230:  * again.  It is perfectly acceptable if these bits are correlated with the
        !           231:  * bits used in the failed attempt, since they are discarded.
        !           232:  */
        !           233: void
        !           234: trueRandConsume(unsigned count)
        !           235: {
        !           236:        assert (trueRandBits >= count);
        !           237:        trueRandBits -= count;
        !           238: }
        !           239: 
        !           240: /*
        !           241:  * Returns a truly random byte if any are available.  It degenerates to
        !           242:  * a pseudorandom value if there are none.  It is not an error to call
        !           243:  * this if none are available.  For example, it is called when generating
        !           244:  * session keys to add to other sources of cryptographic random numbers.
        !           245:  *
        !           246:  * This forces an accumulation if any extra random bytes are pending.
        !           247:  */
        !           248: int
        !           249: trueRandByte(void)
        !           250: {
        !           251:        if (trueRandPending)
        !           252:                trueRandAccum(0);
        !           253: 
        !           254:        return randPoolGetByte();
        !           255: }
        !           256: 
        !           257: /*
        !           258:  * Given an event (typically a keystroke) coded by "event"
        !           259:  * at a random time, add all randomness to the random pool,
        !           260:  * compute a (conservative) estimate of the amount, add it
        !           261:  * to the pool, and return the amount of randomness.
        !           262:  * (The return value is just for informational purposes.)
        !           263:  *
        !           264:  * Double events are okay, but three in a row is considered
        !           265:  * suspiscous and the randomness is counted as 0.
        !           266:  */
        !           267: unsigned
        !           268: trueRandEvent(int event)
        !           269: {
        !           270:        static int event1 = 0, event2 = 0;
        !           271:        word32 delta;
        !           272:        unsigned cbits;
        !           273: 
        !           274:        delta = noise();
        !           275:        randPoolAddBytes((byte *)&event, sizeof(event));
        !           276: 
        !           277:        if (event == event1 && event == event2) {
        !           278:                cbits = 0;
        !           279:        } else {
        !           280:                event2 = event1;
        !           281:                event1 = event;
        !           282: 
        !           283:                for (cbits = 0; delta; cbits++)
        !           284:                        delta >>= 1;
        !           285: 
        !           286:                /* Excessive paranoia? */
        !           287:                if (cbits > 8)
        !           288:                        cbits = 8;
        !           289:        }
        !           290: 
        !           291:        trueRandBits += cbits;
        !           292:        if (trueRandBits > RANDPOOLBITS)
        !           293:                trueRandBits = RANDPOOLBITS;
        !           294: 
        !           295:        return cbits;
        !           296: }
        !           297: 
        !           298: 
        !           299: /*
        !           300:  * Since getting random bits from the keyboard requires user attention,
        !           301:  * we buffer up requests for them until we can do one big request.
        !           302:  */
        !           303: void
        !           304: trueRandAccumLater(unsigned bitcount)
        !           305: {
        !           306:        trueRandPending += bitcount;    /* Wow, that was easy! :-) */
        !           307: }
        !           308: 
        !           309: static void flush_input(void);
        !           310: 
        !           311: /*
        !           312:  * Performs an accumulation of random bits.  As long as there are fewer bits
        !           313:  * in the buffer than are needed (the number passed, plus pending bits),
        !           314:  * prompt for more.
        !           315:  */
        !           316: void
        !           317: trueRandAccum(unsigned count)  /* Get this many random bits ready */
        !           318: {
        !           319:        int c;
        !           320: #if defined(MSDOS) || defined(__MSDOS__)
        !           321:        time_t timer;
        !           322: #endif
        !           323: 
        !           324:        count += trueRandPending;       /* Do deferred accumulation now */
        !           325:        trueRandPending = 0;
        !           326: 
        !           327:        if (count > RANDPOOLBITS)
        !           328:                count = RANDPOOLBITS;
        !           329: 
        !           330:        if (trueRandBits >= count)
        !           331:                return;
        !           332: 
        !           333:        fprintf(stderr,
        !           334: LANG("\nWe need to generate %u random bits.  This is done by measuring the\
        !           335: \ntime intervals between your keystrokes.  Please enter some random text\
        !           336: \non your keyboard until you hear the beep:\n"), count-trueRandBits);
        !           337: 
        !           338:        ttycbreak();
        !           339: 
        !           340:        do {
        !           341:                /* display counter to show progress */
        !           342:                fprintf(stderr,"\r%4d ", count-trueRandBits);
        !           343:                fflush(stderr); /* assure screen update */
        !           344: 
        !           345:                flush_input();  /* If there's no delay, we can't use it */
        !           346:                c = getch();    /* always wait for input */
        !           347: #ifdef MSDOS
        !           348:                if (c == 3)
        !           349:                        breakHandler(SIGINT);
        !           350:                if (c == 0)
        !           351:                        c = getch() + 256;
        !           352: #endif
        !           353:                /* Print flag indicating acceptance (or not) */
        !           354:                putc(trueRandEvent(c) ? '.' : '?' , stderr);
        !           355:        } while (trueRandBits < count);
        !           356: 
        !           357:        fputs("\r   0 *", stderr);
        !           358:        fputs(LANG("\007 -Enough, thank you.\n"), stderr);
        !           359: 
        !           360: #if defined(MSDOS) || defined(__MSDOS__)
        !           361:        /* Wait until one full second has passed without keyboard input */
        !           362:        do {
        !           363:                flush_input();
        !           364:                sleep(1);
        !           365:        } while (kbhit());
        !           366: #else
        !           367:        sleep(1);
        !           368:        flush_input();
        !           369: #endif
        !           370: 
        !           371:        ttynorm();
        !           372: }
        !           373: 
        !           374: #define BS 8
        !           375: #define LF 10
        !           376: #define CR 13
        !           377: #define DEL 127
        !           378: 
        !           379: #ifdef VMS
        !           380: int putch(int);
        !           381: #else
        !           382: #define putch(c) putc(c, stderr)
        !           383: #endif
        !           384: 
        !           385: int
        !           386: getstring(char *strbuf, unsigned maxlen, int echo)
        !           387: /* Gets string from user, with no control characters allowed.
        !           388:  * Also accumulates random numbers.
        !           389:  * maxlen is max length allowed for string.
        !           390:  * echo is TRUE iff we should echo keyboard to screen.
        !           391:  * Returns null-terminated string in strbuf.
        !           392:  */
        !           393: {
        !           394:        unsigned i;
        !           395:        char c;
        !           396: 
        !           397:        ttycbreak();
        !           398: 
        !           399: #ifdef AMIGA
        !           400:        aecho = (int)echo;
        !           401:        echo = FALSE;   /* echo is done in getch */
        !           402: #endif  /* AMIGA */
        !           403: 
        !           404:        fflush(stdout);
        !           405:        i=0;
        !           406:        for (;;) {
        !           407: #ifndef VMS
        !           408:                fflush(stderr);
        !           409: #endif /* VMS */
        !           410:                c = getch();
        !           411:                trueRandEvent(c);
        !           412: #ifdef VMS
        !           413:                if (c == 25) {  /*  Control-Y detected */
        !           414:                    ttynorm();
        !           415:                    breakHandler(SIGINT);
        !           416:                }
        !           417: #endif /* VMS */
        !           418: #if defined(MSDOS) || defined (__MSDOS__)
        !           419:                if (c == 3)
        !           420:                        breakHandler(SIGINT);
        !           421: #endif
        !           422:                if (c==BS || c==DEL) {
        !           423:                        if (i) {
        !           424:                                if (echo) {
        !           425:                                        putch(BS);
        !           426:                                        putch(' ');
        !           427:                                        putch(BS);
        !           428:                                }
        !           429:                                i--;
        !           430:                        }
        !           431:                        continue;
        !           432:                }
        !           433:                if (c < ' ' && c != LF && c != CR) {
        !           434:                        putch('\007');
        !           435: #if defined(MSDOS) || defined (__MSDOS__)
        !           436:                        if (c == 3)
        !           437:                                breakHandler(SIGINT);   
        !           438:                        if (c == 0)
        !           439:                                getch(); /* Skip extended key codes */
        !           440: #endif
        !           441:                        continue;
        !           442:                }
        !           443:                if (echo)
        !           444:                        putch(c);
        !           445:                if (c==CR) {
        !           446:                        if (echo)
        !           447:                                putch(LF);
        !           448:                        break;
        !           449:                }
        !           450:                if (c==LF)
        !           451:                        break;
        !           452:                if (c=='\n')
        !           453:                        break;
        !           454:                strbuf[i++] = c;
        !           455:                if (i >= maxlen) {
        !           456:                        fputs("\007*\n", stderr);       /* -Enough! */
        !           457: #if 0
        !           458:                        while (kbhit())
        !           459:                                getch();        /* clean up any typeahead */
        !           460: #endif
        !           461:                        break;
        !           462:                }
        !           463:        }
        !           464:        strbuf[i] = '\0';       /* null termination of string */
        !           465: 
        !           466:        ttynorm();
        !           467: 
        !           468:        return(i);              /* returns string length */
        !           469: } /* getstring */
        !           470: 
        !           471: 
        !           472: static void
        !           473: flush_input(void)
        !           474: {      /* on unix ttycbreak() will flush the input queue */
        !           475: #if defined(MSDOS) || defined (__MSDOS__)
        !           476:        while (kbhit()) /* flush typahead buffer */
        !           477:                getch();
        !           478: #endif
        !           479: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.