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