news/secadv/prng.txt

   1 OpenSSL Security Advisory [10 July 2001]
   2
   3 WEAKNESS OF THE OpenSSL PRNG IN VERSIONS UP TO OpenSSL 0.9.6a
   4 -------------------------------------------------------------
   5
   6 CONTENTS:
   7  - Synopsis
   8  - Detailed problem description
   9  - Solution
  10  - Impact
  11  - Source code patch [*]
  12  - Acknowledgement
  13
  14 [*] OpenSSL 0.9.6b has been corrected and does not require this patch.
  15
  16 The source code of OpenSSL 0.9.6b is available as file openssl-0.9.6b.tar.gz
  17 from <URL: ftp://ftp.openssl.org/source;type=d>.
  18 If you were previously using the "engine" release of OpenSSL 0.9.6 or
  19 0.9.6a, obtain file openssl-engine-0.9.6b.tar.gz instead.
  20
  21 MD5 checksums:
  22      openssl-0.9.6b.tar.gz          bd8c4d8c5bafc7a4d55d152989fdb327
  23      openssl-engine-0.9.6b.tar.gz   ab5ca5b157459c49bdab06a7db8a5a47
  24
  25 OpenSSL source code can also be obtained from a number of mirror sites.
  26 For a list, see <URL: https://www.openssl.org/source/mirror.html>.
  27
  28 If you are using a pre-compiled OpenSSL package, please look for update
  29 information from the respective software distributor.  The OpenSSL
  30 group itself does not distribute OpenSSL binaries.
  31
  32
  33 SYNOPSIS
  34 --------
  35
  36 The pseudo-random number generator (PRNG) in SSLeay/OpenSSL versions
  37 up to 0.9.6a is weakened by a design error.  Knowing the output of
  38 specific PRNG requests (including a number of consecutive very short
  39 PRNG requests) would allow an attacker to determine the PRNG's
  40 internal state and thus to predict future PRNG output.
  41
  42 Typical applications (including applications using OpenSSL's SSL/TLS
  43 library) are not vulnerable to this attack because PRNG requests
  44 usually happen in larger chunks.  However, we strongly recommend
  45 upgrading to OpenSSL 0.9.6b, which includes a fixed PRNG.
  46 If upgrading to 0.9.6b is not immediately possible, the source
  47 code patch contained at the end of this advisory should be applied.
  48
  49
  50
  51 DETAILED PROBLEM DESCRIPTION
  52 ----------------------------
  53
  54 Recently a cryptographic flaw in OpenSSL's built-in pseudo-random
  55 number generator (PRNG) was pointed out to us by Markku-Juhani
  56 O. Saarinen <markku-juhani.saarinen@nokia.com>, who showed how
  57 an attacker could reconstruct the PRNG's internal state from
  58 the output of a couple of hundred 1-byte PRNG requests.  This problem
  59 dates back to SSLeay, which OpenSSL is based on, and was found in other
  60 SSLeay-based toolkits as well.  While a number of enhancements have
  61 been done to the original PRNG during the development of OpenSSL, this
  62 design error was overlooked so far.
  63
  64 The PRNG (implemented in source code file crypto/md_rand.c) uses a
  65 hash function, by default SHA-1, to update its internal secret state
  66 and to generate output.  The secret state consists of two components:
  67 A chaining variable 'md', sized according to the hash function's
  68 output (160 bits for SHA-1), and a large buffer 'state'.  'md' is
  69 always replaced by a hash function output during the PRNG's operation.
  70 'state' is accessed circularly and is used for storing additional
  71 entropy.
  72
  73 When generating output bytes, OpenSSL versions up to 0.9.6a set 'md'
  74 to the hash of one half of its previous value and some other data,
  75 including bytes from 'state'.  The design error was that the half of
  76 'md' input to the hash function was the same half that was also used
  77 as PRNG output, meaning that it in general cannot be considered
  78 secret.  Also the number of bytes used from 'state' depended on the
  79 number of bytes requested as PRNG output and could be as small as one,
  80 allowing for easy brute-force analysis of all possible cases.
  81 The combination of these effects made it possible to reconstruct
  82 the complete internal PRNG state from the output of one PRNG request
  83 appropriately sized to gain knowledge on 'md' followed by enough
  84 consecutive 1-byte PRNG requests to traverse all of 'state'.
  85
  86
  87 SOLUTION
  88 --------
  89
  90 OpenSSL 0.9.6b changes the PRNG implementation as follows to give the
  91 PRNG its intended strength:
  92
  93 1. When updating 'md' during PRNG output generation, all of the
  94    previous 'md' value is hashed, including the secret half.
  95
  96 2. Also, the number of bytes from 'state' included into the hash is
  97    now independent from the number of PRNG bytes requested.
  98
  99 The first measure alone would be sufficient to solve the problem.  The
 100 second measure makes sure that additional data from 'state' is never
 101 mixed in in small portions; this heuristically further strengthens the
 102 PRNG.
 103
 104
 105 IMPACT
 106 ------
 107
 108 It is unlikely for applications to request PRNG bytes in a pattern
 109 allowing for the attack against the OpenSSL PRNG.  Typically,
 110 applications will request PRNG bytes in larger chunks.
 111 No applications is known to us which is actually vulnerable.
 112
 113 However, the PRNG design flaw is a significant weakness: The PRNG does
 114 not provide the intended strength under all circumstances.  Therefore,
 115 we strongly recommend that all users upgrade to OpenSSL 0.9.6b as soon
 116 as possible.
 117
 118
 119 SOURCE CODE PATCH
 120 -----------------
 121
 122 If upgrading to OpenSSL 0.9.6b is not immediately possible, the
 123 following patch should be applied to file crypto/rand/md_rand.c in the
 124 OpenSSL source code tree.  (The patch is compatible with OpenSSL
 125 versions 0.9.5 up to 0.9.6a.)  This changes the PRNG in two ways, as
 126 discussed above.
 127
 128 --- md_rand.c
 129 +++ md_rand.c
 130 @@ -313,6 +313,7 @@
 131         {
 132         static volatile int stirred_pool = 0;
 133         int i,j,k,st_num,st_idx;
 134 +       int num_ceil;
 135         int ok;
 136         long md_c[2];
 137         unsigned char local_md[MD_DIGEST_LENGTH];
 138 @@ -333,6 +334,12 @@
 139                 }
 140  #endif
 141
 142 +       if (num <= 0)
 143 +               return 1;
 144 +
 145 +       /* round upwards to multiple of MD_DIGEST_LENGTH/2 */
 146 +       num_ceil = (1 + (num-1)/(MD_DIGEST_LENGTH/2)) * (MD_DIGEST_LENGTH/2);
 147 +
 148         /*
 149          * (Based on the rand(3) manpage:)
 150          *
 151 @@ -418,11 +425,11 @@
 152         md_c[1] = md_count[1];
 153         memcpy(local_md, md, sizeof md);
 154
 155 -       state_index+=num;
 156 +       state_index+=num_ceil;
 157         if (state_index > state_num)
 158                 state_index %= state_num;
 159
 160 -       /* state[st_idx], ..., state[(st_idx + num - 1) % st_num]
 161 +       /* state[st_idx], ..., state[(st_idx + num_ceil - 1) % st_num]
 162          * are now ours (but other threads may use them too) */
 163
 164         md_count[0] += 1;
 165 @@ -434,6 +441,7 @@
 166
 167         while (num > 0)
 168                 {
 169 +               /* num_ceil -= MD_DIGEST_LENGTH/2 */
 170                 j=(num >= MD_DIGEST_LENGTH/2)?MD_DIGEST_LENGTH/2:num;
 171                 num-=j;
 172                 MD_Init(&m);
 173 @@ -444,27 +452,28 @@
 174                         curr_pid = 0;
 175                         }
 176  #endif
 177 -               MD_Update(&m,&(local_md[MD_DIGEST_LENGTH/2]),MD_DIGEST_LENGTH/2);
 178 +               MD_Update(&m,local_md,MD_DIGEST_LENGTH);
 179                 MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c));
 180  #ifndef PURIFY
 181                 MD_Update(&m,buf,j); /* purify complains */
 182  #endif
 183 -               k=(st_idx+j)-st_num;
 184 +               k=(st_idx+MD_DIGEST_LENGTH/2)-st_num;
 185                 if (k > 0)
 186                         {
 187 -                       MD_Update(&m,&(state[st_idx]),j-k);
 188 +                       MD_Update(&m,&(state[st_idx]),MD_DIGEST_LENGTH/2-k);
 189                         MD_Update(&m,&(state[0]),k);
 190                         }
 191                 else
 192 -                       MD_Update(&m,&(state[st_idx]),j);
 193 +                       MD_Update(&m,&(state[st_idx]),MD_DIGEST_LENGTH/2);
 194                 MD_Final(local_md,&m);
 195
 196 -               for (i=0; i<j; i++)
 197 +               for (i=0; i<MD_DIGEST_LENGTH/2; i++)
 198                         {
 199                         state[st_idx++]^=local_md[i]; /* may compete with other threads */
 200 -                       *(buf++)=local_md[i+MD_DIGEST_LENGTH/2];
 201                         if (st_idx >= st_num)
 202                                 st_idx=0;
 203 +                       if (i < j)
 204 +                               *(buf++)=local_md[i+MD_DIGEST_LENGTH/2];
 205                         }
 206                 }
 207
 208 *** END OF PATCH ***
 209
 210
 211 ACKNOWLEDGEMENT
 212 ---------------
 213
 214 We thank Markku-Juhani O. Saarinen <markku-juhani.saarinen@nokia.com>
 215 for discovering the PRNG problem and bringing it to our attention.
 216
 217
 218 URL for this Security Advisory:
 219 https://www.openssl.org/news/secadv_prng.txt