lib/silccrypt/silcrng.c

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