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