src/KM_prng.cpp

   1 /*
   2 Copyright (c) 2006, 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
  40 using namespace Kumu;
  41
  42
  43 #ifdef KM_WIN32
  44
  45 //  make up a byte by sampling the perf counter LSB
  46 static byte_t get_perf_byte(byte_t carry)
  47 {
  48   LARGE_INTEGER ticks;
  49   byte_t sha_buf[20];
  50   SHA_CTX SHA;
  51   SHA1_Init(&SHA);
  52   SHA1_Update(&SHA, &carry, sizeof(byte_t));
  53
  54   for ( int i = 0; i < 128; i++ )
  55     {
  56       QueryPerformanceCounter(&ticks);
  57       SHA1_Update(&SHA, &ticks.LowPart, sizeof(ticks.LowPart));
  58     }
  59
  60   SHA1_Final(sha_buf, &SHA);
  61   return sha_buf[0];
  62 }
  63
  64 #else // KM_WIN32
  65
  66 #include <KM_fileio.h>
  67 const char* DEV_URANDOM = "/dev/urandom";
  68
  69 #endif // KM_WIN32
  70
  71
  72 const ui32_t RNG_KEY_SIZE = 512UL;
  73 const ui32_t RNG_KEY_SIZE_BITS = 256UL;
  74 const ui32_t RNG_BLOCK_SIZE = 16UL;
  75 const ui32_t MAX_SEQUENCE_LEN = 0x00040000UL;
  76
  77
  78 // internal implementation class
  79 class h__RNG
  80 {
  81   KM_NO_COPY_CONSTRUCT(h__RNG);
  82
  83 public:
  84   AES_KEY   m_Context;
  85   byte_t    m_ctr_buf[RNG_BLOCK_SIZE];
  86   Mutex     m_Lock;
  87
  88   h__RNG()
  89   {
  90     memset(m_ctr_buf, 0, RNG_BLOCK_SIZE);
  91     byte_t rng_key[RNG_KEY_SIZE];
  92
  93     { // this block scopes the following AutoMutex so that it will be
  94       // released before the call to set_key() below.
  95       AutoMutex Lock(m_Lock);
  96
  97 #ifdef KM_WIN32
  98       for ( ui32_t i = 0; i < RNG_KEY_SIZE; i++ )
  99         {
 100           byte_t carry = ( i == 0 ) ? 0xa3 : rng_key[i-1];
 101           rng_key[i] = get_perf_byte(carry);
 102         }
 103 #else // KM_WIN32
 104       // on POSIX systems we simply read some seed from /dev/urandom
 105       FileReader URandom;
 106
 107       Result_t result = URandom.OpenRead(DEV_URANDOM);
 108
 109       if ( KM_SUCCESS(result) )
 110         {
 111           ui32_t read_count;
 112           result = URandom.Read(rng_key, RNG_KEY_SIZE, &read_count);
 113         }
 114
 115       if ( KM_FAILURE(result) )
 116         DefaultLogSink().Error("Error opening random device: %s\n", DEV_URANDOM);
 117
 118 #endif // KM_WIN32
 119     } // end AutoMutex context
 120
 121     set_key(rng_key);
 122   }
 123
 124   //
 125   void
 126   set_key(const byte_t* key_fodder)
 127   {
 128     assert(key_fodder);
 129     byte_t sha_buf[20];
 130     SHA_CTX SHA;
 131     SHA1_Init(&SHA);
 132
 133     SHA1_Update(&SHA, (byte_t*)&m_Context, sizeof(m_Context));
 134     SHA1_Update(&SHA, key_fodder, RNG_KEY_SIZE);
 135     SHA1_Final(sha_buf, &SHA);
 136
 137     AutoMutex Lock(m_Lock);
 138     AES_set_encrypt_key(sha_buf, RNG_KEY_SIZE_BITS, &m_Context);
 139     *(ui32_t*)(m_ctr_buf + 12) = 1;
 140   }
 141
 142   //
 143   void
 144   fill_rand(byte_t* buf, ui32_t len)
 145   {
 146     assert(len <= MAX_SEQUENCE_LEN);
 147     ui32_t gen_count = 0;
 148     AutoMutex Lock(m_Lock);
 149
 150     while ( gen_count + RNG_BLOCK_SIZE <= len )
 151       {
 152         AES_encrypt(m_ctr_buf, buf + gen_count, &m_Context);
 153         *(ui32_t*)(m_ctr_buf + 12) += 1;
 154         gen_count += RNG_BLOCK_SIZE;
 155       }
 156
 157     if ( len != gen_count ) // partial count needed?
 158       {
 159         byte_t tmp[RNG_BLOCK_SIZE];
 160         AES_encrypt(m_ctr_buf, tmp, &m_Context);
 161         *(ui32_t*)(m_ctr_buf + 12) += 1;
 162         memcpy(buf, tmp, len - gen_count);
 163       }
 164   }
 165 };
 166
 167
 168 static h__RNG* s_RNG = 0;
 169
 170
 171 //------------------------------------------------------------------------------------------
 172 //
 173 // public interface
 174
 175 Kumu::FortunaRNG::FortunaRNG()
 176 {
 177   if ( s_RNG == 0 )
 178     s_RNG = new h__RNG;
 179 }
 180
 181 Kumu::FortunaRNG::~FortunaRNG() {}
 182
 183 //
 184 const byte_t*
 185 Kumu::FortunaRNG::FillRandom(byte_t* buf, ui32_t len)
 186 {
 187   assert(buf);
 188   assert(s_RNG);
 189
 190   while ( len )
 191     {
 192       // 2^20 bytes max per seeding, use 2^19 to save
 193       // room for generating reseed values
 194       ui32_t gen_size = xmin(len, MAX_SEQUENCE_LEN);
 195       s_RNG->fill_rand(buf, gen_size);
 196       buf += gen_size;
 197       len -= gen_size;
 198
 199       // re-seed the generator
 200       byte_t rng_key[RNG_KEY_SIZE];
 201       s_RNG->fill_rand(rng_key, RNG_KEY_SIZE);
 202       s_RNG->set_key(rng_key);
 203   }
 204
 205   return buf;
 206 }
 207
 208 //
 209 const byte_t*
 210 Kumu::FortunaRNG::FillRandom(Kumu::ByteString& Buffer)
 211 {
 212   FillRandom(Buffer.Data(), Buffer.Capacity());
 213   Buffer.Length(Buffer.Capacity());
 214   return Buffer.Data();
 215 }
 216
 217
 218 //
 219 // end KM_prng.cpp
 220 //