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

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