chiark - git - mdw - become/blob - src/keygen.c

   1 /* -*-c-*-
   2  *
   3  * $Id: keygen.c,v 1.5 1998/01/12 16:46:05 mdw Exp $
   4  *
   5  * Key generation
   6  *
   7  * (c) 1998 EBI
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of `become'
  13  *
  14  * `Become' is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU General Public License as published by
  16  * the Free Software Foundation; either version 2 of the License, or
  17  * (at your option) any later version.
  18  *
  19  * `Become' is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with `become'; if not, write to the Free Software Foundation,
  26  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  27  */
  28
  29 /*----- Revision history --------------------------------------------------*
  30  *
  31  * $Log: keygen.c,v $
  32  * Revision 1.5  1998/01/12 16:46:05  mdw
  33  * Fix copyright date.
  34  *
  35  * Revision 1.4  1997/12/08 15:29:27  mdw
  36  * Major update: make random number sources configurable.  Generate
  37  * warnings if there isn't enough randomness available.
  38  *
  39  * Revision 1.3  1997/09/17  15:29:28  mdw
  40  * Mix the noise from the key timings with some other environmental noise
  41  * (obtained from `noise_acquire') for a little bit more randomness.
  42  *
  43  * Revision 1.2  1997/08/04 10:24:23  mdw
  44  * Sources placed under CVS control.
  45  *
  46  * Revision 1.1  1997/07/21  13:47:48  mdw
  47  * Initial revision
  48  *
  49  */
  50
  51 /*----- Header files ------------------------------------------------------*/
  52
  53 /* --- ANSI headers --- */
  54
  55 #include <ctype.h>
  56 #include <errno.h>
  57 #include <signal.h>
  58 #include <stdio.h>
  59 #include <stdlib.h>
  60 #include <string.h>
  61
  62 /* --- Unix headers --- */
  63
  64 #include <sys/types.h>
  65 #include <sys/time.h>
  66 #include <fcntl.h>
  67
  68 #include <termios.h>
  69 #include <unistd.h>
  70
  71 /* --- Local headers --- */
  72
  73 #include "config.h"
  74 #include "mdwopt.h"
  75 #include "noise.h"
  76 #include "rand.h"
  77 #include "tx.h"
  78 #include "utils.h"
  79
  80 /*----- Static variables --------------------------------------------------*/
  81
  82 static struct termios kg__raw, kg__old; /* Terminal settings */
  83 static int kg__tty;                     /* File handle for the terminal */
  84 static FILE *kg__ttyfp;                 /* Stream pointer for terminal */
  85 static unsigned int kg__flags;          /* Various interesting flags */
  86
  87 enum {
  88   kgFlag__cbreak = 1                    /* Terminal is in cbreak mode */
  89 };
  90
  91 /*----- Main code ---------------------------------------------------------*/
  92
  93 /* --- @kg__cbreak@ --- *
  94  *
  95  * Arguments:   ---
  96  *
  97  * Returns:     ---
  98  *
  99  * Use:         Makes the terminal return characters as soon as they're
 100  *              asked for.
 101  */
 102
 103 void kg__cbreak(void)
 104 {
 105   /* --- Don't do this if I don't have to --- */
 106
 107   if (kg__flags & kgFlag__cbreak)
 108     return;
 109
 110   /* --- Fetch the old attributes, and remember them --- */
 111
 112   if (tcgetattr(kg__tty, &kg__old))
 113     die("couldn't read terminal attributes: %s", strerror(errno));
 114   memcpy(&kg__raw, &kg__old, sizeof(kg__raw));
 115
 116   /* --- Now modify them for raw mode --- */
 117
 118   kg__raw.c_lflag &= ~(ICANON | ECHO);
 119   kg__raw.c_cc[VTIME] = 0;
 120   kg__raw.c_cc[VMIN] = 1;
 121
 122   /* --- Remember the new state, and away we go --- */
 123
 124   kg__flags |= kgFlag__cbreak;
 125   if (tcsetattr(kg__tty, TCSAFLUSH, &kg__raw))
 126     die("couldn't set terminal attributes: %s", strerror(errno));
 127 }
 128
 129 /* --- @kg__crepair@ --- *
 130  *
 131  * Arguments:   ---
 132  *
 133  * Returns:     ---
 134  *
 135  * Use:         Unbreaks a cbroken tty.  Obvious, innit?
 136  */
 137
 138 static void kg__crepair(void)
 139 {
 140   /* --- Don't do this if I don't have to --- */
 141
 142   if (~kg__flags & kgFlag__cbreak)
 143     return;
 144
 145   /* --- Reset the old attributes --- */
 146
 147   tcsetattr(kg__tty, TCSAFLUSH, &kg__old);
 148   kg__flags &= ~kgFlag__cbreak;
 149 }
 150
 151 /* --- @kg__signal@ --- *
 152  *
 153  * Arguments:   @int sig@ = signal number
 154  *
 155  * Returns:     ---
 156  *
 157  * Use:         Tidies up if I get a signal.
 158  */
 159
 160 static void kg__signal(int sig)
 161 {
 162   kg__crepair();
 163   signal(sig, SIG_DFL);
 164   raise(sig);
 165 }
 166
 167 /* --- @kgFmt__binary@ --- *
 168  *
 169  * Arguments:   @unsigned char *k@ = pointer to key buffer
 170  *              @size_t bits@ = number of bits to write
 171  *              @FILE *fp@ = stream to write on
 172  *
 173  * Returns:     ---
 174  *
 175  * Use:         Writes bits on a stream.
 176  */
 177
 178 static void kgFmt__binary(unsigned char *k, size_t bits, FILE *fp)
 179 {
 180   fwrite(k, 1, bits / 8, fp);
 181 }
 182
 183 /* --- @kgFmt__base64@ --- *
 184  *
 185  * Arguments:   @unsigned char *k@ = pointer to key buffer
 186  *              @size_t bits@ = number of bits to write
 187  *              @FILE *fp@ = stream to write on
 188  *
 189  * Returns:     ---
 190  *
 191  * Use:         Writes bits on a stream in an encoded way.
 192  */
 193
 194 static void kgFmt__base64(unsigned char *k, size_t bits, FILE *fp)
 195 {
 196   static const char xlt[64] = { "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 197                                 "abcdefghijklmnopqrstuvwxyz"
 198                                 "0123456789+/" };
 199   unsigned long b;
 200   int ll = 0;
 201
 202   while (bits > 24) {
 203     b = ((k[0] & 0xffu) << 16) | ((k[1] & 0xffu) << 8) | (k[2] & 0xffu);
 204     k += 3;
 205     bits -= 24;
 206     putc(xlt[(b >> 18) & 0x3fu], fp);
 207     putc(xlt[(b >> 12) & 0x3fu], fp);
 208     putc(xlt[(b >>  6) & 0x3fu], fp);
 209     putc(xlt[(b >>  0) & 0x3fu], fp);
 210     if ((ll += 4) > 70) {
 211       putc('\n', fp);
 212       ll = 0;
 213     }
 214   }
 215
 216   b = 0;
 217   switch (bits) {
 218     case 24:
 219       b = *k++ & 0xffu;
 220     case 16:
 221       b = (b << 8) | (*k++ & 0xffu);
 222     case 8:
 223       b = (b << 8) | (*k++ & 0xffu);
 224   }
 225   b <<= (24 - bits);
 226   putc(xlt[(b >> 18) & 0x3fu], fp);
 227   putc(xlt[(b >> 12) & 0x3fu], fp);
 228   switch (bits) {
 229     case 24:
 230       putc(xlt[(b >>  6) & 0x3fu], fp);
 231       putc(xlt[(b >>  0) & 0x3fu], fp);
 232       break;
 233     case 16:
 234       putc(xlt[(b >>  6) & 0x3fu], fp);
 235       putc('=', fp);
 236       break;
 237     case 8:
 238       fputs("==", fp);
 239       break;
 240   }
 241
 242   putc('\n', fp);
 243 }
 244
 245 /* --- @kg__gen@ --- *
 246  *
 247  * Arguments:   @unsigned char *ui@ = pointer to array to fill in
 248  *              @size_t sz@ = number of bits to generate
 249  *
 250  * Returns:     ---
 251  *
 252  * Use:         Uses key timings to generate random numbers.  Maybe.
 253  */
 254
 255 static void kg__gen(unsigned char *ui, size_t sz)
 256 {
 257   int bits = 32 < sz ? 32 : sz;
 258   size_t wsz = (sz + 31u) & ~31u;
 259   unsigned long last, ldiff = 0;
 260   unsigned long a = 0;
 261   unsigned long fact = 1000000 / CLOCKS_PER_SEC;
 262
 263   fprintf(kg__ttyfp,
 264 "I need to get %lu random bits; I'll do this by timing your keypresses.\n"
 265 "Please type some arbitrary text until I say `done'.\n",
 266           (unsigned long)sz);
 267
 268   {
 269     struct timeval tv;
 270     gettimeofday(&tv, 0);
 271     last = tv.tv_usec / fact + tv.tv_sec * fact;
 272   }
 273
 274   while (sz) {
 275     int useful;
 276     uint_32 orr, xor;
 277
 278     /* --- Print current status --- */
 279
 280     fprintf(kg__ttyfp, "\r%5lu...", (unsigned long)sz);
 281     fflush(kg__ttyfp);
 282
 283     /* --- Read the next character --- */
 284
 285     {
 286       char buff[16];
 287       if (read(kg__tty, buff, sizeof(buff)) < 0)
 288         die("couldn't read from terminal: %s", strerror(errno));
 289     }
 290
 291     /* --- Fiddle with times --- *
 292      *
 293      * Read the time now.  Turn it into 32 bits of useful information, and
 294      * find the difference between that and the previous time.  Compare this
 295      * with the difference between the previous pair of keypresses.
 296      */
 297
 298     {
 299       struct timeval tv;
 300       uint_32 n, nd;
 301
 302       gettimeofday(&tv, 0);
 303       n = tv.tv_usec / fact + tv.tv_sec * fact;
 304       if (!ldiff) {
 305         ldiff = n - last;
 306         last = n;
 307         continue;
 308       }
 309       nd = n - last;
 310       orr = nd | ldiff;
 311       xor = nd ^ ldiff;
 312       D( printf("\nlast = %08lx, next = %08lx, ldiff = %08lx, nd = %08lx\n",
 313                 (unsigned long)last, (unsigned long)n,
 314                 (unsigned long)ldiff, (unsigned long)nd);
 315          printf("xor = %08lx\n", (unsigned long)xor); )
 316       ldiff = nd;
 317       last = n;
 318     }
 319
 320     /* --- Find the useful bits in this value --- *
 321      *
 322      * Find the least significant set bit in @bowl@ and chop it off.  Then
 323      * find the most significant set bit and chop that off two.  The rest is
 324      * probably interesting.
 325      */
 326
 327     {
 328       unsigned long i;
 329
 330       if (!orr || !xor)
 331         continue; /* erk! */
 332
 333       useful = 30;
 334
 335       i = 0x80000000ul;
 336       if (xor & i) {
 337         while (i && (xor & i) != 0) {
 338           i >>= 1;
 339           useful--;
 340         }
 341       } else {
 342         while (i && (xor & i) == 0) {
 343           i >>= 1;
 344           useful--;
 345         }
 346       }
 347       xor &= ~-i;
 348
 349       while ((orr & 1) == 0) {
 350         useful--;
 351         orr >>= 1;
 352         xor >>= 1;
 353       }
 354       xor >>= 1;
 355
 356       if (useful < 1)
 357         continue;
 358     }
 359
 360     /* --- Now add the bits in the mixing bowl to my stash --- *
 361      *
 362      * There are two cases:
 363      *
 364      * 1. I have more bits than will fit into the accumulator.  Then I must
 365      *    put as many bits into the accumulator as will fit, store the
 366      *    accumulator, and remove the spent bits.
 367      *
 368      * 2. I have too few bits to fit in the accumulator.  Then shift them
 369      *    in and return.
 370      */
 371
 372     while (sz && useful) {
 373
 374       D( printf("got %i bits, need %i/%i: %8lx\n",
 375                 useful, bits, sz, (unsigned long)xor); )
 376
 377       if (useful >= bits) {
 378
 379         D( printf("shifted acc = %08lx\n"
 380                   "   new bits = %08lx\n"
 381                   "     result = %08lx\n",
 382                   (unsigned long)(a << bits),
 383                   (unsigned long)(xor >> (useful - bits)),
 384                   (unsigned long)((a << bits) | (xor >> (useful - bits)))); )
 385
 386         a = (a << bits) | (xor >> (useful - bits));
 387
 388         sz -= bits;
 389         wsz -= bits;
 390         useful -= bits;
 391
 392         if (sz == 0) {
 393           a <<= wsz;
 394           bits = 32 - wsz;
 395         } else
 396           bits = 32;
 397
 398         while (bits > 0) {
 399           D( printf("writing %02x\n", (a >> 24) & 0xffu); )
 400           *ui++ = (a >> 24) & 0xffu;
 401           a <<= 8;
 402           bits -= 8;
 403         }
 404         a = 0;
 405
 406         bits = 32 < sz ? 32 : sz;
 407
 408       } else {
 409
 410         D( printf("shifted acc = %08lx\n"
 411                   "   new bits = %08lx\n"
 412                   "     result = %08lx\n",
 413                   (unsigned long)(a << useful),
 414                   (unsigned long)(xor),
 415                   (unsigned long)((a << useful) | (xor))); )
 416         a = (a << useful) | xor;
 417         bits -= useful;
 418         sz -= useful;
 419         wsz -= useful;
 420         useful = 0;
 421       }
 422     }
 423   }
 424
 425   fputs("\rDone!         \n", kg__ttyfp);
 426   putc('\a', kg__ttyfp); fflush(kg__ttyfp);
 427   sleep(1);
 428 }
 429
 430 /* --- @main@ --- *
 431  *
 432  * Arguments:   @int argc@ = number of arguments
 433  *              @char *argv[]@ = array of arguments
 434  *
 435  * Returns:     Zero if it worked, nonzero if it didn't.
 436  *
 437  * Use:         Generates random numbers from the keyboard.
 438  */
 439
 440 int main(int argc, char *argv[])
 441 {
 442   unsigned char *uip;
 443   size_t sz = 128;
 444   size_t keybits = 0;
 445   unsigned f = 0;
 446   const char *file = 0;
 447   FILE *fp;
 448
 449   enum {
 450     f_envNoise = 1,
 451     f_keyTimer = 2
 452   };
 453
 454   /* --- Formats table --- */
 455
 456   static struct {
 457     const char *name;
 458     void (*proc)(unsigned char *k, size_t bits, FILE *fp);
 459   } format[] = {
 460     { "tx",     tx_putBits },
 461     { "hex",    tx_putBits },
 462     { "binary", kgFmt__binary },
 463     { "base64", kgFmt__base64 },
 464     { 0, 0 }
 465   };
 466
 467   void (*fmt)(unsigned char *, size_t, FILE *) = tx_putBits;
 468
 469   /* --- Explain who I am --- */
 470
 471   ego(argv[0]);
 472
 473   f |= f_envNoise | f_keyTimer;
 474
 475   /* --- Read arguments --- */
 476
 477   for (;;) {
 478     static struct option opts[] = {
 479       { "help",         0,                              0,      'h' },
 480       { "bits",         gFlag_argReq,                   0,      'b' },
 481       { "output",       gFlag_argReq,                   0,      'o' },
 482       { "format",       gFlag_argReq,                   0,      'f' },
 483       { "key-times",    gFlag_negate|gFlag_argOpt,      0,      'k' },
 484       { "env-noise",    gFlag_negate,                   0,      'e' },
 485       { 0,              0,                              0,      0 }
 486     };
 487
 488     int i = mdwopt(argc, argv, "hb:o:f:k+::e+", opts, 0, 0, gFlag_negation);
 489
 490     if (i < 0)
 491       break;
 492     switch (i) {
 493       case 'h':
 494         printf(""
 495 "Usage: %s [-h] [-|+ek] [-b BITS] [-o FILE] [-f FORMAT]\n"
 496 "\n"
 497 "Generates BITS (by default, 128) random bits.  The resulting number is\n"
 498 "written to FILE, or standard output.\n\n"
 499 "Randomness is taken from key-timings and environmental noise, although\n"
 500 "you can disable either (or both) of these sources.\n\n"
 501 "Options provided are:\n\n"
 502 "-h, --help                     Display this help text\n"
 503 "-b, --bits=BITS\t              Generate BITS random bits instead of 128\n"
 504 "-o, --output=FILE              Write bits to FILE, not standard output\n"
 505 "-f, --format=FORMAT            Write bits in FORMAT:\n"
 506 "                                 tx, hex  Hexadecimal\n"
 507 "                                 binary   Raw binary\n"
 508 "                                 base64   Base64-encoded binary\n"
 509 "-e, --[no-]env-noise           Do [not] read environmental noise\n"
 510 "-k, --[no-]key-times[=BITS]    Do [not] read key timing information\n"
 511 "                                 (only read BITS bits from key timings)\n",
 512                quis());
 513         exit(0);
 514         break;
 515       case 'b':
 516         sz = atoi(optarg);
 517         if (sz == 0)
 518           die("bad number of bits (illegible or zero)");
 519         if (sz % 8)
 520           die("can only generate a whole number of 8-bit bytes");
 521         break;
 522       case 'o':
 523         file = optarg;
 524         break;
 525       case 'f':
 526         fmt = 0;
 527         for (i = 0; format[i].name; i++) {
 528           const char *p = format[i].name, *q = optarg;
 529           for (;;) {
 530             if (*q == 0)
 531               break;
 532             if (*p != *q)
 533               break;
 534             p++, q++;
 535           }
 536           if (!*q) {
 537             if (fmt)
 538               die("ambiguous format name: `%s'", optarg);
 539             fmt = format[i].proc;
 540           }
 541         }
 542         if (!fmt)
 543           die("unknown format name: `%s'", optarg);
 544         break;
 545       case 'e':
 546         f |= f_envNoise;
 547         break;
 548       case 'e' | gFlag_negated:
 549         f &= ~f_envNoise;
 550         break;
 551       case 'k':
 552         f |= f_keyTimer;
 553         if (optarg) {
 554           keybits = atoi(optarg);
 555           if (keybits == 0)
 556             die("bad number of bits (illegible or zero)");
 557           if (keybits % 8)
 558             die("bad number of bits (must be multiple of 8)");
 559         }
 560         else
 561           keybits = 0;
 562         break;
 563       case 'k' | gFlag_negated:
 564         f &= ~f_keyTimer;
 565         break;
 566       case '?':
 567         exit(1);
 568         break;
 569     }
 570   }
 571
 572   /* --- Check the sanity of this request --- */
 573
 574   {
 575     size_t bits = 0;
 576
 577     if (f & f_keyTimer) {
 578       if (!keybits)
 579         keybits = sz;
 580       bits += keybits;
 581     }
 582     if (f & f_envNoise)
 583       bits += 384; /* Estimate */
 584
 585     if (bits == 0)
 586       die("no randomness sources given");
 587     if (bits < sz)
 588       moan("warning: randomness may not be sufficiently high");
 589   }
 590
 591   if (optind < argc) {
 592     fprintf(stderr, "Usage: %s [-opts]\n", quis());
 593     exit(1);
 594   }
 595
 596   /* --- Allocate memory --- */
 597
 598   {
 599     size_t buff = sz / 8;
 600     if (f & f_keyTimer && keybits > sz)
 601       buff = keybits / 8;
 602     uip = xmalloc(buff);
 603   }
 604
 605   rand_clear();
 606
 607   /* --- Fetch randomness from key timings --- */
 608
 609   if (f & f_keyTimer) {
 610
 611     /* --- Open the terminal --- *
 612      *
 613      * I'd like to be able to @fprintf@ to the terminal, so use @fopen@.
 614      */
 615
 616     if ((kg__ttyfp = fopen("/dev/tty", "r+")) == 0)
 617       die("couldn't open terminal: %s", strerror(errno));
 618     kg__tty = fileno(kg__ttyfp);
 619
 620     /* --- Tidy up nicely if I die --- */
 621
 622     signal(SIGINT, kg__signal);
 623     signal(SIGTERM, kg__signal);
 624     atexit(kg__crepair);
 625
 626     /* --- Put the terminal into cbreak, read the key, and restore --- */
 627
 628     kg__cbreak();
 629     kg__gen(uip, keybits);
 630     kg__crepair();
 631     rand_add(uip, keybits / 8);
 632     rand_churn();
 633   }
 634
 635   /* --- Find some noise from the environment too --- */
 636
 637   if (f & f_envNoise) {
 638     noise_acquire();
 639     rand_churn();
 640   }
 641
 642   /* --- Now write the number and exit --- */
 643
 644   rand_extract(uip, sz / 8);
 645   D( fputs("*** ", fp); tx_putBits(uip, sz, stdout); )
 646
 647   /* --- Open the output file, if one is specified --- */
 648
 649   if (file) {
 650     int fd;
 651
 652     /* --- Open the file oddly --- *
 653      *
 654      * There's a good reason for this.  I want to be able to @fprintf@ (for
 655      * the benefit of @tx_putWords@ mainly) but I also want to ensure that
 656      * only the user has read permissions for the file.  So I'll use @open@
 657      * with an appropriate mode and then @fdopen@ the file descriptor to
 658      * get a stream.  Yuk.
 659      */
 660
 661     if ((fd = open(file, O_WRONLY | O_CREAT | O_TRUNC, 0600)) < 0)
 662       die("couldn't open output file: %s", strerror(errno));
 663     if ((fp = fdopen(fd, "w")) == 0)
 664       die("couldn't attach stream to output file: %s", strerror(errno));
 665   } else
 666     fp = stdout;
 667
 668   fmt(uip, sz, fp);
 669   if (file)
 670     fclose(fp);
 671   memset(uip, 0, sz / 8);               /* Burn temporary buffer */
 672   rand_clear();
 673   return (0);
 674 }
 675
 676 /*----- That's all, folks -------------------------------------------------*/