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

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