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 (20 * 48)
  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       break;
 356     buf[i] = c;
 357   }
 358
 359   pclose(fd);
 360
 361   if (i != 0) {
 362     /* Add the buffer into random pool */
 363     silc_rng_add_noise(rng, buf, i);
 364     memset(buf, 0, sizeof(buf));
 365   }
 366 #endif
 367 }
 368
 369 /* This function adds the contents of the buffer as noise into random
 370    pool. After adding the noise the pool is stirred. */
 371
 372 void silc_rng_add_noise(SilcRng rng, unsigned char *buffer, SilcUInt32 len)
 373 {
 374   SilcUInt32 i, pos;
 375
 376   pos = silc_rng_get_position(rng);
 377
 378   /* Add the buffer one by one into the pool */
 379   for(i = 0; i < len; i++, buffer++) {
 380     if(pos >= SILC_RNG_POOLSIZE)
 381       break;
 382     rng->pool[pos++] ^= *buffer;
 383   }
 384
 385   /* Stir random pool */
 386   silc_rng_stir_pool(rng);
 387 }
 388
 389 /* XOR's data into the pool */
 390
 391 static void silc_rng_xor(SilcRng rng, SilcUInt32 val, unsigned int pos)
 392 {
 393   SilcUInt32 tmp;
 394
 395   SILC_GET32_MSB(tmp, &rng->pool[pos]);
 396   val ^= tmp + val;
 397   SILC_PUT32_MSB(val, &rng->pool[pos]);
 398 }
 399
 400 /* This function stirs the random pool by encrypting buffer in CFB
 401    (cipher feedback) mode with SHA1 algorithm. */
 402
 403 static void silc_rng_stir_pool(SilcRng rng)
 404 {
 405   int i;
 406   SilcUInt32 iv[5], tmp;
 407
 408   /* Get the IV */
 409   SILC_GET32_MSB(iv[0], &rng->pool[16     ]);
 410   SILC_GET32_MSB(iv[1], &rng->pool[16 +  4]);
 411   SILC_GET32_MSB(iv[2], &rng->pool[16 +  8]);
 412   SILC_GET32_MSB(iv[3], &rng->pool[16 + 12]);
 413   SILC_GET32_MSB(iv[4], &rng->pool[16 + 16]);
 414
 415   /* First CFB pass */
 416   for (i = 0; i < SILC_RNG_POOLSIZE; i += 20) {
 417     silc_hash_transform(rng->sha1, iv, rng->key);
 418
 419     SILC_GET32_MSB(tmp, &rng->pool[i]);
 420     iv[0] ^= tmp;
 421     SILC_PUT32_MSB(iv[0], &rng->pool[i]);
 422
 423     SILC_GET32_MSB(tmp, &rng->pool[i + 4]);
 424     iv[1] ^= tmp;
 425     SILC_PUT32_MSB(iv[1], &rng->pool[i + 4]);
 426
 427     SILC_GET32_MSB(tmp, &rng->pool[i + 8]);
 428     iv[2] ^= tmp;
 429     SILC_PUT32_MSB(iv[2], &rng->pool[i + 8]);
 430
 431     SILC_GET32_MSB(tmp, &rng->pool[i + 12]);
 432     iv[3] ^= tmp;
 433     SILC_PUT32_MSB(iv[3], &rng->pool[i + 12]);
 434
 435     SILC_GET32_MSB(tmp, &rng->pool[i + 16]);
 436     iv[4] ^= tmp;
 437     SILC_PUT32_MSB(iv[4], &rng->pool[i + 16]);
 438   }
 439
 440   /* Get new key */
 441   memcpy(rng->key, &rng->pool[silc_rng_get_position(rng)], sizeof(rng->key));
 442
 443   /* Second CFB pass */
 444   for (i = 0; i < SILC_RNG_POOLSIZE; i += 20) {
 445     silc_hash_transform(rng->sha1, iv, rng->key);
 446
 447     SILC_GET32_MSB(tmp, &rng->pool[i]);
 448     iv[0] ^= tmp;
 449     SILC_PUT32_MSB(iv[0], &rng->pool[i]);
 450
 451     SILC_GET32_MSB(tmp, &rng->pool[i + 4]);
 452     iv[1] ^= tmp;
 453     SILC_PUT32_MSB(iv[1], &rng->pool[i + 4]);
 454
 455     SILC_GET32_MSB(tmp, &rng->pool[i + 8]);
 456     iv[2] ^= tmp;
 457     SILC_PUT32_MSB(iv[2], &rng->pool[i + 8]);
 458
 459     SILC_GET32_MSB(tmp, &rng->pool[i + 12]);
 460     iv[3] ^= tmp;
 461     SILC_PUT32_MSB(iv[3], &rng->pool[i + 12]);
 462
 463     SILC_GET32_MSB(tmp, &rng->pool[i + 16]);
 464     iv[4] ^= tmp;
 465     SILC_PUT32_MSB(iv[4], &rng->pool[i + 16]);
 466   }
 467
 468   memset(iv, 0, sizeof(iv));
 469 }
 470
 471 /* Returns next position where data is fetched from the pool or
 472    put to the pool. */
 473
 474 static SilcUInt32 silc_rng_get_position(SilcRng rng)
 475 {
 476   SilcRngState next;
 477   SilcUInt32 pos;
 478
 479   next = rng->state->next;
 480
 481   pos = rng->state->pos++;
 482   if ((next->low != 0 && pos >= next->low) || (pos >= SILC_RNG_POOLSIZE))
 483     rng->state->pos = rng->state->low;
 484
 485 #ifdef SILC_RNG_DEBUG
 486     fprintf(stderr, "state: %p: low: %lu, pos: %lu\n",
 487             rng->state, rng->state->low, rng->state->pos);
 488 #endif
 489
 490   rng->state = next;
 491
 492   return pos;
 493 }
 494
 495 /* Returns random byte. */
 496
 497 SilcUInt8 silc_rng_get_byte(SilcRng rng)
 498 {
 499   rng->threshold++;
 500
 501   /* Get more soft noise after 64 bits threshold */
 502   if (rng->threshold >= 8)
 503     silc_rng_get_soft_noise(rng);
 504
 505   /* Get hard noise after 160 bits threshold, zero the threshold. */
 506   if (rng->threshold >= 20) {
 507     rng->threshold = 0;
 508     silc_rng_get_hard_noise(rng);
 509   }
 510
 511   return rng->pool[silc_rng_get_position(rng)];
 512 }
 513
 514 /* Return random byte as fast as possible. Reads from /dev/urandom if
 515    available. If not then return from normal RNG (not so fast). */
 516
 517 SilcUInt8 silc_rng_get_byte_fast(SilcRng rng)
 518 {
 519 #ifndef SILC_WIN32
 520   unsigned char buf[1];
 521
 522   if (rng->fd_devurandom == -1) {
 523     rng->fd_devurandom = open("/dev/urandom", O_RDONLY);
 524     if (rng->fd_devurandom < 0)
 525       return silc_rng_get_byte(rng);
 526     fcntl(rng->fd_devurandom, F_SETFL, O_NONBLOCK);
 527   }
 528
 529   if (read(rng->fd_devurandom, buf, sizeof(buf)) < 0)
 530     return silc_rng_get_byte(rng);
 531
 532   return buf[0];
 533 #else
 534   return silc_rng_get_byte(rng);
 535 #endif
 536 }
 537
 538 /* Returns 16 bit random number */
 539
 540 SilcUInt16 silc_rng_get_rn16(SilcRng rng)
 541 {
 542   unsigned char rn[2];
 543   SilcUInt16 num;
 544
 545   rn[0] = silc_rng_get_byte(rng);
 546   rn[1] = silc_rng_get_byte(rng);
 547   SILC_GET16_MSB(num, rn);
 548
 549   return num;
 550 }
 551
 552 /* Returns 32 bit random number */
 553
 554 SilcUInt32 silc_rng_get_rn32(SilcRng rng)
 555 {
 556   unsigned char rn[4];
 557   SilcUInt32 num;
 558
 559   rn[0] = silc_rng_get_byte(rng);
 560   rn[1] = silc_rng_get_byte(rng);
 561   rn[2] = silc_rng_get_byte(rng);
 562   rn[3] = silc_rng_get_byte(rng);
 563   SILC_GET32_MSB(num, rn);
 564
 565   return num;
 566 }
 567
 568 /* Returns random number string. Returned string is in HEX format. */
 569
 570 unsigned char *silc_rng_get_rn_string(SilcRng rng, SilcUInt32 len)
 571 {
 572   int i;
 573   unsigned char *string;
 574
 575   string = silc_calloc((len * 2 + 1), sizeof(unsigned char));
 576
 577   for (i = 0; i < len; i++)
 578     sprintf(string + 2 * i, "%02x", silc_rng_get_byte(rng));
 579
 580   return string;
 581 }
 582
 583 /* Returns random number binary data. */
 584
 585 unsigned char *silc_rng_get_rn_data(SilcRng rng, SilcUInt32 len)
 586 {
 587   int i;
 588   unsigned char *data;
 589
 590   data = silc_calloc(len + 1, sizeof(*data));
 591
 592   for (i = 0; i < len; i++)
 593     data[i] = silc_rng_get_byte(rng);
 594
 595   return data;
 596 }
 597
 598 /* Global RNG. This is global RNG that application can initialize so
 599    that any part of code anywhere can use RNG without having to allocate
 600    new RNG object everytime.  If this is not initialized then these routines
 601    will fail.  Note: currently in SILC applications always initialize this. */
 602
 603 SilcRng global_rng = NULL;
 604
 605 /* Initialize global RNG. If `rng' is provided it is set as the global
 606    RNG object (it can be allocated by the application for example). */
 607
 608 bool silc_rng_global_init(SilcRng rng)
 609 {
 610   if (rng)
 611     global_rng = rng;
 612   else
 613     global_rng = silc_rng_alloc();
 614
 615   return TRUE;
 616 }
 617
 618 /* Uninitialize global RNG */
 619
 620 bool silc_rng_global_uninit(void)
 621 {
 622   if (global_rng) {
 623     silc_rng_free(global_rng);
 624     global_rng = NULL;
 625   }
 626
 627   return TRUE;
 628 }
 629
 630 /* These are analogous to the functions above. */
 631
 632 SilcUInt8 silc_rng_global_get_byte(void)
 633 {
 634   return global_rng ? silc_rng_get_byte(global_rng) : 0;
 635 }
 636
 637 /* Return random byte as fast as possible. Reads from /dev/urandom if
 638    available. If not then return from normal RNG (not so fast). */
 639
 640 SilcUInt8 silc_rng_global_get_byte_fast(void)
 641 {
 642   return global_rng ? silc_rng_get_byte_fast(global_rng) : 0;
 643 }
 644
 645 SilcUInt16 silc_rng_global_get_rn16(void)
 646 {
 647   return global_rng ? silc_rng_get_rn16(global_rng) : 0;
 648 }
 649
 650 SilcUInt32 silc_rng_global_get_rn32(void)
 651 {
 652   return global_rng ? silc_rng_get_rn32(global_rng) : 0;
 653 }
 654
 655 unsigned char *silc_rng_global_get_rn_string(SilcUInt32 len)
 656 {
 657   return global_rng ? silc_rng_get_rn_string(global_rng, len) : NULL;
 658 }
 659
 660 unsigned char *silc_rng_global_get_rn_data(SilcUInt32 len)
 661 {
 662   return global_rng ? silc_rng_get_rn_data(global_rng, len) : NULL;
 663 }
 664
 665 void silc_rng_global_add_noise(unsigned char *buffer, SilcUInt32 len)
 666 {
 667   if (global_rng)
 668     silc_rng_add_noise(global_rng, buffer, len);
 669 }