Guarantee now zero byte is returned by the RNG.
[silc.git] / lib / silccrypt / silcrng.c
1 /*
2
3   silcrng.c
4
5   Author: Pekka Riikonen <priikone@silcnet.org>
6
7   Copyright (C) 1997 - 2003 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; version 2 of the License.
12
13   This program is distributed in the hope that it will be useful,
14   but WITHOUT ANY WARRANTY; without even the implied warranty of
15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16   GNU General Public License for more details.
17
18 */
19 /* $Id$ */
20 /*
21  * Created: Sun Mar  9 00:09:18 1997
22  *
23  * The original RNG was based on Secure Shell's random number generator
24  * by Tatu Ylönen and was used as reference when programming this RNG.
25  * This RNG has been rewritten twice since the creation.
26  */
27
28 #include "silcincludes.h"
29
30 #ifndef WIN32
31 #ifdef HAVE_GETSID
32 extern pid_t getsid (pid_t __pid);
33 #endif
34
35 #ifdef HAVE_GETPGID
36 extern pid_t getpgid (pid_t __pid);
37 #endif
38 #endif
39
40 #undef SILC_RNG_DEBUG
41 /*#define SILC_RNG_DEBUG*/
42
43 /* Number of states to fetch data from pool. */
44 #define SILC_RNG_STATE_NUM 4
45
46 /* Byte size of the random data pool. */
47 #define SILC_RNG_POOLSIZE (20 * 48)
48
49 static SilcUInt32 silc_rng_get_position(SilcRng rng);
50 static void silc_rng_stir_pool(SilcRng rng);
51 static void silc_rng_xor(SilcRng rng, SilcUInt32 val, unsigned int pos);
52 static void silc_rng_exec_command(SilcRng rng, char *command);
53 static void silc_rng_get_hard_noise(SilcRng rng);
54 static void silc_rng_get_medium_noise(SilcRng rng);
55 static void silc_rng_get_soft_noise(SilcRng rng);
56
57 /*
58    SILC SilcRng State context.
59
60    This object is used by the random number generator to provide
61    variable points where the actual random number is fetched from
62    the random pool. This provides that the data is not fetched always
63    from the same point of the pool. Short description of the fields
64    following.
65
66    SilcUInt32 low
67    SilcUInt32 pos
68
69        The index for the random pool buffer. Lowest and current
70        positions.
71
72    SilcRngStateContext *next
73
74        Pointer to the next state. If this is the last state this
75        will point to the first state thus providing circular list.
76
77 */
78 typedef struct SilcRngStateContext {
79   SilcUInt32 low;
80   SilcUInt32 pos;
81   struct SilcRngStateContext *next;
82 } *SilcRngState;
83
84 /*
85    SILC Random Number Generator object.
86
87    This object holds random pool which is used to generate the random
88    numbers used by various routines needing cryptographically strong
89    random numbers. Following short descriptions of the fields.
90
91    unsigned char pool[]
92
93        The random pool. This buffer holds the random data. This is
94        frequently stirred thus providing ever changing randomnes.
95
96    unsigned char key[64]
97
98        Key used in stirring the random pool. The pool is encrypted
99        with SHA1 hash function in CFB (Cipher Feedback) mode.
100
101    SilcSilcRngState state
102
103        State object that is used to get the next position for the
104        random pool. This position is used to fetch data from pool
105        or to save the data to the pool. The state changes everytime
106        SilcRng is used.
107
108    SilcHash sha1
109
110        Hash object (SHA1) used to make the CFB encryption to the
111        random pool. This is allocated when RNG object is allocated and
112        free'd when RNG object is free'd.
113
114    SilcUInt8 threshold
115
116        Threshold to indicate when it is required to acquire more
117        noise from the environment.  More soft noise is acquired after
118        64 bits of output and hard noise every 160 bits of output.
119
120 */
121 struct SilcRngStruct {
122   unsigned char pool[SILC_RNG_POOLSIZE];
123   unsigned char key[64];
124   SilcRngState state;
125   SilcHash sha1;
126   SilcUInt8 threshold;
127   char *devrandom;
128   int fd_devurandom;
129 };
130
131 /* Allocates new RNG object. */
132
133 SilcRng silc_rng_alloc(void)
134 {
135   SilcRng new;
136
137   SILC_LOG_DEBUG(("Allocating new RNG object"));
138
139   new = silc_calloc(1, sizeof(*new));
140   new->fd_devurandom = -1;
141
142   memset(new->pool, 0, sizeof(new->pool));
143   memset(new->key, 0, sizeof(new->key));
144   new->state = NULL;
145   if (!silc_hash_alloc("sha1", &new->sha1)) {
146     silc_free(new);
147     SILC_LOG_ERROR(("Could not allocate sha1 hash, probably not registered"));
148     return NULL;
149   }
150
151   new->devrandom = strdup("/dev/random");
152
153   return new;
154 }
155
156 /* Free's RNG object. */
157
158 void silc_rng_free(SilcRng rng)
159 {
160   if (rng) {
161     SilcRngState t, n;
162
163     memset(rng->pool, 0, sizeof(rng->pool));
164     memset(rng->key, 0, sizeof(rng->key));
165     silc_hash_free(rng->sha1);
166     silc_free(rng->devrandom);
167
168     if (rng->fd_devurandom != -1)
169       close(rng->fd_devurandom);
170
171     for (t = rng->state->next; t != rng->state; ) {
172       n = t->next;
173       silc_free(t);
174       t = n;
175     }
176     silc_free(rng->state);
177
178     silc_free(rng);
179   }
180 }
181
182 /* Initializes random number generator by getting noise from environment.
183    The environmental noise is our so called seed. One should not call
184    this function more than once. */
185
186 void silc_rng_init(SilcRng rng)
187 {
188   int i;
189   SilcRngState first, next;
190
191   assert(rng != NULL);
192
193   SILC_LOG_DEBUG(("Initializing RNG object"));
194
195   /* Initialize the states for the RNG. */
196   rng->state = silc_calloc(1, sizeof(*rng->state));
197   rng->state->low = 0;
198   rng->state->pos = 8;
199   rng->state->next = NULL;
200   first = rng->state;
201   for (i = SILC_RNG_STATE_NUM - 1; i >= 1; i--) {
202     next = silc_calloc(1, sizeof(*rng->state));
203     next->low =
204       (i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM));
205     next->pos =
206       (i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM)) + 8;
207     next->next = rng->state;
208     rng->state = next;
209   }
210   first->next = next;
211   rng->state = first;
212
213   memset(rng->pool, 0, sizeof(rng->pool));
214
215   /* Get noise from various environmental sources */
216   silc_rng_get_soft_noise(rng);
217   silc_rng_get_medium_noise(rng);
218   silc_rng_get_hard_noise(rng);
219   silc_rng_get_soft_noise(rng);
220   silc_free(rng->devrandom);
221   rng->devrandom = strdup("/dev/urandom");
222 }
223
224 /* This function gets 'soft' noise from environment. */
225
226 static void silc_rng_get_soft_noise(SilcRng rng)
227 {
228 #ifndef SILC_WIN32
229   struct tms ptime;
230 #endif
231   SilcUInt32 pos;
232
233   pos = silc_rng_get_position(rng);
234
235   silc_rng_xor(rng, clock(), 0);
236 #ifndef SILC_WIN32
237 #ifdef HAVE_GETPID
238   silc_rng_xor(rng, getpid(), 1);
239 #ifdef HAVE_GETPGID
240   silc_rng_xor(rng, getpgid(getpid()) << 8, 2);
241   silc_rng_xor(rng, getpgid(getpid()) << 8, 3);
242 #endif
243   silc_rng_xor(rng, getgid(), 4);
244 #endif
245 #ifdef HAVE_GETPGRP
246   silc_rng_xor(rng, getpgrp(), 5);
247 #endif
248 #ifdef HAVE_GETSID
249   silc_rng_xor(rng, getsid(getpid()) << 16, 6);
250 #endif
251   silc_rng_xor(rng, times(&ptime), 7);
252   silc_rng_xor(rng, ptime.tms_utime, 8);
253   silc_rng_xor(rng, (ptime.tms_utime + ptime.tms_stime), pos++);
254   silc_rng_xor(rng, (ptime.tms_stime + ptime.tms_cutime), pos++);
255   silc_rng_xor(rng, (ptime.tms_utime + ptime.tms_stime), pos++);
256   silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_stime), pos++);
257   silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_cstime), pos++);
258   silc_rng_xor(rng, (ptime.tms_utime ^ ptime.tms_stime), pos++);
259   silc_rng_xor(rng, (ptime.tms_stime ^ ptime.tms_cutime), pos++);
260   silc_rng_xor(rng, (ptime.tms_cutime + ptime.tms_stime), pos++);
261   silc_rng_xor(rng, (ptime.tms_stime << 8), pos++);
262 #endif
263   silc_rng_xor(rng, clock() << 4, pos++);
264 #ifndef SILC_WIN32
265 #ifdef HAVE_GETPGID
266   silc_rng_xor(rng, getpgid(getpid()) << 8, pos++);
267 #endif
268 #ifdef HAVE_GETPGRP
269   silc_rng_xor(rng, getpgrp(), pos++);
270 #endif
271 #ifdef HAVE_SETSID
272   silc_rng_xor(rng, getsid(getpid()) << 16, pos++);
273 #endif
274   silc_rng_xor(rng, times(&ptime), pos++);
275   silc_rng_xor(rng, ptime.tms_utime, pos++);
276 #ifdef HAVE_GETPGRP
277   silc_rng_xor(rng, getpgrp(), pos++);
278 #endif
279 #endif
280
281 #ifdef SILC_RNG_DEBUG
282   SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
283 #endif
284
285   /* Stir random pool */
286   silc_rng_stir_pool(rng);
287 }
288
289 /* This function gets noise from different commands */
290
291 static void silc_rng_get_medium_noise(SilcRng rng)
292 {
293   silc_rng_exec_command(rng, "ps -leaww 2> /dev/null");
294   silc_rng_exec_command(rng, "ls -afiln ~ 2> /dev/null");
295   silc_rng_exec_command(rng, "ls -afiln /proc 2> /dev/null");
296   silc_rng_exec_command(rng, "ps -axww 2> /dev/null");
297
298 #ifdef SILC_RNG_DEBUG
299   SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
300 #endif
301 }
302
303 /* This function gets 'hard' noise from environment. This tries to
304    get the noise from /dev/random if available. */
305
306 static void silc_rng_get_hard_noise(SilcRng rng)
307 {
308 #ifndef SILC_WIN32
309   unsigned char buf[32];
310   int fd, len, i;
311
312   /* Get noise from /dev/[u]random if available */
313   fd = open(rng->devrandom, O_RDONLY);
314   if (fd < 0)
315     return;
316
317   fcntl(fd, F_SETFL, O_NONBLOCK);
318
319   for (i = 0; i < 2; i++) {
320     len = read(fd, buf, sizeof(buf));
321     if (len <= 0)
322       goto out;
323     silc_rng_add_noise(rng, buf, len);
324   }
325
326 #ifdef SILC_RNG_DEBUG
327   SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
328 #endif
329
330  out:
331   close(fd);
332   memset(buf, 0, sizeof(buf));
333 #endif
334 }
335
336 /* Execs command and gets noise from its output */
337
338 static void silc_rng_exec_command(SilcRng rng, char *command)
339 {
340 #ifndef SILC_WIN32
341   unsigned char buf[1024];
342   FILE *fd;
343   int i;
344   int c;
345
346   /* Open process */
347   fd = popen(command, "r");
348   if (!fd)
349     return;
350
351   /* Get data as much as we can get into the buffer */
352   for (i = 0; i < sizeof(buf); i++) {
353     c = fgetc(fd);
354     if (c == EOF)
355       break;
356     buf[i] = c;
357   }
358
359   pclose(fd);
360
361   if (i != 0) {
362     /* Add the buffer into random pool */
363     silc_rng_add_noise(rng, buf, i);
364     memset(buf, 0, sizeof(buf));
365   }
366 #endif
367 }
368
369 /* This function adds the contents of the buffer as noise into random
370    pool. After adding the noise the pool is stirred. */
371
372 void silc_rng_add_noise(SilcRng rng, unsigned char *buffer, SilcUInt32 len)
373 {
374   SilcUInt32 i, pos;
375
376   pos = silc_rng_get_position(rng);
377
378   /* Add the buffer one by one into the pool */
379   for(i = 0; i < len; i++, buffer++) {
380     if(pos >= SILC_RNG_POOLSIZE)
381       break;
382     rng->pool[pos++] ^= *buffer;
383   }
384
385   /* Stir random pool */
386   silc_rng_stir_pool(rng);
387 }
388
389 /* XOR's data into the pool */
390
391 static void silc_rng_xor(SilcRng rng, SilcUInt32 val, unsigned int pos)
392 {
393   SilcUInt32 tmp;
394
395   SILC_GET32_MSB(tmp, &rng->pool[pos]);
396   val ^= tmp + val;
397   SILC_PUT32_MSB(val, &rng->pool[pos]);
398 }
399
400 /* This function stirs the random pool by encrypting buffer in CFB
401    (cipher feedback) mode with SHA1 algorithm. */
402
403 static void silc_rng_stir_pool(SilcRng rng)
404 {
405   int i;
406   SilcUInt32 iv[5], tmp;
407
408   /* Get the IV */
409   SILC_GET32_MSB(iv[0], &rng->pool[16     ]);
410   SILC_GET32_MSB(iv[1], &rng->pool[16 +  4]);
411   SILC_GET32_MSB(iv[2], &rng->pool[16 +  8]);
412   SILC_GET32_MSB(iv[3], &rng->pool[16 + 12]);
413   SILC_GET32_MSB(iv[4], &rng->pool[16 + 16]);
414
415   /* First CFB pass */
416   for (i = 0; i < SILC_RNG_POOLSIZE; i += 20) {
417     silc_hash_transform(rng->sha1, iv, rng->key);
418
419     SILC_GET32_MSB(tmp, &rng->pool[i]);
420     iv[0] ^= tmp;
421     SILC_PUT32_MSB(iv[0], &rng->pool[i]);
422
423     SILC_GET32_MSB(tmp, &rng->pool[i + 4]);
424     iv[1] ^= tmp;
425     SILC_PUT32_MSB(iv[1], &rng->pool[i + 4]);
426
427     SILC_GET32_MSB(tmp, &rng->pool[i + 8]);
428     iv[2] ^= tmp;
429     SILC_PUT32_MSB(iv[2], &rng->pool[i + 8]);
430
431     SILC_GET32_MSB(tmp, &rng->pool[i + 12]);
432     iv[3] ^= tmp;
433     SILC_PUT32_MSB(iv[3], &rng->pool[i + 12]);
434
435     SILC_GET32_MSB(tmp, &rng->pool[i + 16]);
436     iv[4] ^= tmp;
437     SILC_PUT32_MSB(iv[4], &rng->pool[i + 16]);
438   }
439
440   /* Get new key */
441   memcpy(rng->key, &rng->pool[silc_rng_get_position(rng)], sizeof(rng->key));
442
443   /* Second CFB pass */
444   for (i = 0; i < SILC_RNG_POOLSIZE; i += 20) {
445     silc_hash_transform(rng->sha1, iv, rng->key);
446
447     SILC_GET32_MSB(tmp, &rng->pool[i]);
448     iv[0] ^= tmp;
449     SILC_PUT32_MSB(iv[0], &rng->pool[i]);
450
451     SILC_GET32_MSB(tmp, &rng->pool[i + 4]);
452     iv[1] ^= tmp;
453     SILC_PUT32_MSB(iv[1], &rng->pool[i + 4]);
454
455     SILC_GET32_MSB(tmp, &rng->pool[i + 8]);
456     iv[2] ^= tmp;
457     SILC_PUT32_MSB(iv[2], &rng->pool[i + 8]);
458
459     SILC_GET32_MSB(tmp, &rng->pool[i + 12]);
460     iv[3] ^= tmp;
461     SILC_PUT32_MSB(iv[3], &rng->pool[i + 12]);
462
463     SILC_GET32_MSB(tmp, &rng->pool[i + 16]);
464     iv[4] ^= tmp;
465     SILC_PUT32_MSB(iv[4], &rng->pool[i + 16]);
466   }
467
468   memset(iv, 0, sizeof(iv));
469 }
470
471 /* Returns next position where data is fetched from the pool or
472    put to the pool. */
473
474 static SilcUInt32 silc_rng_get_position(SilcRng rng)
475 {
476   SilcRngState next;
477   SilcUInt32 pos;
478
479   next = rng->state->next;
480
481   pos = rng->state->pos++;
482   if ((next->low != 0 && pos >= next->low) || (pos >= SILC_RNG_POOLSIZE))
483     rng->state->pos = rng->state->low;
484
485 #ifdef SILC_RNG_DEBUG
486     fprintf(stderr, "state: %p: low: %lu, pos: %lu\n",
487             rng->state, rng->state->low, rng->state->pos);
488 #endif
489
490   rng->state = next;
491
492   return pos;
493 }
494
495 /* Returns random byte. */
496
497 SilcUInt8 silc_rng_get_byte(SilcRng rng)
498 {
499   SilcUInt8 byte;
500
501   rng->threshold++;
502
503   /* Get more soft noise after 64 bits threshold */
504   if (rng->threshold >= 8)
505     silc_rng_get_soft_noise(rng);
506
507   /* Get hard noise after 160 bits threshold, zero the threshold. */
508   if (rng->threshold >= 20) {
509     rng->threshold = 0;
510     silc_rng_get_hard_noise(rng);
511   }
512
513   do byte = rng->pool[silc_rng_get_position(rng)]; while (byte == 0x00);
514   return byte;
515 }
516
517 /* Return random byte as fast as possible. Reads from /dev/urandom if
518    available. If not then return from normal RNG (not so fast). */
519
520 SilcUInt8 silc_rng_get_byte_fast(SilcRng rng)
521 {
522 #ifndef SILC_WIN32
523   unsigned char buf[1];
524
525   if (rng->fd_devurandom == -1) {
526     rng->fd_devurandom = open("/dev/urandom", O_RDONLY);
527     if (rng->fd_devurandom < 0)
528       return silc_rng_get_byte(rng);
529     fcntl(rng->fd_devurandom, F_SETFL, O_NONBLOCK);
530   }
531
532   if (read(rng->fd_devurandom, buf, sizeof(buf)) < 0)
533     return silc_rng_get_byte(rng);
534
535   return buf[0] != 0x00 ? buf[0] : silc_rng_get_byte(rng);
536 #else
537   return silc_rng_get_byte(rng);
538 #endif
539 }
540
541 /* Returns 16 bit random number */
542
543 SilcUInt16 silc_rng_get_rn16(SilcRng rng)
544 {
545   unsigned char rn[2];
546   SilcUInt16 num;
547
548   rn[0] = silc_rng_get_byte(rng);
549   rn[1] = silc_rng_get_byte(rng);
550   SILC_GET16_MSB(num, rn);
551
552   return num;
553 }
554
555 /* Returns 32 bit random number */
556
557 SilcUInt32 silc_rng_get_rn32(SilcRng rng)
558 {
559   unsigned char rn[4];
560   SilcUInt32 num;
561
562   rn[0] = silc_rng_get_byte(rng);
563   rn[1] = silc_rng_get_byte(rng);
564   rn[2] = silc_rng_get_byte(rng);
565   rn[3] = silc_rng_get_byte(rng);
566   SILC_GET32_MSB(num, rn);
567
568   return num;
569 }
570
571 /* Returns non-zero random number string. Returned string is in HEX format. */
572
573 unsigned char *silc_rng_get_rn_string(SilcRng rng, SilcUInt32 len)
574 {
575   int i;
576   unsigned char *string;
577
578   string = silc_calloc((len * 2 + 1), sizeof(unsigned char));
579
580   for (i = 0; i < len; i++)
581     sprintf(string + 2 * i, "%02x", silc_rng_get_byte(rng));
582
583   return string;
584 }
585
586 /* Returns non-zero random number binary data. */
587
588 unsigned char *silc_rng_get_rn_data(SilcRng rng, SilcUInt32 len)
589 {
590   int i;
591   unsigned char *data;
592
593   data = silc_calloc(len + 1, sizeof(*data));
594
595   for (i = 0; i < len; i++)
596     data[i] = silc_rng_get_byte(rng);
597
598   return data;
599 }
600
601 /* Global RNG. This is global RNG that application can initialize so
602    that any part of code anywhere can use RNG without having to allocate
603    new RNG object everytime.  If this is not initialized then these routines
604    will fail.  Note: currently in SILC applications always initialize this. */
605
606 SilcRng global_rng = NULL;
607
608 /* Initialize global RNG. If `rng' is provided it is set as the global
609    RNG object (it can be allocated by the application for example). */
610
611 bool silc_rng_global_init(SilcRng rng)
612 {
613   if (rng) {
614     global_rng = rng;
615     return TRUE;
616   }
617
618   global_rng = silc_rng_alloc();
619   silc_rng_init(global_rng);
620
621   return TRUE;
622 }
623
624 /* Uninitialize global RNG */
625
626 bool silc_rng_global_uninit(void)
627 {
628   if (global_rng) {
629     silc_rng_free(global_rng);
630     global_rng = NULL;
631   }
632
633   return TRUE;
634 }
635
636 /* These are analogous to the functions above. */
637
638 SilcUInt8 silc_rng_global_get_byte(void)
639 {
640   return global_rng ? silc_rng_get_byte(global_rng) : 0;
641 }
642
643 /* Return random byte as fast as possible. Reads from /dev/urandom if
644    available. If not then return from normal RNG (not so fast). */
645
646 SilcUInt8 silc_rng_global_get_byte_fast(void)
647 {
648   return global_rng ? silc_rng_get_byte_fast(global_rng) : 0;
649 }
650
651 SilcUInt16 silc_rng_global_get_rn16(void)
652 {
653   return global_rng ? silc_rng_get_rn16(global_rng) : 0;
654 }
655
656 SilcUInt32 silc_rng_global_get_rn32(void)
657 {
658   return global_rng ? silc_rng_get_rn32(global_rng) : 0;
659 }
660
661 unsigned char *silc_rng_global_get_rn_string(SilcUInt32 len)
662 {
663   return global_rng ? silc_rng_get_rn_string(global_rng, len) : NULL;
664 }
665
666 unsigned char *silc_rng_global_get_rn_data(SilcUInt32 len)
667 {
668   return global_rng ? silc_rng_get_rn_data(global_rng, len) : NULL;
669 }
670
671 void silc_rng_global_add_noise(unsigned char *buffer, SilcUInt32 len)
672 {
673   if (global_rng)
674     silc_rng_add_noise(global_rng, buffer, len);
675 }