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