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