2 * Copyright (c) 2013-2014 Mark R V Murray
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 * in this position and unchanged.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 /* This implementation of Fortuna is based on the descriptions found in
29 * ISBN 0-471-22357-3 "Practical Cryptography" by Ferguson and Schneier
32 * The above book is superseded by ISBN 978-0-470-47424-2 "Cryptography
33 * Engineering" by Ferguson, Schneier and Kohno ("FS&K"). The code has
34 * not yet fully caught up with FS&K.
37 #include <sys/cdefs.h>
38 __FBSDID("$FreeBSD$");
41 #include "opt_random.h"
43 #include <sys/param.h>
44 #include <sys/kernel.h>
46 #include <sys/malloc.h>
47 #include <sys/mutex.h>
48 #include <sys/random.h>
49 #include <sys/sysctl.h>
50 #include <sys/systm.h>
52 #include <machine/cpu.h>
54 #include <crypto/rijndael/rijndael-api-fst.h>
55 #include <crypto/sha2/sha2.h>
57 #include <dev/random/hash.h>
58 #include <dev/random/randomdev.h>
59 #include <dev/random/random_adaptors.h>
60 #include <dev/random/random_harvestq.h>
61 #include <dev/random/uint128.h>
62 #include <dev/random/fortuna.h>
64 #include <sys/param.h>
65 #include <sys/types.h>
72 #include "unit_test.h"
74 #include <crypto/rijndael/rijndael-api-fst.h>
75 #include <crypto/sha2/sha2.h>
77 #include <dev/random/hash.h>
78 #include <dev/random/uint128.h>
79 #include <dev/random/fortuna.h>
82 #if !defined(RANDOM_YARROW) && !defined(RANDOM_FORTUNA)
84 #elif defined(RANDOM_YARROW) && defined(RANDOM_FORTUNA)
85 #error "Must define either RANDOM_YARROW or RANDOM_FORTUNA"
88 #if defined(RANDOM_FORTUNA)
91 #define MINPOOLSIZE 64
92 #define DEFPOOLSIZE 256
93 #define MAXPOOLSIZE 65536
95 /* This algorithm (and code) presumes that KEYSIZE is twice as large as BLOCKSIZE */
96 CTASSERT(BLOCKSIZE == sizeof(uint128_t));
97 CTASSERT(KEYSIZE == 2*BLOCKSIZE);
99 /* This is the beastie that needs protecting. It contains all of the
100 * state that we are excited about.
101 * Exactly one is instantiated.
103 static struct fortuna_state {
107 struct randomdev_hash hash;
115 uint8_t byte[BLOCKSIZE];
120 struct randomdev_key key;
125 /* Extras for the OS */
128 /* For use when 'pacing' the reseeds */
133 /* The random_reseed_mtx mutex protects seeding and polling/blocking. */
134 static mtx_t random_reseed_mtx;
136 static struct fortuna_start_cache {
137 uint8_t junk[PAGE_SIZE];
139 struct randomdev_hash hash;
140 } fortuna_start_cache;
143 static struct sysctl_ctx_list random_clist;
144 RANDOM_CHECK_UINT(minpoolsize, MINPOOLSIZE, MAXPOOLSIZE);
148 random_fortuna_init_alg(void)
152 struct sysctl_oid *random_fortuna_o;
155 memset(fortuna_start_cache.junk, 0, sizeof(fortuna_start_cache.junk));
156 fortuna_start_cache.length = 0U;
157 randomdev_hash_init(&fortuna_start_cache.hash);
159 /* Set up a lock for the reseed process */
161 mtx_init(&random_reseed_mtx, "reseed mutex", NULL, MTX_DEF);
163 mtx_init(&random_reseed_mtx, mtx_plain);
167 /* Fortuna parameters. Do not adjust these unless you have
168 * have a very good clue about what they do!
170 random_fortuna_o = SYSCTL_ADD_NODE(&random_clist,
171 SYSCTL_STATIC_CHILDREN(_kern_random),
172 OID_AUTO, "fortuna", CTLFLAG_RW, 0,
173 "Fortuna Parameters");
175 SYSCTL_ADD_PROC(&random_clist,
176 SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO,
177 "minpoolsize", CTLTYPE_UINT|CTLFLAG_RW,
178 &fortuna_state.minpoolsize, DEFPOOLSIZE,
179 random_check_uint_minpoolsize, "IU",
180 "Minimum pool size necessary to cause a reseed automatically");
182 fortuna_state.lasttime = 0U;
185 fortuna_state.minpoolsize = DEFPOOLSIZE;
187 /* F&S - InitializePRNG() */
189 /* F&S - P_i = \epsilon */
190 for (i = 0; i < NPOOLS; i++) {
191 randomdev_hash_init(&fortuna_state.pool[i].hash);
192 fortuna_state.pool[i].length = 0U;
195 /* F&S - ReseedCNT = 0 */
196 fortuna_state.reseedcount = 0U;
198 /* F&S - InitializeGenerator() */
201 uint128_clear(&fortuna_state.counter.whole);
204 memset(&fortuna_state.key, 0, sizeof(fortuna_state.key));
208 random_fortuna_deinit_alg(void)
211 mtx_destroy(&random_reseed_mtx);
212 memset(&fortuna_state, 0, sizeof(fortuna_state));
215 /* F&S - AddRandomEvent() */
216 /* Process a single stochastic event off the harvest queue */
218 random_fortuna_process_event(struct harvest_event *event)
222 /* We must be locked for all this as plenty of state gets messed with */
223 mtx_lock(&random_reseed_mtx);
225 /* Accumulate the event into the appropriate pool
226 * where each event carries the destination information
228 /* F&S - P_i = P_i|<harvested stuff> */
229 /* The hash_init and hash_finish are done in random_fortuna_read() below */
230 pl = event->he_destination % NPOOLS;
231 randomdev_hash_iterate(&fortuna_state.pool[pl].hash, event, sizeof(*event));
232 /* No point in counting above the outside maximum */
233 fortuna_state.pool[pl].length += event->he_size;
234 fortuna_state.pool[pl].length = MIN(fortuna_state.pool[pl].length, MAXPOOLSIZE);
236 /* Done with state-messing */
237 mtx_unlock(&random_reseed_mtx);
241 /* Reseed Mutex is held */
243 reseed(uint8_t *junk, u_int length)
245 struct randomdev_hash context;
246 uint8_t hash[KEYSIZE];
248 KASSERT(fortuna_state.minpoolsize > 0, ("random: Fortuna threshold = 0"));
250 mtx_assert(&random_reseed_mtx, MA_OWNED);
253 /* FS&K - K = Hd(K|s) where Hd(m) is H(H(0^512|m)) */
254 randomdev_hash_init(&context);
255 randomdev_hash_iterate(&context, zero_region, 512/8);
256 randomdev_hash_iterate(&context, &fortuna_state.key, sizeof(fortuna_state.key));
257 randomdev_hash_iterate(&context, junk, length);
258 randomdev_hash_finish(&context, hash);
259 randomdev_hash_init(&context);
260 randomdev_hash_iterate(&context, hash, KEYSIZE);
261 randomdev_hash_finish(&context, hash);
262 randomdev_encrypt_init(&fortuna_state.key, hash);
263 memset(hash, 0, sizeof(hash));
265 /* Unblock the device if it was blocked due to being unseeded */
266 if (uint128_is_zero(fortuna_state.counter.whole))
267 random_adaptor_unblock();
268 /* FS&K - C = C + 1 */
269 uint128_increment(&fortuna_state.counter.whole);
272 /* F&S - GenerateBlocks() */
273 /* Reseed Mutex is held, and buf points to a whole number of blocks. */
275 random_fortuna_genblocks(uint8_t *buf, u_int blockcount)
279 for (i = 0u; i < blockcount; i++) {
280 /* F&S - r = r|E(K,C) */
281 randomdev_encrypt(&fortuna_state.key, fortuna_state.counter.byte, buf, BLOCKSIZE);
284 /* F&S - C = C + 1 */
285 uint128_increment(&fortuna_state.counter.whole);
289 /* F&S - PseudoRandomData() */
290 /* Reseed Mutex is held, and buf points to a whole number of blocks. */
292 random_fortuna_genrandom(uint8_t *buf, u_int bytecount)
294 static uint8_t temp[BLOCKSIZE*(KEYSIZE/BLOCKSIZE)];
297 /* F&S - assert(n < 2^20) */
298 KASSERT((bytecount <= (1 << 20)), ("invalid single read request to fortuna of %d bytes", bytecount));
300 /* F&S - r = first-n-bytes(GenerateBlocks(ceil(n/16))) */
301 blockcount = bytecount / BLOCKSIZE;
302 random_fortuna_genblocks(buf, blockcount);
303 /* TODO: FIX! remove memcpy()! */
304 if (bytecount % BLOCKSIZE > 0) {
305 random_fortuna_genblocks(temp, 1);
306 memcpy(buf + (blockcount * BLOCKSIZE), temp, bytecount % BLOCKSIZE);
309 /* F&S - K = GenerateBlocks(2) */
310 random_fortuna_genblocks(temp, KEYSIZE/BLOCKSIZE);
311 randomdev_encrypt_init(&fortuna_state.key, temp);
312 memset(temp, 0, sizeof(temp));
315 /* F&S - RandomData() */
316 /* Used to return processed entropy from the PRNG */
317 /* The argument buf points to a whole number of blocks. */
319 random_fortuna_read(uint8_t *buf, u_int bytecount)
324 struct randomdev_hash context;
325 uint8_t s[NPOOLS*KEYSIZE], temp[KEYSIZE];
329 /* We must be locked for all this as plenty of state gets messed with */
330 mtx_lock(&random_reseed_mtx);
332 /* if buf == NULL and bytecount == 0 then this is the pre-read. */
333 /* if buf == NULL and bytecount != 0 then this is the post-read; ignore. */
335 if (bytecount == 0) {
336 if (fortuna_state.pool[0].length >= fortuna_state.minpoolsize
338 /* F&S - Use 'getsbinuptime()' to prevent reseed-spamming. */
339 && ((thistime = getsbinuptime()) - fortuna_state.lasttime > hz/10)
343 fortuna_state.lasttime = thistime;
347 /* F&S - ReseedCNT = ReseedCNT + 1 */
348 fortuna_state.reseedcount++;
349 /* s = \epsilon by default */
350 for (i = 0; i < NPOOLS; i++) {
351 /* F&S - if Divides(ReseedCnt, 2^i) ... */
352 if ((fortuna_state.reseedcount % (1 << i)) == 0U) {
353 seedlength += KEYSIZE;
354 /* F&S - temp = (P_i) */
355 randomdev_hash_finish(&fortuna_state.pool[i].hash, temp);
356 /* F&S - P_i = \epsilon */
357 randomdev_hash_init(&fortuna_state.pool[i].hash);
358 fortuna_state.pool[i].length = 0U;
359 /* F&S - s = s|H(temp) */
360 randomdev_hash_init(&context);
361 randomdev_hash_iterate(&context, temp, KEYSIZE);
362 randomdev_hash_finish(&context, s + i*KEYSIZE);
368 printf("random: active reseed: reseedcount [%d] ", fortuna_state.reseedcount);
369 for (i = 0; i < NPOOLS; i++)
370 printf(" %d", fortuna_state.pool[i].length);
374 reseed(s, seedlength);
377 memset(s, 0, seedlength);
379 memset(temp, 0, sizeof(temp));
380 memset(&context, 0, sizeof(context));
384 /* if buf != NULL do a regular read. */
386 random_fortuna_genrandom(buf, bytecount);
388 mtx_unlock(&random_reseed_mtx);
391 /* Internal function to hand external entropy to the PRNG */
393 random_fortuna_write(uint8_t *buf, u_int count)
395 uint8_t temp[KEYSIZE];
399 timestamp = get_cyclecount();
400 randomdev_hash_iterate(&fortuna_start_cache.hash, ×tamp, sizeof(timestamp));
401 randomdev_hash_iterate(&fortuna_start_cache.hash, buf, count);
402 timestamp = get_cyclecount();
403 randomdev_hash_iterate(&fortuna_start_cache.hash, ×tamp, sizeof(timestamp));
404 randomdev_hash_finish(&fortuna_start_cache.hash, temp);
405 for (i = 0; i < KEYSIZE; i++)
406 fortuna_start_cache.junk[(fortuna_start_cache.length + i)%PAGE_SIZE] ^= temp[i];
407 fortuna_start_cache.length += KEYSIZE;
410 printf("random: %s - ", __func__);
411 for (i = 0; i < KEYSIZE; i++)
412 printf("%02X", temp[i]);
416 memset(temp, 0, KEYSIZE);
418 /* We must be locked for all this as plenty of state gets messed with */
419 mtx_lock(&random_reseed_mtx);
421 randomdev_hash_init(&fortuna_start_cache.hash);
423 reseed(fortuna_start_cache.junk, MIN(PAGE_SIZE, fortuna_start_cache.length));
424 memset(fortuna_start_cache.junk, 0, sizeof(fortuna_start_cache.junk));
426 mtx_unlock(&random_reseed_mtx);
430 random_fortuna_reseed(void)
437 random_fortuna_seeded(void)
440 return (!uint128_is_zero(fortuna_state.counter.whole));
443 #endif /* RANDOM_FORTUNA */