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 #ifndef SILC_WIN32
 307   char buf[1024];
 308   FILE *fd;
 309   int i;
 310   int c;
 311
 312   /* Open process */
 313   fd = popen(command, "r");
 314   if (!fd)
 315     return;
 316
 317   /* Get data as much as we can get into the buffer */
 318   for (i = 0; i < sizeof(buf); i++) {
 319     c = fgetc(fd);
 320     if (c == EOF) {
 321       if (!i)
 322         return;
 323       break;
 324     }
 325     buf[i] = c;
 326   }
 327
 328   pclose(fd);
 329
 330   /* Add the buffer into random pool */
 331   silc_rng_add_noise(rng, buf, strlen(buf));
 332   memset(buf, 0, sizeof(buf));
 333 #endif
 334 }
 335
 336 /* This function adds the contents of the buffer as noise into random
 337    pool. After adding the noise the pool is stirred. */
 338
 339 void silc_rng_add_noise(SilcRng rng, unsigned char *buffer, uint32 len)
 340 {
 341   uint32 i, pos;
 342
 343   pos = silc_rng_get_position(rng);
 344
 345   /* Add the buffer one by one into the pool */
 346   for(i = 0; i < len; i++, buffer++) {
 347     if(pos >= SILC_RNG_POOLSIZE)
 348       break;
 349     rng->pool[pos++] ^= *buffer;
 350   }
 351
 352   /* Stir random pool */
 353   silc_rng_stir_pool(rng);
 354 }
 355
 356 /* XOR's data into the pool */
 357
 358 static void silc_rng_xor(SilcRng rng, uint32 val, unsigned int pos)
 359 {
 360   assert(rng != NULL);
 361   rng->pool[pos] ^= val + val;
 362 }
 363
 364 /* This function stirs the random pool by encrypting buffer in CFB
 365    (cipher feedback) mode with SHA1 algorithm. */
 366
 367 static void silc_rng_stir_pool(SilcRng rng)
 368 {
 369   int i;
 370   uint32 iv[5];
 371
 372   /* Get the IV */
 373   memcpy(iv, &rng->pool[SILC_RNG_POOLSIZE - 256], sizeof(iv));
 374
 375   /* First CFB pass */
 376   for (i = 0; i < SILC_RNG_POOLSIZE; i += 5) {
 377     rng->sha1->hash->transform(iv, rng->key);
 378     iv[0] = rng->pool[i] ^= iv[0];
 379     iv[1] = rng->pool[i + 1] ^= iv[1];
 380     iv[2] = rng->pool[i + 2] ^= iv[2];
 381     iv[3] = rng->pool[i + 3] ^= iv[3];
 382     iv[4] = rng->pool[i + 4] ^= iv[4];
 383   }
 384
 385   /* Get new key */
 386   memcpy(rng->key, &rng->pool[silc_rng_get_position(rng)], sizeof(rng->key));
 387
 388   /* Second CFB pass */
 389   for (i = 0; i < SILC_RNG_POOLSIZE; i += 5) {
 390     rng->sha1->hash->transform(iv, rng->key);
 391     iv[0] = rng->pool[i] ^= iv[0];
 392     iv[1] = rng->pool[i + 1] ^= iv[1];
 393     iv[2] = rng->pool[i + 2] ^= iv[2];
 394     iv[3] = rng->pool[i + 3] ^= iv[3];
 395     iv[4] = rng->pool[i + 4] ^= iv[4];
 396   }
 397
 398   memset(iv, 0, sizeof(iv));
 399 }
 400
 401 /* Returns next position where data is fetched from the pool or
 402    put to the pool. */
 403
 404 static uint32 silc_rng_get_position(SilcRng rng)
 405 {
 406   SilcRngState next;
 407   uint32 pos;
 408
 409   next = rng->state->next;
 410
 411   pos = rng->state->pos++;
 412   if ((next->low != 0 && pos >= next->low) || (pos >= SILC_RNG_POOLSIZE))
 413     rng->state->pos = rng->state->low;
 414
 415 #ifdef SILC_RNG_DEBUG
 416     fprintf(stderr, "state: %p: low: %lu, pos: %lu\n",
 417             rng->state, rng->state->low, rng->state->pos);
 418 #endif
 419
 420   rng->state = next;
 421
 422   return pos;
 423 }
 424
 425 /* Returns random byte. */
 426
 427 unsigned char silc_rng_get_byte(SilcRng rng)
 428 {
 429   rng->threshhold++;
 430
 431   /* Get more soft noise after 64 bits threshhold */
 432   if (rng->threshhold >= 8)
 433     silc_rng_get_soft_noise(rng);
 434
 435   /* Get hard noise after 160 bits threshhold, zero the threshhold. */
 436   if (rng->threshhold >= 20) {
 437     rng->threshhold = 0;
 438     silc_rng_get_hard_noise(rng);
 439   }
 440
 441   return rng->pool[silc_rng_get_position(rng)];
 442 }
 443
 444 /* Returns 16 bit random number */
 445
 446 uint16 silc_rng_get_rn16(SilcRng rng)
 447 {
 448   unsigned char rn[2];
 449   uint16 num;
 450
 451   rn[0] = silc_rng_get_byte(rng);
 452   rn[1] = silc_rng_get_byte(rng);
 453   SILC_GET16_MSB(num, rn);
 454
 455   return num;
 456 }
 457
 458 /* Returns 32 bit random number */
 459
 460 uint32 silc_rng_get_rn32(SilcRng rng)
 461 {
 462   unsigned char rn[4];
 463   uint16 num;
 464
 465   rn[0] = silc_rng_get_byte(rng);
 466   rn[1] = silc_rng_get_byte(rng);
 467   rn[2] = silc_rng_get_byte(rng);
 468   rn[3] = silc_rng_get_byte(rng);
 469   SILC_GET32_MSB(num, rn);
 470
 471   return num;
 472 }
 473
 474 /* Returns random number string. Returned string is in HEX format. */
 475
 476 unsigned char *silc_rng_get_rn_string(SilcRng rng, uint32 len)
 477 {
 478   int i;
 479   unsigned char *string;
 480
 481   string = silc_calloc((len * 2 + 1), sizeof(unsigned char));
 482
 483   for (i = 0; i < len; i++)
 484     sprintf(string + 2 * i, "%02x", silc_rng_get_byte(rng));
 485
 486   return string;
 487 }
 488
 489 /* Returns random number binary data. */
 490
 491 unsigned char *silc_rng_get_rn_data(SilcRng rng, uint32 len)
 492 {
 493   int i;
 494   unsigned char *data;
 495
 496   data = silc_calloc(len + 1, sizeof(*data));
 497
 498   for (i = 0; i < len; i++)
 499     data[i] = silc_rng_get_byte(rng);
 500
 501   return data;
 502 }
 503
 504 /* Global RNG. This is global RNG that application can initialize so
 505    that any part of code anywhere can use RNG without having to allocate
 506    new RNG object everytime.  If this is not initialized then these routines
 507    will fail.  Note: currently in SILC applications always initialize this. */
 508
 509 SilcRng global_rng = NULL;
 510
 511 /* Initialize global RNG. If `rng' is provided it is set as the global
 512    RNG object (it can be allocated by the application for example). */
 513
 514 int silc_rng_global_init(SilcRng rng)
 515 {
 516   if (rng)
 517     global_rng = rng;
 518   else
 519     global_rng = silc_rng_alloc();
 520
 521   return TRUE;
 522 }
 523
 524 /* Uninitialize global RNG */
 525
 526 int silc_rng_global_uninit()
 527 {
 528   if (global_rng) {
 529     silc_rng_free(global_rng);
 530     global_rng = NULL;
 531   }
 532
 533   return TRUE;
 534 }
 535
 536 /* These are analogous to the functions above. */
 537
 538 unsigned char silc_rng_global_get_byte()
 539 {
 540   return global_rng ? silc_rng_get_byte(global_rng) : 0;
 541 }
 542
 543 uint16 silc_rng_global_get_rn16()
 544 {
 545   return global_rng ? silc_rng_get_rn16(global_rng) : 0;
 546 }
 547
 548 uint32 silc_rng_global_get_rn32()
 549 {
 550   return global_rng ? silc_rng_get_rn32(global_rng) : 0;
 551 }
 552
 553 unsigned char *silc_rng_global_get_rn_string(uint32 len)
 554 {
 555   return global_rng ? silc_rng_get_rn_string(global_rng, len) : NULL;
 556 }
 557
 558 unsigned char *silc_rng_global_get_rn_data(uint32 len)
 559 {
 560   return global_rng ? silc_rng_get_rn_data(global_rng, len) : NULL;
 561 }
 562
 563 void silc_rng_global_add_noise(unsigned char *buffer, uint32 len)
 564 {
 565   if (global_rng)
 566     silc_rng_add_noise(global_rng, buffer, len);
 567 }