Cryptography: PRNG Requirements

•When a PRNG or PRF is used for a cryptographic application, then the basic requirement is that an adversary who does not know the seed is unable to determine the pseudorandom string.

•For example, if the pseudorandom bit stream is used in a stream cipher, then knowledge of the pseudorandom bit stream would enable the adversary to recover the plaintext from the ciphertext.

•Similarly, we wish to protect the output value of a PRF.

–consider the following scenario. A 128-bit seed, together with some context-specific values, are used to generate a 128-bit secret key that is subsequently used for symmetric encryption.

–Under normal circumstances, a 128-bit key is safe from a brute-force attack.

–However, if the PRF does not generate effectively random 128-bit output values, it may be possible for an adversary to narrow the possibilities and successfully use a brute force attack.

•This general requirement for secrecy of the output of a PRNG or PRF leads to specific requirements in the areas of

–randomness,

–unpredictability, and

–the characteristics of the seed.

 
PRNG Requirements - Randomness

•In terms of randomness, the requirement for a PRNG is that the generated bit stream appear random even though it is deterministic.

•There is no single test that can determine if a PRNG generates numbers that have the characteristic of randomness.

•The best that can be done is to apply a sequence of tests to the PRNG.

•If the PRNG exhibits randomness on the basis of multiple tests, then it can be assumed to satisfy the randomness requirement.

 

•NIST SP 800-22 (A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications) specifies that the tests should seek to establish the following three characteristics:

–Uniformity

–Scalability

–Consistency

•Uniformity: At any point in the generation of a sequence of random or pseudorandom bits, the occurrence of a zero or one is equally likely, i.e., the probability of each is exactly 1/2. The expected number of zeros (or ones) is n/2, where n = the sequence length.

•Scalability: Any test applicable to a sequence can also be applied to subsequences extracted at random. If a sequence is random, then any such extracted subsequence should also be random. Hence, any extracted subsequence should pass any test for randomness.

•Consistency: The behavior of a generator must be consistent across starting values (seeds). It is inadequate to test a PRNG based on the output from a single seed or an TRNG on the basis of an output produced from a single physical output

PRNG Requirements - Seed

•For cryptographic applications, the seed that serves as input to the PRNG must be secure.

–Because the PRNG is a deterministic algorithm, if the adversary can deduce the seed, then the output can also be determined.

•Therefore, the seed must be unpredictable.

•In fact, the seed itself must be a random or pseudorandom number.

•Typically, the seed is generated by a TRNG