2 Copyright (c) 2006-2009, John Hurst
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
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.
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.
29 \brief Fortuna pseudo-random number generator
37 #include <openssl/aes.h>
38 #include <openssl/sha.h>
39 #include <openssl/bn.h>
45 # include <wincrypt.h>
47 # include <KM_fileio.h>
48 const char* DEV_URANDOM = "/dev/urandom";
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;
58 // internal implementation class
61 KM_NO_COPY_CONSTRUCT(h__RNG);
65 byte_t m_ctr_buf[RNG_BLOCK_SIZE];
70 memset(m_ctr_buf, 0, RNG_BLOCK_SIZE);
71 byte_t rng_key[RNG_KEY_SIZE];
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);
78 HCRYPTPROV hProvider = 0;
79 CryptAcquireContext(&hProvider, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
80 CryptGenRandom(hProvider, RNG_KEY_SIZE, rng_key);
82 // on POSIX systems we simply read some seed from /dev/urandom
85 Result_t result = URandom.OpenRead(DEV_URANDOM);
87 if ( KM_SUCCESS(result) )
90 result = URandom.Read(rng_key, RNG_KEY_SIZE, &read_count);
93 if ( KM_FAILURE(result) )
94 DefaultLogSink().Error("Error opening random device: %s\n", DEV_URANDOM);
97 } // end AutoMutex context
104 set_key(const byte_t* key_fodder)
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);
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;
122 fill_rand(byte_t* buf, ui32_t len)
124 assert(len <= MAX_SEQUENCE_LEN);
125 ui32_t gen_count = 0;
126 AutoMutex Lock(m_Lock);
128 while ( gen_count + RNG_BLOCK_SIZE <= len )
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;
135 if ( len != gen_count ) // partial count needed?
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);
145 static h__RNG* s_RNG = 0;
148 //------------------------------------------------------------------------------------------
150 // Fortuna public interface
152 Kumu::FortunaRNG::FortunaRNG()
158 Kumu::FortunaRNG::~FortunaRNG() {}
162 Kumu::FortunaRNG::FillRandom(byte_t* buf, ui32_t len)
169 // 2^20 bytes max per seeding, use 2^19 to save
170 // room for generating reseed values
171 ui32_t gen_size = xmin(len, MAX_SEQUENCE_LEN);
172 s_RNG->fill_rand(buf, gen_size);
176 // re-seed the generator
177 byte_t rng_key[RNG_KEY_SIZE];
178 s_RNG->fill_rand(rng_key, RNG_KEY_SIZE);
179 s_RNG->set_key(rng_key);
187 Kumu::FortunaRNG::FillRandom(Kumu::ByteString& Buffer)
189 FillRandom(Buffer.Data(), Buffer.Capacity());
190 Buffer.Length(Buffer.Capacity());
191 return Buffer.Data();
194 //------------------------------------------------------------------------------------------
197 // FIPS 186-2 Sec. 3.1 as modified by Change 1, section entitled "General Purpose Random Number Generation"
199 Kumu::Gen_FIPS_186_Value(const byte_t* key, ui32_t key_size, byte_t* out_buf, ui32_t out_buf_len)
201 byte_t sha_buf[SHA_DIGEST_LENGTH];
202 const ui32_t key_buf_len = 64;
203 byte_t key_buf[key_buf_len];
205 BN_CTX* ctx1 = BN_CTX_new(); // used by BN_* functions
209 memset(key_buf, 0, key_buf_len);
210 memcpy(key_buf, key, xmin<ui32_t>(key_buf_len, key_size));
212 // create the 2^160 constant
213 BIGNUM c_2powb, c_2, c_160;
214 BN_init(&c_2powb); BN_init(&c_2); BN_init(&c_160);
215 BN_set_word(&c_2, 2);
216 BN_set_word(&c_160, 160);
217 BN_exp(&c_2powb, &c_2, &c_160, ctx1);
221 // step c -- x = G(t,xkey)
223 SHA1_Update(&SHA, key_buf, key_buf_len);
224 ui32_t* buf_p = (ui32_t*)sha_buf;
225 *buf_p++ = KM_i32_BE(SHA.h0);
226 *buf_p++ = KM_i32_BE(SHA.h1);
227 *buf_p++ = KM_i32_BE(SHA.h2);
228 *buf_p++ = KM_i32_BE(SHA.h3);
229 *buf_p++ = KM_i32_BE(SHA.h4);
230 memcpy(out_buf, sha_buf, xmin<ui32_t>(out_buf_len, SHA_DIGEST_LENGTH));
232 if ( out_buf_len <= SHA_DIGEST_LENGTH )
235 out_buf_len -= SHA_DIGEST_LENGTH;
236 out_buf += SHA_DIGEST_LENGTH;
239 BIGNUM xkey1, xkey_buf, x0;
240 BN_init(&xkey1); BN_init(&xkey_buf); BN_init(&x0);
242 BN_bin2bn(key_buf, SHA_DIGEST_LENGTH, &xkey1);
243 BN_bin2bn(sha_buf, SHA_DIGEST_LENGTH, &x0);
244 BN_add_word(&xkey1, 1); // xkey += 1
245 BN_add(&xkey_buf, &xkey1, &x0); // xkey += x
246 BN_mod(&xkey1, &xkey_buf, &c_2powb, ctx1); // xkey = xkey mod (2^160)
248 ui32_t bn_buf_len = BN_num_bytes(&xkey1);
249 assert(bn_buf_len < SHA_DIGEST_LENGTH+1);
250 memset(key_buf, 0, key_buf_len);
251 BN_bn2bin(&xkey1, key_buf);