lib/silccrypt/silcrng.c

   1 /*
   2
   3   silcrng.c
   4
   5   Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
   6
   7   Copyright (C) 1997 - 2001 Pekka Riikonen
   8
   9   This program is free software; you can redistribute it and/or modify
  10   it under the terms of the GNU General Public License as published by
  11   the Free Software Foundation; either version 2 of the License, or
  12   (at your option) any later version.
  13
  14   This program is distributed in the hope that it will be useful,
  15   but WITHOUT ANY WARRANTY; without even the implied warranty of
  16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17   GNU General Public License for more details.
  18
  19 */
  20 /* $Id$ */
  21 /*
  22  * Created: Sun Mar  9 00:09:18 1997
  23  *
  24  * The original RNG was based on Secure Shell's random number generator
  25  * by Tatu Ylönen and was used as reference when programming this RNG.
  26  * This RNG has been rewritten twice since the creation.
  27  */
  28
  29 #include "silcincludes.h"
  30
  31 #undef SILC_RNG_DEBUG
  32 /*#define SILC_RNG_DEBUG*/
  33
  34 /* Number of states to fetch data from pool. */
  35 #define SILC_RNG_STATE_NUM 4
  36
  37 /* Byte size of the random data pool. */
  38 #define SILC_RNG_POOLSIZE 1024
  39
  40 static uint32 silc_rng_get_position(SilcRng rng);
  41 static void silc_rng_stir_pool(SilcRng rng);
  42 static void silc_rng_xor(SilcRng rng, uint32 val, unsigned int pos);
  43 static void silc_rng_exec_command(SilcRng rng, char *command);
  44 static void silc_rng_get_hard_noise(SilcRng rng);
  45 static void silc_rng_get_medium_noise(SilcRng rng);
  46 static void silc_rng_get_soft_noise(SilcRng rng);
  47
  48 /*
  49    SILC SilcRng State context.
  50
  51    This object is used by the random number generator to provide
  52    variable points where the actual random number is fetched from
  53    the random pool. This provides that the data is not fetched always
  54    from the same point of the pool. Short description of the fields
  55    following.
  56
  57    uint32 low
  58    uint32 pos
  59
  60        The index for the random pool buffer. Lowest and current
  61        positions.
  62
  63    SilcRngStateContext *next
  64
  65        Pointer to the next state. If this is the last state this
  66        will point to the first state thus providing circular list.
  67
  68 */
  69 typedef struct SilcRngStateContext {
  70   uint32 low;
  71   uint32 pos;
  72   struct SilcRngStateContext *next;
  73 } *SilcRngState;
  74
  75 /*
  76    SILC Random Number Generator object.
  77
  78    This object holds random pool which is used to generate the random
  79    numbers used by various routines needing cryptographically strong
  80    random numbers. Following short descriptions of the fields.
  81
  82    unsigned char pool[]
  83
  84        The random pool. This buffer holds the random data. This is
  85        frequently stirred thus providing ever changing randomnes.
  86
  87    unsigned char key[64]
  88
  89        Key used in stirring the random pool. The pool is encrypted
  90        with SHA1 hash function in CFB (Cipher Feedback) mode.
  91
  92    SilcSilcRngState state
  93
  94        State object that is used to get the next position for the
  95        random pool. This position is used to fetch data from pool
  96        or to save the data to the pool. The state changes everytime
  97        SilcRng is used.
  98
  99    SilcHash sha1
 100
 101        Hash object (SHA1) used to make the CFB encryption to the
 102        random pool. This is allocated when RNG object is allocated and
 103        free'd when RNG object is free'd.
 104
 105    uint8 threshhold
 106
 107        Threshhold to indicate when it is required to acquire more
 108        noise from the environment.  More soft noise is acquired after
 109        64 bits of output and hard noise every 160 bits of output.
 110
 111 */
 112 typedef struct SilcRngObjectStruct {
 113   unsigned char pool[SILC_RNG_POOLSIZE];
 114   unsigned char key[64];
 115   SilcRngState state;
 116   SilcHash sha1;
 117   uint8 threshhold;
 118   char *devrandom;
 119   int fd_devurandom;
 120 } SilcRngObject;
 121
 122 /* Allocates new RNG object. */
 123
 124 SilcRng silc_rng_alloc()
 125 {
 126   SilcRng new;
 127
 128   SILC_LOG_DEBUG(("Allocating new RNG object"));
 129
 130   new = silc_calloc(1, sizeof(*new));
 131   new->fd_devurandom = -1;
 132
 133   memset(new->pool, 0, sizeof(new->pool));
 134   memset(new->key, 0, sizeof(new->key));
 135   new->state = NULL;
 136   silc_hash_alloc("sha1", &new->sha1);
 137
 138   new->devrandom = strdup("/dev/random");
 139
 140   return new;
 141 }
 142
 143 /* Free's RNG object. */
 144
 145 void silc_rng_free(SilcRng rng)
 146 {
 147   if (rng) {
 148     memset(rng->pool, 0, sizeof(rng->pool));
 149     memset(rng->key, 0, sizeof(rng->key));
 150     silc_hash_free(rng->sha1);
 151     silc_free(rng->devrandom);
 152
 153     if (rng->fd_devurandom != -1)
 154       close(rng->fd_devurandom);
 155
 156     silc_free(rng);
 157   }
 158 }
 159
 160 /* Initializes random number generator by getting noise from environment.
 161    The environmental noise is our so called seed. One should not call
 162    this function more than once. */
 163
 164 void silc_rng_init(SilcRng rng)
 165 {
 166   int i;
 167   SilcRngState first, next;
 168
 169   assert(rng != NULL);
 170
 171   SILC_LOG_DEBUG(("Initializing RNG object"));
 172
 173   /* Initialize the states for the RNG. */
 174   rng->state = silc_calloc(1, sizeof(*rng->state));
 175   rng->state->low = 0;
 176   rng->state->pos = 8;
 177   rng->state->next = NULL;
 178   first = rng->state;
 179   for (i = SILC_RNG_STATE_NUM - 1; i >= 1; i--) {
 180     next = silc_calloc(1, sizeof(*rng->state));
 181     next->low =
 182       (i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM));
 183     next->pos =
 184       (i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM)) + 8;
 185     next->next = rng->state;
 186     rng->state = next;
 187   }
 188   first->next = next;
 189   rng->state = first;
 190
 191   memset(rng->pool, 0, sizeof(rng->pool));
 192
 193   /* Get noise from various environmental sources */
 194   silc_rng_get_soft_noise(rng);
 195   silc_rng_get_medium_noise(rng);
 196   silc_rng_get_hard_noise(rng);
 197   silc_rng_get_soft_noise(rng);
 198   silc_free(rng->devrandom);
 199   rng->devrandom = strdup("/dev/urandom");
 200 }
 201
 202 /* This function gets 'soft' noise from environment. */
 203
 204 static void silc_rng_get_soft_noise(SilcRng rng)
 205 {
 206 #ifndef SILC_WIN32
 207   struct tms ptime;
 208 #endif
 209   uint32 pos;
 210
 211   pos = silc_rng_get_position(rng);
 212
 213   silc_rng_xor(rng, clock(), 0);
 214 #ifndef SILC_WIN32
 215 #ifdef HAVE_GETPID
 216   silc_rng_xor(rng, getpid(), 1);
 217 #ifdef HAVE_GETPGID
 218   silc_rng_xor(rng, getpgid(getpid()) << 8, 2);
 219   silc_rng_xor(rng, getpgid(getpid()) << 8, 3);
 220 #endif
 221   silc_rng_xor(rng, getgid(), 4);
 222 #endif
 223 #ifdef HAVE_GETPGRP
 224   silc_rng_xor(rng, getpgrp(), 5);
 225 #endif
 226 #ifdef HAVE_GETSID
 227   silc_rng_xor(rng, getsid(getpid()) << 16, 6);
 228 #endif
 229   silc_rng_xor(rng, times(&ptime), 7);
 230   silc_rng_xor(rng, ptime.tms_utime, 8);
 231   silc_rng_xor(rng, (ptime.tms_utime + ptime.tms_stime), pos++);
 232   silc_rng_xor(rng, (ptime.tms_stime + ptime.tms_cutime), pos++);
 233   silc_rng_xor(rng, (ptime.tms_utime + ptime.tms_stime), pos++);
 234   silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_stime), pos++);
 235   silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_cstime), pos++);
 236   silc_rng_xor(rng, (ptime.tms_utime ^ ptime.tms_stime), pos++);
 237   silc_rng_xor(rng, (ptime.tms_stime ^ ptime.tms_cutime), pos++);
 238   silc_rng_xor(rng, (ptime.tms_cutime + ptime.tms_stime), pos++);
 239   silc_rng_xor(rng, (ptime.tms_stime << 8), pos++);
 240 #endif
 241   silc_rng_xor(rng, clock() << 4, pos++);
 242 #ifndef SILC_WIN32
 243 #ifdef HAVE_GETPGID
 244   silc_rng_xor(rng, getpgid(getpid()) << 8, pos++);
 245 #endif
 246 #ifdef HAVE_GETPGRP
 247   silc_rng_xor(rng, getpgrp(), pos++);
 248 #endif
 249 #ifdef HAVE_SETSID
 250   silc_rng_xor(rng, getsid(getpid()) << 16, pos++);
 251 #endif
 252   silc_rng_xor(rng, times(&ptime), pos++);
 253   silc_rng_xor(rng, ptime.tms_utime, pos++);
 254 #ifdef HAVE_GETPGRP
 255   silc_rng_xor(rng, getpgrp(), pos++);
 256 #endif
 257 #endif
 258
 259 #ifdef SILC_RNG_DEBUG
 260   SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
 261 #endif
 262
 263   /* Stir random pool */
 264   silc_rng_stir_pool(rng);
 265 }
 266
 267 /* This function gets noise from different commands */
 268
 269 static void silc_rng_get_medium_noise(SilcRng rng)
 270 {
 271   silc_rng_exec_command(rng, "ps -leaww 2> /dev/null");
 272   silc_rng_exec_command(rng, "ls -afiln ~ 2> /dev/null");
 273   silc_rng_exec_command(rng, "ls -afiln /proc 2> /dev/null");
 274   silc_rng_exec_command(rng, "ps -axww 2> /dev/null");
 275
 276 #ifdef SILC_RNG_DEBUG
 277   SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
 278 #endif
 279 }
 280
 281 /* This function gets 'hard' noise from environment. This tries to
 282    get the noise from /dev/random if available. */
 283
 284 static void silc_rng_get_hard_noise(SilcRng rng)
 285 {
 286 #ifndef SILC_WIN32
 287   unsigned char buf[32];
 288   int fd, len, i;
 289
 290   /* Get noise from /dev/[u]random if available */
 291   fd = open(rng->devrandom, O_RDONLY);
 292   if (fd < 0)
 293     return;
 294
 295   fcntl(fd, F_SETFL, O_NONBLOCK);
 296
 297   for (i = 0; i < 2; i++) {
 298     len = read(fd, buf, sizeof(buf));
 299     if (len <= 0)
 300       goto out;
 301     silc_rng_add_noise(rng, buf, len);
 302   }
 303
 304 #ifdef SILC_RNG_DEBUG
 305   SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
 306 #endif
 307
 308  out:
 309   close(fd);
 310   memset(buf, 0, sizeof(buf));
 311 #endif
 312 }
 313
 314 /* Execs command and gets noise from its output */
 315
 316 static void silc_rng_exec_command(SilcRng rng, char *command)
 317 {
 318 #ifndef SILC_WIN32
 319   unsigned char buf[1024];
 320   FILE *fd;
 321   int i;
 322   int c;
 323
 324   /* Open process */
 325   fd = popen(command, "r");
 326   if (!fd)
 327     return;
 328
 329   /* Get data as much as we can get into the buffer */
 330   for (i = 0; i < sizeof(buf); i++) {
 331     c = fgetc(fd);
 332     if (c == EOF) {
 333       if (!i)
 334         return;
 335       break;
 336     }
 337     buf[i] = c;
 338   }
 339
 340   pclose(fd);
 341
 342   /* Add the buffer into random pool */
 343   silc_rng_add_noise(rng, buf, strlen(buf));
 344   memset(buf, 0, sizeof(buf));
 345 #endif
 346 }
 347
 348 /* This function adds the contents of the buffer as noise into random
 349    pool. After adding the noise the pool is stirred. */
 350
 351 void silc_rng_add_noise(SilcRng rng, unsigned char *buffer, uint32 len)
 352 {
 353   uint32 i, pos;
 354
 355   pos = silc_rng_get_position(rng);
 356
 357   /* Add the buffer one by one into the pool */
 358   for(i = 0; i < len; i++, buffer++) {
 359     if(pos >= SILC_RNG_POOLSIZE)
 360       break;
 361     rng->pool[pos++] ^= *buffer;
 362   }
 363
 364   /* Stir random pool */
 365   silc_rng_stir_pool(rng);
 366 }
 367
 368 /* XOR's data into the pool */
 369
 370 static void silc_rng_xor(SilcRng rng, uint32 val, unsigned int pos)
 371 {
 372   assert(rng != NULL);
 373   rng->pool[pos] ^= val + val;
 374 }
 375
 376 /* This function stirs the random pool by encrypting buffer in CFB
 377    (cipher feedback) mode with SHA1 algorithm. */
 378
 379 static void silc_rng_stir_pool(SilcRng rng)
 380 {
 381   int i;
 382   uint32 iv[5];
 383
 384   /* Get the IV */
 385   memcpy(iv, &rng->pool[16], sizeof(iv));
 386
 387   /* First CFB pass */
 388   for (i = 0; i < SILC_RNG_POOLSIZE; i += 5) {
 389     rng->sha1->hash->transform(iv, rng->key);
 390     iv[0] = rng->pool[i] ^= iv[0];
 391     iv[1] = rng->pool[i + 1] ^= iv[1];
 392     iv[2] = rng->pool[i + 2] ^= iv[2];
 393     iv[3] = rng->pool[i + 3] ^= iv[3];
 394     iv[4] = rng->pool[i + 4] ^= iv[4];
 395   }
 396
 397   /* Get new key */
 398   memcpy(rng->key, &rng->pool[silc_rng_get_position(rng)], sizeof(rng->key));
 399
 400   /* Second CFB pass */
 401   for (i = 0; i < SILC_RNG_POOLSIZE; i += 5) {
 402     rng->sha1->hash->transform(iv, rng->key);
 403     iv[0] = rng->pool[i] ^= iv[0];
 404     iv[1] = rng->pool[i + 1] ^= iv[1];
 405     iv[2] = rng->pool[i + 2] ^= iv[2];
 406     iv[3] = rng->pool[i + 3] ^= iv[3];
 407     iv[4] = rng->pool[i + 4] ^= iv[4];
 408   }
 409
 410   memset(iv, 0, sizeof(iv));
 411 }
 412
 413 /* Returns next position where data is fetched from the pool or
 414    put to the pool. */
 415
 416 static uint32 silc_rng_get_position(SilcRng rng)
 417 {
 418   SilcRngState next;
 419   uint32 pos;
 420
 421   next = rng->state->next;
 422
 423   pos = rng->state->pos++;
 424   if ((next->low != 0 && pos >= next->low) || (pos >= SILC_RNG_POOLSIZE))
 425     rng->state->pos = rng->state->low;
 426
 427 #ifdef SILC_RNG_DEBUG
 428     fprintf(stderr, "state: %p: low: %lu, pos: %lu\n",
 429             rng->state, rng->state->low, rng->state->pos);
 430 #endif
 431
 432   rng->state = next;
 433
 434   return pos;
 435 }
 436
 437 /* Returns random byte. */
 438
 439 unsigned char silc_rng_get_byte(SilcRng rng)
 440 {
 441   rng->threshhold++;
 442
 443   /* Get more soft noise after 64 bits threshhold */
 444   if (rng->threshhold >= 8)
 445     silc_rng_get_soft_noise(rng);
 446
 447   /* Get hard noise after 160 bits threshhold, zero the threshhold. */
 448   if (rng->threshhold >= 20) {
 449     rng->threshhold = 0;
 450     silc_rng_get_hard_noise(rng);
 451   }
 452
 453   return rng->pool[silc_rng_get_position(rng)];
 454 }
 455
 456 /* Returns 16 bit random number */
 457
 458 uint16 silc_rng_get_rn16(SilcRng rng)
 459 {
 460   unsigned char rn[2];
 461   uint16 num;
 462
 463   rn[0] = silc_rng_get_byte(rng);
 464   rn[1] = silc_rng_get_byte(rng);
 465   SILC_GET16_MSB(num, rn);
 466
 467   return num;
 468 }
 469
 470 /* Returns 32 bit random number */
 471
 472 uint32 silc_rng_get_rn32(SilcRng rng)
 473 {
 474   unsigned char rn[4];
 475   uint16 num;
 476
 477   rn[0] = silc_rng_get_byte(rng);
 478   rn[1] = silc_rng_get_byte(rng);
 479   rn[2] = silc_rng_get_byte(rng);
 480   rn[3] = silc_rng_get_byte(rng);
 481   SILC_GET32_MSB(num, rn);
 482
 483   return num;
 484 }
 485
 486 /* Returns random number string. Returned string is in HEX format. */
 487
 488 unsigned char *silc_rng_get_rn_string(SilcRng rng, uint32 len)
 489 {
 490   int i;
 491   unsigned char *string;
 492
 493   string = silc_calloc((len * 2 + 1), sizeof(unsigned char));
 494
 495   for (i = 0; i < len; i++)
 496     sprintf(string + 2 * i, "%02x", silc_rng_get_byte(rng));
 497
 498   return string;
 499 }
 500
 501 /* Returns random number binary data. */
 502
 503 unsigned char *silc_rng_get_rn_data(SilcRng rng, uint32 len)
 504 {
 505   int i;
 506   unsigned char *data;
 507
 508   data = silc_calloc(len + 1, sizeof(*data));
 509
 510   for (i = 0; i < len; i++)
 511     data[i] = silc_rng_get_byte(rng);
 512
 513   return data;
 514 }
 515
 516 /* Global RNG. This is global RNG that application can initialize so
 517    that any part of code anywhere can use RNG without having to allocate
 518    new RNG object everytime.  If this is not initialized then these routines
 519    will fail.  Note: currently in SILC applications always initialize this. */
 520
 521 SilcRng global_rng = NULL;
 522
 523 /* Initialize global RNG. If `rng' is provided it is set as the global
 524    RNG object (it can be allocated by the application for example). */
 525
 526 int silc_rng_global_init(SilcRng rng)
 527 {
 528   if (rng)
 529     global_rng = rng;
 530   else
 531     global_rng = silc_rng_alloc();
 532
 533   return TRUE;
 534 }
 535
 536 /* Uninitialize global RNG */
 537
 538 int silc_rng_global_uninit()
 539 {
 540   if (global_rng) {
 541     silc_rng_free(global_rng);
 542     global_rng = NULL;
 543   }
 544
 545   return TRUE;
 546 }
 547
 548 /* These are analogous to the functions above. */
 549
 550 unsigned char silc_rng_global_get_byte()
 551 {
 552   return global_rng ? silc_rng_get_byte(global_rng) : 0;
 553 }
 554
 555 /* Return random byte as fast as possible. Reads from /dev/urandom if
 556    available. If not then return from normal RNG (not so fast). */
 557
 558 unsigned char silc_rng_global_get_byte_fast()
 559 {
 560 #ifndef SILC_WIN32
 561   unsigned char buf[1];
 562
 563   if (!global_rng)
 564     return 0;
 565
 566   if (global_rng->fd_devurandom == -1) {
 567     global_rng->fd_devurandom = open("/dev/urandom", O_RDONLY);
 568     if (global_rng < 0)
 569       return silc_rng_global_get_byte();
 570     fcntl(global_rng->fd_devurandom, F_SETFL, O_NONBLOCK);
 571   }
 572
 573   if (read(global_rng->fd_devurandom, buf, sizeof(buf)) < 0)
 574     return silc_rng_global_get_byte();
 575
 576   return buf[0];
 577 #else
 578   return silc_rng_global_get_byte();
 579 #endif
 580 }
 581
 582 uint16 silc_rng_global_get_rn16()
 583 {
 584   return global_rng ? silc_rng_get_rn16(global_rng) : 0;
 585 }
 586
 587 uint32 silc_rng_global_get_rn32()
 588 {
 589   return global_rng ? silc_rng_get_rn32(global_rng) : 0;
 590 }
 591
 592 unsigned char *silc_rng_global_get_rn_string(uint32 len)
 593 {
 594   return global_rng ? silc_rng_get_rn_string(global_rng, len) : NULL;
 595 }
 596
 597 unsigned char *silc_rng_global_get_rn_data(uint32 len)
 598 {
 599   return global_rng ? silc_rng_get_rn_data(global_rng, len) : NULL;
 600 }
 601
 602 void silc_rng_global_add_noise(unsigned char *buffer, uint32 len)
 603 {
 604   if (global_rng)
 605     silc_rng_add_noise(global_rng, buffer, len);
 606 }