1 /****h* silccrypt/silcrng.h
9 * Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
11 * Copyright (C) 1997 - 2001 Pekka Riikonen
13 * This program is free software; you can redistribute it and/or modify
14 * it under the terms of the GNU General Public License as published by
15 * the Free Software Foundation; either version 2 of the License, or
16 * (at your option) any later version.
18 * This program is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 * GNU General Public License for more details.
25 * SILC Random Number Generator is cryptographically strong pseudo random
26 * number generator. It is used to generate all the random numbers needed
27 * in the SILC sessions. All key material and other sources needing random
28 * numbers use this generator.
30 * The RNG has a random pool of 1024 bytes of size that provides the actual
31 * random numbers for the application. The pool is initialized when the
32 * RNG is allocated and initialized with silc_rng_alloc and silc_rng_init
33 * functions, respectively.
36 * Random Pool Initialization
38 * The RNG's random pool is the source of all random output data. The pool is
39 * initialized with silc_rng_init and application can reseed it at any time
40 * by calling the silc_rng_add_noise function.
42 * The initializing phase attempts to set the random pool in a state that it
43 * is impossible to learn the input data to the RNG or any random output
44 * data. This is achieved by acquiring noise from various system sources. The
45 * first source is called to provide "soft noise". This noise is various
46 * data from system's processes. The second source is called to provide
47 * "medium noise". This noise is various output data from executed commands.
48 * Usually the commands are Unix `ps' and `ls' commands with various options.
49 * The last source is called to provide "hard noise" and is noise from
50 * system's /dev/random, if it exists.
53 * Stirring the Random Pool
55 * Every time data is acquired from any source, the pool is stirred. The
56 * stirring process performs an CFB (cipher feedback) encryption with SHA1
57 * algorithm to the entire random pool. First it acquires an IV (Initial
58 * Vector) from the constant location of the pool and performs the first CFB
59 * pass. Then it acquires a new encryption key from variable location of the
60 * pool and performs the second CFB pass. The encryption key thus is always
61 * acquired from unguessable data.
63 * The encryption process to the entire random pool assures that it is
64 * impossible to learn the input data to the random pool without breaking the
65 * encryption process. This would effectively mean breaking the SHA1 hash
66 * function. The encryption process also assures that each random output from
67 * the random pool is secured with cryptographically strong function, the
70 * The random pool can be restirred by the application at any point by
71 * calling the silc_rng_add_noise function. This function adds new noise to
72 * the pool and then stirs the entire pool.
75 * Stirring Threshholds
77 * The random pool has two threshholds that controls when the random pool
78 * needs more new noise and requires restirring. As previously mentioned, the
79 * application may do this by calling the silc_rng_add_noise. However, the
80 * RNG performs this also automatically.
82 * The first threshhold gets soft noise from system and stirs the random pool.
83 * The threshhold is reached after 64 bits of random data has been fetched
84 * from the RNG. After the 64 bits, the soft noise acquiring and restirring
85 * process is performed every 8 bits of random output data until the second
86 * threshhold is reached.
88 * The second threshhold gets hard noise from system and stirs the random
89 * pool. The threshhold is reached after 160 bits of random output. After the
90 * noise is acquired (from /dev/random) the random pool is stirred and the
91 * threshholds are set to zero. The process is repeated again after 64 bits of
92 * output for first threshhold and after 160 bits of output for the second
96 * Internal State of the Random Pool
98 * The random pool has also internal state that provides several variable
99 * distinct points to the random pool where the data is fetched. The state
100 * changes every 8 bits of output data and it is guaranteed that the fetched
101 * 8 bits of data is from distinct location compared to the previous 8 bits.
102 * It is also guaranteed that the internal state never wraps before
103 * restirring the entire random pool. The internal state means that the data
104 * is not fetched linearly from the pool, eg. starting from zero and wrapping
105 * at the end of the pool. The internal state is not dependent of any random
106 * data in the pool. The internal states are initialized (by default the pool
107 * is splitted to four different sections (states)) at the RNG
108 * initialization phase. The state's current position is added linearly and
109 * wraps at the the start of the next state. The states provides the distinct
113 * Security Considerations
115 * The security of this random number generator, like of any other RNG's,
116 * depends of the initial state of the RNG. The initial state of the random
117 * number generators must be unknown to an adversary. This means that after
118 * the RNG is initialized it is required that the input data to the RNG and
119 * the output data to the application has no correlation of any kind that
120 * could be used to compromise the acquired random numbers or any future
123 * It is, however, clear that the correlation exists but it needs to be
124 * hard to solve for an adversary. To accomplish this the input data to the
125 * random number generator needs to be secret. Usually this is impossible to
126 * achieve. That is why SILC's RNG acquires the noise from three different
127 * sources and provides for the application an interface to add more noise at
128 * any time. The first source ("soft noise") is known to the adversary but
129 * requires exact timing to get all of the input data. However, getting only
130 * partial data is easy. The second source ("medium noise") depends on the
131 * place of execution of the application. Getting at least partial data is
132 * easy but securing for example the user's home directory from outside access
133 * makes it harder. The last source ("hard noise") is considered to be the
134 * most secure source of data. An adversary is not considered to have any
135 * access on this data. This of course greatly depends on the operating system.
137 * These three sources are considered to be adequate since the random pool is
138 * relatively large and the output of each bit of the random pool is secured
139 * by cryptographically secure function, the SHA1 in CFB mode encryption.
140 * Furthermore the application may provide other random data, such as random
141 * key strokes or mouse movement to the RNG. However, it is recommended that
142 * the application would not be the single point of source for the RNG, in
143 * either intializing or reseeding phases later in the session. Good solution
144 * is probably to use both, the application's seeds and the RNG's own
147 * The RNG must also assure that any old or future random numbers are not
148 * compromised if an adversary would learn the initial input data (or any
149 * input data for that matter). The SILC's RNG provides good protection for
150 * this even if the some of the output bits would be compromised in old or
151 * future random numbers. The RNG reinitalizes (reseeds) itself using the
152 * threshholds after every 64 and 160 bits of output. This is considered to be
153 * adequate even if some of the bits would get compromised. Also, the
154 * applications that use the RNG usually fetches at least 256 bits from the
155 * RNG. This means that everytime RNG is accessed both of the threshholds are
156 * reached. This should mean that the RNG is never too long in an compromised
157 * state and recovers as fast as possible.
159 * Currently the SILC's RNG does not use random seed files to store some
160 * random data for future initializing. This is important and must be
161 * implemented in the future.
168 /* Forward declaration. Actual object is in source file. */
169 typedef struct SilcRngObjectStruct *SilcRng;
172 SilcRng silc_rng_alloc();
173 void silc_rng_free(SilcRng rng);
174 void silc_rng_init(SilcRng rng);
175 unsigned char silc_rng_get_byte(SilcRng rng);
176 uint16 silc_rng_get_rn16(SilcRng rng);
177 uint32 silc_rng_get_rn32(SilcRng rng);
178 unsigned char *silc_rng_get_rn_string(SilcRng rng, uint32 len);
179 unsigned char *silc_rng_get_rn_data(SilcRng rng, uint32 len);
180 void silc_rng_add_noise(SilcRng rng, unsigned char *buffer, uint32 len);
182 int silc_rng_global_init(SilcRng rng);
183 int silc_rng_global_uninit();
184 unsigned char silc_rng_global_get_byte();
185 uint16 silc_rng_global_get_rn16();
186 uint32 silc_rng_global_get_rn32();
187 unsigned char *silc_rng_global_get_rn_string(uint32 len);
188 unsigned char *silc_rng_global_get_rn_data(uint32 len);
189 void silc_rng_global_add_noise(unsigned char *buffer, uint32 len);