5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 1997 - 2014 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.
21 * Created: Sun Mar 9 00:09:18 1997
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.
32 extern pid_t getsid (pid_t __pid);
36 extern pid_t getpgid (pid_t __pid);
41 /*#define SILC_RNG_DEBUG*/
43 /* Number of states to fetch data from pool. */
44 #define SILC_RNG_STATE_NUM 4
46 /* Byte size of the random data pool. */
47 #define SILC_RNG_POOLSIZE (20 * 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);
58 SILC SilcRng State context.
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
69 The index for the random pool buffer. Lowest and current
72 SilcRngStateContext *next
74 Pointer to the next state. If this is the last state this
75 will point to the first state thus providing circular list.
78 typedef struct SilcRngStateContext {
81 struct SilcRngStateContext *next;
85 SILC Random Number Generator object.
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.
93 The random pool. This buffer holds the random data. This is
94 frequently stirred thus providing ever changing randomnes.
98 Key used in stirring the random pool. The pool is encrypted
99 with SHA1 hash function in CFB (Cipher Feedback) mode.
101 SilcSilcRngState state
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
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.
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.
121 struct SilcRngStruct {
122 unsigned char pool[SILC_RNG_POOLSIZE];
123 unsigned char key[64];
131 /* Allocates new RNG object. */
133 SilcRng silc_rng_alloc(void)
137 SILC_LOG_DEBUG(("Allocating new RNG object"));
139 new = silc_calloc(1, sizeof(*new));
140 new->fd_devurandom = -1;
142 memset(new->pool, 0, sizeof(new->pool));
143 memset(new->key, 0, sizeof(new->key));
145 if (!silc_hash_alloc("sha1", &new->sha1)) {
147 SILC_LOG_ERROR(("Could not allocate sha1 hash, probably not registered"));
151 new->devrandom = strdup("/dev/random");
152 if (!new->devrandom) {
160 /* Free's RNG object. */
162 void silc_rng_free(SilcRng rng)
167 memset(rng->pool, 0, sizeof(rng->pool));
168 memset(rng->key, 0, sizeof(rng->key));
169 silc_hash_free(rng->sha1);
170 silc_free(rng->devrandom);
172 if (rng->fd_devurandom != -1)
173 close(rng->fd_devurandom);
175 for (t = rng->state->next; t != rng->state; ) {
180 silc_free(rng->state);
186 /* Initializes random number generator by getting noise from environment.
187 The environmental noise is our so called seed. One should not call
188 this function more than once. */
190 void silc_rng_init(SilcRng rng)
193 SilcRngState first, next;
197 SILC_LOG_DEBUG(("Initializing RNG object"));
199 /* Initialize the states for the RNG. */
200 rng->state = silc_calloc(1, sizeof(*rng->state));
202 SILC_LOG_ERROR(("Error allocating memory for RNG"));
207 rng->state->next = NULL;
209 for (i = SILC_RNG_STATE_NUM - 1; i >= 1; i--) {
210 next = silc_calloc(1, sizeof(*rng->state));
212 SILC_LOG_ERROR(("Error allocating memory for RNG"));
216 (i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM));
218 (i * (sizeof(rng->pool) / SILC_RNG_STATE_NUM)) + 8;
219 next->next = rng->state;
225 memset(rng->pool, 0, sizeof(rng->pool));
227 /* Get noise from various environmental sources */
228 silc_rng_get_soft_noise(rng);
229 silc_rng_get_medium_noise(rng);
230 silc_rng_get_hard_noise(rng);
231 silc_rng_get_soft_noise(rng);
232 silc_free(rng->devrandom);
233 rng->devrandom = strdup("/dev/urandom");
236 /* This function gets 'soft' noise from environment. */
238 static void silc_rng_get_soft_noise(SilcRng rng)
244 #ifdef HAVE_GETRUSAGE
248 pos = silc_rng_get_position(rng);
250 silc_rng_xor(rng, clock(), 0);
253 silc_rng_xor(rng, getpid(), 1);
255 silc_rng_xor(rng, getpgid(getpid()) << 8, 2);
256 silc_rng_xor(rng, getpgid(getpid()) << 8, 3);
259 silc_rng_xor(rng, getgid(), 4);
263 silc_rng_xor(rng, getpgrp(), 5);
266 silc_rng_xor(rng, getsid(getpid()) << 16, 6);
269 silc_rng_xor(rng, times(&ptime), 7);
270 silc_rng_xor(rng, ptime.tms_utime, 8);
271 silc_rng_xor(rng, (ptime.tms_utime + ptime.tms_stime), pos++);
272 silc_rng_xor(rng, (ptime.tms_stime + ptime.tms_cutime), pos++);
273 silc_rng_xor(rng, (ptime.tms_utime + ptime.tms_stime), pos++);
274 silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_stime), pos++);
275 silc_rng_xor(rng, (ptime.tms_cutime ^ ptime.tms_cstime), pos++);
276 silc_rng_xor(rng, (ptime.tms_utime ^ ptime.tms_stime), pos++);
277 silc_rng_xor(rng, (ptime.tms_stime ^ ptime.tms_cutime), pos++);
278 silc_rng_xor(rng, (ptime.tms_cutime + ptime.tms_stime), pos++);
279 silc_rng_xor(rng, (ptime.tms_stime << 8), pos++);
280 #endif /* SILC_SYMBIAN */
282 silc_rng_xor(rng, clock() << 4, pos++);
285 silc_rng_xor(rng, getpgid(getpid()) << 8, pos++);
288 silc_rng_xor(rng, getpgrp(), pos++);
291 silc_rng_xor(rng, getsid(getpid()) << 16, pos++);
294 silc_rng_xor(rng, times(&ptime), pos++);
295 silc_rng_xor(rng, ptime.tms_utime, pos++);
296 #endif /* SILC_SYMBIAN */
298 silc_rng_xor(rng, getpgrp(), pos++);
301 #ifdef HAVE_GETRUSAGE
302 getrusage(RUSAGE_SELF, &r);
303 silc_rng_xor(rng, (r.ru_utime.tv_sec + r.ru_utime.tv_usec), pos++);
304 silc_rng_xor(rng, (r.ru_utime.tv_sec ^ r.ru_utime.tv_usec), pos++);
305 silc_rng_xor(rng, (r.ru_stime.tv_sec + r.ru_stime.tv_usec), pos++);
306 silc_rng_xor(rng, (r.ru_stime.tv_sec ^ r.ru_stime.tv_usec), pos++);
308 silc_rng_xor(rng, (r.ru_maxrss + r.ru_ixrss), pos++);
309 silc_rng_xor(rng, (r.ru_maxrss ^ r.ru_ixrss), pos++);
310 silc_rng_xor(rng, (r.ru_idrss + r.ru_idrss), pos++);
311 silc_rng_xor(rng, (r.ru_idrss ^ r.ru_idrss), pos++);
312 silc_rng_xor(rng, (r.ru_idrss << 16), pos++);
313 silc_rng_xor(rng, (r.ru_minflt + r.ru_majflt), pos++);
314 silc_rng_xor(rng, (r.ru_minflt ^ r.ru_majflt), pos++);
315 silc_rng_xor(rng, (r.ru_nswap + r.ru_oublock + r.ru_inblock), pos++);
316 silc_rng_xor(rng, (r.ru_nswap << 8), pos++);
317 silc_rng_xor(rng, (r.ru_inblock + r.ru_oublock), pos++);
318 silc_rng_xor(rng, (r.ru_inblock ^ r.ru_oublock), pos++);
319 silc_rng_xor(rng, (r.ru_msgsnd ^ r.ru_msgrcv), pos++);
320 silc_rng_xor(rng, (r.ru_nsignals + r.ru_msgsnd + r.ru_msgrcv), pos++);
321 silc_rng_xor(rng, (r.ru_nsignals << 16), pos++);
322 silc_rng_xor(rng, (r.ru_nvcsw + r.ru_nivcsw), pos++);
323 silc_rng_xor(rng, (r.ru_nvcsw ^ r.ru_nivcsw), pos++);
324 #endif /* SILC_SYMBIAN */
325 #endif /* HAVE_GETRUSAGE */
327 #ifdef SILC_RNG_DEBUG
328 SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
331 /* Stir random pool */
332 silc_rng_stir_pool(rng);
335 /* This function gets noise from different commands */
337 static void silc_rng_get_medium_noise(SilcRng rng)
339 /* If getrusage is available, there is no need for shell commands */
340 #ifdef HAVE_GETRUSAGE
343 silc_rng_exec_command(rng, "ps -leaww 2> /dev/null");
344 silc_rng_exec_command(rng, "ls -afiln ~ 2> /dev/null");
345 silc_rng_exec_command(rng, "ls -afiln /proc 2> /dev/null");
346 silc_rng_exec_command(rng, "ps -axww 2> /dev/null");
348 #ifdef SILC_RNG_DEBUG
349 SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
353 /* This function gets 'hard' noise from environment. This tries to
354 get the noise from /dev/random if available. */
356 static void silc_rng_get_hard_noise(SilcRng rng)
358 #if defined(SILC_UNIX)
359 unsigned char buf[32];
362 /* Get noise from /dev/[u]random if available */
363 fd = open(rng->devrandom, O_RDONLY);
367 fcntl(fd, F_SETFL, O_NONBLOCK);
369 for (i = 0; i < 2; i++) {
370 len = read(fd, buf, sizeof(buf));
373 silc_rng_add_noise(rng, buf, len);
376 #ifdef SILC_RNG_DEBUG
377 SILC_LOG_HEXDUMP(("pool"), rng->pool, sizeof(rng->pool));
382 memset(buf, 0, sizeof(buf));
386 /* Execs command and gets noise from its output */
388 static void silc_rng_exec_command(SilcRng rng, char *command)
390 #if defined(SILC_UNIX)
391 unsigned char buf[1024];
397 fd = popen(command, "r");
401 /* Get data as much as we can get into the buffer */
402 for (i = 0; i < sizeof(buf); i++) {
412 /* Add the buffer into random pool */
413 silc_rng_add_noise(rng, buf, i);
414 memset(buf, 0, sizeof(buf));
419 /* This function adds the contents of the buffer as noise into random
420 pool. After adding the noise the pool is stirred. */
422 void silc_rng_add_noise(SilcRng rng, unsigned char *buffer, SilcUInt32 len)
426 pos = silc_rng_get_position(rng);
428 /* Add the buffer one by one into the pool */
429 for(i = 0; i < len; i++, buffer++) {
430 if(pos >= SILC_RNG_POOLSIZE)
432 rng->pool[pos++] ^= *buffer;
435 /* Stir random pool */
436 silc_rng_stir_pool(rng);
439 /* XOR's data into the pool */
441 static void silc_rng_xor(SilcRng rng, SilcUInt32 val, unsigned int pos)
445 SILC_GET32_MSB(tmp, &rng->pool[pos]);
447 SILC_PUT32_MSB(val, &rng->pool[pos]);
450 /* This function stirs the random pool by encrypting buffer in CFB
451 (cipher feedback) mode with SHA1 algorithm. */
453 static void silc_rng_stir_pool(SilcRng rng)
456 SilcUInt32 iv[5], tmp;
459 SILC_GET32_MSB(iv[0], &rng->pool[16 ]);
460 SILC_GET32_MSB(iv[1], &rng->pool[16 + 4]);
461 SILC_GET32_MSB(iv[2], &rng->pool[16 + 8]);
462 SILC_GET32_MSB(iv[3], &rng->pool[16 + 12]);
463 SILC_GET32_MSB(iv[4], &rng->pool[16 + 16]);
466 for (i = 0; i < SILC_RNG_POOLSIZE; i += 20) {
467 silc_hash_transform(rng->sha1, iv, rng->key);
469 SILC_GET32_MSB(tmp, &rng->pool[i]);
471 SILC_PUT32_MSB(iv[0], &rng->pool[i]);
473 SILC_GET32_MSB(tmp, &rng->pool[i + 4]);
475 SILC_PUT32_MSB(iv[1], &rng->pool[i + 4]);
477 SILC_GET32_MSB(tmp, &rng->pool[i + 8]);
479 SILC_PUT32_MSB(iv[2], &rng->pool[i + 8]);
481 SILC_GET32_MSB(tmp, &rng->pool[i + 12]);
483 SILC_PUT32_MSB(iv[3], &rng->pool[i + 12]);
485 SILC_GET32_MSB(tmp, &rng->pool[i + 16]);
487 SILC_PUT32_MSB(iv[4], &rng->pool[i + 16]);
491 memcpy(rng->key, &rng->pool[silc_rng_get_position(rng)], sizeof(rng->key));
493 /* Second CFB pass */
494 for (i = 0; i < SILC_RNG_POOLSIZE; i += 20) {
495 silc_hash_transform(rng->sha1, iv, rng->key);
497 SILC_GET32_MSB(tmp, &rng->pool[i]);
499 SILC_PUT32_MSB(iv[0], &rng->pool[i]);
501 SILC_GET32_MSB(tmp, &rng->pool[i + 4]);
503 SILC_PUT32_MSB(iv[1], &rng->pool[i + 4]);
505 SILC_GET32_MSB(tmp, &rng->pool[i + 8]);
507 SILC_PUT32_MSB(iv[2], &rng->pool[i + 8]);
509 SILC_GET32_MSB(tmp, &rng->pool[i + 12]);
511 SILC_PUT32_MSB(iv[3], &rng->pool[i + 12]);
513 SILC_GET32_MSB(tmp, &rng->pool[i + 16]);
515 SILC_PUT32_MSB(iv[4], &rng->pool[i + 16]);
518 memset(iv, 0, sizeof(iv));
521 /* Returns next position where data is fetched from the pool or
524 static SilcUInt32 silc_rng_get_position(SilcRng rng)
529 next = rng->state->next;
531 pos = rng->state->pos++;
532 if ((next->low != 0 && pos >= next->low) || (pos >= SILC_RNG_POOLSIZE))
533 rng->state->pos = rng->state->low;
535 #ifdef SILC_RNG_DEBUG
536 fprintf(stderr, "state: %p: low: %lu, pos: %lu\n",
537 rng->state, rng->state->low, rng->state->pos);
545 /* Returns random byte. */
547 SilcUInt8 silc_rng_get_byte(SilcRng rng)
553 /* Get more soft noise after 64 bits threshold */
554 if (rng->threshold >= 8)
555 silc_rng_get_soft_noise(rng);
557 /* Get hard noise after 160 bits threshold, zero the threshold. */
558 if (rng->threshold >= 20) {
560 silc_rng_get_hard_noise(rng);
563 do byte = rng->pool[silc_rng_get_position(rng)]; while (byte == 0x00);
567 /* Return random byte as fast as possible. Reads from /dev/urandom if
568 available. If not then return from normal RNG (not so fast). */
570 SilcUInt8 silc_rng_get_byte_fast(SilcRng rng)
572 #if defined(SILC_UNIX)
573 unsigned char buf[1];
575 if (rng->fd_devurandom == -1) {
576 rng->fd_devurandom = open("/dev/urandom", O_RDONLY);
577 if (rng->fd_devurandom < 0)
578 return silc_rng_get_byte(rng);
579 fcntl(rng->fd_devurandom, F_SETFL, O_NONBLOCK);
582 if (read(rng->fd_devurandom, buf, sizeof(buf)) < 0)
583 return silc_rng_get_byte(rng);
585 return buf[0] != 0x00 ? buf[0] : silc_rng_get_byte(rng);
587 return silc_rng_get_byte(rng);
591 /* Returns 16 bit random number */
593 SilcUInt16 silc_rng_get_rn16(SilcRng rng)
598 rn[0] = silc_rng_get_byte(rng);
599 rn[1] = silc_rng_get_byte(rng);
600 SILC_GET16_MSB(num, rn);
605 /* Returns 32 bit random number */
607 SilcUInt32 silc_rng_get_rn32(SilcRng rng)
612 rn[0] = silc_rng_get_byte(rng);
613 rn[1] = silc_rng_get_byte(rng);
614 rn[2] = silc_rng_get_byte(rng);
615 rn[3] = silc_rng_get_byte(rng);
616 SILC_GET32_MSB(num, rn);
621 /* Returns non-zero random number string. Returned string is in HEX format. */
623 unsigned char *silc_rng_get_rn_string(SilcRng rng, SilcUInt32 len)
626 unsigned char *string;
628 string = silc_calloc((len * 2 + 1), sizeof(unsigned char));
632 for (i = 0; i < len; i++)
633 sprintf(string + 2 * i, "%02x", silc_rng_get_byte(rng));
638 /* Returns non-zero random number binary data. */
640 unsigned char *silc_rng_get_rn_data(SilcRng rng, SilcUInt32 len)
645 data = silc_calloc(len + 1, sizeof(*data));
649 for (i = 0; i < len; i++)
650 data[i] = silc_rng_get_byte(rng);
655 /* Global RNG. This is global RNG that application can initialize so
656 that any part of code anywhere can use RNG without having to allocate
657 new RNG object everytime. If this is not initialized then these routines
658 will fail. Note: currently in SILC applications always initialize this. */
660 SilcRng global_rng = NULL;
662 /* Initialize global RNG. If `rng' is provided it is set as the global
663 RNG object (it can be allocated by the application for example). */
665 SilcBool silc_rng_global_init(SilcRng rng)
672 global_rng = silc_rng_alloc();
673 silc_rng_init(global_rng);
678 /* Uninitialize global RNG */
680 SilcBool silc_rng_global_uninit(void)
683 silc_rng_free(global_rng);
690 /* These are analogous to the functions above. */
692 SilcUInt8 silc_rng_global_get_byte(void)
694 return global_rng ? silc_rng_get_byte(global_rng) : 0;
697 /* Return random byte as fast as possible. Reads from /dev/urandom if
698 available. If not then return from normal RNG (not so fast). */
700 SilcUInt8 silc_rng_global_get_byte_fast(void)
702 return global_rng ? silc_rng_get_byte_fast(global_rng) : 0;
705 SilcUInt16 silc_rng_global_get_rn16(void)
707 return global_rng ? silc_rng_get_rn16(global_rng) : 0;
710 SilcUInt32 silc_rng_global_get_rn32(void)
712 return global_rng ? silc_rng_get_rn32(global_rng) : 0;
715 unsigned char *silc_rng_global_get_rn_string(SilcUInt32 len)
717 return global_rng ? silc_rng_get_rn_string(global_rng, len) : NULL;
720 unsigned char *silc_rng_global_get_rn_data(SilcUInt32 len)
722 return global_rng ? silc_rng_get_rn_data(global_rng, len) : NULL;
725 void silc_rng_global_add_noise(unsigned char *buffer, SilcUInt32 len)
728 silc_rng_add_noise(global_rng, buffer, len);