1 /*-
2 * Copyright (c) 2017 W. Dean Freeman
3 * Copyright (c) 2013-2015 Mark R V Murray
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer
11 * in this position and unchanged.
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 *
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 */
28
29 /*
30 * This implementation of Fortuna is based on the descriptions found in
31 * ISBN 978-0-470-47424-2 "Cryptography Engineering" by Ferguson, Schneier
32 * and Kohno ("FS&K").
33 */
34
35 #include <sys/cdefs.h>
36 __FBSDID("$FreeBSD$");
37
38 #include <sys/limits.h>
39
40 #ifdef _KERNEL
41 #include <sys/param.h>
42 #include <sys/kernel.h>
43 #include <sys/lock.h>
44 #include <sys/malloc.h>
45 #include <sys/mutex.h>
46 #include <sys/random.h>
47 #include <sys/sdt.h>
48 #include <sys/sysctl.h>
49 #include <sys/systm.h>
50
51 #include <machine/cpu.h>
52
53 #include <crypto/rijndael/rijndael-api-fst.h>
54 #include <crypto/sha2/sha256.h>
55
56 #include <dev/random/hash.h>
57 #include <dev/random/randomdev.h>
58 #include <dev/random/random_harvestq.h>
59 #include <dev/random/uint128.h>
60 #include <dev/random/fortuna.h>
61 #else /* !_KERNEL */
62 #include <sys/param.h>
63 #include <inttypes.h>
64 #include <stdbool.h>
65 #include <stdio.h>
66 #include <stdlib.h>
67 #include <string.h>
68 #include <threads.h>
69
70 #include "unit_test.h"
71
72 #include <crypto/rijndael/rijndael-api-fst.h>
73 #include <crypto/sha2/sha256.h>
74
75 #include <dev/random/hash.h>
76 #include <dev/random/randomdev.h>
77 #include <dev/random/uint128.h>
78 #include <dev/random/fortuna.h>
79 #endif /* _KERNEL */
80
81 /* Defined in FS&K */
82 #define RANDOM_FORTUNA_NPOOLS 32 /* The number of accumulation pools */
83 #define RANDOM_FORTUNA_DEFPOOLSIZE 64 /* The default pool size/length for a (re)seed */
84 #define RANDOM_FORTUNA_MAX_READ (1 << 20) /* Max bytes in a single read */
85
86 /*
87 * The allowable range of RANDOM_FORTUNA_DEFPOOLSIZE. The default value is above.
88 * Making RANDOM_FORTUNA_DEFPOOLSIZE too large will mean a long time between reseeds,
89 * and too small may compromise initial security but get faster reseeds.
90 */
91 #define RANDOM_FORTUNA_MINPOOLSIZE 16
92 #define RANDOM_FORTUNA_MAXPOOLSIZE INT_MAX
93 CTASSERT(RANDOM_FORTUNA_MINPOOLSIZE <= RANDOM_FORTUNA_DEFPOOLSIZE);
94 CTASSERT(RANDOM_FORTUNA_DEFPOOLSIZE <= RANDOM_FORTUNA_MAXPOOLSIZE);
95
96 /* This algorithm (and code) presumes that RANDOM_KEYSIZE is twice as large as RANDOM_BLOCKSIZE */
97 CTASSERT(RANDOM_BLOCKSIZE == sizeof(uint128_t));
98 CTASSERT(RANDOM_KEYSIZE == 2*RANDOM_BLOCKSIZE);
99
100 /* Probes for dtrace(1) */
101 #ifdef _KERNEL
102 SDT_PROVIDER_DECLARE(random);
103 SDT_PROVIDER_DEFINE(random);
104 SDT_PROBE_DEFINE2(random, fortuna, event_processor, debug, "u_int", "struct fs_pool *");
105 #endif /* _KERNEL */
106
107 /*
108 * This is the beastie that needs protecting. It contains all of the
109 * state that we are excited about. Exactly one is instantiated.
110 */
111 static struct fortuna_state {
112 struct fs_pool { /* P_i */
113 u_int fsp_length; /* Only the first one is used by Fortuna */
114 struct randomdev_hash fsp_hash;
115 } fs_pool[RANDOM_FORTUNA_NPOOLS];
116 u_int fs_reseedcount; /* ReseedCnt */
117 uint128_t fs_counter; /* C */
118 struct randomdev_key fs_key; /* K */
119 u_int fs_minpoolsize; /* Extras */
120 /* Extras for the OS */
121 #ifdef _KERNEL
122 /* For use when 'pacing' the reseeds */
123 sbintime_t fs_lasttime;
124 #endif
125 /* Reseed lock */
126 mtx_t fs_mtx;
127 } fortuna_state;
128
129 #ifdef _KERNEL
130 static struct sysctl_ctx_list random_clist;
131 RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE);
132 #else
133 static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE];
134 #endif
135
136 static void random_fortuna_pre_read(void);
137 static void random_fortuna_read(uint8_t *, u_int);
138 static bool random_fortuna_seeded(void);
139 static void random_fortuna_process_event(struct harvest_event *);
140 static void random_fortuna_init_alg(void *);
141 static void random_fortuna_deinit_alg(void *);
142
143 static void random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount);
144
145 struct random_algorithm random_alg_context = {
146 .ra_ident = "Fortuna",
147 .ra_init_alg = random_fortuna_init_alg,
148 .ra_deinit_alg = random_fortuna_deinit_alg,
149 .ra_pre_read = random_fortuna_pre_read,
150 .ra_read = random_fortuna_read,
151 .ra_seeded = random_fortuna_seeded,
152 .ra_event_processor = random_fortuna_process_event,
153 .ra_poolcount = RANDOM_FORTUNA_NPOOLS,
154 };
155
156 /* ARGSUSED */
157 static void
random_fortuna_init_alg(void * unused __unused)158 random_fortuna_init_alg(void *unused __unused)
159 {
160 int i;
161 #ifdef _KERNEL
162 struct sysctl_oid *random_fortuna_o;
163 #endif
164
165 RANDOM_RESEED_INIT_LOCK();
166 /*
167 * Fortuna parameters. Do not adjust these unless you have
168 * have a very good clue about what they do!
169 */
170 fortuna_state.fs_minpoolsize = RANDOM_FORTUNA_DEFPOOLSIZE;
171 #ifdef _KERNEL
172 fortuna_state.fs_lasttime = 0;
173 random_fortuna_o = SYSCTL_ADD_NODE(&random_clist,
174 SYSCTL_STATIC_CHILDREN(_kern_random),
175 OID_AUTO, "fortuna", CTLFLAG_RW, 0,
176 "Fortuna Parameters");
177 SYSCTL_ADD_PROC(&random_clist,
178 SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO,
179 "minpoolsize", CTLTYPE_UINT | CTLFLAG_RWTUN,
180 &fortuna_state.fs_minpoolsize, RANDOM_FORTUNA_DEFPOOLSIZE,
181 random_check_uint_fs_minpoolsize, "IU",
182 "Minimum pool size necessary to cause a reseed");
183 KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0 at startup"));
184 #endif
185
186 /*-
187 * FS&K - InitializePRNG()
188 * - P_i = \epsilon
189 * - ReseedCNT = 0
190 */
191 for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) {
192 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash);
193 fortuna_state.fs_pool[i].fsp_length = 0;
194 }
195 fortuna_state.fs_reseedcount = 0;
196 /*-
197 * FS&K - InitializeGenerator()
198 * - C = 0
199 * - K = 0
200 */
201 fortuna_state.fs_counter = UINT128_ZERO;
202 explicit_bzero(&fortuna_state.fs_key, sizeof(fortuna_state.fs_key));
203 }
204
205 /* ARGSUSED */
206 static void
random_fortuna_deinit_alg(void * unused __unused)207 random_fortuna_deinit_alg(void *unused __unused)
208 {
209
210 RANDOM_RESEED_DEINIT_LOCK();
211 explicit_bzero(&fortuna_state, sizeof(fortuna_state));
212 #ifdef _KERNEL
213 sysctl_ctx_free(&random_clist);
214 #endif
215 }
216
217 /*-
218 * FS&K - AddRandomEvent()
219 * Process a single stochastic event off the harvest queue
220 */
221 static void
random_fortuna_process_event(struct harvest_event * event)222 random_fortuna_process_event(struct harvest_event *event)
223 {
224 u_int pl;
225
226 RANDOM_RESEED_LOCK();
227 /*-
228 * FS&K - P_i = P_i|<harvested stuff>
229 * Accumulate the event into the appropriate pool
230 * where each event carries the destination information.
231 *
232 * The hash_init() and hash_finish() calls are done in
233 * random_fortuna_pre_read().
234 *
235 * We must be locked against pool state modification which can happen
236 * during accumulation/reseeding and reading/regating.
237 */
238 pl = event->he_destination % RANDOM_FORTUNA_NPOOLS;
239 /*
240 * We ignore low entropy static/counter fields towards the end of the
241 * he_event structure in order to increase measurable entropy when
242 * conducting SP800-90B entropy analysis measurements of seed material
243 * fed into PRNG.
244 * -- wdf
245 */
246 KASSERT(event->he_size <= sizeof(event->he_entropy),
247 ("%s: event->he_size: %hhu > sizeof(event->he_entropy): %zu\n",
248 __func__, event->he_size, sizeof(event->he_entropy)));
249 randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash,
250 &event->he_somecounter, sizeof(event->he_somecounter));
251 randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash,
252 event->he_entropy, event->he_size);
253
254 /*-
255 * Don't wrap the length. This is a "saturating" add.
256 * XXX: FIX!!: We don't actually need lengths for anything but fs_pool[0],
257 * but it's been useful debugging to see them all.
258 */
259 fortuna_state.fs_pool[pl].fsp_length = MIN(RANDOM_FORTUNA_MAXPOOLSIZE,
260 fortuna_state.fs_pool[pl].fsp_length +
261 sizeof(event->he_somecounter) + event->he_size);
262 explicit_bzero(event, sizeof(*event));
263 RANDOM_RESEED_UNLOCK();
264 }
265
266 /*-
267 * FS&K - Reseed()
268 * This introduces new key material into the output generator.
269 * Additionally it increments the output generator's counter
270 * variable C. When C > 0, the output generator is seeded and
271 * will deliver output.
272 * The entropy_data buffer passed is a very specific size; the
273 * product of RANDOM_FORTUNA_NPOOLS and RANDOM_KEYSIZE.
274 */
275 static void
random_fortuna_reseed_internal(uint32_t * entropy_data,u_int blockcount)276 random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount)
277 {
278 struct randomdev_hash context;
279 uint8_t hash[RANDOM_KEYSIZE];
280
281 RANDOM_RESEED_ASSERT_LOCK_OWNED();
282 /*-
283 * FS&K - K = Hd(K|s) where Hd(m) is H(H(0^512|m))
284 * - C = C + 1
285 */
286 randomdev_hash_init(&context);
287 randomdev_hash_iterate(&context, zero_region, RANDOM_ZERO_BLOCKSIZE);
288 randomdev_hash_iterate(&context, &fortuna_state.fs_key, sizeof(fortuna_state.fs_key));
289 randomdev_hash_iterate(&context, entropy_data, RANDOM_KEYSIZE*blockcount);
290 randomdev_hash_finish(&context, hash);
291 randomdev_hash_init(&context);
292 randomdev_hash_iterate(&context, hash, RANDOM_KEYSIZE);
293 randomdev_hash_finish(&context, hash);
294 randomdev_encrypt_init(&fortuna_state.fs_key, hash);
295 explicit_bzero(hash, sizeof(hash));
296 /* Unblock the device if this is the first time we are reseeding. */
297 if (uint128_is_zero(fortuna_state.fs_counter))
298 randomdev_unblock();
299 uint128_increment(&fortuna_state.fs_counter);
300 }
301
302 /*-
303 * FS&K - GenerateBlocks()
304 * Generate a number of complete blocks of random output.
305 */
306 static __inline void
random_fortuna_genblocks(uint8_t * buf,u_int blockcount)307 random_fortuna_genblocks(uint8_t *buf, u_int blockcount)
308 {
309 u_int i;
310
311 RANDOM_RESEED_ASSERT_LOCK_OWNED();
312 for (i = 0; i < blockcount; i++) {
313 /*-
314 * FS&K - r = r|E(K,C)
315 * - C = C + 1
316 */
317 randomdev_encrypt(&fortuna_state.fs_key, &fortuna_state.fs_counter, buf, RANDOM_BLOCKSIZE);
318 buf += RANDOM_BLOCKSIZE;
319 uint128_increment(&fortuna_state.fs_counter);
320 }
321 }
322
323 /*-
324 * FS&K - PseudoRandomData()
325 * This generates no more than 2^20 bytes of data, and cleans up its
326 * internal state when finished. It is assumed that a whole number of
327 * blocks are available for writing; any excess generated will be
328 * ignored.
329 */
330 static __inline void
random_fortuna_genrandom(uint8_t * buf,u_int bytecount)331 random_fortuna_genrandom(uint8_t *buf, u_int bytecount)
332 {
333 static uint8_t temp[RANDOM_BLOCKSIZE*(RANDOM_KEYS_PER_BLOCK)];
334 u_int blockcount;
335
336 RANDOM_RESEED_ASSERT_LOCK_OWNED();
337 /*-
338 * FS&K - assert(n < 2^20 (== 1 MB)
339 * - r = first-n-bytes(GenerateBlocks(ceil(n/16)))
340 * - K = GenerateBlocks(2)
341 */
342 KASSERT((bytecount <= RANDOM_FORTUNA_MAX_READ), ("invalid single read request to Fortuna of %d bytes", bytecount));
343 blockcount = howmany(bytecount, RANDOM_BLOCKSIZE);
344 random_fortuna_genblocks(buf, blockcount);
345 random_fortuna_genblocks(temp, RANDOM_KEYS_PER_BLOCK);
346 randomdev_encrypt_init(&fortuna_state.fs_key, temp);
347 explicit_bzero(temp, sizeof(temp));
348 }
349
350 /*-
351 * FS&K - RandomData() (Part 1)
352 * Used to return processed entropy from the PRNG. There is a pre_read
353 * required to be present (but it can be a stub) in order to allow
354 * specific actions at the begin of the read.
355 */
356 void
random_fortuna_pre_read(void)357 random_fortuna_pre_read(void)
358 {
359 #ifdef _KERNEL
360 sbintime_t now;
361 #endif
362 struct randomdev_hash context;
363 uint32_t s[RANDOM_FORTUNA_NPOOLS*RANDOM_KEYSIZE_WORDS];
364 uint8_t temp[RANDOM_KEYSIZE];
365 u_int i;
366
367 KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0"));
368 #ifdef _KERNEL
369 /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */
370 now = getsbinuptime();
371 #endif
372 RANDOM_RESEED_LOCK();
373
374 if (fortuna_state.fs_pool[0].fsp_length >= fortuna_state.fs_minpoolsize
375 #ifdef _KERNEL
376 /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */
377 && (now - fortuna_state.fs_lasttime > SBT_1S/10)
378 #endif
379 ) {
380 #ifdef _KERNEL
381 fortuna_state.fs_lasttime = now;
382 #endif
383
384 /* FS&K - ReseedCNT = ReseedCNT + 1 */
385 fortuna_state.fs_reseedcount++;
386 /* s = \epsilon at start */
387 for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) {
388 /* FS&K - if Divides(ReseedCnt, 2^i) ... */
389 if ((fortuna_state.fs_reseedcount % (1 << i)) == 0) {
390 /*-
391 * FS&K - temp = (P_i)
392 * - P_i = \epsilon
393 * - s = s|H(temp)
394 */
395 randomdev_hash_finish(&fortuna_state.fs_pool[i].fsp_hash, temp);
396 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash);
397 fortuna_state.fs_pool[i].fsp_length = 0;
398 randomdev_hash_init(&context);
399 randomdev_hash_iterate(&context, temp, RANDOM_KEYSIZE);
400 randomdev_hash_finish(&context, s + i*RANDOM_KEYSIZE_WORDS);
401 } else
402 break;
403 }
404 #ifdef _KERNEL
405 SDT_PROBE2(random, fortuna, event_processor, debug, fortuna_state.fs_reseedcount, fortuna_state.fs_pool);
406 #endif
407 /* FS&K */
408 random_fortuna_reseed_internal(s, i < RANDOM_FORTUNA_NPOOLS ? i + 1 : RANDOM_FORTUNA_NPOOLS);
409 /* Clean up and secure */
410 explicit_bzero(s, sizeof(s));
411 explicit_bzero(temp, sizeof(temp));
412 explicit_bzero(&context, sizeof(context));
413 }
414 RANDOM_RESEED_UNLOCK();
415 }
416
417 /*-
418 * FS&K - RandomData() (Part 2)
419 * Main read from Fortuna, continued. May be called multiple times after
420 * the random_fortuna_pre_read() above.
421 * The supplied buf MUST be a multiple of RANDOM_BLOCKSIZE in size.
422 * Lots of code presumes this for efficiency, both here and in other
423 * routines. You are NOT allowed to break this!
424 */
425 void
random_fortuna_read(uint8_t * buf,u_int bytecount)426 random_fortuna_read(uint8_t *buf, u_int bytecount)
427 {
428
429 KASSERT((bytecount % RANDOM_BLOCKSIZE) == 0, ("%s(): bytecount (= %d) must be a multiple of %d", __func__, bytecount, RANDOM_BLOCKSIZE ));
430 RANDOM_RESEED_LOCK();
431 random_fortuna_genrandom(buf, bytecount);
432 RANDOM_RESEED_UNLOCK();
433 }
434
435 bool
random_fortuna_seeded(void)436 random_fortuna_seeded(void)
437 {
438
439 return (!uint128_is_zero(fortuna_state.fs_counter));
440 }
441