2 * Copyright (c) 2013-2015 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.
29 * This implementation of Fortuna is based on the descriptions found in
30 * ISBN 978-0-470-47424-2 "Cryptography Engineering" by Ferguson, Schneier
34 #include <sys/cdefs.h>
35 __FBSDID("$FreeBSD$");
37 #include <sys/limits.h>
40 #include <sys/param.h>
41 #include <sys/kernel.h>
43 #include <sys/malloc.h>
44 #include <sys/mutex.h>
45 #include <sys/random.h>
47 #include <sys/sysctl.h>
48 #include <sys/systm.h>
50 #include <machine/cpu.h>
52 #include <crypto/rijndael/rijndael-api-fst.h>
53 #include <crypto/sha2/sha256.h>
55 #include <dev/random/hash.h>
56 #include <dev/random/randomdev.h>
57 #include <dev/random/random_harvestq.h>
58 #include <dev/random/uint128.h>
59 #include <dev/random/fortuna.h>
68 #include "unit_test.h"
70 #include <crypto/rijndael/rijndael-api-fst.h>
71 #include <crypto/sha2/sha256.h>
73 #include <dev/random/hash.h>
74 #include <dev/random/randomdev.h>
75 #include <dev/random/uint128.h>
76 #include <dev/random/fortuna.h>
80 #define RANDOM_FORTUNA_NPOOLS 32 /* The number of accumulation pools */
81 #define RANDOM_FORTUNA_DEFPOOLSIZE 64 /* The default pool size/length for a (re)seed */
82 #define RANDOM_FORTUNA_MAX_READ (1 << 20) /* Max bytes in a single read */
85 * The allowable range of RANDOM_FORTUNA_DEFPOOLSIZE. The default value is above.
86 * Making RANDOM_FORTUNA_DEFPOOLSIZE too large will mean a long time between reseeds,
87 * and too small may compromise initial security but get faster reseeds.
89 #define RANDOM_FORTUNA_MINPOOLSIZE 16
90 #define RANDOM_FORTUNA_MAXPOOLSIZE UINT_MAX
91 CTASSERT(RANDOM_FORTUNA_MINPOOLSIZE <= RANDOM_FORTUNA_DEFPOOLSIZE);
92 CTASSERT(RANDOM_FORTUNA_DEFPOOLSIZE <= RANDOM_FORTUNA_MAXPOOLSIZE);
94 /* This algorithm (and code) presumes that RANDOM_KEYSIZE is twice as large as RANDOM_BLOCKSIZE */
95 CTASSERT(RANDOM_BLOCKSIZE == sizeof(uint128_t));
96 CTASSERT(RANDOM_KEYSIZE == 2*RANDOM_BLOCKSIZE);
98 /* Probes for dtrace(1) */
99 SDT_PROVIDER_DECLARE(random);
100 SDT_PROVIDER_DEFINE(random);
101 SDT_PROBE_DEFINE2(random, fortuna, event_processor, debug, "u_int", "struct fs_pool *");
104 * This is the beastie that needs protecting. It contains all of the
105 * state that we are excited about. Exactly one is instantiated.
107 static struct fortuna_state {
108 struct fs_pool { /* P_i */
109 u_int fsp_length; /* Only the first one is used by Fortuna */
110 struct randomdev_hash fsp_hash;
111 } fs_pool[RANDOM_FORTUNA_NPOOLS];
112 u_int fs_reseedcount; /* ReseedCnt */
113 uint128_t fs_counter; /* C */
114 struct randomdev_key fs_key; /* K */
115 u_int fs_minpoolsize; /* Extras */
116 /* Extras for the OS */
118 /* For use when 'pacing' the reseeds */
119 sbintime_t fs_lasttime;
126 static struct sysctl_ctx_list random_clist;
127 RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE);
129 static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE];
132 static void random_fortuna_pre_read(void);
133 static void random_fortuna_read(uint8_t *, u_int);
134 static bool random_fortuna_seeded(void);
135 static void random_fortuna_process_event(struct harvest_event *);
136 static void random_fortuna_init_alg(void *);
137 static void random_fortuna_deinit_alg(void *);
139 static void random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount);
141 struct random_algorithm random_alg_context = {
142 .ra_ident = "Fortuna",
143 .ra_init_alg = random_fortuna_init_alg,
144 .ra_deinit_alg = random_fortuna_deinit_alg,
145 .ra_pre_read = random_fortuna_pre_read,
146 .ra_read = random_fortuna_read,
147 .ra_seeded = random_fortuna_seeded,
148 .ra_event_processor = random_fortuna_process_event,
149 .ra_poolcount = RANDOM_FORTUNA_NPOOLS,
154 random_fortuna_init_alg(void *unused __unused)
158 struct sysctl_oid *random_fortuna_o;
161 RANDOM_RESEED_INIT_LOCK();
163 * Fortuna parameters. Do not adjust these unless you have
164 * have a very good clue about what they do!
166 fortuna_state.fs_minpoolsize = RANDOM_FORTUNA_DEFPOOLSIZE;
168 fortuna_state.fs_lasttime = 0;
169 random_fortuna_o = SYSCTL_ADD_NODE(&random_clist,
170 SYSCTL_STATIC_CHILDREN(_kern_random),
171 OID_AUTO, "fortuna", CTLFLAG_RW, 0,
172 "Fortuna Parameters");
173 SYSCTL_ADD_PROC(&random_clist,
174 SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO,
175 "minpoolsize", CTLTYPE_UINT | CTLFLAG_RWTUN,
176 &fortuna_state.fs_minpoolsize, RANDOM_FORTUNA_DEFPOOLSIZE,
177 random_check_uint_fs_minpoolsize, "IU",
178 "Minimum pool size necessary to cause a reseed");
179 KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0 at startup"));
183 * FS&K - InitializePRNG()
187 for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) {
188 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash);
189 fortuna_state.fs_pool[i].fsp_length = 0;
191 fortuna_state.fs_reseedcount = 0;
193 * FS&K - InitializeGenerator()
197 fortuna_state.fs_counter = UINT128_ZERO;
198 explicit_bzero(&fortuna_state.fs_key, sizeof(fortuna_state.fs_key));
203 random_fortuna_deinit_alg(void *unused __unused)
206 RANDOM_RESEED_DEINIT_LOCK();
207 explicit_bzero(&fortuna_state, sizeof(fortuna_state));
209 sysctl_ctx_free(&random_clist);
214 * FS&K - AddRandomEvent()
215 * Process a single stochastic event off the harvest queue
218 random_fortuna_process_event(struct harvest_event *event)
222 RANDOM_RESEED_LOCK();
224 * FS&K - P_i = P_i|<harvested stuff>
225 * Accumulate the event into the appropriate pool
226 * where each event carries the destination information.
228 * The hash_init() and hash_finish() calls are done in
229 * random_fortuna_pre_read().
231 * We must be locked against pool state modification which can happen
232 * during accumulation/reseeding and reading/regating.
234 pl = event->he_destination % RANDOM_FORTUNA_NPOOLS;
235 randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash, event, sizeof(*event));
237 * Don't wrap the length. Doing the the hard way so as not to wrap at MAXUINT.
238 * This is a "saturating" add.
239 * XXX: FIX!!: We don't actually need lengths for anything but fs_pool[0],
240 * but it's been useful debugging to see them all.
242 if (RANDOM_FORTUNA_MAXPOOLSIZE - fortuna_state.fs_pool[pl].fsp_length > event->he_size)
243 fortuna_state.fs_pool[pl].fsp_length += event->he_size;
245 fortuna_state.fs_pool[pl].fsp_length = RANDOM_FORTUNA_MAXPOOLSIZE;
246 explicit_bzero(event, sizeof(*event));
247 RANDOM_RESEED_UNLOCK();
252 * This introduces new key material into the output generator.
253 * Additionally it increments the output generator's counter
254 * variable C. When C > 0, the output generator is seeded and
255 * will deliver output.
256 * The entropy_data buffer passed is a very specific size; the
257 * product of RANDOM_FORTUNA_NPOOLS and RANDOM_KEYSIZE.
260 random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount)
262 struct randomdev_hash context;
263 uint8_t hash[RANDOM_KEYSIZE];
265 RANDOM_RESEED_ASSERT_LOCK_OWNED();
267 * FS&K - K = Hd(K|s) where Hd(m) is H(H(0^512|m))
270 randomdev_hash_init(&context);
271 randomdev_hash_iterate(&context, zero_region, RANDOM_ZERO_BLOCKSIZE);
272 randomdev_hash_iterate(&context, &fortuna_state.fs_key, sizeof(fortuna_state.fs_key));
273 randomdev_hash_iterate(&context, entropy_data, RANDOM_KEYSIZE*blockcount);
274 randomdev_hash_finish(&context, hash);
275 randomdev_hash_init(&context);
276 randomdev_hash_iterate(&context, hash, RANDOM_KEYSIZE);
277 randomdev_hash_finish(&context, hash);
278 randomdev_encrypt_init(&fortuna_state.fs_key, hash);
279 explicit_bzero(hash, sizeof(hash));
280 /* Unblock the device if this is the first time we are reseeding. */
281 if (uint128_is_zero(fortuna_state.fs_counter))
283 uint128_increment(&fortuna_state.fs_counter);
287 * FS&K - GenerateBlocks()
288 * Generate a number of complete blocks of random output.
291 random_fortuna_genblocks(uint8_t *buf, u_int blockcount)
295 RANDOM_RESEED_ASSERT_LOCK_OWNED();
296 for (i = 0; i < blockcount; i++) {
298 * FS&K - r = r|E(K,C)
301 randomdev_encrypt(&fortuna_state.fs_key, &fortuna_state.fs_counter, buf, RANDOM_BLOCKSIZE);
302 buf += RANDOM_BLOCKSIZE;
303 uint128_increment(&fortuna_state.fs_counter);
308 * FS&K - PseudoRandomData()
309 * This generates no more than 2^20 bytes of data, and cleans up its
310 * internal state when finished. It is assumed that a whole number of
311 * blocks are available for writing; any excess generated will be
315 random_fortuna_genrandom(uint8_t *buf, u_int bytecount)
317 static uint8_t temp[RANDOM_BLOCKSIZE*(RANDOM_KEYS_PER_BLOCK)];
320 RANDOM_RESEED_ASSERT_LOCK_OWNED();
322 * FS&K - assert(n < 2^20 (== 1 MB)
323 * - r = first-n-bytes(GenerateBlocks(ceil(n/16)))
324 * - K = GenerateBlocks(2)
326 KASSERT((bytecount <= RANDOM_FORTUNA_MAX_READ), ("invalid single read request to Fortuna of %d bytes", bytecount));
327 blockcount = howmany(bytecount, RANDOM_BLOCKSIZE);
328 random_fortuna_genblocks(buf, blockcount);
329 random_fortuna_genblocks(temp, RANDOM_KEYS_PER_BLOCK);
330 randomdev_encrypt_init(&fortuna_state.fs_key, temp);
331 explicit_bzero(temp, sizeof(temp));
335 * FS&K - RandomData() (Part 1)
336 * Used to return processed entropy from the PRNG. There is a pre_read
337 * required to be present (but it can be a stub) in order to allow
338 * specific actions at the begin of the read.
341 random_fortuna_pre_read(void)
346 struct randomdev_hash context;
347 uint32_t s[RANDOM_FORTUNA_NPOOLS*RANDOM_KEYSIZE_WORDS];
348 uint8_t temp[RANDOM_KEYSIZE];
351 KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0"));
353 /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */
354 now = getsbinuptime();
356 RANDOM_RESEED_LOCK();
358 if (fortuna_state.fs_pool[0].fsp_length >= fortuna_state.fs_minpoolsize
360 /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */
361 && (now - fortuna_state.fs_lasttime > hz/10)
365 fortuna_state.fs_lasttime = now;
368 /* FS&K - ReseedCNT = ReseedCNT + 1 */
369 fortuna_state.fs_reseedcount++;
370 /* s = \epsilon at start */
371 for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) {
372 /* FS&K - if Divides(ReseedCnt, 2^i) ... */
373 if ((fortuna_state.fs_reseedcount % (1 << i)) == 0) {
375 * FS&K - temp = (P_i)
379 randomdev_hash_finish(&fortuna_state.fs_pool[i].fsp_hash, temp);
380 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash);
381 fortuna_state.fs_pool[i].fsp_length = 0;
382 randomdev_hash_init(&context);
383 randomdev_hash_iterate(&context, temp, RANDOM_KEYSIZE);
384 randomdev_hash_finish(&context, s + i*RANDOM_KEYSIZE_WORDS);
388 SDT_PROBE2(random, fortuna, event_processor, debug, fortuna_state.fs_reseedcount, fortuna_state.fs_pool);
390 random_fortuna_reseed_internal(s, i < RANDOM_FORTUNA_NPOOLS ? i + 1 : RANDOM_FORTUNA_NPOOLS);
391 /* Clean up and secure */
392 explicit_bzero(s, sizeof(s));
393 explicit_bzero(temp, sizeof(temp));
394 explicit_bzero(&context, sizeof(context));
396 RANDOM_RESEED_UNLOCK();
400 * FS&K - RandomData() (Part 2)
401 * Main read from Fortuna, continued. May be called multiple times after
402 * the random_fortuna_pre_read() above.
403 * The supplied buf MUST be a multiple of RANDOM_BLOCKSIZE in size.
404 * Lots of code presumes this for efficiency, both here and in other
405 * routines. You are NOT allowed to break this!
408 random_fortuna_read(uint8_t *buf, u_int bytecount)
411 KASSERT((bytecount % RANDOM_BLOCKSIZE) == 0, ("%s(): bytecount (= %d) must be a multiple of %d", __func__, bytecount, RANDOM_BLOCKSIZE ));
412 RANDOM_RESEED_LOCK();
413 random_fortuna_genrandom(buf, bytecount);
414 RANDOM_RESEED_UNLOCK();
418 random_fortuna_seeded(void)
421 return (!uint128_is_zero(fortuna_state.fs_counter));