(Old) Random Number Generator Algorithms in CryptoSys API and the CryptoSys PKI Toolkit

This describes in detail the [now superseded] deterministic random number generator (RNG) algorithm used in CryptoSys API and the CryptoSys PKI Toolkit. We assert that the following CryptoSys RNG functions are fully compliant with the requirements of FIPS PUB 140-2, Security Requirements For Cryptographic Modules (as updated with Change Notice 2 on 3 December 2002) and with ANSI X9.31 Appendix A.2.4 (which replaces X9.17 Appendix C):

CryptoSys API Version 3 
RNG_KeyBytes
RNG_KeyHex
CryptoSys API Version 2 (deprecated) 
RNG_KeyGenerate
RNG_KeyGenHex
CryptoSys PKI 
RNG_Bytes

This information is published for peer review and comment. Please contact us with your comments. See also the later version of this document.

Contents

Definitions

Random Number:
1. A number selected from a known set of numbers in such a way that each number in the set has the same probability of occurrence. 2. A number obtained by chance. 3. One of a sequence of numbers considered appropriate for satisfying certain statistical tests or believed to be free from conditions that might bias the result of a calculation.
(Federal Standard 1037C).
Random Number Generator:
Random Number Generators (RNGs) used for cryptographic applications typically produce a sequence of zero and one bits that may be combined into sub-sequences or blocks of random numbers. There are two basic classes: deterministic and nondeterministic. A deterministic RNG consists of an algorithm that produces a sequence of bits from an initial value called a seed. A nondeterministic RNG produces output that is dependent on some unpredictable physical source that is outside human control. There are no FIPS Approved nondeterministic random number generators. [FIPS140]
Pseudo-Random Number Generator:
A pseudo-random number generator, or PRNG, is a random number generator that produces a sequence of values based on a seed and a current state. Given the same seed, a PRNG will always output the same sequence of values. [LAVA]
Seed key:
A secret value used to initialize a cryptographic function or operation. [FIPS140]
The terms pseudo-random number generator and deterministic RNG can be taken as equivalent for our purposes.

Terminology

We use the term RNG in this document to mean a deterministic RNG or PRNG that complies with FIPS 140-2 and X9.31. When we're talking about a random number, we use the terms number, byte, bit and bit string interchangably depending on the context. Note, too, that the term seed is used in three separate contexts: the seed key used to initiate the RNG algorithm, a user-supplied seed, and a value SD stored in memory to retain entropy between calls.

Design Principles

The objective is to produce a sequence of the required number of pseudorandom bits. The algorithm must comply with the standard. The method must be independent of hardware. No data is to be stored in permanent storage. The algorithm should make sure that subsequent calls in the same thread or two calls on parallel threads do not produce indentical resuls. It should minimise the chances that two calls on different computers at the same time will produce an identical result. It should minimise the requirements to store persistent information between calls and be safe to use in a multi-threaded environment.

Security requirements

A minimum security requirement for a pseudorandom bit generator is that the length k of the random seed should be sufficiently large so that a search over 2^k elements (the total number of possible seeds) is infeasible for an adversary. Two general requirements are that the output sequences of a PRNG should be statistically indistinguishable from truly random sequences, and the output should be unpredictable to an adversary with limited computational resources. [MENE]

The Theory

From FIPS PUB 140-2 Annex C [FIPS140-C]:

ANNEX C: APPROVED RANDOM NUMBER GENERATORS

Annex C provides a list of the FIPS Approved random number generators applicable to FIPS PUB 140-2
(snip)...
3. American Bankers Association, Digital Signatures Using Reversible Public Key Cryptography for the Financial Services Industry (rDSA), ANSI X9.31-1998 - Appendix A.2.4.
From X9.31-1998 Appendix A [AX931] and reproduced in [RNG931EXT]:

A.2.4 Generating Pseudo Random Numbers Using the DEA

