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 <asdcp/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 <asdcp/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_int = reinterpret_cast<ui32_t*> (m_ctr_buf + 12);
 120     *m_ctr_buf_int = 1;
 121   }
 122
 123   //
 124   void
 125   fill_rand(byte_t* buf, ui32_t len)
 126   {
 127     assert(len <= MAX_SEQUENCE_LEN);
 128     ui32_t gen_count = 0;
 129     AutoMutex Lock(m_Lock);
 130
 131     while ( gen_count + RNG_BLOCK_SIZE <= len )
 132       {
 133         AES_encrypt(m_ctr_buf, buf + gen_count, &m_Context);
 134         ui32_t* m_ctr_buf_int = reinterpret_cast<ui32_t*> (m_ctr_buf + 12);
 135         *m_ctr_buf_int += 1;
 136         gen_count += RNG_BLOCK_SIZE;
 137       }
 138
 139     if ( len != gen_count ) // partial count needed?
 140       {
 141         byte_t tmp[RNG_BLOCK_SIZE];
 142         AES_encrypt(m_ctr_buf, tmp, &m_Context);
 143         memcpy(buf + gen_count, tmp, len - gen_count);
 144       }
 145
 146     if (cth_test)
 147       {
 148 #ifdef __unix__
 149         for (unsigned int i = 0; i < len; ++i)
 150           buf[i] = rand_r(&m_cth_test_rng_state);
 151 #endif
 152       }
 153   }
 154
 155   void reset()
 156     {
 157       m_cth_test_rng_state = 1;
 158     }
 159 };
 160
 161
 162 static h__RNG* s_RNG = 0;
 163
 164
 165 //------------------------------------------------------------------------------------------
 166 //
 167 // Fortuna public interface
 168
 169 Kumu::FortunaRNG::FortunaRNG()
 170 {
 171   if ( s_RNG == 0 )
 172     s_RNG = new h__RNG;
 173 }
 174
 175 Kumu::FortunaRNG::~FortunaRNG() {}
 176
 177 //
 178 const byte_t*
 179 Kumu::FortunaRNG::FillRandom(byte_t* buf, ui32_t len)
 180 {
 181   assert(buf);
 182   assert(s_RNG);
 183   const byte_t* front_of_buffer = buf;
 184
 185   while ( len )
 186     {
 187       // 2^20 bytes max per seeding, use 2^19 to save
 188       // room for generating reseed values
 189       ui32_t gen_size = xmin(len, MAX_SEQUENCE_LEN);
 190       s_RNG->fill_rand(buf, gen_size);
 191       buf += gen_size;
 192       len -= gen_size;
 193
 194       // re-seed the generator
 195       byte_t rng_key[RNG_KEY_SIZE];
 196       s_RNG->fill_rand(rng_key, RNG_KEY_SIZE);
 197       s_RNG->set_key(rng_key);
 198   }
 199
 200   return front_of_buffer;
 201 }
 202
 203 //
 204 const byte_t*
 205 Kumu::FortunaRNG::FillRandom(Kumu::ByteString& Buffer)
 206 {
 207   FillRandom(Buffer.Data(), Buffer.Capacity());
 208   Buffer.Length(Buffer.Capacity());
 209   return Buffer.Data();
 210 }
 211
 212 void
 213 Kumu::FortunaRNG::Reset()
 214 {
 215   s_RNG->reset();
 216 }
 217
 218 //------------------------------------------------------------------------------------------
 219
 220 //
 221 // FIPS 186-2 Sec. 3.1 as modified by Change 1, section entitled "General Purpose Random Number Generation"
 222 void
 223 Kumu::Gen_FIPS_186_Value(const byte_t* key, ui32_t key_size, byte_t* out_buf, ui32_t out_buf_len)
 224 {
 225   byte_t sha_buf[SHA_DIGEST_LENGTH];
 226   ui32_t const xkey_len = 64; // 512/8
 227   byte_t xkey[xkey_len];
 228   BN_CTX* ctx1 = BN_CTX_new(); // used by BN_* functions
 229   assert(ctx1);
 230
 231   if ( key_size > xkey_len )
 232     DefaultLogSink().Warn("Key too large for FIPS 186 seed, truncating to 64 bytes.\n");
 233
 234   // init key
 235   memset(xkey, 0, xkey_len);
 236   memcpy(xkey, key, xmin<ui32_t>(key_size, xkey_len));
 237
 238   if ( key_size < SHA_DIGEST_LENGTH )
 239     key_size = SHA_DIGEST_LENGTH; // pad short key ( b < 160 )
 240
 241   // create the 2^b constant
 242   BIGNUM* c_2powb = BN_new();
 243   BIGNUM* c_2 = BN_new();
 244   BIGNUM* c_b = BN_new();
 245   BN_set_word(c_2, 2);
 246   BN_set_word(c_b, key_size * 8);
 247   BN_exp(c_2powb, c_2, c_b, ctx1);
 248
 249   for (;;)
 250     {
 251       SHA_CTX SHA;
 252
 253       // step c -- x = G(t,xkey)
 254       SHA1_Init(&SHA); // set t
 255       SHA1_Update(&SHA, xkey, xkey_len);
 256
 257       ui32_t* buf_p = (ui32_t*)sha_buf;
 258       *buf_p++ = KM_i32_BE(SHA.h0);
 259       *buf_p++ = KM_i32_BE(SHA.h1);
 260       *buf_p++ = KM_i32_BE(SHA.h2);
 261       *buf_p++ = KM_i32_BE(SHA.h3);
 262       *buf_p++ = KM_i32_BE(SHA.h4);
 263       memcpy(out_buf, sha_buf, xmin<ui32_t>(out_buf_len, SHA_DIGEST_LENGTH));
 264
 265       if ( out_buf_len <= SHA_DIGEST_LENGTH )
 266         break;
 267
 268       out_buf_len -= SHA_DIGEST_LENGTH;
 269       out_buf += SHA_DIGEST_LENGTH;
 270
 271       // step d -- XKEY = (1 + XKEY + x) mod 2^b
 272       BIGNUM* bn_tmp = BN_new();
 273       BIGNUM* bn_xkey = BN_new();
 274       BIGNUM* bn_x_n = BN_new();
 275
 276       BN_bin2bn(xkey, key_size, bn_xkey);
 277       BN_bin2bn(sha_buf, SHA_DIGEST_LENGTH, bn_x_n);
 278       BN_add_word(bn_xkey, 1);            // xkey += 1
 279       BN_add(bn_tmp, bn_xkey, bn_x_n);       // xkey += x
 280       BN_mod(bn_xkey, bn_tmp, c_2powb, ctx1);  // xkey = xkey mod (2^b)
 281
 282       memset(xkey, 0, xkey_len);
 283       ui32_t bn_buf_len = BN_num_bytes(bn_xkey);
 284       ui32_t idx = ( bn_buf_len < key_size ) ? key_size - bn_buf_len : 0;
 285       BN_bn2bin(bn_xkey, &xkey[idx]);
 286
 287       BN_free(bn_tmp);
 288       BN_free(bn_xkey);
 289       BN_free(bn_x_n);
 290     }
 291
 292   BN_free(c_2powb);
 293   BN_free(c_2);
 294   BN_free(c_b);
 295   BN_CTX_free(ctx1);
 296 }
 297
 298 //
 299 // end KM_prng.cpp
 300 //