lib/silccrypt/silcrng.h

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