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