5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 1997 - 2008 Pekka Riikonen
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.
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.
20 * Created: Sun Mar 9 00:09:18 1997
22 * The original RNG was based on Secure Shell's random number generator
23 * by Tatu Ylönen and was used as reference when programming this RNG.
24 * This RNG has been rewritten twice since the creation.
27 #include "silccrypto.h"
31 extern pid_t getsid (pid_t __pid);
35 extern pid_t getpgid (pid_t __pid);
40 /*#define SILC_RNG_DEBUG*/
42 /* Number of states to fetch data from pool. */
43 #define SILC_RNG_STATE_NUM 4
45 /* Byte size of the random data pool. */
46 #define SILC_RNG_POOLSIZE (20 * 48)
48 static SilcUInt32 silc_rng_get_position(SilcRng rng);
49 static void silc_rng_stir_pool(SilcRng rng);
50 static void silc_rng_xor(SilcRng rng, SilcUInt32 val, unsigned int pos);
51 static void silc_rng_exec_command(SilcRng rng, char *command);
52 static void silc_rng_get_hard_noise(SilcRng rng);
53 static void silc_rng_get_medium_noise(SilcRng rng);
54 static void silc_rng_get_soft_noise(SilcRng rng);
57 SILC SilcRng State context.
59 This object is used by the random number generator to provide
60 variable points where the actual random number is fetched from
61 the random pool. This provides that the data is not fetched always
62 from the same point of the pool. Short description of the fields
68 The index for the random pool buffer. Lowest and current
71 SilcRngStateContext *next
73 Pointer to the next state. If this is the last state this
74 will point to the first state thus providing circular list.
77 typedef struct SilcRngStateContext {
80 struct SilcRngStateContext *next;
84 SILC Random Number Generator object.
86 This object holds random pool which is used to generate the random
87 numbers used by various routines needing cryptographically strong
88 random numbers. Following short descriptions of the fields.
92 The random pool. This buffer holds the random data. This is
93 frequently stirred thus providing ever changing randomnes.
97 Key used in stirring the random pool. The pool is encrypted
98 with SHA1 hash function in CFB (Cipher Feedback) mode.
100 SilcSilcRngState state
102 State object that is used to get the next position for the
103 random pool. This position is used to fetch data from pool
104 or to save the data to the pool. The state changes everytime
109 Hash object (SHA1) used to make the CFB encryption to the
110 random pool. This is allocated when RNG object is allocated and
111 free'd when RNG object is free'd.
115 Threshold to indicate when it is required to acquire more
116 noise from the environment. More soft noise is acquired after
117 64 bits of output and hard noise every 160 bits of output.
120 struct SilcRngStruct {
121 unsigned char pool[SILC_RNG_POOLSIZE];
122 unsigned char key[64];
130 /* Allocates new RNG object. */
132 SilcRng silc_rng_alloc(void)
136 SILC_LOG_DEBUG(("Allocating new RNG object"));
138 new = silc_calloc(1, sizeof(*new));
139 new->fd_devurandom = -1;
141 memset(new->pool, 0, sizeof(new->pool));
142 memset(new->key, 0, sizeof(new->key));
144 if (!silc_hash_alloc("sha1", &new->sha1)) {
146 SILC_LOG_ERROR(("Could not allocate sha1 hash, probably not registered"));
150 new->devrandom = strdup("/dev/random");
155 /* Free's RNG object. */
157 void silc_rng_free(SilcRng rng)
162 memset(rng->pool, 0, sizeof(rng->pool));
163 memset(rng->key, 0, sizeof(rng->key));
164 silc_hash_free(rng->sha1);
165 silc_free(rng->devrandom);
167 if (rng->fd_devurandom != -1)
168 close(rng->fd_devurandom);
170 for (t = rng->state->next; t != rng->state; ) {
175 silc_free(rng->state);
181 /* Initializes random number generator by getting noise from environment.
182 The environmental noise is our so called seed. One should not call
183 this function more than once. */
185 void silc_rng_init(SilcRng rng)
188 SilcRngState first, next;
192 SILC_LOG_DEBUG(("Initializing RNG object"));
194 /* Initialize the states for the RNG. */
195 rng->state = silc_calloc(1, sizeof(*rng->state));
198 rng->state->next = NULL;
200 for (i = SILC_RNG_STATE_NUM - 1; i >= 1; i--) {
201 next = silc_calloc(1, sizeof(*rng->state));
203 (i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM));
205 (i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM)) + 8;
206 next->next = rng->state;
212 memset(rng->pool, 0, sizeof(rng->pool));
214 /* Get noise from various environmental sources */
215 silc_rng_get_soft_noise(rng);
216 silc_rng_get_medium_noise(rng);
217 silc_rng_get_hard_noise(rng);
218 silc_rng_get_soft_noise(rng);
219 silc_free(rng->devrandom);
220 rng->devrandom = strdup("/dev/urandom");
223 /* This function gets 'soft' noise from environment. */
225 static void silc_rng_get_soft_noise(SilcRng rng)
231 #ifdef HAVE_GETRUSAGE
235 pos = silc_rng_get_position(rng);
237 silc_rng_xor(rng, clock(), 0);
240 silc_rng_xor(rng, getpid(), 1);
242 silc_rng_xor(rng, getpgid(getpid()) << 8, 2);
243 silc_rng_xor(rng, getpgid(getpid()) << 8, 3);
246 silc_rng_xor(rng, getgid(), 4);
250 silc_rng_xor(rng, getpgrp(), 5);
253 silc_rng_xor(rng, getsid(getpid()) << 16, 6);
256 silc_rng_xor(rng, times(&ptime), 7);
257 silc_rng_xor(rng, ptime.tms_utime, 8);
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_utime + ptime.tms_stime), pos++);
261 silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_stime), pos++);
262 silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_cstime), pos++);
263 silc_rng_xor(rng, (ptime.tms_utime ^ ptime.tms_stime), pos++);
264 silc_rng_xor(rng, (ptime.tms_stime ^ ptime.tms_cutime), pos++);
265 silc_rng_xor(rng, (ptime.tms_cutime + ptime.tms_stime), pos++);
266 silc_rng_xor(rng, (ptime.tms_stime << 8), pos++);
267 #endif /* SILC_SYMBIAN */
269 silc_rng_xor(rng, clock() << 4, pos++);
272 silc_rng_xor(rng, getpgid(getpid()) << 8, pos++);
275 silc_rng_xor(rng, getpgrp(), pos++);
278 silc_rng_xor(rng, getsid(getpid()) << 16, pos++);
281 silc_rng_xor(rng, times(&ptime), pos++);
282 silc_rng_xor(rng, ptime.tms_utime, pos++);
283 #endif /* SILC_SYMBIAN */
285 silc_rng_xor(rng, getpgrp(), pos++);
288 #ifdef HAVE_GETRUSAGE
289 getrusage(RUSAGE_SELF, &r);
290 silc_rng_xor(rng, (r.ru_utime.tv_sec + r.ru_utime.tv_usec), pos++);
291 silc_rng_xor(rng, (r.ru_utime.tv_sec ^ r.ru_utime.tv_usec), pos++);
292 silc_rng_xor(rng, (r.ru_stime.tv_sec + r.ru_stime.tv_usec), pos++);
293 silc_rng_xor(rng, (r.ru_stime.tv_sec ^ r.ru_stime.tv_usec), pos++);
295 silc_rng_xor(rng, (r.ru_maxrss + r.ru_ixrss), pos++);
296 silc_rng_xor(rng, (r.ru_maxrss ^ r.ru_ixrss), pos++);
297 silc_rng_xor(rng, (r.ru_idrss + r.ru_idrss), pos++);
298 silc_rng_xor(rng, (r.ru_idrss ^ r.ru_idrss), pos++);
299 silc_rng_xor(rng, (r.ru_idrss << 16), pos++);
300 silc_rng_xor(rng, (r.ru_minflt + r.ru_majflt), pos++);
301 silc_rng_xor(rng, (r.ru_minflt ^ r.ru_majflt), pos++);
302 silc_rng_xor(rng, (r.ru_nswap + r.ru_oublock + r.ru_inblock), pos++);
303 silc_rng_xor(rng, (r.ru_nswap << 8), pos++);
304 silc_rng_xor(rng, (r.ru_inblock + r.ru_oublock), pos++);
305 silc_rng_xor(rng, (r.ru_inblock ^ r.ru_oublock), pos++);
306 silc_rng_xor(rng, (r.ru_msgsnd ^ r.ru_msgrcv), pos++);
307 silc_rng_xor(rng, (r.ru_nsignals + r.ru_msgsnd + r.ru_msgrcv), pos++);
308 silc_rng_xor(rng, (r.ru_nsignals << 16), pos++);
309 silc_rng_xor(rng, (r.ru_nvcsw + r.ru_nivcsw), pos++);
310 silc_rng_xor(rng, (r.ru_nvcsw ^ r.ru_nivcsw), pos++);
311 #endif /* SILC_SYMBIAN */
312 #endif /* HAVE_GETRUSAGE */
314 #ifdef SILC_RNG_DEBUG
315 SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
318 /* Stir random pool */
319 silc_rng_stir_pool(rng);
322 /* This function gets noise from different commands */
324 static void silc_rng_get_medium_noise(SilcRng rng)
326 /* If getrusage is available, there is no need for shell commands */
327 #ifdef HAVE_GETRUSAGE
330 silc_rng_exec_command(rng, "ps -leaww 2> /dev/null");
331 silc_rng_exec_command(rng, "ls -afiln ~ 2> /dev/null");
332 silc_rng_exec_command(rng, "ls -afiln /proc 2> /dev/null");
333 silc_rng_exec_command(rng, "ps -axww 2> /dev/null");
335 #ifdef SILC_RNG_DEBUG
336 SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
340 /* This function gets 'hard' noise from environment. This tries to
341 get the noise from /dev/random if available. */
343 static void silc_rng_get_hard_noise(SilcRng rng)
345 #if defined(SILC_UNIX)
346 unsigned char buf[32];
349 /* Get noise from /dev/[u]random if available */
350 fd = silc_file_open(rng->devrandom, O_RDONLY);
354 fcntl(fd, F_SETFL, O_NONBLOCK);
356 for (i = 0; i < 2; i++) {
357 len = read(fd, buf, sizeof(buf));
360 silc_rng_add_noise(rng, buf, len);
363 #ifdef SILC_RNG_DEBUG
364 SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
369 memset(buf, 0, sizeof(buf));
373 /* Execs command and gets noise from its output */
375 static void silc_rng_exec_command(SilcRng rng, char *command)
377 #if defined(SILC_UNIX)
378 unsigned char buf[1024];
384 fd = popen(command, "r");
388 /* Get data as much as we can get into the buffer */
389 for (i = 0; i < sizeof(buf); i++) {
399 /* Add the buffer into random pool */
400 silc_rng_add_noise(rng, buf, i);
401 memset(buf, 0, sizeof(buf));
406 /* This function adds the contents of the buffer as noise into random
407 pool. After adding the noise the pool is stirred. */
409 void silc_rng_add_noise(SilcRng rng, unsigned char *buffer, SilcUInt32 len)
413 pos = silc_rng_get_position(rng);
415 /* Add the buffer one by one into the pool */
416 for(i = 0; i < len; i++, buffer++) {
417 if(pos >= SILC_RNG_POOLSIZE)
419 rng->pool[pos++] ^= *buffer;
422 /* Stir random pool */
423 silc_rng_stir_pool(rng);
426 /* XOR's data into the pool */
428 static void silc_rng_xor(SilcRng rng, SilcUInt32 val, unsigned int pos)
432 SILC_GET32_MSB(tmp, &rng->pool[pos]);
434 SILC_PUT32_MSB(val, &rng->pool[pos]);
437 /* This function stirs the random pool by encrypting buffer in CFB
438 (cipher feedback) mode with SHA1 algorithm. */
440 static void silc_rng_stir_pool(SilcRng rng)
443 SilcUInt32 iv[5], tmp;
446 SILC_GET32_MSB(iv[0], &rng->pool[16 ]);
447 SILC_GET32_MSB(iv[1], &rng->pool[16 + 4]);
448 SILC_GET32_MSB(iv[2], &rng->pool[16 + 8]);
449 SILC_GET32_MSB(iv[3], &rng->pool[16 + 12]);
450 SILC_GET32_MSB(iv[4], &rng->pool[16 + 16]);
453 for (i = 0; i < SILC_RNG_POOLSIZE; i += 20) {
454 silc_hash_transform(rng->sha1, iv, rng->key);
456 SILC_GET32_MSB(tmp, &rng->pool[i]);
458 SILC_PUT32_MSB(iv[0], &rng->pool[i]);
460 SILC_GET32_MSB(tmp, &rng->pool[i + 4]);
462 SILC_PUT32_MSB(iv[1], &rng->pool[i + 4]);
464 SILC_GET32_MSB(tmp, &rng->pool[i + 8]);
466 SILC_PUT32_MSB(iv[2], &rng->pool[i + 8]);
468 SILC_GET32_MSB(tmp, &rng->pool[i + 12]);
470 SILC_PUT32_MSB(iv[3], &rng->pool[i + 12]);
472 SILC_GET32_MSB(tmp, &rng->pool[i + 16]);
474 SILC_PUT32_MSB(iv[4], &rng->pool[i + 16]);
478 memcpy(rng->key, &rng->pool[silc_rng_get_position(rng)], sizeof(rng->key));
480 /* Second CFB pass */
481 for (i = 0; i < SILC_RNG_POOLSIZE; i += 20) {
482 silc_hash_transform(rng->sha1, iv, rng->key);
484 SILC_GET32_MSB(tmp, &rng->pool[i]);
486 SILC_PUT32_MSB(iv[0], &rng->pool[i]);
488 SILC_GET32_MSB(tmp, &rng->pool[i + 4]);
490 SILC_PUT32_MSB(iv[1], &rng->pool[i + 4]);
492 SILC_GET32_MSB(tmp, &rng->pool[i + 8]);
494 SILC_PUT32_MSB(iv[2], &rng->pool[i + 8]);
496 SILC_GET32_MSB(tmp, &rng->pool[i + 12]);
498 SILC_PUT32_MSB(iv[3], &rng->pool[i + 12]);
500 SILC_GET32_MSB(tmp, &rng->pool[i + 16]);
502 SILC_PUT32_MSB(iv[4], &rng->pool[i + 16]);
505 memset(iv, 0, sizeof(iv));
508 /* Returns next position where data is fetched from the pool or
511 static SilcUInt32 silc_rng_get_position(SilcRng rng)
516 next = rng->state->next;
518 pos = rng->state->pos++;
519 if ((next->low != 0 && pos >= next->low) || (pos >= SILC_RNG_POOLSIZE))
520 rng->state->pos = rng->state->low;
522 #ifdef SILC_RNG_DEBUG
523 fprintf(stderr, "state: %p: low: %lu, pos: %lu\n",
524 rng->state, rng->state->low, rng->state->pos);
532 /* Returns random byte. */
534 SilcUInt8 silc_rng_get_byte(SilcRng rng)
540 /* Get more soft noise after 64 bits threshold */
541 if (rng->threshold >= 8)
542 silc_rng_get_soft_noise(rng);
544 /* Get hard noise after 160 bits threshold, zero the threshold. */
545 if (rng->threshold >= 20) {
547 silc_rng_get_hard_noise(rng);
550 do byte = rng->pool[silc_rng_get_position(rng)]; while (byte == 0x00);
554 /* Return random byte as fast as possible. Reads from /dev/urandom if
555 available. If not then return from normal RNG (not so fast). */
557 SilcUInt8 silc_rng_get_byte_fast(SilcRng rng)
559 #if defined(SILC_UNIX)
560 unsigned char buf[1];
562 if (rng->fd_devurandom == -1) {
563 rng->fd_devurandom = open("/dev/urandom", O_RDONLY);
564 if (rng->fd_devurandom < 0)
565 return silc_rng_get_byte(rng);
566 fcntl(rng->fd_devurandom, F_SETFL, O_NONBLOCK);
569 if (read(rng->fd_devurandom, buf, sizeof(buf)) < 0)
570 return silc_rng_get_byte(rng);
572 return buf[0] != 0x00 ? buf[0] : silc_rng_get_byte(rng);
574 return silc_rng_get_byte(rng);
578 /* Returns 16 bit random number */
580 SilcUInt16 silc_rng_get_rn16(SilcRng rng)
585 rn[0] = silc_rng_get_byte(rng);
586 rn[1] = silc_rng_get_byte(rng);
587 SILC_GET16_MSB(num, rn);
592 /* Returns 32 bit random number */
594 SilcUInt32 silc_rng_get_rn32(SilcRng rng)
599 rn[0] = silc_rng_get_byte(rng);
600 rn[1] = silc_rng_get_byte(rng);
601 rn[2] = silc_rng_get_byte(rng);
602 rn[3] = silc_rng_get_byte(rng);
603 SILC_GET32_MSB(num, rn);
608 /* Returns non-zero random number string. Returned string is in HEX format. */
610 unsigned char *silc_rng_get_rn_string(SilcRng rng, SilcUInt32 len)
613 unsigned char *string;
615 string = silc_calloc((len * 2 + 1), sizeof(unsigned char));
617 for (i = 0; i < len; i++)
618 sprintf(string + 2 * i, "%02x", silc_rng_get_byte(rng));
623 /* Returns non-zero random number binary data. */
625 SilcBool silc_rng_get_rn_data(SilcRng rng, SilcUInt32 len, unsigned char *buf,
633 for (i = 0; i < len; i++)
634 buf[i] = silc_rng_get_byte(rng);
639 /* Global RNG. This is global RNG that application can initialize so
640 that any part of code anywhere can use RNG without having to allocate
641 new RNG object everytime. If this is not initialized then these routines
642 will fail. Note: currently in SILC applications always initialize this. */
644 SilcRng global_rng = NULL;
646 /* Initialize global RNG. If `rng' is provided it is set as the global
647 RNG object (it can be allocated by the application for example). */
649 SilcBool silc_rng_global_init(SilcRng rng)
656 global_rng = silc_rng_alloc();
657 silc_rng_init(global_rng);
662 /* Uninitialize global RNG */
664 SilcBool silc_rng_global_uninit(void)
667 silc_rng_free(global_rng);
674 /* These are analogous to the functions above. */
676 SilcUInt8 silc_rng_global_get_byte(void)
678 return global_rng ? silc_rng_get_byte(global_rng) : 0;
681 /* Return random byte as fast as possible. Reads from /dev/urandom if
682 available. If not then return from normal RNG (not so fast). */
684 SilcUInt8 silc_rng_global_get_byte_fast(void)
686 return global_rng ? silc_rng_get_byte_fast(global_rng) : 0;
689 SilcUInt16 silc_rng_global_get_rn16(void)
691 return global_rng ? silc_rng_get_rn16(global_rng) : 0;
694 SilcUInt32 silc_rng_global_get_rn32(void)
696 return global_rng ? silc_rng_get_rn32(global_rng) : 0;
699 unsigned char *silc_rng_global_get_rn_string(SilcUInt32 len)
701 return global_rng ? silc_rng_get_rn_string(global_rng, len) : NULL;
704 SilcBool silc_rng_global_get_rn_data(SilcRng rng, SilcUInt32 len,
705 unsigned char *buf, SilcUInt32 buf_size)
707 return global_rng ? silc_rng_get_rn_data(global_rng, len, buf,
711 void silc_rng_global_add_noise(unsigned char *buffer, SilcUInt32 len)
714 silc_rng_add_noise(global_rng, buffer, len);