lib/silccrypt/silcrng.c

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