Let ede*X(Y) represent the DEA multiple encryption of Y under the key *X. Let *K be a DEA key pair reserved only for the generation of pseudo random numbers, let V be a 64-bit seed value which is also kept secret, and let XOR be the exclusive-or operator. Let DT be a date/time vector which is updated on each iteration. I is an intermediate value. A 64-bit vector R is generated as follows: 
I = ede*K(DT)
R = ede*K(I XOR V) and a new V is generated by V = ede*K(R XOR I).
Successive values of R may be concatenated to produce a pseudo random number of the desired length.
From FIPS PUB 140-2 Section 4.9.2 Self-Tests - Conditional Tests [FIPS140]:

Continuous random number generator test.

If a cryptographic module employs Approved or non-Approved RNGs in an Approved mode of operation, the module shall perform the following continuous random number generator test on each RNG that tests for failure to a constant value.

1. If each call to a RNG produces blocks of n bits (where n > 15), the first n-bit block generated after power-up, initialization, or reset shall not be used, but shall be saved for comparison with the next n-bit block to be generated. Each subsequent generation of an n-bit block shall be compared with the previously generated block. The test shall fail if any two compared n-bit blocks are equal.

Notation

Our FIPS 140-2 Compliant RNG Algorithm for generating N pseudorandom bytes

Given

Step 1. Generate 32 pseudo-random bytes with the seed key generator (described below), adding the user-supplied seed, U, if any.

Step 2. Set the 192-bit Triple DES key, K, as the first 24 bytes generated in step 1, and set the seed, S, as the last 8 bytes [Note 1].

Step 3. Set D as a 64-bit representation of the current date and time [Note 2].

Step 4. Generate the 64-bit block X0 = G(S, K, D) where G is the X9.17 RNG algorithm described in ANSI X9.17 Appendix C/ANSI X9.31 Appendix A, and where S is updated as per that algorithm.

Step 5. Set up to carry out continuous random number generator tests:

  1. If X0 equals L or X0 equals P, stop and notify a failure of the continuous random number generator test.
  2. Set L = X0 and store in thread-safe memory for the next call.
  3. Set P = X0.

Step 6. For R = N until R is equal to zero, do:

  1. Generate a 64-bit block X = G(S, K, D), updating S in the process (see below).
  2. If X equals the previously-generated block, P, then stop and notify a failure of the continuous random number generator test [Note 3].
  3. Set B = the lesser of R and 8.
  4. Output B bytes from X. [Note 6]
  5. Set R = R - B.
  6. Set P = X.

Step 7. Generate a final block Xf = G(S, K, D) and set P = Xf [Note 3].

Step 8. Zeroise K, S, D, X and any other internal buffers used. Retain L and P for subsequent use.

Flowchart

RNG

X9.17/X9.31 algorithm to generate the next 64-bit block

Given

Step 1. Compute the 64-bit block X = G(S, K, D) as follows:

  1. I = E(D, K)
  2. X = E(I XOR S, K)
  3. S' = E(X XOR I, K)
where E(p, K) is the Triple DES encryption of the 64-bit block p using key K.

Step 2. Return X and set S = S' for the next cycle.

 

Algorithm to generate a seed key

Given

Step 1. Increment the counter CC and save the updated value for subsequent calls. Roll over to zero if the value is incremented beyond ULONG_MAX.

Step 2. Create a 512 bit/64 byte message block as follows [Note 4]:

DT || SST || CC || SD
where On a Win32 system, we use this for the system status:
SST = PID || TID || TC || MS
where On a Linux system, we use:
SST = PID || TC || SI
where SI is a 288-bit representation of the current overall system statistics, truncated as necessary.

