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     SilcRngState t, n;
 162
 163     memset(rng->pool, 0, sizeof(rng->pool));
 164     memset(rng->key, 0, sizeof(rng->key));
 165     silc_hash_free(rng->sha1);
 166     silc_free(rng->devrandom);
 167
 168     if (rng->fd_devurandom != -1)
 169       close(rng->fd_devurandom);
 170
 171     for (t = rng->state->next; t != rng->state; ) {
 172       n = t->next;
 173       silc_free(t);
 174       t = n;
 175     }
 176     silc_free(rng->state);
 177
 178     silc_free(rng);
 179   }
 180 }
 181
 182 /* Initializes random number generator by getting noise from environment.
 183    The environmental noise is our so called seed. One should not call
 184    this function more than once. */
 185
 186 void silc_rng_init(SilcRng rng)
 187 {
 188   int i;
 189   SilcRngState first, next;
 190
 191   assert(rng != NULL);
 192
 193   SILC_LOG_DEBUG(("Initializing RNG object"));
 194
 195   /* Initialize the states for the RNG. */
 196   rng->state = silc_calloc(1, sizeof(*rng->state));
 197   rng->state->low = 0;
 198   rng->state->pos = 8;
 199   rng->state->next = NULL;
 200   first = rng->state;
 201   for (i = SILC_RNG_STATE_NUM - 1; i >= 1; i--) {
 202     next = silc_calloc(1, sizeof(*rng->state));
 203     next->low =
 204       (i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM));
 205     next->pos =
 206       (i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM)) + 8;
 207     next->next = rng->state;
 208     rng->state = next;
 209   }
 210   first->next = next;
 211   rng->state = first;
 212
 213   memset(rng->pool, 0, sizeof(rng->pool));
 214
 215   /* Get noise from various environmental sources */
 216   silc_rng_get_soft_noise(rng);
 217   silc_rng_get_medium_noise(rng);
 218   silc_rng_get_hard_noise(rng);
 219   silc_rng_get_soft_noise(rng);
 220   silc_free(rng->devrandom);
 221   rng->devrandom = strdup("/dev/urandom");
 222 }
 223
 224 /* This function gets 'soft' noise from environment. */
 225
 226 static void silc_rng_get_soft_noise(SilcRng rng)
 227 {
 228 #ifndef SILC_WIN32
 229   struct tms ptime;
 230 #endif
 231   SilcUInt32 pos;
 232
 233   pos = silc_rng_get_position(rng);
 234
 235   silc_rng_xor(rng, clock(), 0);
 236 #ifndef SILC_WIN32
 237 #ifdef HAVE_GETPID
 238   silc_rng_xor(rng, getpid(), 1);
 239 #ifdef HAVE_GETPGID
 240   silc_rng_xor(rng, getpgid(getpid()) << 8, 2);
 241   silc_rng_xor(rng, getpgid(getpid()) << 8, 3);
 242 #endif
 243   silc_rng_xor(rng, getgid(), 4);
 244 #endif
 245 #ifdef HAVE_GETPGRP
 246   silc_rng_xor(rng, getpgrp(), 5);
 247 #endif
 248 #ifdef HAVE_GETSID
 249   silc_rng_xor(rng, getsid(getpid()) << 16, 6);
 250 #endif
 251   silc_rng_xor(rng, times(&ptime), 7);
 252   silc_rng_xor(rng, ptime.tms_utime, 8);
 253   silc_rng_xor(rng, (ptime.tms_utime + ptime.tms_stime), pos++);
 254   silc_rng_xor(rng, (ptime.tms_stime + ptime.tms_cutime), pos++);
 255   silc_rng_xor(rng, (ptime.tms_utime + ptime.tms_stime), pos++);
 256   silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_stime), pos++);
 257   silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_cstime), pos++);
 258   silc_rng_xor(rng, (ptime.tms_utime ^ ptime.tms_stime), pos++);
 259   silc_rng_xor(rng, (ptime.tms_stime ^ ptime.tms_cutime), pos++);
 260   silc_rng_xor(rng, (ptime.tms_cutime + ptime.tms_stime), pos++);
 261   silc_rng_xor(rng, (ptime.tms_stime << 8), pos++);
 262 #endif
 263   silc_rng_xor(rng, clock() << 4, pos++);
 264 #ifndef SILC_WIN32
 265 #ifdef HAVE_GETPGID
 266   silc_rng_xor(rng, getpgid(getpid()) << 8, pos++);
 267 #endif
 268 #ifdef HAVE_GETPGRP
 269   silc_rng_xor(rng, getpgrp(), pos++);
 270 #endif
 271 #ifdef HAVE_SETSID
 272   silc_rng_xor(rng, getsid(getpid()) << 16, pos++);
 273 #endif
 274   silc_rng_xor(rng, times(&ptime), pos++);
 275   silc_rng_xor(rng, ptime.tms_utime, pos++);
 276 #ifdef HAVE_GETPGRP
 277   silc_rng_xor(rng, getpgrp(), pos++);
 278 #endif
 279 #endif
 280
 281 #ifdef SILC_RNG_DEBUG
 282   SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
 283 #endif
 284
 285   /* Stir random pool */
 286   silc_rng_stir_pool(rng);
 287 }
 288
 289 /* This function gets noise from different commands */
 290
 291 static void silc_rng_get_medium_noise(SilcRng rng)
 292 {
 293   silc_rng_exec_command(rng, "ps -leaww 2> /dev/null");
 294   silc_rng_exec_command(rng, "ls -afiln ~ 2> /dev/null");
 295   silc_rng_exec_command(rng, "ls -afiln /proc 2> /dev/null");
 296   silc_rng_exec_command(rng, "ps -axww 2> /dev/null");
 297
 298 #ifdef SILC_RNG_DEBUG
 299   SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
 300 #endif
 301 }
 302
 303 /* This function gets 'hard' noise from environment. This tries to
 304    get the noise from /dev/random if available. */
 305
 306 static void silc_rng_get_hard_noise(SilcRng rng)
 307 {
 308 #ifndef SILC_WIN32
 309   unsigned char buf[32];
 310   int fd, len, i;
 311
 312   /* Get noise from /dev/[u]random if available */
 313   fd = open(rng->devrandom, O_RDONLY);
 314   if (fd < 0)
 315     return;
 316
 317   fcntl(fd, F_SETFL, O_NONBLOCK);
 318
 319   for (i = 0; i < 2; i++) {
 320     len = read(fd, buf, sizeof(buf));
 321     if (len <= 0)
 322       goto out;
 323     silc_rng_add_noise(rng, buf, len);
 324   }
 325
 326 #ifdef SILC_RNG_DEBUG
 327   SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
 328 #endif
 329
 330  out:
 331   close(fd);
 332   memset(buf, 0, sizeof(buf));
 333 #endif
 334 }
 335
 336 /* Execs command and gets noise from its output */
 337
 338 static void silc_rng_exec_command(SilcRng rng, char *command)
 339 {
 340 #ifndef SILC_WIN32
 341   unsigned char buf[1024];
 342   FILE *fd;
 343   int i;
 344   int c;
 345
 346   /* Open process */
 347   fd = popen(command, "r");
 348   if (!fd)
 349     return;
 350
 351   /* Get data as much as we can get into the buffer */
 352   for (i = 0; i < sizeof(buf); i++) {
 353     c = fgetc(fd);
 354     if (c == EOF) {
 355       if (!i)
 356         return;
 357       break;
 358     }
 359     buf[i] = c;
 360   }
 361
 362   pclose(fd);
 363
 364   /* Add the buffer into random pool */
 365   silc_rng_add_noise(rng, buf, i);
 366   memset(buf, 0, sizeof(buf));
 367 #endif
 368 }
 369
 370 /* This function adds the contents of the buffer as noise into random
 371    pool. After adding the noise the pool is stirred. */
 372
 373 void silc_rng_add_noise(SilcRng rng, unsigned char *buffer, SilcUInt32 len)
 374 {
 375   SilcUInt32 i, pos;
 376
 377   pos = silc_rng_get_position(rng);
 378
 379   /* Add the buffer one by one into the pool */
 380   for(i = 0; i < len; i++, buffer++) {
 381     if(pos >= SILC_RNG_POOLSIZE)
 382       break;
 383     rng->pool[pos++] ^= *buffer;
 384   }
 385
 386   /* Stir random pool */
 387   silc_rng_stir_pool(rng);
 388 }
 389
 390 /* XOR's data into the pool */
 391
 392 static void silc_rng_xor(SilcRng rng, SilcUInt32 val, unsigned int pos)
 393 {
 394   assert(rng != NULL);
 395   rng->pool[pos] ^= val + val;
 396 }
 397
 398 /* This function stirs the random pool by encrypting buffer in CFB
 399    (cipher feedback) mode with SHA1 algorithm. */
 400
 401 static void silc_rng_stir_pool(SilcRng rng)
 402 {
 403   int i;
 404   SilcUInt32 iv[5];
 405
 406   /* Get the IV */
 407   memcpy(iv, &rng->pool[16], sizeof(iv));
 408
 409   /* First CFB pass */
 410   for (i = 0; i < SILC_RNG_POOLSIZE; i += 5) {
 411     silc_hash_transform(rng->sha1, iv, rng->key);
 412     iv[0] = rng->pool[i] ^= iv[0];
 413     iv[1] = rng->pool[i + 1] ^= iv[1];
 414     iv[2] = rng->pool[i + 2] ^= iv[2];
 415     iv[3] = rng->pool[i + 3] ^= iv[3];
 416     iv[4] = rng->pool[i + 4] ^= iv[4];
 417   }
 418
 419   /* Get new key */
 420   memcpy(rng->key, &rng->pool[silc_rng_get_position(rng)], sizeof(rng->key));
 421
 422   /* Second CFB pass */
 423   for (i = 0; i < SILC_RNG_POOLSIZE; i += 5) {
 424     silc_hash_transform(rng->sha1, iv, rng->key);
 425     iv[0] = rng->pool[i] ^= iv[0];
 426     iv[1] = rng->pool[i + 1] ^= iv[1];
 427     iv[2] = rng->pool[i + 2] ^= iv[2];
 428     iv[3] = rng->pool[i + 3] ^= iv[3];
 429     iv[4] = rng->pool[i + 4] ^= iv[4];
 430   }
 431
 432   memset(iv, 0, sizeof(iv));
 433 }
 434
 435 /* Returns next position where data is fetched from the pool or
 436    put to the pool. */
 437
 438 static SilcUInt32 silc_rng_get_position(SilcRng rng)
 439 {
 440   SilcRngState next;
 441   SilcUInt32 pos;
 442
 443   next = rng->state->next;
 444
 445   pos = rng->state->pos++;
 446   if ((next->low != 0 && pos >= next->low) || (pos >= SILC_RNG_POOLSIZE))
 447     rng->state->pos = rng->state->low;
 448
 449 #ifdef SILC_RNG_DEBUG
 450     fprintf(stderr, "state: %p: low: %lu, pos: %lu\n",
 451             rng->state, rng->state->low, rng->state->pos);
 452 #endif
 453
 454   rng->state = next;
 455
 456   return pos;
 457 }
 458
 459 /* Returns random byte. */
 460
 461 SilcUInt8 silc_rng_get_byte(SilcRng rng)
 462 {
 463   rng->threshold++;
 464
 465   /* Get more soft noise after 64 bits threshold */
 466   if (rng->threshold >= 8)
 467     silc_rng_get_soft_noise(rng);
 468
 469   /* Get hard noise after 160 bits threshold, zero the threshold. */
 470   if (rng->threshold >= 20) {
 471     rng->threshold = 0;
 472     silc_rng_get_hard_noise(rng);
 473   }
 474
 475   return rng->pool[silc_rng_get_position(rng)];
 476 }
 477
 478 /* Return random byte as fast as possible. Reads from /dev/urandom if
 479    available. If not then return from normal RNG (not so fast). */
 480
 481 SilcUInt8 silc_rng_get_byte_fast(SilcRng rng)
 482 {
 483 #ifndef SILC_WIN32
 484   unsigned char buf[1];
 485
 486   if (rng->fd_devurandom == -1) {
 487     rng->fd_devurandom = open("/dev/urandom", O_RDONLY);
 488     if (rng < 0)
 489       return silc_rng_get_byte(rng);
 490     fcntl(rng->fd_devurandom, F_SETFL, O_NONBLOCK);
 491   }
 492
 493   if (read(rng->fd_devurandom, buf, sizeof(buf)) < 0)
 494     return silc_rng_get_byte(rng);
 495
 496   return buf[0];
 497 #else
 498   return silc_rng_get_byte(rng);
 499 #endif
 500 }
 501
 502 /* Returns 16 bit random number */
 503
 504 SilcUInt16 silc_rng_get_rn16(SilcRng rng)
 505 {
 506   unsigned char rn[2];
 507   SilcUInt16 num;
 508
 509   rn[0] = silc_rng_get_byte(rng);
 510   rn[1] = silc_rng_get_byte(rng);
 511   SILC_GET16_MSB(num, rn);
 512
 513   return num;
 514 }
 515
 516 /* Returns 32 bit random number */
 517
 518 SilcUInt32 silc_rng_get_rn32(SilcRng rng)
 519 {
 520   unsigned char rn[4];
 521   SilcUInt16 num;
 522
 523   rn[0] = silc_rng_get_byte(rng);
 524   rn[1] = silc_rng_get_byte(rng);
 525   rn[2] = silc_rng_get_byte(rng);
 526   rn[3] = silc_rng_get_byte(rng);
 527   SILC_GET32_MSB(num, rn);
 528
 529   return num;
 530 }
 531
 532 /* Returns random number string. Returned string is in HEX format. */
 533
 534 unsigned char *silc_rng_get_rn_string(SilcRng rng, SilcUInt32 len)
 535 {
 536   int i;
 537   unsigned char *string;
 538
 539   string = silc_calloc((len * 2 + 1), sizeof(unsigned char));
 540
 541   for (i = 0; i < len; i++)
 542     sprintf(string + 2 * i, "%02x", silc_rng_get_byte(rng));
 543
 544   return string;
 545 }
 546
 547 /* Returns random number binary data. */
 548
 549 unsigned char *silc_rng_get_rn_data(SilcRng rng, SilcUInt32 len)
 550 {
 551   int i;
 552   unsigned char *data;
 553
 554   data = silc_calloc(len + 1, sizeof(*data));
 555
 556   for (i = 0; i < len; i++)
 557     data[i] = silc_rng_get_byte(rng);
 558
 559   return data;
 560 }
 561
 562 /* Global RNG. This is global RNG that application can initialize so
 563    that any part of code anywhere can use RNG without having to allocate
 564    new RNG object everytime.  If this is not initialized then these routines
 565    will fail.  Note: currently in SILC applications always initialize this. */
 566
 567 SilcRng global_rng = NULL;
 568
 569 /* Initialize global RNG. If `rng' is provided it is set as the global
 570    RNG object (it can be allocated by the application for example). */
 571
 572 bool silc_rng_global_init(SilcRng rng)
 573 {
 574   if (rng)
 575     global_rng = rng;
 576   else
 577     global_rng = silc_rng_alloc();
 578
 579   return TRUE;
 580 }
 581
 582 /* Uninitialize global RNG */
 583
 584 bool silc_rng_global_uninit(void)
 585 {
 586   if (global_rng) {
 587     silc_rng_free(global_rng);
 588     global_rng = NULL;
 589   }
 590
 591   return TRUE;
 592 }
 593
 594 /* These are analogous to the functions above. */
 595
 596 SilcUInt8 silc_rng_global_get_byte(void)
 597 {
 598   return global_rng ? silc_rng_get_byte(global_rng) : 0;
 599 }
 600
 601 /* Return random byte as fast as possible. Reads from /dev/urandom if
 602    available. If not then return from normal RNG (not so fast). */
 603
 604 SilcUInt8 silc_rng_global_get_byte_fast(void)
 605 {
 606   return global_rng ? silc_rng_get_byte_fast(global_rng) : 0;
 607 }
 608
 609 SilcUInt16 silc_rng_global_get_rn16(void)
 610 {
 611   return global_rng ? silc_rng_get_rn16(global_rng) : 0;
 612 }
 613
 614 SilcUInt32 silc_rng_global_get_rn32(void)
 615 {
 616   return global_rng ? silc_rng_get_rn32(global_rng) : 0;
 617 }
 618
 619 unsigned char *silc_rng_global_get_rn_string(SilcUInt32 len)
 620 {
 621   return global_rng ? silc_rng_get_rn_string(global_rng, len) : NULL;
 622 }
 623
 624 unsigned char *silc_rng_global_get_rn_data(SilcUInt32 len)
 625 {
 626   return global_rng ? silc_rng_get_rn_data(global_rng, len) : NULL;
 627 }
 628
 629 void silc_rng_global_add_noise(unsigned char *buffer, SilcUInt32 len)
 630 {
 631   if (global_rng)
 632     silc_rng_add_noise(global_rng, buffer, len);
 633 }