doc/rand.doc

   1 My Random number library.
   2
   3 These routines can be used to generate pseudo random numbers and can be
   4 used to 'seed' the pseudo random number generator (RNG).  The RNG make no
   5 effort to reproduce the same random number stream with each execution.
   6 Various other routines in the SSLeay library 'seed' the RNG when suitable
   7 'random' input data is available.  Read the section at the end for details
   8 on the design of the RNG.
   9
  10 void RAND_bytes(
  11 unsigned char *buf,
  12 int num);
  13         This routine puts 'num' random bytes into 'buf'.  One should make
  14         sure RAND_seed() has been called before using this routine.
  15
  16 void RAND_seed(
  17 unsigned char *buf,
  18 int num);
  19         This routine adds more 'seed' data the RNG state.  'num' bytes
  20         are added to the RNG state, they are taken from 'buf'.  This
  21         routine can be called with sensitive data such as user entered
  22         passwords.  This sensitive data is in no way recoverable from
  23         the RAND library routines or state.  Try to pass as much data
  24         from 'random' sources as possible into the RNG via this function.
  25         Also strongly consider using the RAND_load_file() and
  26         RAND_write_file() routines.
  27
  28 void RAND_cleanup();
  29         When a program has finished with the RAND library, if it so
  30         desires, it can 'zero' all RNG state.
  31
  32 The following 3 routines are convenience routines that can be used to
  33 'save' and 'restore' data from/to the RNG and it's state.
  34 Since the more 'random' data that is feed as seed data the better, why not
  35 keep it around between executions of the program?  Of course the
  36 application should pass more 'random' data in via RAND_seed() and
  37 make sure no-one can read the 'random' data file.
  38
  39 char *RAND_file_name(
  40 char *buf,
  41 int size);
  42         This routine returns a 'default' name for the location of a 'rand'
  43         file.  The 'rand' file should keep a sequence of random bytes used
  44         to initialise the RNG.  The filename is put in 'buf'.  Buf is 'size'
  45         bytes long.  Buf is returned if things go well, if they do not,
  46         NULL is returned.  The 'rand' file name is generated in the
  47         following way.  First, if there is a 'RANDFILE' environment
  48         variable, it is returned.  Second, if there is a 'HOME' environment
  49         variable, $HOME/.rand is returned.  Third, NULL is returned.  NULL
  50         is also returned if a buf would overflow.
  51
  52 int RAND_load_file(
  53 char *file,
  54 long number);
  55         This function 'adds' the 'file' into the RNG state.  It does this by
  56         doing a RAND_seed() on the value returned from a stat() system call
  57         on the file and if 'number' is non-zero, upto 'number' bytes read
  58         from the file.  The number of bytes passed to RAND_seed() is returned.
  59
  60 int RAND_write_file(
  61 char *file),
  62         RAND_write_file() writes N random bytes to the file 'file', where
  63         N is the size of the internal RND state (currently 1k).
  64         This is a suitable method of saving RNG state for reloading via
  65         RAND_load_file().
  66
  67 What follows is a description of this RNG and a description of the rational
  68 behind it's design.
  69
  70 It should be noted that this RNG is intended to be used to generate
  71 'random' keys for various ciphers including generation of DH and RSA keys.
  72
  73 It should also be noted that I have just created a system that I am happy with.
  74 It may be overkill but that does not worry me.  I have not spent that much
  75 time on this algorithm so if there are glaring errors, please let me know.
  76 Speed has not been a consideration in the design of these routines.
  77
  78 First up I will state the things I believe I need for a good RNG.
  79 1) A good hashing algorithm to mix things up and to convert the RNG 'state'
  80    to random numbers.
  81 2) An initial source of random 'state'.
  82 3) The state should be very large.  If the RNG is being used to generate
  83    4096 bit RSA keys, 2 2048 bit random strings are required (at a minimum).
  84    If your RNG state only has 128 bits, you are obviously limiting the
  85    search space to 128 bits, not 2048.  I'm probably getting a little
  86    carried away on this last point but it does indicate that it may not be
  87    a bad idea to keep quite a lot of RNG state.  It should be easier to
  88    break a cipher than guess the RNG seed data.
  89 4) Any RNG seed data should influence all subsequent random numbers
  90    generated.  This implies that any random seed data entered will have
  91    an influence on all subsequent random numbers generated.
  92 5) When using data to seed the RNG state, the data used should not be
  93    extractable from the RNG state.  I believe this should be a
  94    requirement because one possible source of 'secret' semi random
  95    data would be a private key or a password.  This data must
  96    not be disclosed by either subsequent random numbers or a
  97    'core' dump left by a program crash.
  98 6) Given the same initial 'state', 2 systems should deviate in their RNG state
  99    (and hence the random numbers generated) over time if at all possible.
 100 7) Given the random number output stream, it should not be possible to determine
 101    the RNG state or the next random number.
 102
 103
 104 The algorithm is as follows.
 105
 106 There is global state made up of a 1023 byte buffer (the 'state'), a
 107 working message digest ('md') and a counter ('count').
 108
 109 Whenever seed data is added, it is inserted into the 'state' as
 110 follows.
 111         The input is chopped up into units of 16 bytes (or less for
 112         the last block).  Each of these blocks is run through the MD5
 113         message digest.  The data passed to the MD5 digest is the
 114         current 'md', the same number of bytes from the 'state'
 115         (the location determined by in incremented looping index) as
 116         the current 'block' and the new key data 'block'.  The result
 117         of this is kept in 'md' and also xored into the 'state' at the
 118         same locations that were used as input into the MD5.
 119         I believe this system addresses points 1 (MD5), 3 (the 'state'),
 120         4 (via the 'md'), 5 (by the use of MD5 and xor).
 121
 122 When bytes are extracted from the RNG, the following process is used.
 123 For each group of 8 bytes (or less), we do the following,
 124         Input into MD5, the top 8 bytes from 'md', the byte that are
 125         to be overwritten by the random bytes and bytes from the
 126         'state' (incrementing looping index).  From this digest output
 127         (which is kept in 'md'), the top (upto) 8 bytes are
 128         returned to the caller and the bottom (upto) 8 bytes are xored
 129         into the 'state'.
 130         Finally, after we have finished 'generation' random bytes for the
 131         called, 'count' (which is incremented) and 'md' are fed into MD5 and
 132         the results are kept in 'md'.
 133         I believe the above addressed points 1 (use of MD5), 6 (by
 134         hashing into the 'state' the 'old' data from the caller that
 135         is about to be overwritten) and 7 (by not using the 8 bytes
 136         given to the caller to update the 'state', but they are used
 137         to update 'md').
 138
 139 So of the points raised, only 2 is not addressed, but sources of
 140 random data will always be a problem.
 141