asdcplib/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 const ui32_t RNG_KEY_SIZE = 512UL;
  52 const ui32_t RNG_KEY_SIZE_BITS = 256UL;
  53 const ui32_t RNG_BLOCK_SIZE = 16UL;
  54 const ui32_t MAX_SEQUENCE_LEN = 0x00040000UL;
  55
  56
  57 // internal implementation class
  58 class h__RNG
  59 {
  60   KM_NO_COPY_CONSTRUCT(h__RNG);
  61
  62 public:
  63   AES_KEY   m_Context;
  64   byte_t    m_ctr_buf[RNG_BLOCK_SIZE];
  65   Mutex     m_Lock;
  66   unsigned int m_libdcp_test_rng_state;
  67
  68   h__RNG()
  69   {
  70     memset(m_ctr_buf, 0, RNG_BLOCK_SIZE);
  71     byte_t rng_key[RNG_KEY_SIZE];
  72
  73     { // this block scopes the following AutoMutex so that it will be
  74       // released before the call to set_key() below.
  75       AutoMutex Lock(m_Lock);
  76
  77 #ifdef KM_WIN32
  78       HCRYPTPROV hProvider = 0;
  79       CryptAcquireContext(&hProvider, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
  80       CryptGenRandom(hProvider, RNG_KEY_SIZE, rng_key);
  81 #else // KM_WIN32
  82       // on POSIX systems we simply read some seed from /dev/urandom
  83       FileReader URandom;
  84
  85       Result_t result = URandom.OpenRead(DEV_URANDOM);
  86
  87       if ( KM_SUCCESS(result) )
  88         {
  89           ui32_t read_count;
  90           result = URandom.Read(rng_key, RNG_KEY_SIZE, &read_count);
  91         }
  92
  93       if ( KM_FAILURE(result) )
  94         DefaultLogSink().Error("Error opening random device: %s\n", DEV_URANDOM);
  95
  96 #endif // KM_WIN32
  97     } // end AutoMutex context
  98
  99     set_key(rng_key);
 100
 101     m_libdcp_test_rng_state = 1;
 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 (libdcp_test)
 145       {
 146         for (unsigned int i = 0; i < len; ++i)
 147           buf[i] = rand_r(&m_libdcp_test_rng_state);
 148       }
 149   }
 150 };
 151
 152
 153 static h__RNG* s_RNG = 0;
 154
 155
 156 //------------------------------------------------------------------------------------------
 157 //
 158 // Fortuna public interface
 159
 160 Kumu::FortunaRNG::FortunaRNG()
 161 {
 162   if ( s_RNG == 0 )
 163     s_RNG = new h__RNG;
 164 }
 165
 166 Kumu::FortunaRNG::~FortunaRNG() {}
 167
 168 //
 169 const byte_t*
 170 Kumu::FortunaRNG::FillRandom(byte_t* buf, ui32_t len)
 171 {
 172   assert(buf);
 173   assert(s_RNG);
 174   const byte_t* front_of_buffer = buf;
 175
 176   while ( len )
 177     {
 178       // 2^20 bytes max per seeding, use 2^19 to save
 179       // room for generating reseed values
 180       ui32_t gen_size = xmin(len, MAX_SEQUENCE_LEN);
 181       s_RNG->fill_rand(buf, gen_size);
 182       buf += gen_size;
 183       len -= gen_size;
 184
 185       // re-seed the generator
 186       byte_t rng_key[RNG_KEY_SIZE];
 187       s_RNG->fill_rand(rng_key, RNG_KEY_SIZE);
 188       s_RNG->set_key(rng_key);
 189   }
 190
 191   return front_of_buffer;
 192 }
 193
 194 //
 195 const byte_t*
 196 Kumu::FortunaRNG::FillRandom(Kumu::ByteString& Buffer)
 197 {
 198   FillRandom(Buffer.Data(), Buffer.Capacity());
 199   Buffer.Length(Buffer.Capacity());
 200   return Buffer.Data();
 201 }
 202
 203 //------------------------------------------------------------------------------------------
 204
 205 //
 206 // FIPS 186-2 Sec. 3.1 as modified by Change 1, section entitled "General Purpose Random Number Generation"
 207 void
 208 Kumu::Gen_FIPS_186_Value(const byte_t* key, ui32_t key_size, byte_t* out_buf, ui32_t out_buf_len)
 209 {
 210   byte_t sha_buf[SHA_DIGEST_LENGTH];
 211   ui32_t const xkey_len = 64; // 512/8
 212   byte_t xkey[xkey_len];
 213   BN_CTX* ctx1 = BN_CTX_new(); // used by BN_* functions
 214   assert(ctx1);
 215
 216   if ( key_size > xkey_len )
 217     DefaultLogSink().Warn("Key too large for FIPS 186 seed, truncating to 64 bytes.\n");
 218
 219   // init key
 220   memset(xkey, 0, xkey_len);
 221   memcpy(xkey, key, xmin<ui32_t>(key_size, xkey_len));
 222
 223   if ( key_size < SHA_DIGEST_LENGTH )
 224     key_size = SHA_DIGEST_LENGTH; // pad short key ( b < 160 )
 225
 226   // create the 2^b constant
 227   BIGNUM c_2powb, c_2, c_b;
 228   BN_init(&c_2powb);  BN_init(&c_2);  BN_init(&c_b);
 229   BN_set_word(&c_2, 2);
 230   BN_set_word(&c_b, key_size * 8);
 231   BN_exp(&c_2powb, &c_2, &c_b, ctx1);
 232
 233   for (;;)
 234     {
 235       SHA_CTX SHA;
 236
 237       // step c -- x = G(t,xkey)
 238       SHA1_Init(&SHA); // set t
 239       SHA1_Update(&SHA, xkey, xkey_len);
 240
 241       ui32_t* buf_p = (ui32_t*)sha_buf;
 242       *buf_p++ = KM_i32_BE(SHA.h0);
 243       *buf_p++ = KM_i32_BE(SHA.h1);
 244       *buf_p++ = KM_i32_BE(SHA.h2);
 245       *buf_p++ = KM_i32_BE(SHA.h3);
 246       *buf_p++ = KM_i32_BE(SHA.h4);
 247       memcpy(out_buf, sha_buf, xmin<ui32_t>(out_buf_len, SHA_DIGEST_LENGTH));
 248
 249       if ( out_buf_len <= SHA_DIGEST_LENGTH )
 250         break;
 251
 252       out_buf_len -= SHA_DIGEST_LENGTH;
 253       out_buf += SHA_DIGEST_LENGTH;
 254
 255       // step d -- XKEY = (1 + XKEY + x) mod 2^b
 256       BIGNUM bn_tmp, bn_xkey, bn_x_n;
 257       BN_init(&bn_tmp);  BN_init(&bn_xkey);    BN_init(&bn_x_n);
 258
 259       BN_bin2bn(xkey, key_size, &bn_xkey);
 260       BN_bin2bn(sha_buf, SHA_DIGEST_LENGTH, &bn_x_n);
 261       BN_add_word(&bn_xkey, 1);            // xkey += 1
 262       BN_add(&bn_tmp, &bn_xkey, &bn_x_n);       // xkey += x
 263       BN_mod(&bn_xkey, &bn_tmp, &c_2powb, ctx1);  // xkey = xkey mod (2^b)
 264
 265       memset(xkey, 0, xkey_len);
 266       ui32_t bn_buf_len = BN_num_bytes(&bn_xkey);
 267       ui32_t idx = ( bn_buf_len < key_size ) ? key_size - bn_buf_len : 0;
 268       BN_bn2bin(&bn_xkey, &xkey[idx]);
 269     }
 270
 271   BN_CTX_free(ctx1);
 272 }
 273
 274 //
 275 // end KM_prng.cpp
 276 //