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