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