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