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

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