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