Step 3. If the user has supplied an optional seed of M bytes, add these to the message block as follows:

  1. Increment the counter value, CC'.
  2. Compute the 160-bit SHA-1 message digest of (M || CC').
  3. XOR this digest with the message block at byte offset 32: 
    |<--------------------------(64 bytes)------------------------->| 
+-------+-------------------------------------------+---+-------+
|DT(8)  |SYSTEM STATUS (44)                         |CC |SD(8)  | 
+-------+-----------------------+-------------------+---+-------+
0       8                       32                  52  56      64
                                +-------------------+
XOR user-supplied seed:         |   HASH(seed||CC') |
                                +-------------------+
This step has changed from an earlier method - see Note 5.

Step 4. For R = N until R is equal to zero, do:

  1. Create an SHA-1 digest of the message block
  2. Replace the first 20 bytes of the block with the resulting message digest bytes.
  3. Set B = the lesser of R and 20.
  4. Output B bytes from the updated message block.
  5. Set R = R - B.

Step 5. Update SD as follows:

  1. Create an SHA-1 digest of the final message block from the previous step
  2. Set SD' = the first 64 bits/8 bytes of the resulting digest.
  3. Set SD = SD XOR SD'.
  4. Save the updated SD in thread-safe memory for use in subsequent calls.

Step 6. Zeroise the message block and any other internal buffers used.

 

On Start-Up

When the process or thread starts:
  1. Initialise the counter CC with a pseudo-random 32-bit value using a separate and not-necessarily-secure generator like rand() and store in thread-safe memory. This value will be used as the counter CC in the seed key algorithm above.
  2. Set L = P = SD = 0 and store in thread-safe memory.
  3. Call the RNG function to generate 8 bytes/64 bits and ignore the output. This will set and store two 64-bit values L and P for continuous testing, and a new 64-bit seed SD for subsequent calls. If this attempt to generate an RNG fails (e.g. by generating a zero value), stop and notify a failure of the RNG function.
Note that each thread has its own independent set of persistent values, CC, SD, L and P, stored in thread-safe memory between calls to the RNG.

Notes

  1. Derivation of key K and seed

    The ANSI standard requires that the DEA key, K, is reserved (and presumably is kept secret) and that the seed is secret, but gives no further guidance on how they might be derived. There is no advice in the newer Implementation Guidance for the FIPS PUB 140-2 [FIPS1402IG] but the older Implementation Guidance for the FIPS PUB 140-1 [FIPS140IG] advised that
    It is acceptable for the output of a random number generator to generate a seed value for one of the FIPS-approved pseudorandom number generators listed above, in order to generate keys.
    We assert that our method of deriving an independent key and seed each time using an SHA-1 hash of certain volatile and time-related system variables is in accordance with the standard.

  2. 64-bit representation of the current date and time

    On a Win32 system:- 
    	#include <windows.h>
	#include <string.h>
	FILETIME ft;

	GetSystemTimeAsFileTime(&ft);
	memcpy(output, &ft, sizeof(FILETIME));
    On a Linux system, you might do this:- 
    	#include <sys/time.h>
	struct timeval tv;
	gettimeofday(&tv, NULL);
	memcpy(output, &tv, sizeof(tv));
    The value produced here may be longer than 64 bits.

  3. Continuous checks using P and L

    The 64-bit value P is used to carry out the continuous test required in Section 4.9.2 of FIPS 140-2, comparing each 64-bit block generated by the function G with the previously-generated block. The 64-bit value L is used to carry out an additional check to make sure that consecutive calls to the RNG do not return identical values. This additional check is not required by FIPS 140-2, but it catches the situation where the same seed key is used as the last time the RNG was called. In our opinion this is the most likely form of failure of this deterministic algorithm.

    Note that after a call to the RNG, neither of the stored values P or L have been output by the RNG. Each time the RNG is called, a dummy block is generated to compare with the last value, L, and an extra dummy block is generated at the end to make sure the final value of P is different from the last block of output.

  4. Choice of initial value for seed key generator

    We chose the components of this particular 512-bit value for the following reasons:

    It could be improved by keeping a "pool" of randomness on the hard-drive or by capturing "random" hardware values such as mouse movements, keystroke timings, or fluctuations in pressure across the hard drive head. These are precluded by our design criteria of being hardware independent and not storing any permanent data on the user's system..

    To produce the system-related seed values on a Win32 system:- 
    #include <windows.h>
static int get_SystemStatus_W32(BYTE *buf, int maxlen)
{
	int ni = 0;
	DWORD dwRes;
	MEMORYSTATUS ms;
	dwRes = GetCurrentProcessId();
	if (maxlen >= sizeof(DWORD))
	{
		memcpy(&buf[ni], (POINTER)&dwRes, sizeof(dwRes));
		ni += sizeof(dwRes);
		maxlen -= sizeof(dwRes);
	}
	dwRes = GetCurrentThreadId();
	if (maxlen >= sizeof(DWORD))
	{
		memcpy(&buf[ni], (POINTER)&dwRes, sizeof(dwRes));
		ni += sizeof(dwRes);
		maxlen -= sizeof(dwRes);
	}
	dwRes = GetTickCount();
	if (maxlen >= sizeof(DWORD))
	{
		memcpy(&buf[ni], (POINTER)&dwRes, sizeof(dwRes));
		ni += sizeof(dwRes);
		maxlen -= sizeof(dwRes);
	}
	ms.dwLength = sizeof(MEMORYSTATUS);
	GlobalMemoryStatus(&ms);
	if (maxlen >= sizeof(MEMORYSTATUS))
	{
		memcpy(&buf[ni], (POINTER)&ms, sizeof(MEMORYSTATUS));
		ni += sizeof(MEMORYSTATUS);
		maxlen -= sizeof(MEMORYSTATUS);
	}
	return ni;
}
    On Linux, we had problems trying to use pthread-related functions, so we used this :- 
    #include <sys/sysinfo.h>
#include <sys/times.h>
#include <sys/unistd.h>
#include <sys/types.h>
static int get_SystemStatus_UX(BYTE *buf, int maxlen)
{
	int ni = 0;
	pid_t pid;
	struct tms ptimes;
	clock_t clk;
	struct sysinfo si;
	int copylen;
	/* Process ID */
	pid = getpid();	/* in <sys/unistd.h> */
	if (maxlen > 0)
	{
		copylen = min(sizeof(pid), maxlen);
		memcpy(&buf[ni], (POINTER)&pid, copylen);
		ni += copylen;
		maxlen -= copylen;
	}
	/* Get clock ticks since system booted (probably) */
	clk = times(&ptimes);	/* in <sys/times.h> */
	if (maxlen > 0)
	{
		copylen = min(sizeof(clk), maxlen);
		memcpy(&buf[ni], (POINTER)&clk, copylen);
		ni += copylen;
		maxlen -= copylen;
	}
	/* Obtain system statistics. */
	sysinfo (&si);	/* <sys/sysinfo.h> */
	if (maxlen > 0)
	{
		copylen = min(sizeof(si), maxlen);
		memcpy(&buf[ni], (POINTER)&si, copylen);
		ni += copylen;
		maxlen -= copylen;
	}
	return ni;
}

  5. Change in methods for blending the user-supplied seed

    Old method:
    1. if M <= 64, XOR the first M bytes of the message block with the seed bytes, i.e.
      for j=1 to M set block_byte(j) = block_byte(j) XOR seed_byte(j); or
    2. if M > 64, repeatedly XOR the message block with next 64 seed bytes until the remaining number of seed bytes is less than or equal to 64, then do as in (a).
    The new method described above creates the SHA-1 message digest of the user-supplied seed together with a counter and then XORs this into the message block. Using a message digest destroys any structure in the user-supplied seed that might conceivably be used to affect the state of the block.

  6. What we really do

    Actually, we don't do any of this. We just use the C stdlib function rand(). We know nobody ever reads this far :-)

References

Comments? Disagree? Found a mistake? Please let us know.

This page last updated: 9 September 2007

Copyright (C) 2003-25 DI Management Services Pty Limited
<https://di-mgt.com.au>   <https://cryptosys.net>