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.2  2000/07/05 06:08:43  priikone
  31  *      Global cosmetic change.
  32  *
  33  * Revision 1.1.1.1  2000/06/27 11:36:55  priikone
  34  *      Imported from internal CVS/Added Log headers.
  35  *
  36  *
  37  */
  38
  39 #include "silcincludes.h"
  40
  41 #undef SILC_RNG_DEBUG
  42 /* #define SILC_RNG_DEBUG */
  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    unsigned int low
  54    unsigned int 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   unsigned int low;
  67   unsigned int 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 #if 0
 165     next->pos = sizeof(rng->pool) -
 166       ((i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM))) + 8;
 167 #endif
 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 }
 181
 182 /* This function gets 'soft' noise from environment. */
 183
 184 void silc_rng_get_soft_noise(SilcRng rng)
 185 {
 186   struct tms ptime;
 187
 188   silc_rng_xor(rng, clock(), 0);
 189   silc_rng_xor(rng, getpid(), 1);
 190   silc_rng_xor(rng, getpgid(getpid() << 8), 2);
 191   silc_rng_xor(rng, getpgid(getpid() << 8), 3);
 192   silc_rng_xor(rng, getgid(), 4);
 193   silc_rng_xor(rng, getpgrp(), 5);
 194   silc_rng_xor(rng, getsid(getpid() << 16), 6);
 195   silc_rng_xor(rng, times(&ptime), 7);
 196   silc_rng_xor(rng, ptime.tms_utime, 8);
 197   silc_rng_xor(rng, (ptime.tms_utime + ptime.tms_stime), 9);
 198   silc_rng_xor(rng, (ptime.tms_stime + ptime.tms_cutime), 10);
 199   silc_rng_xor(rng, (ptime.tms_utime + ptime.tms_stime), 11);
 200   silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_stime), 12);
 201   silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_cstime), 13);
 202   silc_rng_xor(rng, (ptime.tms_utime ^ ptime.tms_stime), 14);
 203   silc_rng_xor(rng, (ptime.tms_stime ^ ptime.tms_cutime), 15);
 204   silc_rng_xor(rng, (ptime.tms_cutime + ptime.tms_stime), 16);
 205   silc_rng_xor(rng, (ptime.tms_stime << 8), 17);
 206   silc_rng_xor(rng, clock() << 4, 18);
 207   silc_rng_xor(rng, getpgid(getpid() << 8), 19);
 208   silc_rng_xor(rng, getpgrp(), 20);
 209   silc_rng_xor(rng, getsid(getpid() << 16), 21);
 210   silc_rng_xor(rng, times(&ptime), 22);
 211   silc_rng_xor(rng, ptime.tms_utime, 23);
 212   silc_rng_xor(rng, getpgrp(), 24);
 213
 214   /* Stir random pool */
 215   silc_rng_stir_pool(rng);
 216 }
 217
 218 /* This function gets noise from different commands */
 219
 220 void silc_rng_get_medium_noise(SilcRng rng)
 221 {
 222   silc_rng_exec_command(rng, "ps -lefaww 2> /dev/null");
 223   silc_rng_exec_command(rng, "ls -afiln 2> /dev/null");
 224   silc_rng_exec_command(rng, "ps -asww 2> /dev/null");
 225   silc_rng_exec_command(rng, "ls -afiln /proc 2> /dev/null");
 226   /*
 227   silc_rng_exec_command(rng, "ps -ef 2> /dev/null");
 228   silc_rng_exec_command(rng, "ls -alin /dev 2> /dev/null");
 229   */
 230 }
 231
 232 /* This function gets 'hard' noise from environment. This tries to
 233    get the noise from /dev/random if available. */
 234
 235 void silc_rng_get_hard_noise(SilcRng rng)
 236 {
 237   char buf[32];
 238   int fd, len, i;
 239
 240   /* Get noise from /dev/random if available */
 241   fd = open("/dev/random", O_RDONLY);
 242   if (fd < 0)
 243     return;
 244
 245   fcntl(fd, F_SETFL, O_NONBLOCK);
 246
 247   for (i = 0; i < 8; i++) {
 248     len = read(fd, buf, sizeof(buf));
 249     if (len <= 0)
 250       goto out;
 251     silc_rng_add_noise(rng, buf, len);
 252   }
 253
 254  out:
 255   close(fd);
 256   memset(buf, 0, sizeof(buf));
 257 }
 258
 259 /* Execs command and gets noise from its output */
 260
 261 void silc_rng_exec_command(SilcRng rng, char *command)
 262 {
 263   char buf[2048];
 264   FILE *fd;
 265   int i;
 266   int c;
 267
 268   /* Open process */
 269   fd = popen(command, "r");
 270   if (!fd)
 271     return;
 272
 273   /* Get data as much as we can get into the buffer */
 274   for (i = 0; i < sizeof(buf); i++) {
 275     c = fgetc(fd);
 276     if (c == EOF) {
 277       if (!i)
 278         return;
 279       break;
 280     }
 281     buf[i] = c;
 282   }
 283
 284   pclose(fd);
 285
 286   /* Add the buffer into random pool */
 287   silc_rng_add_noise(rng, buf, strlen(buf));
 288   memset(buf, 0, sizeof(buf));
 289 }
 290
 291 /* This function adds the contents of the buffer as noise into random
 292    pool. After adding the noise the pool is stirred. */
 293
 294 void silc_rng_add_noise(SilcRng rng, unsigned char *buffer,
 295                         unsigned int len)
 296 {
 297   unsigned int i, pos;
 298
 299   pos = silc_rng_get_position(rng);
 300
 301   /* Add the buffer one by one into the pool */
 302   for(i = 0; i < len; i++, buffer++) {
 303     if(pos >= SILC_RNG_POOLSIZE)
 304       break;
 305     rng->pool[pos++] ^= *buffer;
 306   }
 307
 308   /* Stir random pool */
 309   silc_rng_stir_pool(rng);
 310 }
 311
 312 /* XOR's data into the pool */
 313
 314 void silc_rng_xor(SilcRng rng, unsigned int val, unsigned int pos)
 315 {
 316   assert(rng != NULL);
 317   rng->pool[pos] ^= val + val;
 318 }
 319
 320 /* This function stirs the random pool by encrypting buffer in CFB
 321    (cipher feedback) mode with SHA1 algorithm. */
 322
 323 void silc_rng_stir_pool(SilcRng rng)
 324 {
 325   int i;
 326   unsigned long iv[5];
 327
 328   /* Get the IV */
 329   memcpy(iv, &rng->pool[SILC_RNG_POOLSIZE - 256], sizeof(iv));
 330
 331   /* First CFB pass */
 332   for (i = 0; i < SILC_RNG_POOLSIZE; i += 5) {
 333     rng->sha1->hash->transform(iv, rng->key);
 334     iv[0] = rng->pool[i] ^= iv[0];
 335     iv[1] = rng->pool[i + 1] ^= iv[1];
 336     iv[2] = rng->pool[i + 2] ^= iv[2];
 337     iv[3] = rng->pool[i + 3] ^= iv[3];
 338     iv[4] = rng->pool[i + 4] ^= iv[4];
 339   }
 340
 341   /* Get new key */
 342   memcpy(rng->key, &rng->pool[silc_rng_get_position(rng)], sizeof(rng->key));
 343
 344   /* Second CFB pass */
 345   for (i = 0; i < SILC_RNG_POOLSIZE; i += 5) {
 346     rng->sha1->hash->transform(iv, rng->key);
 347     iv[0] = rng->pool[i] ^= iv[0];
 348     iv[1] = rng->pool[i + 1] ^= iv[1];
 349     iv[2] = rng->pool[i + 2] ^= iv[2];
 350     iv[3] = rng->pool[i + 3] ^= iv[3];
 351     iv[4] = rng->pool[i + 4] ^= iv[4];
 352   }
 353
 354   memset(iv, 0, sizeof(iv));
 355 }
 356
 357 /* Returns next position where data is fetched from the pool or
 358    put to the pool. */
 359
 360 unsigned int silc_rng_get_position(SilcRng rng)
 361 {
 362   SilcRngState next;
 363   unsigned int pos;
 364
 365   next = rng->state->next;
 366
 367   pos = rng->state->pos++;
 368   if ((next->low != 0 && pos >= next->low) || (pos >= SILC_RNG_POOLSIZE))
 369     rng->state->pos = rng->state->low;
 370
 371 #ifdef SILC_RNG_DEBUG
 372     fprintf(stderr, "state: %p: low: %d, pos: %d\n",
 373             rng->state, rng->state->low, rng->state->pos);
 374 #endif
 375
 376   rng->state = next;
 377
 378   return pos;
 379 }
 380
 381 /* returns random byte. Every two byte is from pools low or high state. */
 382
 383 unsigned char silc_rng_get_byte(SilcRng rng)
 384 {
 385   return rng->pool[silc_rng_get_position(rng)];
 386 }
 387
 388 /* Returns 16 bit random number */
 389
 390 unsigned short silc_rng_get_rn16(SilcRng rng)
 391 {
 392   unsigned char rn[2];
 393   unsigned short num;
 394
 395   rn[0] = silc_rng_get_byte(rng);
 396   rn[1] = silc_rng_get_byte(rng);
 397   SILC_GET16_MSB(num, rn);
 398
 399   return num;
 400 }
 401
 402 /* Returns 32 bit random number */
 403
 404 unsigned int silc_rng_get_rn32(SilcRng rng)
 405 {
 406   unsigned char rn[4];
 407   unsigned short num;
 408
 409   rn[0] = silc_rng_get_byte(rng);
 410   rn[1] = silc_rng_get_byte(rng);
 411   rn[2] = silc_rng_get_byte(rng);
 412   rn[3] = silc_rng_get_byte(rng);
 413   SILC_GET32_MSB(num, rn);
 414
 415   return num;
 416 }
 417
 418 /* Returns random number string. Returned string is in HEX format. */
 419
 420 unsigned char *silc_rng_get_rn_string(SilcRng rng, unsigned int len)
 421 {
 422   int i;
 423   unsigned char *string;
 424
 425   string = silc_calloc((len * 2 + 1), sizeof(unsigned char));
 426
 427   for (i = 0; i < len; i++)
 428     sprintf(string + 2 * i, "%02x", silc_rng_get_byte(rng));
 429
 430   return string;
 431 }