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