lib/doc/silcrng_intro.html

   1 <big><b>Introduction to Random Number Generator</b></big>
   2
   3 <br />&nbsp;<br />&nbsp;<br />
   4 <b>Overview</b>
   5
   6 <br />&nbsp;<br />
   7 SILC Random Number Generator is cryptographically strong pseudo random
   8 number generator. It is used to generate all the random numbers needed
   9 in the SILC sessions. All key material and other sources needing random
  10 numbers use this generator.
  11
  12 <br />&nbsp;<br />
  13 The RNG has a random pool of 1024 bytes of size that provides the actual
  14 random numbers for the application. The pool is initialized when the
  15 RNG is allocated and initialized with silc_rng_alloc and silc_rng_init
  16 functions, respectively.
  17
  18
  19 <br />&nbsp;<br />&nbsp;<br />
  20 <b>Random Pool Initialization</b>
  21
  22 <br />&nbsp;<br />
  23 The RNG's random pool is the source of all random output data. The pool is
  24 initialized with silc_rng_init and application can reseed it at any time
  25 by calling the silc_rng_add_noise function.
  26
  27 <br />&nbsp;<br />
  28 The initializing phase attempts to set the random pool in a state that it
  29 is impossible to learn the input data to the RNG or any random output
  30 data. This is achieved by acquiring noise from various system sources. The
  31 first source is called to provide "soft noise". This noise is various
  32 data from system's processes. The second source is called to provide
  33 "medium noise". This noise is various output data from executed commands.
  34 Usually the commands are Unix `ps' and `ls' commands with various options.
  35 The last source is called to provide "hard noise" and is noise from
  36 system's /dev/random, if it exists.
  37
  38
  39 <br />&nbsp;<br />&nbsp;<br />
  40 <b>Stirring the Random Pool</b>
  41
  42 <br />&nbsp;<br />
  43 Every time data is acquired from any source, the pool is stirred. The
  44 stirring process performs an CFB (cipher feedback) encryption with SHA1
  45 algorithm to the entire random pool. First it acquires an IV (Initial
  46 Vector) from the constant (random) location of the pool and performs
  47 the first CFB pass. Then it acquires a new encryption key from variable
  48 location of the pool and performs the second CFB pass. The encryption
  49 key thus is always acquired from unguessable data.
  50
  51 <br />&nbsp;<br />
  52 The encryption process to the entire random pool assures that it is
  53 impossible to learn the input data to the random pool without breaking the
  54 encryption process. This would effectively mean breaking the SHA1 hash
  55 function. The encryption process also assures that each random output from
  56 the random pool is secured with cryptographically strong function, the
  57 SHA1 in this case.
  58
  59 <br />&nbsp;<br />
  60 The random pool can be restirred by the application at any point by
  61 calling the silc_rng_add_noise function. This function adds new noise to
  62 the pool and then stirs the entire pool.
  63
  64
  65 <br />&nbsp;<br />&nbsp;<br />
  66 <b>Stirring Thresholds</b>
  67
  68 <br />&nbsp;<br />
  69 The random pool has two thresholds that controls when the random pool
  70 needs more new noise and requires restirring. As previously mentioned, the
  71 application may do this by calling the silc_rng_add_noise. However, the
  72 RNG performs this also automatically.
  73
  74 <br />&nbsp;<br />
  75 The first threshold gets soft noise from system and stirs the random pool.
  76 The threshold is reached after 64 bits of random data has been fetched
  77 from the RNG. After the 64 bits, the soft noise acquiring and restirring
  78 process is performed every 8 bits of random output data until the second
  79 threshold is reached.
  80
  81 <br />&nbsp;<br />
  82 The second threshold gets hard noise from system and stirs the random
  83 pool. The threshold is reached after 160 bits of random output. After the
  84 noise is acquired (from /dev/urandom) the random pool is stirred and the
  85 thresholds are set to zero. The process is repeated again after 64 bits of
  86 output for first threshold and after 160 bits of output for the second
  87 threshold.
  88
  89
  90 <br />&nbsp;<br />&nbsp;<br />
  91 <b>Internal State of the Random Pool</b>
  92
  93 <br />&nbsp;<br />
  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 <br />&nbsp;<br />&nbsp;<br />
 110 <b>Security Considerations</b>
 111
 112 <br />&nbsp;<br />
 113 The security of this random number generator, like of any other RNG's,
 114 depends of the initial state of the RNG. The initial state of the random
 115 number generators must be unknown to an adversary. This means that after
 116 the RNG is initialized it is required that the input data to the RNG and
 117 the output data to the application has no correlation of any kind that
 118 could be used to compromise the acquired random numbers or any future
 119 random numbers.
 120
 121 <br />&nbsp;<br />
 122 It is, however, clear that the correlation exists but it needs to be
 123 hard to solve for an adversary. To accomplish this the input data to the
 124 random number generator needs to be secret. Usually this is impossible to
 125 achieve. That is why SILC's RNG acquires the noise from three different
 126 sources and provides for the application an interface to add more noise at
 127 any time. The first source ("soft noise") is known to the adversary but
 128 requires exact timing to get all of the input data. However, getting only
 129 partial data is easy. The second source ("medium noise") depends on the
 130 place of execution of the application. Getting at least partial data is
 131 easy but securing for example the user's home directory from outside access
 132 makes it harder. The last source ("hard noise") is considered to be the
 133 most secure source of data. An adversary is not considered to have any
 134 access on this data. This of course greatly depends on the operating system.
 135
 136 <br />&nbsp;<br />
 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
 145 sources, equally.
 146
 147 <br />&nbsp;<br />
 148 The RNG must also assure that any old or future random numbers are not
 149 compromised if an adversary would learn the initial input data (or any
 150 input data for that matter). The SILC's RNG provides good protection for
 151 this even if the some of the input bits would be compromised for old or
 152 future random numbers. The RNG reinitalizes (reseeds) itself using the
 153 thresholds after every 64 and 160 bits of output. This is considered to be
 154 adequate even if some of the bits would get compromised. Also, the
 155 applications that use the RNG usually fetches at least 256 bits from the
 156 RNG. This means that everytime RNG is accessed both of the thresholds are
 157 reached. This should mean that the RNG is never too long in an compromised
 158 state and recovers as fast as possible.
 159
 160
 161 <br />&nbsp;<br />&nbsp;<br />
 162 <b>Caveat Windows Programmer</b>
 163
 164 <br />&nbsp;<br />
 165 The caller must be cautios when using this RNG with native WIN32 system.
 166 The RNG most likely is impossible to set in unguessable state just by
 167 using the RNG's input data sources.  On WIN32 it is stronly suggested
 168 that caller would add more random noise after the initialization of the
 169 RNG using the silc_rng_add_noise function.  For example, random mouse
 170 movements may be used.
 171