1 /* -*- c-basic-offset: 2; -*- */
4 Copyright (c) 2006-2009, John Hurst
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions
10 1. Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
12 2. Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in the
14 documentation and/or other materials provided with the distribution.
15 3. The name of the author may not be used to endorse or promote products
16 derived from this software without specific prior written permission.
18 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 \version $Id: KM_prng.cpp,v 1.9 2011/06/14 23:38:33 jhurst Exp $
31 \brief Fortuna pseudo-random number generator
39 #include <openssl/aes.h>
40 #include <openssl/sha.h>
41 #include <openssl/bn.h>
47 # include <wincrypt.h>
49 # include <KM_fileio.h>
50 const char* DEV_URANDOM = "/dev/urandom";
53 const ui32_t RNG_KEY_SIZE = 512UL;
54 const ui32_t RNG_KEY_SIZE_BITS = 256UL;
55 const ui32_t RNG_BLOCK_SIZE = 16UL;
56 const ui32_t MAX_SEQUENCE_LEN = 0x00040000UL;
59 // internal implementation class
62 KM_NO_COPY_CONSTRUCT(h__RNG);
66 byte_t m_ctr_buf[RNG_BLOCK_SIZE];
68 unsigned int m_libdcp_test_rng_state;
72 memset(m_ctr_buf, 0, RNG_BLOCK_SIZE);
73 byte_t rng_key[RNG_KEY_SIZE];
75 { // this block scopes the following AutoMutex so that it will be
76 // released before the call to set_key() below.
77 AutoMutex Lock(m_Lock);
80 HCRYPTPROV hProvider = 0;
81 CryptAcquireContext(&hProvider, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
82 CryptGenRandom(hProvider, RNG_KEY_SIZE, rng_key);
84 // on POSIX systems we simply read some seed from /dev/urandom
87 Result_t result = URandom.OpenRead(DEV_URANDOM);
89 if ( KM_SUCCESS(result) )
92 result = URandom.Read(rng_key, RNG_KEY_SIZE, &read_count);
95 if ( KM_FAILURE(result) )
96 DefaultLogSink().Error("Error opening random device: %s\n", DEV_URANDOM);
99 } // end AutoMutex context
110 set_key(const byte_t* key_fodder)
117 SHA1_Update(&SHA, (byte_t*)&m_Context, sizeof(m_Context));
118 SHA1_Update(&SHA, key_fodder, RNG_KEY_SIZE);
119 SHA1_Final(sha_buf, &SHA);
121 AutoMutex Lock(m_Lock);
122 AES_set_encrypt_key(sha_buf, RNG_KEY_SIZE_BITS, &m_Context);
123 *(ui32_t*)(m_ctr_buf + 12) = 1;
128 fill_rand(byte_t* buf, ui32_t len)
130 assert(len <= MAX_SEQUENCE_LEN);
131 ui32_t gen_count = 0;
132 AutoMutex Lock(m_Lock);
134 while ( gen_count + RNG_BLOCK_SIZE <= len )
136 AES_encrypt(m_ctr_buf, buf + gen_count, &m_Context);
137 *(ui32_t*)(m_ctr_buf + 12) += 1;
138 gen_count += RNG_BLOCK_SIZE;
141 if ( len != gen_count ) // partial count needed?
143 byte_t tmp[RNG_BLOCK_SIZE];
144 AES_encrypt(m_ctr_buf, tmp, &m_Context);
145 memcpy(buf + gen_count, tmp, len - gen_count);
151 for (unsigned int i = 0; i < len; ++i)
152 buf[i] = rand_r(&m_libdcp_test_rng_state);
156 #ifdef LIBDCP_WINDOWS
164 m_libdcp_test_rng_state = 1;
170 static h__RNG* s_RNG = 0;
173 //------------------------------------------------------------------------------------------
175 // Fortuna public interface
177 Kumu::FortunaRNG::FortunaRNG()
183 Kumu::FortunaRNG::~FortunaRNG() {}
187 Kumu::FortunaRNG::FillRandom(byte_t* buf, ui32_t len)
191 const byte_t* front_of_buffer = buf;
195 // 2^20 bytes max per seeding, use 2^19 to save
196 // room for generating reseed values
197 ui32_t gen_size = xmin(len, MAX_SEQUENCE_LEN);
198 s_RNG->fill_rand(buf, gen_size);
202 // re-seed the generator
203 byte_t rng_key[RNG_KEY_SIZE];
204 s_RNG->fill_rand(rng_key, RNG_KEY_SIZE);
205 s_RNG->set_key(rng_key);
208 return front_of_buffer;
213 Kumu::FortunaRNG::FillRandom(Kumu::ByteString& Buffer)
215 FillRandom(Buffer.Data(), Buffer.Capacity());
216 Buffer.Length(Buffer.Capacity());
217 return Buffer.Data();
222 Kumu::FortunaRNG::Reset()
228 //------------------------------------------------------------------------------------------
231 // FIPS 186-2 Sec. 3.1 as modified by Change 1, section entitled "General Purpose Random Number Generation"
233 Kumu::Gen_FIPS_186_Value(const byte_t* key, ui32_t key_size, byte_t* out_buf, ui32_t out_buf_len)
235 byte_t sha_buf[SHA_DIGEST_LENGTH];
236 ui32_t const xkey_len = 64; // 512/8
237 byte_t xkey[xkey_len];
238 BN_CTX* ctx1 = BN_CTX_new(); // used by BN_* functions
241 if ( key_size > xkey_len )
242 DefaultLogSink().Warn("Key too large for FIPS 186 seed, truncating to 64 bytes.\n");
245 memset(xkey, 0, xkey_len);
246 memcpy(xkey, key, xmin<ui32_t>(key_size, xkey_len));
248 if ( key_size < SHA_DIGEST_LENGTH )
249 key_size = SHA_DIGEST_LENGTH; // pad short key ( b < 160 )
251 // create the 2^b constant
252 BIGNUM c_2powb, c_2, c_b;
253 BN_init(&c_2powb); BN_init(&c_2); BN_init(&c_b);
254 BN_set_word(&c_2, 2);
255 BN_set_word(&c_b, key_size * 8);
256 BN_exp(&c_2powb, &c_2, &c_b, ctx1);
262 // step c -- x = G(t,xkey)
263 SHA1_Init(&SHA); // set t
264 SHA1_Update(&SHA, xkey, xkey_len);
266 ui32_t* buf_p = (ui32_t*)sha_buf;
267 *buf_p++ = KM_i32_BE(SHA.h0);
268 *buf_p++ = KM_i32_BE(SHA.h1);
269 *buf_p++ = KM_i32_BE(SHA.h2);
270 *buf_p++ = KM_i32_BE(SHA.h3);
271 *buf_p++ = KM_i32_BE(SHA.h4);
272 memcpy(out_buf, sha_buf, xmin<ui32_t>(out_buf_len, SHA_DIGEST_LENGTH));
274 if ( out_buf_len <= SHA_DIGEST_LENGTH )
277 out_buf_len -= SHA_DIGEST_LENGTH;
278 out_buf += SHA_DIGEST_LENGTH;
280 // step d -- XKEY = (1 + XKEY + x) mod 2^b
281 BIGNUM bn_tmp, bn_xkey, bn_x_n;
282 BN_init(&bn_tmp); BN_init(&bn_xkey); BN_init(&bn_x_n);
284 BN_bin2bn(xkey, key_size, &bn_xkey);
285 BN_bin2bn(sha_buf, SHA_DIGEST_LENGTH, &bn_x_n);
286 BN_add_word(&bn_xkey, 1); // xkey += 1
287 BN_add(&bn_tmp, &bn_xkey, &bn_x_n); // xkey += x
288 BN_mod(&bn_xkey, &bn_tmp, &c_2powb, ctx1); // xkey = xkey mod (2^b)
290 memset(xkey, 0, xkey_len);
291 ui32_t bn_buf_len = BN_num_bytes(&bn_xkey);
292 ui32_t idx = ( bn_buf_len < key_size ) ? key_size - bn_buf_len : 0;
293 BN_bn2bin(&bn_xkey, &xkey[idx]);