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