src/KM_prng.cpp

   1 /*
   2 Copyright (c) 2006-2009, John Hurst
   3 All rights reserved.
   4
   5 Redistribution and use in source and binary forms, with or without
   6 modification, are permitted provided that the following conditions
   7 are met:
   8 1. Redistributions of source code must retain the above copyright
   9    notice, this list of conditions and the following disclaimer.
  10 2. Redistributions in binary form must reproduce the above copyright
  11    notice, this list of conditions and the following disclaimer in the
  12    documentation and/or other materials provided with the distribution.
  13 3. The name of the author may not be used to endorse or promote products
  14    derived from this software without specific prior written permission.
  15
  16 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26 */
  27   /*! \file    KM_prng.cpp
  28     \version $Id: KM_prng.cpp,v 1.9 2011/06/14 23:38:33 jhurst Exp $
  29     \brief   Fortuna pseudo-random number generator
  30   */
  31
  32 #include <KM_prng.h>
  33 #include <KM_log.h>
  34 #include <KM_mutex.h>
  35 #include <string.h>
  36 #include <assert.h>
  37 #include <openssl/aes.h>
  38 #include <openssl/sha.h>
  39 #include <openssl/bn.h>
  40
  41 using namespace Kumu;
  42
  43
  44 #ifdef KM_WIN32
  45 # include <wincrypt.h>
  46 #else // KM_WIN32
  47 # include <KM_fileio.h>
  48 const char* DEV_URANDOM = "/dev/urandom";
  49 #endif // KM_WIN32
  50
  51
  52 const ui32_t RNG_KEY_SIZE = 512UL;
  53 const ui32_t RNG_KEY_SIZE_BITS = 256UL;
  54 const ui32_t RNG_BLOCK_SIZE = 16UL;
  55 const ui32_t MAX_SEQUENCE_LEN = 0x00040000UL;
  56
  57
  58 // internal implementation class
  59 class h__RNG
  60 {
  61   KM_NO_COPY_CONSTRUCT(h__RNG);
  62
  63 public:
  64   AES_KEY   m_Context;
  65   byte_t    m_ctr_buf[RNG_BLOCK_SIZE];
  66   Mutex     m_Lock;
  67   unsigned int m_cth_test_rng_state;
  68
  69   h__RNG()
  70   {
  71     memset(m_ctr_buf, 0, RNG_BLOCK_SIZE);
  72     byte_t rng_key[RNG_KEY_SIZE];
  73
  74     { // this block scopes the following AutoMutex so that it will be
  75       // released before the call to set_key() below.
  76       AutoMutex Lock(m_Lock);
  77
  78 #ifdef KM_WIN32
  79       HCRYPTPROV hProvider = 0;
  80       CryptAcquireContext(&hProvider, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
  81       CryptGenRandom(hProvider, RNG_KEY_SIZE, rng_key);
  82 #else // KM_WIN32
  83       // on POSIX systems we simply read some seed from /dev/urandom
  84       FileReader URandom;
  85
  86       Result_t result = URandom.OpenRead(DEV_URANDOM);
  87
  88       if ( KM_SUCCESS(result) )
  89         {
  90           ui32_t read_count;
  91           result = URandom.Read(rng_key, RNG_KEY_SIZE, &read_count);
  92         }
  93
  94       if ( KM_FAILURE(result) )
  95         DefaultLogSink().Error("Error opening random device: %s\n", DEV_URANDOM);
  96
  97 #endif // KM_WIN32
  98     } // end AutoMutex context
  99
 100     set_key(rng_key);
 101     reset();
 102   }
 103
 104   //
 105   void
 106   set_key(const byte_t* key_fodder)
 107   {
 108     assert(key_fodder);
 109     byte_t sha_buf[20];
 110     SHA_CTX SHA;
 111     SHA1_Init(&SHA);
 112
 113     SHA1_Update(&SHA, (byte_t*)&m_Context, sizeof(m_Context));
 114     SHA1_Update(&SHA, key_fodder, RNG_KEY_SIZE);
 115     SHA1_Final(sha_buf, &SHA);
 116
 117     AutoMutex Lock(m_Lock);
 118     AES_set_encrypt_key(sha_buf, RNG_KEY_SIZE_BITS, &m_Context);
 119     *(ui32_t*)(m_ctr_buf + 12) = 1;
 120   }
 121
 122   //
 123   void
 124   fill_rand(byte_t* buf, ui32_t len)
 125   {
 126     assert(len <= MAX_SEQUENCE_LEN);
 127     ui32_t gen_count = 0;
 128     AutoMutex Lock(m_Lock);
 129
 130     while ( gen_count + RNG_BLOCK_SIZE <= len )
 131       {
 132         AES_encrypt(m_ctr_buf, buf + gen_count, &m_Context);
 133         *(ui32_t*)(m_ctr_buf + 12) += 1;
 134         gen_count += RNG_BLOCK_SIZE;
 135       }
 136
 137     if ( len != gen_count ) // partial count needed?
 138       {
 139         byte_t tmp[RNG_BLOCK_SIZE];
 140         AES_encrypt(m_ctr_buf, tmp, &m_Context);
 141         memcpy(buf + gen_count, tmp, len - gen_count);
 142       }
 143
 144     if (cth_test)
 145       {
 146 #ifdef __unix__
 147         for (unsigned int i = 0; i < len; ++i)
 148           buf[i] = rand_r(&m_cth_test_rng_state);
 149 #endif
 150       }
 151   }
 152
 153   void reset()
 154     {
 155       m_cth_test_rng_state = 1;
 156     }
 157 };
 158
 159
 160 static h__RNG* s_RNG = 0;
 161
 162
 163 //------------------------------------------------------------------------------------------
 164 //
 165 // Fortuna public interface
 166
 167 Kumu::FortunaRNG::FortunaRNG()
 168 {
 169   if ( s_RNG == 0 )
 170     s_RNG = new h__RNG;
 171 }
 172
 173 Kumu::FortunaRNG::~FortunaRNG() {}
 174
 175 //
 176 const byte_t*
 177 Kumu::FortunaRNG::FillRandom(byte_t* buf, ui32_t len)
 178 {
 179   assert(buf);
 180   assert(s_RNG);
 181   const byte_t* front_of_buffer = buf;
 182
 183   while ( len )
 184     {
 185       // 2^20 bytes max per seeding, use 2^19 to save
 186       // room for generating reseed values
 187       ui32_t gen_size = xmin(len, MAX_SEQUENCE_LEN);
 188       s_RNG->fill_rand(buf, gen_size);
 189       buf += gen_size;
 190       len -= gen_size;
 191
 192       // re-seed the generator
 193       byte_t rng_key[RNG_KEY_SIZE];
 194       s_RNG->fill_rand(rng_key, RNG_KEY_SIZE);
 195       s_RNG->set_key(rng_key);
 196   }
 197
 198   return front_of_buffer;
 199 }
 200
 201 //
 202 const byte_t*
 203 Kumu::FortunaRNG::FillRandom(Kumu::ByteString& Buffer)
 204 {
 205   FillRandom(Buffer.Data(), Buffer.Capacity());
 206   Buffer.Length(Buffer.Capacity());
 207   return Buffer.Data();
 208 }
 209
 210 void
 211 Kumu::FortunaRNG::Reset()
 212 {
 213   s_RNG->reset();
 214 }
 215
 216 //------------------------------------------------------------------------------------------
 217
 218 //
 219 // FIPS 186-2 Sec. 3.1 as modified by Change 1, section entitled "General Purpose Random Number Generation"
 220 void
 221 Kumu::Gen_FIPS_186_Value(const byte_t* key, ui32_t key_size, byte_t* out_buf, ui32_t out_buf_len)
 222 {
 223   byte_t sha_buf[SHA_DIGEST_LENGTH];
 224   ui32_t const xkey_len = 64; // 512/8
 225   byte_t xkey[xkey_len];
 226   BN_CTX* ctx1 = BN_CTX_new(); // used by BN_* functions
 227   assert(ctx1);
 228
 229   if ( key_size > xkey_len )
 230     DefaultLogSink().Warn("Key too large for FIPS 186 seed, truncating to 64 bytes.\n");
 231
 232   // init key
 233   memset(xkey, 0, xkey_len);
 234   memcpy(xkey, key, xmin<ui32_t>(key_size, xkey_len));
 235
 236   if ( key_size < SHA_DIGEST_LENGTH )
 237     key_size = SHA_DIGEST_LENGTH; // pad short key ( b < 160 )
 238
 239   // create the 2^b constant
 240   BIGNUM c_2powb, c_2, c_b;
 241   BN_init(&c_2powb);  BN_init(&c_2);  BN_init(&c_b);
 242   BN_set_word(&c_2, 2);
 243   BN_set_word(&c_b, key_size * 8);
 244   BN_exp(&c_2powb, &c_2, &c_b, ctx1);
 245
 246   for (;;)
 247     {
 248       SHA_CTX SHA;
 249
 250       // step c -- x = G(t,xkey)
 251       SHA1_Init(&SHA); // set t
 252       SHA1_Update(&SHA, xkey, xkey_len);
 253
 254       ui32_t* buf_p = (ui32_t*)sha_buf;
 255       *buf_p++ = KM_i32_BE(SHA.h0);
 256       *buf_p++ = KM_i32_BE(SHA.h1);
 257       *buf_p++ = KM_i32_BE(SHA.h2);
 258       *buf_p++ = KM_i32_BE(SHA.h3);
 259       *buf_p++ = KM_i32_BE(SHA.h4);
 260       memcpy(out_buf, sha_buf, xmin<ui32_t>(out_buf_len, SHA_DIGEST_LENGTH));
 261
 262       if ( out_buf_len <= SHA_DIGEST_LENGTH )
 263         break;
 264
 265       out_buf_len -= SHA_DIGEST_LENGTH;
 266       out_buf += SHA_DIGEST_LENGTH;
 267
 268       // step d -- XKEY = (1 + XKEY + x) mod 2^b
 269       BIGNUM bn_tmp, bn_xkey, bn_x_n;
 270       BN_init(&bn_tmp);  BN_init(&bn_xkey);    BN_init(&bn_x_n);
 271
 272       BN_bin2bn(xkey, key_size, &bn_xkey);
 273       BN_bin2bn(sha_buf, SHA_DIGEST_LENGTH, &bn_x_n);
 274       BN_add_word(&bn_xkey, 1);            // xkey += 1
 275       BN_add(&bn_tmp, &bn_xkey, &bn_x_n);       // xkey += x
 276       BN_mod(&bn_xkey, &bn_tmp, &c_2powb, ctx1);  // xkey = xkey mod (2^b)
 277
 278       memset(xkey, 0, xkey_len);
 279       ui32_t bn_buf_len = BN_num_bytes(&bn_xkey);
 280       ui32_t idx = ( bn_buf_len < key_size ) ? key_size - bn_buf_len : 0;
 281       BN_bn2bin(&bn_xkey, &xkey[idx]);
 282     }
 283
 284   BN_CTX_free(ctx1);
 285 }
 286
 287 //
 288 // end KM_prng.cpp
 289 //