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$
  29     \brief   Fortuna pseudo-random number generator
  30   */
  31
  32 #include <asdcp/KM_prng.h>
  33 #include <asdcp/KM_log.h>
  34 #include <asdcp/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 #if HAVE_VALGRIND_MEMCHECK_H
  41 #include <valgrind/memcheck.h>
  42 #endif
  43
  44 using namespace Kumu;
  45
  46
  47 #ifdef KM_WIN32
  48 # include <wincrypt.h>
  49 #else // KM_WIN32
  50 # include <asdcp/KM_fileio.h>
  51 const char* DEV_URANDOM = "/dev/urandom";
  52 #endif // KM_WIN32
  53
  54
  55 const ui32_t RNG_KEY_SIZE = 512UL;
  56 const ui32_t RNG_KEY_SIZE_BITS = 256UL;
  57 const ui32_t RNG_BLOCK_SIZE = 16UL;
  58 const ui32_t MAX_SEQUENCE_LEN = 0x00040000UL;
  59
  60
  61 // internal implementation class
  62 class h__RNG
  63 {
  64   KM_NO_COPY_CONSTRUCT(h__RNG);
  65
  66 public:
  67   AES_KEY   m_Context;
  68   byte_t    m_ctr_buf[RNG_BLOCK_SIZE];
  69   Mutex     m_Lock;
  70   unsigned int m_cth_test_rng_state;
  71
  72   h__RNG()
  73   {
  74     memset(m_ctr_buf, 0, RNG_BLOCK_SIZE);
  75     byte_t rng_key[RNG_KEY_SIZE];
  76
  77     { // this block scopes the following AutoMutex so that it will be
  78       // released before the call to set_key() below.
  79       AutoMutex Lock(m_Lock);
  80
  81 #ifdef KM_WIN32
  82       HCRYPTPROV hProvider = 0;
  83       CryptAcquireContext(&hProvider, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
  84       CryptGenRandom(hProvider, RNG_KEY_SIZE, rng_key);
  85 #else // KM_WIN32
  86       // on POSIX systems we simply read some seed from /dev/urandom
  87       FileReader URandom;
  88
  89       Result_t result = URandom.OpenRead(DEV_URANDOM);
  90
  91       if ( KM_SUCCESS(result) )
  92         {
  93           ui32_t read_count;
  94           result = URandom.Read(rng_key, RNG_KEY_SIZE, &read_count);
  95         }
  96
  97 #if HAVE_VALGRIND_MEMCHECK_H
  98       VALGRIND_MAKE_MEM_DEFINED (rng_key, RNG_KEY_SIZE);
  99 #endif
 100
 101       if ( KM_FAILURE(result) )
 102         DefaultLogSink().Error("Error opening random device: %s\n", DEV_URANDOM);
 103
 104 #endif // KM_WIN32
 105     } // end AutoMutex context
 106
 107     set_key(rng_key);
 108     reset();
 109   }
 110
 111   //
 112   void
 113   set_key(const byte_t* key_fodder)
 114   {
 115     assert(key_fodder);
 116     byte_t sha_buf[20];
 117     SHA_CTX SHA;
 118     SHA1_Init(&SHA);
 119
 120     SHA1_Update(&SHA, (byte_t*)&m_Context, sizeof(m_Context));
 121     SHA1_Update(&SHA, key_fodder, RNG_KEY_SIZE);
 122     SHA1_Final(sha_buf, &SHA);
 123
 124 #if HAVE_VALGRIND_MEMCHECK_H
 125     VALGRIND_MAKE_MEM_DEFINED (sha_buf, 20);
 126     VALGRIND_MAKE_MEM_DEFINED (&m_Context, sizeof(m_Context));
 127 #endif
 128
 129     AutoMutex Lock(m_Lock);
 130     AES_set_encrypt_key(sha_buf, RNG_KEY_SIZE_BITS, &m_Context);
 131     ui32_t* m_ctr_buf_int = reinterpret_cast<ui32_t*> (m_ctr_buf + 12);
 132     *m_ctr_buf_int = 1;
 133   }
 134
 135   //
 136   void
 137   fill_rand(byte_t* buf, ui32_t len)
 138   {
 139     assert(len <= MAX_SEQUENCE_LEN);
 140     ui32_t gen_count = 0;
 141     AutoMutex Lock(m_Lock);
 142
 143     while ( gen_count + RNG_BLOCK_SIZE <= len )
 144       {
 145         AES_encrypt(m_ctr_buf, buf + gen_count, &m_Context);
 146         ui32_t* m_ctr_buf_int = reinterpret_cast<ui32_t*> (m_ctr_buf + 12);
 147         *m_ctr_buf_int += 1;
 148         gen_count += RNG_BLOCK_SIZE;
 149       }
 150
 151     if ( len != gen_count ) // partial count needed?
 152       {
 153         byte_t tmp[RNG_BLOCK_SIZE];
 154         AES_encrypt(m_ctr_buf, tmp, &m_Context);
 155         memcpy(buf + gen_count, tmp, len - gen_count);
 156       }
 157
 158     if (cth_test)
 159       {
 160 #ifdef __unix__
 161         for (unsigned int i = 0; i < len; ++i)
 162           buf[i] = rand_r(&m_cth_test_rng_state);
 163 #endif
 164       }
 165
 166 #if HAVE_VALGRIND_MEMCHECK_H
 167     VALGRIND_MAKE_MEM_DEFINED (buf, len);
 168 #endif
 169
 170   }
 171
 172   void reset()
 173     {
 174       m_cth_test_rng_state = 1;
 175     }
 176 };
 177
 178
 179 static h__RNG* s_RNG = 0;
 180
 181
 182 //------------------------------------------------------------------------------------------
 183 //
 184 // Fortuna public interface
 185
 186 Kumu::FortunaRNG::FortunaRNG()
 187 {
 188   if ( s_RNG == 0 )
 189     s_RNG = new h__RNG;
 190 }
 191
 192 Kumu::FortunaRNG::~FortunaRNG() {}
 193
 194 //
 195 const byte_t*
 196 Kumu::FortunaRNG::FillRandom(byte_t* buf, ui32_t len)
 197 {
 198   assert(buf);
 199   assert(s_RNG);
 200   const byte_t* front_of_buffer = buf;
 201
 202   while ( len )
 203     {
 204       // 2^20 bytes max per seeding, use 2^19 to save
 205       // room for generating reseed values
 206       ui32_t gen_size = xmin(len, MAX_SEQUENCE_LEN);
 207       s_RNG->fill_rand(buf, gen_size);
 208       buf += gen_size;
 209       len -= gen_size;
 210
 211       // re-seed the generator
 212       byte_t rng_key[RNG_KEY_SIZE];
 213       s_RNG->fill_rand(rng_key, RNG_KEY_SIZE);
 214       s_RNG->set_key(rng_key);
 215   }
 216
 217 #if HAVE_VALGRIND_MEMCHECK_H
 218   VALGRIND_MAKE_MEM_DEFINED(buf, len);
 219 #endif
 220
 221   return front_of_buffer;
 222 }
 223
 224 //
 225 const byte_t*
 226 Kumu::FortunaRNG::FillRandom(Kumu::ByteString& Buffer)
 227 {
 228   FillRandom(Buffer.Data(), Buffer.Capacity());
 229   Buffer.Length(Buffer.Capacity());
 230   return Buffer.Data();
 231 }
 232
 233 void
 234 Kumu::FortunaRNG::Reset()
 235 {
 236   s_RNG->reset();
 237 }
 238
 239 //------------------------------------------------------------------------------------------
 240
 241 //
 242 // FIPS 186-2 Sec. 3.1 as modified by Change 1, section entitled "General Purpose Random Number Generation"
 243 void
 244 Kumu::Gen_FIPS_186_Value(const byte_t* key, ui32_t key_size, byte_t* out_buf, ui32_t out_buf_len)
 245 {
 246   byte_t sha_buf[SHA_DIGEST_LENGTH];
 247   ui32_t const xkey_len = 64; // 512/8
 248   byte_t xkey[xkey_len];
 249   BN_CTX* ctx1 = BN_CTX_new(); // used by BN_* functions
 250   assert(ctx1);
 251
 252   if ( key_size > xkey_len )
 253     DefaultLogSink().Warn("Key too large for FIPS 186 seed, truncating to 64 bytes.\n");
 254
 255   // init key
 256   memset(xkey, 0, xkey_len);
 257   memcpy(xkey, key, xmin<ui32_t>(key_size, xkey_len));
 258
 259   if ( key_size < SHA_DIGEST_LENGTH )
 260     key_size = SHA_DIGEST_LENGTH; // pad short key ( b < 160 )
 261
 262   // create the 2^b constant
 263   BIGNUM* c_2powb = BN_new();
 264   BIGNUM* c_2 = BN_new();
 265   BIGNUM* c_b = BN_new();
 266   BN_set_word(c_2, 2);
 267   BN_set_word(c_b, key_size * 8);
 268   BN_exp(c_2powb, c_2, c_b, ctx1);
 269
 270   for (;;)
 271     {
 272       SHA_CTX SHA;
 273
 274       // step c -- x = G(t,xkey)
 275       SHA1_Init(&SHA); // set t
 276       SHA1_Update(&SHA, xkey, xkey_len);
 277
 278       ui32_t* buf_p = (ui32_t*)sha_buf;
 279       *buf_p++ = KM_i32_BE(SHA.h0);
 280       *buf_p++ = KM_i32_BE(SHA.h1);
 281       *buf_p++ = KM_i32_BE(SHA.h2);
 282       *buf_p++ = KM_i32_BE(SHA.h3);
 283       *buf_p++ = KM_i32_BE(SHA.h4);
 284       memcpy(out_buf, sha_buf, xmin<ui32_t>(out_buf_len, SHA_DIGEST_LENGTH));
 285
 286       if ( out_buf_len <= SHA_DIGEST_LENGTH )
 287         break;
 288
 289       out_buf_len -= SHA_DIGEST_LENGTH;
 290       out_buf += SHA_DIGEST_LENGTH;
 291
 292       // step d -- XKEY = (1 + XKEY + x) mod 2^b
 293       BIGNUM* bn_tmp = BN_new();
 294       BIGNUM* bn_xkey = BN_new();
 295       BIGNUM* bn_x_n = BN_new();
 296
 297       BN_bin2bn(xkey, key_size, bn_xkey);
 298       BN_bin2bn(sha_buf, SHA_DIGEST_LENGTH, bn_x_n);
 299       BN_add_word(bn_xkey, 1);            // xkey += 1
 300       BN_add(bn_tmp, bn_xkey, bn_x_n);       // xkey += x
 301       BN_mod(bn_xkey, bn_tmp, c_2powb, ctx1);  // xkey = xkey mod (2^b)
 302
 303       memset(xkey, 0, xkey_len);
 304       ui32_t bn_buf_len = BN_num_bytes(bn_xkey);
 305       ui32_t idx = ( bn_buf_len < key_size ) ? key_size - bn_buf_len : 0;
 306       BN_bn2bin(bn_xkey, &xkey[idx]);
 307
 308       BN_free(bn_tmp);
 309       BN_free(bn_xkey);
 310       BN_free(bn_x_n);
 311     }
 312
 313   BN_free(c_2powb);
 314   BN_free(c_2);
 315   BN_free(c_b);
 316   BN_CTX_free(ctx1);
 317 }
 318
 319 //
 320 // end KM_prng.cpp
 321 //