projects/linux·blob master · refs

617 lines · 18.3 KiB

1/*
2 * DRBG: Deterministic Random Bits Generator
3 * Implementation of the HMAC SHA-512 DRBG from NIST SP800-90A
4 *
5 * Copyright Stephan Mueller <[email protected]>, 2014
6 * Copyright 2026 Google LLC
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, and the entire permission notice in its entirety,
13 * including the disclaimer of warranties.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. The name of the author may not be used to endorse or promote
18 * products derived from this software without specific prior
19 * written permission.
20 *
21 * ALTERNATIVELY, this product may be distributed under the terms of
22 * the GNU General Public License, in which case the provisions of the GPL are
23 * required INSTEAD OF the above restrictions. (This clause is
24 * necessary due to a potential bad interaction between the GPL and
25 * the restrictions contained in a BSD-style copyright.)
26 *
27 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
28 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
29 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
30 * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
31 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
32 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
33 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
34 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
35 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
36 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
37 * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
38 * DAMAGE.
39 *
40 * DRBG Usage
41 * ==========
42 * The SP 800-90A DRBG allows the user to specify a personalization string
43 * for initialization as well as an additional information string for each
44 * random number request. The following code fragments show how a caller
45 * uses the kernel crypto API to use the full functionality of the DRBG.
46 *
47 * Usage without any additional data
48 * ---------------------------------
49 * struct crypto_rng *drng;
50 * int err;
51 * char data[DATALEN];
52 *
53 * drng = crypto_alloc_rng(drng_name, 0, 0);
54 * err = crypto_rng_get_bytes(drng, data, DATALEN);
55 * crypto_free_rng(drng);
56 *
57 *
58 * Usage with personalization string during initialization
59 * -------------------------------------------------------
60 * struct crypto_rng *drng;
61 * int err;
62 * char data[DATALEN];
63 * char personalization[11] = "some-string";
64 *
65 * drng = crypto_alloc_rng(drng_name, 0, 0);
66 * // The reset completely re-initializes the DRBG with the provided
67 * // personalization string
68 * err = crypto_rng_reset(drng, personalization, strlen(personalization));
69 * err = crypto_rng_get_bytes(drng, data, DATALEN);
70 * crypto_free_rng(drng);
71 *
72 *
73 * Usage with additional information string during random number request
74 * ---------------------------------------------------------------------
75 * struct crypto_rng *drng;
76 * int err;
77 * char data[DATALEN];
78 * char addtl_string[11] = "some-string";
79 *
80 * drng = crypto_alloc_rng(drng_name, 0, 0);
81 * err = crypto_rng_generate(drng, addtl_string, strlen(addtl_string),
82 data, DATALEN);
83 * crypto_free_rng(drng);
84 *
85 *
86 * Usage with personalization and additional information strings
87 * -------------------------------------------------------------
88 * Just mix both scenarios above.
89 */
90
91#include <crypto/internal/rng.h>
92#include <crypto/sha2.h>
93#include <linux/fips.h>
94#include <linux/kernel.h>
95#include <linux/module.h>
96#include <linux/mutex.h>
97#include <linux/string_choices.h>
98#include <linux/unaligned.h>
99
100/* State length in bytes */
101#define DRBG_STATE_LEN SHA512_DIGEST_SIZE
102
103/* Security strength in bytes */
104#define DRBG_SEC_STRENGTH (SHA512_DIGEST_SIZE / 2)
105
106/*
107 * Maximum number of requests before reseeding is forced.
108 * SP800-90A allows this to be up to 2**48. We use a lower value.
109 */
110#define DRBG_MAX_REQUESTS 4096
111
112/*
113 * Maximum number of random bytes that can be requested at once.
114 * SP800-90A allows up to 2**19 bits, which is 2**16 bytes.
115 */
116#define DRBG_MAX_REQUEST_BYTES (1 << 16)
117
118/*
119 * Maximum length of additional info and personalization strings, in bytes.
120 * SP800-90A allows up to 2**35 bits, i.e. 2**32 bytes. We use 2**32 - 2 bytes
121 * so that the value never quite completely fills the range of a size_t,
122 * allowing the health check to verify that larger values are rejected.
123 */
124#define DRBG_MAX_ADDTL_BYTES (U32_MAX - 1)
125
126struct drbg_state {
127 struct mutex drbg_mutex; /* lock around DRBG */
128 u8 V[DRBG_STATE_LEN]; /* internal state -- 10.1.2.1 1a */
129 struct hmac_sha512_key key; /* current key -- 10.1.2.1 1b */
130 /* Number of RNG requests since last reseed -- 10.1.2.1 1c */
131 size_t reseed_ctr;
132 bool instantiated;
133 struct crypto_rng *jent;
134 const u8 *test_entropy;
135 size_t test_entropylen;
136};
137
138/******************************************************************
139 * HMAC DRBG functions
140 ******************************************************************/
141
142/* update function of HMAC DRBG as defined in 10.1.2.2 */
143static void drbg_hmac_update(struct drbg_state *drbg,
144 const u8 *data1, size_t data1_len,
145 const u8 *data2, size_t data2_len)
146{
147 struct hmac_sha512_ctx hmac_ctx;
148 u8 new_key[DRBG_STATE_LEN];
149
150 for (u8 i = 0; i < 2; i++) {
151 /* 10.1.2.2 step 1 and 4 -- concatenation and HMAC for key */
152 hmac_sha512_init(&hmac_ctx, &drbg->key);
153 hmac_sha512_update(&hmac_ctx, drbg->V, DRBG_STATE_LEN);
154 hmac_sha512_update(&hmac_ctx, &i, 1);
155 hmac_sha512_update(&hmac_ctx, data1, data1_len);
156 hmac_sha512_update(&hmac_ctx, data2, data2_len);
157 hmac_sha512_final(&hmac_ctx, new_key);
158 hmac_sha512_preparekey(&drbg->key, new_key, DRBG_STATE_LEN);
159
160 /* 10.1.2.2 step 2 and 5 -- HMAC for V */
161 hmac_sha512(&drbg->key, drbg->V, DRBG_STATE_LEN, drbg->V);
162
163 /* 10.1.2.2 step 3 */
164 if (data1_len == 0 && data2_len == 0)
165 break;
166 }
167 memzero_explicit(new_key, sizeof(new_key));
168}
169
170/* generate function of HMAC DRBG as defined in 10.1.2.5 */
171static void drbg_hmac_generate(struct drbg_state *drbg, u8 *out, size_t outlen,
172 const u8 *addtl1, size_t addtl1_len)
173{
174 u8 addtl2[32];
175 size_t addtl2_len = 0;
176
177 /*
178 * Append some bytes from get_random_bytes() to the additional input
179 * string, except when in test mode (as it would break the tests).
180 * Using a nonempty additional input string works around the forward
181 * secrecy bug in HMAC_DRBG described by Woodage & Shumow (2018)
182 * (https://eprint.iacr.org/2018/349.pdf). Filling the string with
183 * get_random_bytes() rather than a fixed value is safer still, and in
184 * particular makes random.c reseeds be immediately reflected.
185 *
186 * Note that there's no need to pull bytes from jitterentropy here too,
187 * since FIPS doesn't require any entropy in the additional input.
188 */
189 if (drbg->test_entropylen == 0) {
190 get_random_bytes(addtl2, sizeof(addtl2));
191 addtl2_len = sizeof(addtl2);
192 }
193
194 /* 10.1.2.5 step 2 */
195 if (addtl1_len || addtl2_len)
196 drbg_hmac_update(drbg, addtl1, addtl1_len, addtl2, addtl2_len);
197
198 while (outlen) {
199 size_t n = min(DRBG_STATE_LEN, outlen);
200
201 /* 10.1.2.5 step 4.1 */
202 hmac_sha512(&drbg->key, drbg->V, DRBG_STATE_LEN, drbg->V);
203
204 /* 10.1.2.5 step 4.2 */
205 memcpy(out, drbg->V, n);
206 out += n;
207 outlen -= n;
208 }
209
210 /* 10.1.2.5 step 6 */
211 drbg_hmac_update(drbg, addtl1, addtl1_len, addtl2, addtl2_len);
212
213 memzero_explicit(addtl2, sizeof(addtl2));
214}
215
216/*
217 * Seeding or reseeding of the DRBG
218 *
219 * @drbg: DRBG state struct
220 * @pers: personalization / additional information buffer
221 * @pers_len: length of @pers in bytes
222 * @reseed: false for initial seeding (instantiation), true for reseeding
223 *
224 * return:
225 * 0 on success
226 * error value otherwise
227 */
228static int drbg_seed(struct drbg_state *drbg, const u8 *pers, size_t pers_len,
229 bool reseed)
230 __must_hold(&drbg->drbg_mutex)
231{
232 int ret;
233 u8 entropy_buf[(32 + 16) * 2];
234 size_t entropylen;
235 const u8 *entropy;
236
237 /* 9.1 / 9.2 / 9.3.1 step 3 */
238 if (pers_len > DRBG_MAX_ADDTL_BYTES) {
239 pr_devel("DRBG: personalization string too long %zu\n",
240 pers_len);
241 return -EINVAL;
242 }
243
244 if (drbg->test_entropylen) {
245 entropy = drbg->test_entropy;
246 entropylen = drbg->test_entropylen;
247 pr_devel("DRBG: using test entropy\n");
248 } else {
249 /*
250 * Gather entropy equal to the security strength of the DRBG.
251 * With a derivation function, a nonce is required in addition
252 * to the entropy. A nonce must be at least 1/2 of the security
253 * strength of the DRBG in size. Thus, entropy + nonce is 3/2
254 * of the strength. The consideration of a nonce is only
255 * applicable during initial seeding.
256 */
257 entropy = entropy_buf;
258 if (!reseed)
259 entropylen = ((DRBG_SEC_STRENGTH + 1) / 2) * 3;
260 else
261 entropylen = DRBG_SEC_STRENGTH;
262 BUG_ON(entropylen * 2 > sizeof(entropy_buf));
263
264 /* Get seed from in-kernel /dev/urandom */
265 get_random_bytes(entropy_buf, entropylen);
266
267 if (!drbg->jent) {
268 pr_devel("DRBG: (re)seeding with %zu bytes of entropy\n",
269 entropylen);
270 } else {
271 /*
272 * Get seed from Jitter RNG, failures are
273 * fatal only in FIPS mode.
274 */
275 ret = crypto_rng_get_bytes(drbg->jent,
276 &entropy_buf[entropylen],
277 entropylen);
278 if (fips_enabled && ret) {
279 pr_devel("DRBG: jent failed with %d\n", ret);
280
281 /*
282 * Do not treat the transient failure of the
283 * Jitter RNG as an error that needs to be
284 * reported. The combined number of the
285 * maximum reseed threshold times the maximum
286 * number of Jitter RNG transient errors is
287 * less than the reseed threshold required by
288 * SP800-90A allowing us to treat the
289 * transient errors as such.
290 *
291 * However, we mandate that at least the first
292 * seeding operation must succeed with the
293 * Jitter RNG.
294 */
295 if (!reseed || ret != -EAGAIN)
296 goto out;
297 }
298
299 entropylen *= 2;
300 pr_devel("DRBG: (re)seeding with %zu bytes of entropy\n",
301 entropylen);
302 }
303 }
304
305 if (pers_len)
306 pr_devel("DRBG: using personalization string\n");
307
308 drbg_hmac_update(drbg, entropy, entropylen, pers, pers_len);
309 drbg->reseed_ctr = 1;
310 ret = 0;
311out:
312 memzero_explicit(entropy_buf, sizeof(entropy_buf));
313
314 return ret;
315}
316
317/*
318 * Generate random bytes from an SP800-90A DRBG.
319 *
320 * @drbg DRBG state handle
321 * @out Buffer where to store the random bytes
322 * @outlen Number of random bytes to generate
323 * @addtl Optional additional input that is mixed into state
324 * @addtl_len Length of @addtl in bytes, may be 0
325 *
326 * return: 0 when all bytes are generated; < 0 in case of an error
327 */
328static int drbg_generate(struct drbg_state *drbg, u8 *out, size_t outlen,
329 const u8 *addtl, size_t addtl_len)
330 __must_hold(&drbg->drbg_mutex)
331{
332 int err;
333
334 if (!drbg->instantiated) {
335 pr_devel("DRBG: not yet instantiated\n");
336 return -EINVAL;
337 }
338 if (out == NULL || outlen == 0) {
339 pr_devel("DRBG: no output buffer provided\n");
340 return -EINVAL;
341 }
342 if (addtl == NULL && addtl_len != 0) {
343 pr_devel("DRBG: wrong format of additional information\n");
344 return -EINVAL;
345 }
346
347 /* 9.3.1 step 2 */
348 if (outlen > DRBG_MAX_REQUEST_BYTES) {
349 pr_devel("DRBG: request length is too long %zu\n", outlen);
350 return -EINVAL;
351 }
352
353 /* 9.3.1 step 3 is implicit with the chosen DRBG */
354
355 /* 9.3.1 step 4 */
356 if (addtl_len > DRBG_MAX_ADDTL_BYTES) {
357 pr_devel("DRBG: additional information string too long %zu\n",
358 addtl_len);
359 return -EINVAL;
360 }
361 /* 9.3.1 step 5 is implicit with the chosen DRBG */
362
363 /*
364 * 9.3.1 step 6 and 9 supplemented by 9.3.2 step c is implemented
365 * here. The spec is a bit convoluted here, we make it simpler.
366 *
367 * We no longer try to detect when random.c has reseeded itself and call
368 * drbg_seed() then too, since drbg_hmac_generate() adds bytes from
369 * random.c to the additional input, which is a de facto reseed anyway.
370 */
371 if (drbg->reseed_ctr > DRBG_MAX_REQUESTS) {
372 pr_devel("DRBG: reseeding before generation\n");
373 /* 9.3.1 steps 7.1 through 7.3 */
374 err = drbg_seed(drbg, addtl, addtl_len, true);
375 if (err)
376 return err;
377 /* 9.3.1 step 7.4 */
378 addtl = NULL;
379 addtl_len = 0;
380 }
381
382 /* 9.3.1 step 8 and 10 */
383 drbg_hmac_generate(drbg, out, outlen, addtl, addtl_len);
384
385 /* 10.1.2.5 step 7 */
386 drbg->reseed_ctr++;
387
388 /*
389 * Section 11.3.3 requires to re-perform self tests after some
390 * generated random numbers. The chosen value after which self
391 * test is performed is arbitrary, but it should be reasonable.
392 * However, we do not perform the self tests because of the following
393 * reasons: it is mathematically impossible that the initial self tests
394 * were successfully and the following are not. If the initial would
395 * pass and the following would not, the kernel integrity is violated.
396 * In this case, the entire kernel operation is questionable and it
397 * is unlikely that the integrity violation only affects the
398 * correct operation of the DRBG.
399 */
400
401 return 0;
402}
403
404/***************************************************************
405 * Kernel crypto API interface to DRBG
406 ***************************************************************/
407
408static int drbg_kcapi_init(struct crypto_tfm *tfm)
409{
410 struct drbg_state *drbg = crypto_tfm_ctx(tfm);
411
412 mutex_init(&drbg->drbg_mutex);
413
414 return 0;
415}
416
417/* Set test entropy in the DRBG. */
418static void drbg_kcapi_set_entropy(struct crypto_rng *tfm,
419 const u8 *data, unsigned int len)
420{
421 struct drbg_state *drbg = crypto_rng_ctx(tfm);
422
423 mutex_lock(&drbg->drbg_mutex);
424 drbg->test_entropy = data;
425 drbg->test_entropylen = len;
426 mutex_unlock(&drbg->drbg_mutex);
427}
428
429/* Seed (i.e. instantiate) or re-seed the DRBG. */
430static int drbg_kcapi_seed(struct crypto_rng *tfm,
431 const u8 *pers, unsigned int pers_len)
432{
433 static const u8 initial_key[DRBG_STATE_LEN]; /* all zeroes */
434 struct drbg_state *drbg = crypto_rng_ctx(tfm);
435 int ret;
436
437 pr_devel("DRBG: Initializing DRBG\n");
438 guard(mutex)(&drbg->drbg_mutex);
439
440 if (drbg->instantiated)
441 return drbg_seed(drbg, pers, pers_len, /* reseed= */ true);
442
443 /* 9.1 step 1 is implicit with the selected DRBG type */
444
445 /*
446 * 9.1 step 2 is implicit, as this implementation doesn't support
447 * prediction resistance
448 */
449
450 /* 9.1 step 4 is implicit in DRBG_SEC_STRENGTH */
451
452 memset(drbg->V, 1, DRBG_STATE_LEN);
453 hmac_sha512_preparekey(&drbg->key, initial_key, DRBG_STATE_LEN);
454
455 /* Allocate jitterentropy_rng if not in test mode. */
456 if (drbg->test_entropylen == 0) {
457 drbg->jent = crypto_alloc_rng("jitterentropy_rng", 0, 0);
458 if (IS_ERR(drbg->jent)) {
459 ret = PTR_ERR(drbg->jent);
460 drbg->jent = NULL;
461 if (fips_enabled)
462 return ret;
463 pr_info("DRBG: Continuing without Jitter RNG\n");
464 }
465 }
466
467 ret = drbg_seed(drbg, pers, pers_len, /* reseed= */ false);
468 if (ret) {
469 crypto_free_rng(drbg->jent);
470 drbg->jent = NULL;
471 return ret;
472 }
473 drbg->instantiated = true;
474 return 0;
475}
476
477/*
478 * Generate random numbers invoked by the kernel crypto API:
479 *
480 * src is additional input supplied to the RNG.
481 * slen is the length of src.
482 * dst is the output buffer where random data is to be stored.
483 * dlen is the length of dst.
484 */
485static int drbg_kcapi_generate(struct crypto_rng *tfm,
486 const u8 *src, unsigned int slen,
487 u8 *dst, unsigned int dlen)
488{
489 struct drbg_state *drbg = crypto_rng_ctx(tfm);
490
491 /*
492 * Break the request into multiple requests if needed, to avoid
493 * exceeding the maximum request length of the core algorithm.
494 */
495 do {
496 unsigned int n = min(dlen, DRBG_MAX_REQUEST_BYTES);
497 int err;
498
499 mutex_lock(&drbg->drbg_mutex);
500 err = drbg_generate(drbg, dst, n, src, slen);
501 mutex_unlock(&drbg->drbg_mutex);
502 if (err < 0)
503 return err;
504 dst += n;
505 dlen -= n;
506 } while (dlen);
507 return 0;
508}
509
510/* Uninstantiate the DRBG. */
511static void drbg_kcapi_exit(struct crypto_tfm *tfm)
512{
513 struct drbg_state *drbg = crypto_tfm_ctx(tfm);
514
515 crypto_free_rng(drbg->jent);
516 memzero_explicit(drbg, sizeof(*drbg));
517}
518
519/*
520 * Tests as defined in 11.3.2 in addition to the cipher tests: testing
521 * of the error handling.
522 *
523 * Note: testing of failing seed source as defined in 11.3.2 is not applicable
524 * as seed source of get_random_bytes does not fail.
525 *
526 * Note 2: There is no sensible way of testing the reseed counter
527 * enforcement, so skip it.
528 */
529static inline int __init drbg_healthcheck_sanity(void)
530{
531#define OUTBUFLEN 16
532 u8 buf[OUTBUFLEN];
533 struct drbg_state *drbg = NULL;
534 int ret;
535
536 /* only perform test in FIPS mode */
537 if (!fips_enabled)
538 return 0;
539
540 drbg = kzalloc_obj(struct drbg_state);
541 if (!drbg)
542 return -ENOMEM;
543
544 guard(mutex_init)(&drbg->drbg_mutex);
545 drbg->instantiated = true;
546
547 /*
548 * if the following tests fail, it is likely that there is a buffer
549 * overflow as buf is much smaller than the requested or provided
550 * string lengths -- in case the error handling does not succeed
551 * we may get an OOPS. And we want to get an OOPS as this is a
552 * grave bug.
553 */
554
555 /* overflow addtllen with additional info string */
556 ret = drbg_generate(drbg, buf, OUTBUFLEN, buf,
557 DRBG_MAX_ADDTL_BYTES + 1);
558 BUG_ON(ret == 0);
559 /* overflow max_bits */
560 ret = drbg_generate(drbg, buf, DRBG_MAX_REQUEST_BYTES + 1, NULL, 0);
561 BUG_ON(ret == 0);
562
563 /* overflow max addtllen with personalization string */
564 ret = drbg_seed(drbg, buf, DRBG_MAX_ADDTL_BYTES + 1, false);
565 BUG_ON(ret == 0);
566 /* all tests passed */
567
568 pr_devel("DRBG: Sanity tests for failure code paths successfully "
569 "completed\n");
570
571 kfree(drbg);
572 return 0;
573}
574
575static struct rng_alg drbg_alg = {
576 .base.cra_name = "stdrng",
577 .base.cra_driver_name = "drbg_nopr_hmac_sha512",
578 .base.cra_priority = 201,
579 .base.cra_ctxsize = sizeof(struct drbg_state),
580 .base.cra_module = THIS_MODULE,
581 .base.cra_init = drbg_kcapi_init,
582 .set_ent = drbg_kcapi_set_entropy,
583 .seed = drbg_kcapi_seed,
584 .generate = drbg_kcapi_generate,
585 .base.cra_exit = drbg_kcapi_exit,
586};
587
588static int __init drbg_init(void)
589{
590 int ret;
591
592 ret = drbg_healthcheck_sanity();
593 if (ret)
594 return ret;
595
596 /*
597 * In FIPS mode, boost the algorithm priority to ensure that when users
598 * request "stdrng", they really get the algorithm from here.
599 */
600 if (fips_enabled)
601 drbg_alg.base.cra_priority += 2000;
602
603 return crypto_register_rng(&drbg_alg);
604}
605
606static void __exit drbg_exit(void)
607{
608 crypto_unregister_rng(&drbg_alg);
609}
610
611module_init(drbg_init);
612module_exit(drbg_exit);
613MODULE_LICENSE("GPL");
614MODULE_AUTHOR("Stephan Mueller <[email protected]>");
615MODULE_DESCRIPTION("NIST SP800-90A Deterministic Random Bit Generator (DRBG)");
616MODULE_ALIAS_CRYPTO("stdrng");
617MODULE_ALIAS_CRYPTO("drbg_nopr_hmac_sha512");