3
* ***** BEGIN LICENSE BLOCK *****
4
* Version: MPL 1.1/GPL 2.0/LGPL 2.1
6
* The contents of this file are subject to the Mozilla Public License Version
7
* 1.1 (the "License"); you may not use this file except in compliance with
8
* the License. You may obtain a copy of the License at
9
* http://www.mozilla.org/MPL/
11
* Software distributed under the License is distributed on an "AS IS" basis,
12
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13
* for the specific language governing rights and limitations under the
16
* The Original Code is the Netscape security libraries.
18
* The Initial Developer of the Original Code is
19
* Netscape Communications Corporation.
20
* Portions created by the Initial Developer are Copyright (C) 1994-2000
21
* the Initial Developer. All Rights Reserved.
25
* Alternatively, the contents of this file may be used under the terms of
26
* either the GNU General Public License Version 2 or later (the "GPL"), or
27
* the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
28
* in which case the provisions of the GPL or the LGPL are applicable instead
29
* of those above. If you wish to allow use of your version of this file only
30
* under the terms of either the GPL or the LGPL, and not to allow others to
31
* use your version of this file under the terms of the MPL, indicate your
32
* decision by deleting the provisions above and replace them with the notice
33
* and other provisions required by the GPL or the LGPL. If you do not delete
34
* the provisions above, a recipient may use your version of this file under
35
* the terms of any one of the MPL, the GPL or the LGPL.
37
* ***** END LICENSE BLOCK ***** */
38
/* $Id: prng_fips1861.c,v 1.22.2.4 2006/10/13 17:02:58 wtchang%redhat.com Exp $ */
50
#include "secrng.h" /* for RNG_GetNoise() */
54
* The minimum amount of seed data required before the generator will
56
* Note that this is a measure of the number of bytes sent to
57
* RNG_RandomUpdate, not the actual amount of entropy present in the
58
* generator. Naturally, it is impossible to know (at this level) just
59
* how much entropy is present in the provided seed data. A bare minimum
60
* of entropy would be 20 bytes, so by requiring 1K this code is making
61
* the tacit assumption that at least 1 byte of pure entropy is provided
62
* with every 8 bytes supplied to RNG_RandomUpdate. The reality of this
63
* assumption is left up to the caller.
65
#define MIN_SEED_COUNT 1024
68
* Steps taken from Algorithm 1 of FIPS 186-2 Change Notice 1
72
* According to FIPS 186-2, 160 <= b <= 512.
73
* For our purposes, we will assume b == 160,
74
* 256, or 512 (the output size of SHA-1,
75
* SHA-256, or SHA-512).
78
#define BSIZE (FIPS_B / PR_BITS_PER_BYTE)
79
#if BSIZE != SHA256_LENGTH
80
#error "this file requires that BSIZE and SHA256_LENGTH be equal"
83
/* Output size of the G function */
85
#define GSIZE (FIPS_G / PR_BITS_PER_BYTE)
88
* Add two b-bit numbers represented as arrays of BSIZE bytes.
89
* The numbers are big-endian, MSB first, so addition is done
90
* from the end of the buffer to the beginning.
92
#define ADD_B_BIT_PLUS_CARRY(dest, add1, add2, cy) \
94
for (k=BSIZE-1; k>=0; --k) { \
95
carry += add1[k] + add2[k]; \
96
dest[k] = (PRUint8)carry; \
100
#define ADD_B_BIT_2(dest, add1, add2) \
101
ADD_B_BIT_PLUS_CARRY(dest, add1, add2, 0)
105
* FIPS requires result from Step 3.3 to be reduced mod q when generating
106
* random numbers for DSA.
108
* Input: w, 2*GSIZE bytes
109
* q, DSA_SUBPRIME_LEN bytes
110
* Output: xj, DSA_SUBPRIME_LEN bytes
113
FIPS186Change_ReduceModQForDSA(const unsigned char *w,
114
const unsigned char *q,
119
SECStatus rv = SECSuccess;
121
/* Initialize MPI integers. */
125
CHECK_MPI_OK( mp_init(&W) );
126
CHECK_MPI_OK( mp_init(&Q) );
127
CHECK_MPI_OK( mp_init(&Xj) );
129
* Convert input arguments into MPI integers.
131
CHECK_MPI_OK( mp_read_unsigned_octets(&W, w, 2*GSIZE) );
132
CHECK_MPI_OK( mp_read_unsigned_octets(&Q, q, DSA_SUBPRIME_LEN) );
134
* Algorithm 1 of FIPS 186-2 Change Notice 1, Step 3.3
136
* xj = (w0 || w1) mod q
138
CHECK_MPI_OK( mp_mod(&W, &Q, &Xj) );
139
CHECK_MPI_OK( mp_to_fixlen_octets(&Xj, xj, DSA_SUBPRIME_LEN) );
145
MP_TO_SEC_ERROR(err);
152
* Specialized SHA1-like function. This function appends zeroes to a
153
* single input block and runs a single instance of the compression function,
154
* as specified in FIPS 186-2 appendix 3.3.
157
RNG_UpdateAndEnd_FIPS186_2(SHA1Context *ctx,
158
unsigned char *input, unsigned int inputLen,
159
unsigned char *hashout, unsigned int *pDigestLen,
160
unsigned int maxDigestLen);
165
struct RNGContextStr {
166
PRUint8 XKEY[BSIZE]; /* Seed for next SHA iteration */
167
PRUint8 Xj[2*GSIZE]; /* Output from previous operation. */
168
PZLock *lock; /* Lock to serialize access to global rng */
169
PRUint8 avail; /* # bytes of output available, [0...2*GSIZE] */
170
PRUint32 seedCount; /* number of seed bytes given to generator */
171
PRBool isValid; /* false if RNG reaches an invalid state */
173
typedef struct RNGContextStr RNGContext;
174
static RNGContext *globalrng = NULL;
175
static RNGContext theGlobalRng;
178
* Clean up the global RNG context
183
unsigned char inputhash[BSIZE];
186
/* destroy context lock */
187
PZ_DestroyLock(globalrng->lock);
189
/* zero global RNG context except for XKEY to preserve entropy */
190
rv = SHA256_HashBuf(inputhash, globalrng->XKEY, BSIZE);
191
PORT_Assert(SECSuccess == rv);
192
memset(globalrng, 0, sizeof(*globalrng));
193
memcpy(globalrng->XKEY, inputhash, BSIZE);
199
* The core of Algorithm 1 of FIPS 186-2 Change Notice 1,
200
* separated from alg_fips186_2_cn_1 as a standalone function
201
* for FIPS algorithm testing.
204
* XKEY [input/output]: the state of the RNG (seed-key)
205
* XSEEDj [input]: optional user input (seed)
206
* x_j [output]: output of the RNG
209
* This function usually returns SECSuccess. The only reason
210
* this function returns SECFailure is that XSEEDj equals
211
* XKEY, including the intermediate XKEY value between the two
212
* iterations. (This test is actually a FIPS 140-2 requirement
213
* and not required for FIPS algorithm testing, but it is too
214
* hard to separate from this function.) If this function fails,
215
* XKEY is not updated, but some data may have been written to
216
* x_j, which should be ignored.
219
FIPS186Change_GenerateX(unsigned char *XKEY, const unsigned char *XSEEDj,
222
/* SHA1 context for G(t, XVAL) function */
224
/* XKEY for iteration 1 */
225
PRUint8 XKEY_1[BSIZE];
226
const PRUint8 *XKEY_old;
228
/* input to hash function */
230
/* used by ADD_B_BIT macros */
232
/* store the output of G(t, XVAL) in the rightmost GSIZE bytes */
236
SECStatus rv = SECSuccess;
239
/* zero the leftmost bytes so we can pass it to ADD_B_BIT_PLUS_CARRY */
240
memset(w_i, 0, BSIZE - GSIZE);
243
* <Step 2> Initialize t, taken care of in SHA-1 (same initial values)
245
* <Step 3.1> XSEEDj is optional user input
247
for (i = 0; i < 2; i++) {
248
/* only update XKEY when both iterations have been completed */
250
/* for iteration 0 */
254
/* for iteration 1 */
259
* <Step 3.2a> XVAL = (XKEY + XSEEDj) mod 2^b
260
* :always reduced mod 2^b, since storing as b-bit value
264
if (memcmp(XKEY_old, XSEEDj, BSIZE) == 0) {
265
/* Should we add the error code SEC_ERROR_BAD_RNG_SEED? */
266
PORT_SetError(SEC_ERROR_INVALID_ARGS);
270
ADD_B_BIT_2(XVAL, XKEY_old, XSEEDj);
273
memcpy(XVAL, XKEY_old, BSIZE);
276
* <Step 3.2b> Wi = G(t, XVAL)
277
* :FIPS 186-2 specifies a different padding than the SHA1 180-1
278
* :specification, this function is implemented in
279
* :RNG_UpdateAndEnd_FIPS186_2 below.
282
RNG_UpdateAndEnd_FIPS186_2(&sha1cx, XVAL, BSIZE,
283
&w_i[BSIZE - GSIZE], &len, GSIZE);
285
* <Step 3.2c> XKEY = (1 + XKEY + Wi) mod 2^b
286
* :always reduced mod 2^b, since storing as 160-bit value
288
ADD_B_BIT_PLUS_CARRY(XKEY_new, XKEY_old, w_i, 1);
290
* <Step 3.3> Xj = (W0 || W1)
292
memcpy(&x_j[i*GSIZE], &w_i[BSIZE - GSIZE], GSIZE);
297
memset(&w_i[BSIZE - GSIZE], 0, GSIZE);
298
memset(XVAL, 0, BSIZE);
299
memset(XKEY_1, 0, BSIZE);
304
* Implementation of Algorithm 1 of FIPS 186-2 Change Notice 1,
305
* hereinafter called alg_cn_1(). It is assumed a lock for the global
306
* rng context has already been acquired.
307
* Calling this function with XSEEDj == NULL is equivalent to saying there
308
* is no optional user input, which is further equivalent to saying that
309
* the optional user input is 0.
312
alg_fips186_2_cn_1(RNGContext *rng, const unsigned char *XSEEDj)
314
/* store a copy of the output to compare with the previous output */
315
PRUint8 x_j[2*GSIZE];
319
/* RNG has alread entered an invalid state. */
320
PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
323
rv = FIPS186Change_GenerateX(rng->XKEY, XSEEDj, x_j);
324
if (rv != SECSuccess) {
327
/* [FIPS 140-2] verify output does not match previous output */
328
if (memcmp(x_j, rng->Xj, 2*GSIZE) == 0) {
329
/* failed FIPS 140-2 continuous RNG test. RNG now invalid. */
330
rng->isValid = PR_FALSE;
331
PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
335
/* Xj is the output */
336
memcpy(rng->Xj, x_j, 2*GSIZE);
337
/* Always have a full buffer after executing alg_cn_1() */
338
rng->avail = 2*GSIZE;
342
memset(x_j, 0, 2*GSIZE);
346
/* Use NSPR to prevent RNG_RNGInit from being called from separate
347
* threads, creating a race condition.
349
static const PRCallOnceType pristineCallOnce;
350
static PRCallOnceType coRNGInit;
351
static PRStatus rng_init(void)
353
unsigned char bytes[SYSTEM_RNG_SEED_COUNT];
354
unsigned int numBytes;
355
if (globalrng == NULL) {
356
/* create a new global RNG context */
357
globalrng = &theGlobalRng;
358
PORT_Assert(NULL == globalrng->lock);
359
/* create a lock for it */
360
globalrng->lock = PZ_NewLock(nssILockOther);
361
if (globalrng->lock == NULL) {
363
PORT_SetError(PR_OUT_OF_MEMORY_ERROR);
366
/* the RNG is in a valid state */
367
globalrng->isValid = PR_TRUE;
368
/* Try to get some seed data for the RNG */
369
numBytes = RNG_SystemRNG(bytes, sizeof bytes);
370
PORT_Assert(numBytes == 0 || numBytes == sizeof bytes);
372
RNG_RandomUpdate(bytes, numBytes);
373
memset(bytes, 0, numBytes);
374
} else if (PORT_GetError() != PR_NOT_IMPLEMENTED_ERROR) {
375
PZ_DestroyLock(globalrng->lock);
376
globalrng->lock = NULL;
377
globalrng->isValid = PR_FALSE;
381
numBytes = RNG_GetNoise(bytes, sizeof bytes);
382
RNG_RandomUpdate(bytes, numBytes);
388
* Initialize the global RNG context and give it some seed input taken
389
* from the system. This function is thread-safe and will only allow
390
* the global context to be initialized once. The seed input is likely
391
* small, so it is imperative that RNG_RandomUpdate() be called with
392
* additional seed data before the generator is used. A good way to
393
* provide the generator with additional entropy is to call
394
* RNG_SystemInfoForRNG(). Note that NSS_Init() does exactly that.
399
/* Allow only one call to initialize the context */
400
PR_CallOnce(&coRNGInit, rng_init);
401
/* Make sure there is a context */
402
return (globalrng != NULL) ? PR_SUCCESS : PR_FAILURE;
406
** Update the global random number generator with more seeding
410
prng_RandomUpdate(RNGContext *rng, const void *data, size_t bytes)
412
SECStatus rv = SECSuccess;
413
/* check for a valid global RNG context */
414
PORT_Assert(rng != NULL);
416
PORT_SetError(SEC_ERROR_INVALID_ARGS);
419
/* RNG_SystemInfoForRNG() sometimes does this, not really an error */
425
* Random information is initially supplied by a call to
426
* RNG_SystemInfoForRNG(). That function collects entropy from
427
* the system and calls RNG_RandomUpdate() to seed the generator.
428
* Algorithm 1 of FIPS 186-2 Change Notice 1, step 1 specifies that
429
* a secret value for the seed-key must be chosen before the
430
* generator can begin. The size of XKEY is b bits, so fill it
431
* with the b-bit hash of the input to the first RNG_RandomUpdate()
434
if (rng->seedCount == 0) {
435
/* This is the first call to RandomUpdate(). Use a hash
436
* of the input to set the seed-key, XKEY.
438
* <Step 1> copy hash of seed bytes into context's XKEY
440
SHA256_HashBuf(rng->XKEY, data, bytes);
441
/* Now continue with algorithm. */
442
rv = alg_fips186_2_cn_1(rng, NULL);
443
/* As per FIPS 140-2 continuous RNG test requirement, the first
444
* iteration of output is discarded. So here there is really
445
* no output available. This forces another execution of alg_cn_1()
446
* before any bytes can be extracted from the generator.
449
} else if (bytes == BSIZE && memcmp(rng->XKEY, data, BSIZE) == 0) {
450
/* Should we add the error code SEC_ERROR_BAD_RNG_SEED? */
451
PORT_SetError(SEC_ERROR_INVALID_ARGS);
455
* FIPS 186-2 does not specify how to reseed the RNG. We retrofit
456
* our RNG with a reseed function from NIST SP 800-90.
458
* Use a hash of the seed-key and the input to reseed the RNG.
462
SHA256_Update(&ctx, rng->XKEY, BSIZE);
463
SHA256_Update(&ctx, data, bytes);
464
SHA256_End(&ctx, rng->XKEY, NULL, BSIZE);
466
/* If got this far, have added bytes of seed data. */
467
if (rv == SECSuccess)
468
rng->seedCount += bytes;
469
PZ_Unlock(rng->lock);
470
/* --- UNLOCKED --- */
475
** Update the global random number generator with more seeding
479
RNG_RandomUpdate(const void *data, size_t bytes)
481
return prng_RandomUpdate(globalrng, data, bytes);
485
** Generate some random bytes, using the global random number generator
489
prng_GenerateGlobalRandomBytes(RNGContext *rng,
490
void *dest, size_t len)
493
SECStatus rv = SECSuccess;
494
unsigned char *output = dest;
495
/* check for a valid global RNG context */
496
PORT_Assert(rng != NULL);
498
PORT_SetError(SEC_ERROR_INVALID_ARGS);
503
/* Check the amount of seed data in the generator. If not enough,
504
* don't produce any data.
506
if (rng->seedCount < MIN_SEED_COUNT) {
507
PZ_Unlock(rng->lock);
508
PORT_SetError(SEC_ERROR_NEED_RANDOM);
512
* If there are enough bytes of random data, send back Xj,
513
* else call alg_cn_1() with 0's to generate more random data.
515
while (len > 0 && rv == SECSuccess) {
516
if (rng->avail == 0) {
517
/* All available bytes are used, so generate more. */
518
rv = alg_fips186_2_cn_1(rng, NULL);
520
/* number of bytes to obtain on this iteration (max of 40) */
521
num = PR_MIN(rng->avail, len);
523
* if avail < 2*GSIZE, the first 2*GSIZE - avail bytes have
527
memcpy(output, rng->Xj + (2*GSIZE - rng->avail), num);
533
PZ_Unlock(rng->lock);
534
/* --- UNLOCKED --- */
539
** Generate some random bytes, using the global random number generator
543
RNG_GenerateGlobalRandomBytes(void *dest, size_t len)
545
return prng_GenerateGlobalRandomBytes(globalrng, dest, len);
549
RNG_RNGShutdown(void)
551
/* check for a valid global RNG context */
552
PORT_Assert(globalrng != NULL);
553
if (globalrng == NULL) {
554
/* Should set a "not initialized" error code. */
555
PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
560
/* reset the callonce struct to allow a new call to RNG_RNGInit() */
561
coRNGInit = pristineCallOnce;
565
* SHA: Generate hash value from context
566
* Specialized function for PRNG
567
* The PRNG specified in FIPS 186-2 3.3 uses a function, G,
568
* which has the same initialization and compression functions
569
* as SHA1 180-1, but uses different padding. FIPS 186-2 3.3
570
* specifies that the message be padded with 0's until the size
574
RNG_UpdateAndEnd_FIPS186_2(SHA1Context *ctx,
575
unsigned char *input, unsigned int inputLen,
576
unsigned char *hashout, unsigned int *pDigestLen,
577
unsigned int maxDigestLen)
579
#if defined(SHA_NEED_TMP_VARIABLE)
580
register PRUint32 tmp;
582
static const unsigned char bulk_pad0[64] = { 0,0,0,0,0,0,0,0,0,0,
583
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
584
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
586
PORT_Assert(maxDigestLen >= SHA1_LENGTH);
587
PORT_Assert(inputLen <= SHA1_INPUT_LEN);
592
SHA1_Update(ctx, input, inputLen);
595
* This will fill the input block and cause the compression function
598
SHA1_Update(ctx, bulk_pad0, SHA1_INPUT_LEN - inputLen);
604
*pDigestLen = SHA1_LENGTH;
608
* Specialized RNG for DSA
610
* As per Algorithm 1 of FIPS 186-2 Change Notice 1, in step 3.3 the value
611
* Xj should be reduced mod q, a 160-bit prime number. Since this parameter
612
* is only meaningful in the context of DSA, the above RNG functions
613
* were implemented without it. They are re-implemented below for use
619
** Generate some random bytes, using the global random number generator
620
** object. In DSA mode, so there is a q.
623
DSA_GenerateGlobalRandomBytes(void *dest, size_t len, const unsigned char *q)
626
unsigned char w[2*GSIZE];
628
PORT_Assert(q && len == DSA_SUBPRIME_LEN);
629
if (len != DSA_SUBPRIME_LEN) {
630
PORT_SetError(SEC_ERROR_OUTPUT_LEN);
636
rv = prng_GenerateGlobalRandomBytes(globalrng, w, 2*GSIZE);
637
if (rv != SECSuccess) {
640
FIPS186Change_ReduceModQForDSA(w, q, (unsigned char *)dest);
added
removed
security/nss-fips/lib/freebl/prng_fips1861.c
