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