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