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

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