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 /*
  21  * Created: Sun Mar  9 00:09:18 1997
  22  *
  23  * This RNG is based on Secure Shell's random number generator.
  24  */
  25 /* XXX: Some operations block resulting slow initialization.
  26  * XXX: I have some pending changes to make this better. */
  27 /*
  28  * $Id$
  29  * $Log$
  30  * Revision 1.1  2000/06/27 11:36:55  priikone
  31  * Initial revision
  32  *
  33  *
  34  */
  35
  36 #include "silcincludes.h"
  37
  38 #undef SILC_RNG_DEBUG
  39 /* #define SILC_RNG_DEBUG */
  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    unsigned int low
  51    unsigned int 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   unsigned int low;
  64   unsigned int 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 */
  99 typedef struct SilcRngObjectStruct {
 100   unsigned char pool[SILC_RNG_POOLSIZE];
 101   unsigned char key[64];
 102   SilcRngState state;
 103   SilcHash sha1;
 104 } SilcRngObject;
 105
 106 /* Allocates new RNG object. */
 107
 108 SilcRng silc_rng_alloc()
 109 {
 110   SilcRng new;
 111
 112   SILC_LOG_DEBUG(("Allocating new RNG object"));
 113
 114   new = silc_calloc(1, sizeof(*new));
 115   if (!new) {
 116     SILC_LOG_ERROR(("Could not allocate new RNG object"));
 117     return NULL;
 118   }
 119
 120   memset(new->pool, 0, sizeof(new->pool));
 121   memset(new->key, 0, sizeof(new->key));
 122   new->state = NULL;
 123   silc_hash_alloc("sha1", &new->sha1);
 124
 125   return new;
 126 }
 127
 128 /* Free's RNG object. */
 129
 130 void silc_rng_free(SilcRng rng)
 131 {
 132   if (rng) {
 133     memset(rng->pool, 0, sizeof(rng->pool));
 134     memset(rng->key, 0, sizeof(rng->key));
 135     silc_free(rng->sha1);
 136     silc_free(rng);
 137   }
 138 }
 139
 140 /* Initializes random number generator by getting noise from environment.
 141    The environmental noise is our so called seed. One should not call
 142    this function more than once. */
 143
 144 void silc_rng_init(SilcRng rng)
 145 {
 146   int i;
 147   SilcRngState first, next;
 148
 149   assert(rng != NULL);
 150
 151   SILC_LOG_DEBUG(("Initializing RNG object"));
 152
 153   /* Initialize the states for the RNG. */
 154   rng->state = silc_malloc(sizeof(*rng->state));
 155   rng->state->low = 0;
 156   rng->state->pos = 8;
 157   rng->state->next = NULL;
 158   first = rng->state;
 159   for (i = SILC_RNG_STATE_NUM - 1; i >= 1; i--) {
 160     next = silc_malloc(sizeof(*rng->state));
 161     next->low =
 162       (i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM));
 163     next->pos =
 164       (i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM)) + 8;
 165 #if 0
 166     next->pos = sizeof(rng->pool) -
 167       ((i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM))) + 8;
 168 #endif
 169     next->next = rng->state;
 170     rng->state = next;
 171   }
 172   first->next = next;
 173   rng->state = first;
 174
 175   memset(rng->pool, 0, sizeof(rng->pool));
 176
 177   /* Get noise from various environmental sources */
 178   silc_rng_get_soft_noise(rng);
 179   silc_rng_get_medium_noise(rng);
 180   silc_rng_get_hard_noise(rng);
 181 }
 182
 183 /* This function gets 'soft' noise from environment. */
 184
 185 void silc_rng_get_soft_noise(SilcRng rng)
 186 {
 187   struct tms ptime;
 188
 189   silc_rng_xor(rng, clock(), 0);
 190   silc_rng_xor(rng, getpid(), 1);
 191   silc_rng_xor(rng, getpgid(getpid() << 8), 2);
 192   silc_rng_xor(rng, getpgid(getpid() << 8), 3);
 193   silc_rng_xor(rng, getgid(), 4);
 194   silc_rng_xor(rng, getpgrp(), 5);
 195   silc_rng_xor(rng, getsid(getpid() << 16), 6);
 196   silc_rng_xor(rng, times(&ptime), 7);
 197   silc_rng_xor(rng, ptime.tms_utime, 8);
 198   silc_rng_xor(rng, (ptime.tms_utime + ptime.tms_stime), 9);
 199   silc_rng_xor(rng, (ptime.tms_stime + ptime.tms_cutime), 10);
 200   silc_rng_xor(rng, (ptime.tms_utime + ptime.tms_stime), 11);
 201   silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_stime), 12);
 202   silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_cstime), 13);
 203   silc_rng_xor(rng, (ptime.tms_utime ^ ptime.tms_stime), 14);
 204   silc_rng_xor(rng, (ptime.tms_stime ^ ptime.tms_cutime), 15);
 205   silc_rng_xor(rng, (ptime.tms_cutime + ptime.tms_stime), 16);
 206   silc_rng_xor(rng, (ptime.tms_stime << 8), 17);
 207   silc_rng_xor(rng, clock() << 4, 18);
 208   silc_rng_xor(rng, getpgid(getpid() << 8), 19);
 209   silc_rng_xor(rng, getpgrp(), 20);
 210   silc_rng_xor(rng, getsid(getpid() << 16), 21);
 211   silc_rng_xor(rng, times(&ptime), 22);
 212   silc_rng_xor(rng, ptime.tms_utime, 23);
 213   silc_rng_xor(rng, getpgrp(), 24);
 214
 215   /* Stir random pool */
 216   silc_rng_stir_pool(rng);
 217 }
 218
 219 /* This function gets noise from different commands */
 220
 221 void silc_rng_get_medium_noise(SilcRng rng)
 222 {
 223   silc_rng_exec_command(rng, "ps -lefaww 2> /dev/null");
 224   silc_rng_exec_command(rng, "ls -afiln 2> /dev/null");
 225   silc_rng_exec_command(rng, "ps -asww 2> /dev/null");
 226   silc_rng_exec_command(rng, "ls -afiln /proc 2> /dev/null");
 227   /*
 228   silc_rng_exec_command(rng, "ps -ef 2> /dev/null");
 229   silc_rng_exec_command(rng, "ls -alin /dev 2> /dev/null");
 230   */
 231 }
 232
 233 /* This function gets 'hard' noise from environment. This tries to
 234    get the noise from /dev/random if available. */
 235
 236 void silc_rng_get_hard_noise(SilcRng rng)
 237 {
 238   char buf[32];
 239   int fd, len, i;
 240
 241   /* Get noise from /dev/random if available */
 242   fd = open("/dev/random", O_RDONLY);
 243   if (fd < 0)
 244     return;
 245
 246   fcntl(fd, F_SETFL, O_NONBLOCK);
 247
 248   for (i = 0; i < 8; i++) {
 249     len = read(fd, buf, sizeof(buf));
 250     if (len <= 0)
 251       goto out;
 252     silc_rng_add_noise(rng, buf, len);
 253   }
 254
 255  out:
 256   close(fd);
 257   memset(buf, 0, sizeof(buf));
 258 }
 259
 260 /* Execs command and gets noise from its output */
 261
 262 void silc_rng_exec_command(SilcRng rng, char *command)
 263 {
 264   char buf[2048];
 265   FILE *fd;
 266   int i;
 267   int c;
 268
 269   /* Open process */
 270   fd = popen(command, "r");
 271   if (!fd)
 272     return;
 273
 274   /* Get data as much as we can get into the buffer */
 275   for (i = 0; i < sizeof(buf); i++) {
 276     c = fgetc(fd);
 277     if (c == EOF) {
 278       if (!i)
 279         return;
 280       break;
 281     }
 282     buf[i] = c;
 283   }
 284
 285   pclose(fd);
 286
 287   /* Add the buffer into random pool */
 288   silc_rng_add_noise(rng, buf, strlen(buf));
 289   memset(buf, 0, sizeof(buf));
 290 }
 291
 292 /* This function adds the contents of the buffer as noise into random
 293    pool. After adding the noise the pool is stirred. */
 294
 295 void silc_rng_add_noise(SilcRng rng, unsigned char *buffer,
 296                         unsigned int len)
 297 {
 298   unsigned int i, pos;
 299
 300   pos = silc_rng_get_position(rng);
 301
 302   /* Add the buffer one by one into the pool */
 303   for(i = 0; i < len; i++, buffer++) {
 304     if(pos >= SILC_RNG_POOLSIZE)
 305       break;
 306     rng->pool[pos++] ^= *buffer;
 307   }
 308
 309   /* Stir random pool */
 310   silc_rng_stir_pool(rng);
 311 }
 312
 313 /* XOR's data into the pool */
 314
 315 void silc_rng_xor(SilcRng rng, unsigned int val, unsigned int pos)
 316 {
 317   assert(rng != NULL);
 318   rng->pool[pos] ^= val + val;
 319 }
 320
 321 /* This function stirs the random pool by encrypting buffer in CFB
 322    (cipher feedback) mode with SHA1 algorithm. */
 323
 324 void silc_rng_stir_pool(SilcRng rng)
 325 {
 326   int i;
 327   unsigned long iv[5];
 328
 329   /* Get the IV */
 330   memcpy(iv, &rng->pool[SILC_RNG_POOLSIZE - 256], sizeof(iv));
 331
 332   /* First CFB pass */
 333   for (i = 0; i < SILC_RNG_POOLSIZE; i += 5) {
 334     rng->sha1->hash->transform(iv, rng->key);
 335     iv[0] = rng->pool[i] ^= iv[0];
 336     iv[1] = rng->pool[i + 1] ^= iv[1];
 337     iv[2] = rng->pool[i + 2] ^= iv[2];
 338     iv[3] = rng->pool[i + 3] ^= iv[3];
 339     iv[4] = rng->pool[i + 4] ^= iv[4];
 340   }
 341
 342   /* Get new key */
 343   memcpy(rng->key, &rng->pool[silc_rng_get_position(rng)], sizeof(rng->key));
 344
 345   /* Second CFB pass */
 346   for (i = 0; i < SILC_RNG_POOLSIZE; i += 5) {
 347     rng->sha1->hash->transform(iv, rng->key);
 348     iv[0] = rng->pool[i] ^= iv[0];
 349     iv[1] = rng->pool[i + 1] ^= iv[1];
 350     iv[2] = rng->pool[i + 2] ^= iv[2];
 351     iv[3] = rng->pool[i + 3] ^= iv[3];
 352     iv[4] = rng->pool[i + 4] ^= iv[4];
 353   }
 354
 355   memset(iv, 0, sizeof(iv));
 356 }
 357
 358 /* Returns next position where data is fetched from the pool or
 359    put to the pool. */
 360
 361 unsigned int silc_rng_get_position(SilcRng rng)
 362 {
 363   SilcRngState next;
 364   unsigned int pos;
 365
 366   next = rng->state->next;
 367
 368   pos = rng->state->pos++;
 369   if ((next->low != 0 && pos >= next->low) || (pos >= SILC_RNG_POOLSIZE))
 370     rng->state->pos = rng->state->low;
 371
 372 #ifdef SILC_RNG_DEBUG
 373     fprintf(stderr, "state: %p: low: %d, pos: %d\n",
 374             rng->state, rng->state->low, rng->state->pos);
 375 #endif
 376
 377   rng->state = next;
 378
 379   return pos;
 380 }
 381
 382 /* returns random byte. Every two byte is from pools low or high state. */
 383
 384 unsigned char silc_rng_get_byte(SilcRng rng)
 385 {
 386   return rng->pool[silc_rng_get_position(rng)];
 387 }
 388
 389 /* Returns 16 bit random number */
 390
 391 unsigned short silc_rng_get_rn16(SilcRng rng)
 392 {
 393   unsigned char rn[2];
 394   unsigned short num;
 395
 396   rn[0] = silc_rng_get_byte(rng);
 397   rn[1] = silc_rng_get_byte(rng);
 398   SILC_GET16_MSB(num, rn);
 399
 400   return num;
 401 }
 402
 403 /* Returns 32 bit random number */
 404
 405 unsigned int silc_rng_get_rn32(SilcRng rng)
 406 {
 407   unsigned char rn[4];
 408   unsigned short num;
 409
 410   rn[0] = silc_rng_get_byte(rng);
 411   rn[1] = silc_rng_get_byte(rng);
 412   rn[2] = silc_rng_get_byte(rng);
 413   rn[3] = silc_rng_get_byte(rng);
 414   SILC_GET32_MSB(num, rn);
 415
 416   return num;
 417 }
 418
 419 /* Returns random number string. Returned string is in HEX format. */
 420
 421 unsigned char *silc_rng_get_rn_string(SilcRng rng, unsigned int len)
 422 {
 423   int i;
 424   unsigned char *string;
 425
 426   string = silc_calloc((len * 2 + 1), sizeof(unsigned char));
 427   if (string == NULL)
 428     return NULL;
 429
 430   for (i = 0; i < len; i++)
 431     sprintf(string + 2 * i, "%02x", silc_rng_get_byte(rng));
 432
 433   return string;
 434 }