Cryptography: True Random Number Generator

Entropy Sources

•A true random number generator (TRNG) uses a nondeterministic source to produce randomness.

•Most operate by measuring unpredictable natural processes, such as pulse detectors of ionizing radiation events, gas discharge tubes, and leaky capacitors.

•Intel has developed a commercially available chip that samples thermal noise by amplifying the voltage measured across undriven resistors.

•LavaRnd is an open source project for creating truly random numbers using inexpensive cameras, open source code, and inexpensive hardware.

•The system uses a saturated CCD in a light-tight can as a chaotic source to produce the seed.

•Software processes the result into truly random numbers in a variety of formats.

RFC 4086 lists the following possible sources of randomness that, with care, easily can be used on a computer to generate true random sequences.

•Sound/video input: Many computers are built with inputs that digitize some real-world analog source, such as sound from a microphone or video input from a camera.

–The “input” from a sound digitizer with no source plugged in or from a camera with the lens cap on is essentially thermal noise. If the system has enough gain to detect anything, such input can provide reasonably high quality random bits.

•Disk drives: Disk drives have small random fluctuations in their rotational speed due to chaotic air turbulence. The addition of low-level disk seek-time instrumentation produces a series of measurements that contain this randomness.

–Such data is usually highly correlated, so significant processing is needed. Nevertheless, experimentation a decade ago showed that, with such processing, even slow disk drives on the slower computers of that day could easily produce 100 bits a minute or more of excellent random data.

Cryptography: Stream Ciphers and Its Requirements

•A typical stream cipher encrypts plaintext one byte at a time, although a stream cipher may be designed to operate on one bit at a time or on units larger than a byte at a time.

•

•Figure 7.5 is a representative diagram of stream cipher structure. 

•In this structure, a key is input to a pseudorandom bit generator that produces a stream of 8-bit numbers that are apparently random.

•

•The output of the generator, called a keystream, is combined one byte at a time with the plaintext stream using the bit- wise exclusive-OR (XOR) operation. 

•The stream cipher is similar to the one-time pad.

•The difference is that a one-time pad uses a genuine random number stream, whereas a stream cipher uses a pseudorandom number stream.

 

Following are important design considerations for a stream cipher.

1.The encryption sequence should have a large period. A pseudorandom num- ber generator uses a function that produces a deterministic stream of bits that eventually repeats. The longer the period of repeat the more difficult it will be to do cryptanalysis. This is essentially the same consideration that was discussed with reference to the Vigenère cipher, namely that the longer the keyword the more difficult the cryptanalysis.

●

2.The keystream should approximate the properties of a true random number stream as close as possible. For example, there should be an approximately equal number of 1s and 0s. If the keystream is treated as a stream of bytes, then all of the 256 possible byte values should appear approximately equally often. The more random-appearing the keystream is, the more randomized the ciphertext is, making cryptanalysis more difficult.

●

3.The output of the pseudorandom number generator is conditioned on the value of the input key. To guard against brute-force attacks, the key needs to be sufficiently long. The same considerations that apply to block ciphers are valid here. Thus, with current technology, a key length of at least 128 bits is desirable. 

Stream Ciphers - Advantages

•With a properly designed pseudorandom number generator, a stream cipher can be as secure as a block cipher of comparable key length.

•A potential advantage of a stream cipher is that stream ciphers that do not use block ciphers as a building block are typically faster and use far less code than do block ciphers.

•

•For applications that require encryption/decryption of a stream of data, such as over a data communications channel or a browser/Web link, a stream cipher might be the better alternative.

•For applications that deal with blocks of data, such as file transfer, e-mail, and database, block ciphers may be more appropriate.

•However, either type of cipher can be used in virtually any application.  

 

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

Cryptography: TRNGs, PRNGs, and PRFs

•Cryptographic applications typically make use of algorithmic techniques for random number generation.

•These algorithms are deterministic and therefore produce sequences of numbers that are not statistically random.

•However, if the algorithm is good, the resulting sequences will pass many reasonable tests of randomness. Such numbers are referred to as pseudorandom numbers.

PRNGs 

•In contrast, a PRNG takes as input a fixed value, called the seed, and produces a sequence of output bits using a deterministic algorithm.

•Typically, as shown, there is some feedback path by which some of the results of the algorithm are fed back as input as additional output bits are produced.

•The important thing to note is that the output bit stream is determined solely by the input value or values, so that an adversary who knows the algorithm and the seed can reproduce the entire bit stream.

PRNGs Vs PRF 

Figure 7.1 shows two different forms of PRNGs, based on application.

•Pseudorandom number generator: An algorithm that is used to produce an open-ended sequence of bits is referred to as a PRNG. A common application for an open-ended sequence of bits is as input to a symmetric stream cipher.

•Pseudorandom function (PRF): A PRF is used to produced a pseudorandom string of bits of some fixed length. Examples are symmetric encryption keys and nonces. Typically, the PRF takes as input a seed plus some context specific values, such as a user ID or an application ID.

•Other than the number of bits produced, there is no difference between a PRNG and a PRF.

•The same algorithms can be used in both applications.

•Both require a seed and both must exhibit randomness and unpredictability.

•Further, a PRNG application may also employ context-specific input.

Cryptography: Random Numbers - Criteria for a Random Number

 
Principles of Pseudorandom Number Generation 

•Random numbers play an important role in the use of encryption for various network security applications

•The Use of Random Numbers: A number of network security algorithms and protocols based on cryptography make use of random binary numbers. For example,

–Key distribution

–Session key generation

–Generation of keys for the RSA public-key encryption algorithm

–Generation of a bit stream for symmetric stream encryption

These applications give rise to two distinct and not necessarily compatible requirements for a sequence of random numbers:

•randomness and

•unpredictability

RANDOMNESS 

•The sequence of numbers be random in some well-defined statistical sense.

•The following two criteria are used to validate that a sequence of numbers is random:

–Uniform distribution: The distribution of bits in the sequence should be uniform; that is, the frequency of occurrence of ones and zeros should be approximately equal.

–Independence: No one subsequence in the sequence can be inferred from the others.

UNPREDICTABILITY 

•In applications such as reciprocal authentication, session key generation, and stream ciphers, the requirement is not just that the sequence of numbers be statistically random but that the successive members of the sequence are unpredictable.

•With “true” random sequences, each number is statistically independent of other numbers in the sequence and therefore unpredictable.

•However, true random numbers are seldom used; rather, sequences of numbers that appear to be random are generated by some algorithm.

•In this latter case, care must be taken that an opponent not be able to predict future elements of the sequence on the basis of earlier elements.

 

Cryptography: Galois Field GF(p)

How Do We Know That GF(23) Is A Finite Field?

•We do know that GF (23) is an abelian group because of the operation of polynomial addition satisfies all of the requirements on a group operator and because polynomial addition is commutative.

•GF (23) is also a commutative ring because polynomial multiplication distributes over polynomial addition

–polynomial multiplication meets all the other stipulations on the ring operator: closedness, associativity, commutativity

•

•GF (23) is an integral domain because of the fact that the set contains the multiplicative identity element 1 and because if for a ∈ GF(23) and b ∈ GF(23) we have

  a×b = 0 mod(x3+x+1)

•Then either a = 0 or b = 0.

•We now argue that GF (23) is a finite field because it is a finite set and because it contains a unique multiplicative inverse for every non-zero element.

•GF (23) contains a unique multiplicative inverse for every non- zero element for the same reason that Z7 contains a unique multiplicative inverse for every non-zero integer in the set.

–For a counter example, recall that Z8 does not possess multiplicative inverses for 2, 4, and 6.

–Stated formally, we say that for every non-zero element a ∈ GF(23) there is always a unique element b∈GF(23) such that a×b = 1.

•The above conclusion follows from the fact if you multiply a non-zero element a with each of the eight elements of GF(23), the result will be the eight distinct elements of GF(23).

–Obviously, the results of such multiplications must equal 1 for exactly one of the non-zero element of GF(23).

–So if a×b = 1, then b must be the multiplicative inverse for a.

•

•The same thing happens in Z7. If you multiply a non-zero element a of this set with each of the seven elements of Z7, you will get seven distinct answers.

–The answer must therefore equal 1 for at least one such multiplication. When the answer is 1, you have your multiplicative inverse for a.

•For a counter example, this is not what happens in Z8. When you multiply 2 with every element of Z8, you do not get eight distinct answers.

–Multiplying 2 with every element of Z8 yields {0, 2, 4, 6, 0, 2, 4, 6} that has only four distinct elements

 

•For a more formal proof (by contradiction) of the fact that if you multiply a non-zero element a of GF(23) with every element of the same set, no two answers will be the same, let’s assume that this assertion is false. That is, we assume the existence of two distinct b and c in the set such that

a × b ≡ a × c mod (x3 + x + 1)

That implies

a×(b−c) ≡ 0 mod (x3+x+1)

•That implies that either a is 0 or that b equals c. In either case, we have a contradiction.

•The upshot is that GF (23) is a finite field.

GF(2n) Is A Finite Field For Every N 

•GF(2n) is a finite field for every n.

•To find all the polynomials in GF (2n), we obviously need an irreducible polynomial of degree n.

•AES arithmetic is based on GF (28). It uses the following irreducible polynomial

x8 +x4 +x3 +x+1

•In general, GF(pn) is a finite field for any prime p.

–The elements of GF(pn) are polynomials over GF(p)

–which is the same as the set of residues Zp

Finding the Multiplicative Inverse  

•Just as the Euclidean algorithm can be adapted to find the greatest common divisor of two polynomials, the extended Euclidean algorithm can be adapted to find the multiplicative inverse of a polynomial.

•

•Specifically, the algorithm will find the multiplicative inverse of b(x) modulo a(x) if the degree of b(x) is less than the degree of a(x) and gcd[a(x), b(x)] = 1.

•

•If a(x) is an irreducible polynomial, then it has no factor other than itself or 1, so that gcd[a(x), b(x)] = 1.

•Given polynomials a(x) and b(x) with the degree of a(x) greater than the degree of b(x), we solve the following equation for the values v(x), w(x), and d(x), where d(x) = gcd[a(x), b(x)]:

  a(x)v(x) + b(x)w(x) = d(x)

•If d(x) = 1, then w(x) is the multiplicative inverse of b(x) modulo a(x).

•The calculations are as follows.

 

Cryptography: Polynomial Arithmetic

•Why study polynomial arithmetic?

•Defining finite fields over sets of polynomials will allow us to create a finite set of numbers that are particularly appropriate for digital computation. Since these numbers will constitute a finite field, we will be able to carry out all arithmetic operations on them — in particular the operation of division — without error.

We are concerned with polynomials in a single variable x, and we can distinguish three classes of polynomial arithmetic.

•Ordinary polynomial arithmetic, using the basic rules of algebra.

•Polynomial arithmetic in which the arithmetic on the coefficients is performed modulo p ; that is, the coefficients are in GF(p).

•Polynomial arithmetic in which the coefficients are in GF(p), and the polynomials are defined modulo a polynomial m(x) whose highest power is some integer n.

Polynomial Arithmetic with Coefficients in Zp  

•Let us now consider polynomials in which the coefficients are elements of some field F;

–Referred as a polynomial over the field F.

•In that case, it is easy to show that the set of such polynomials is a ring, referred to as a polynomial ring.

•That is, if we consider each distinct polynomial to be an element of the set, then that set is a ring.

•When polynomial arithmetic is performed on polynomials over a field, then division is possible.

–Note that this does not mean that exact division is possible.

•Let us clarify this distinction.

•Within a field, given two elements a and b, the quotient a/b is also an element of the field.

•However, given a ring R that is not a field, in general, division will result in both a quotient and a remainder; this is not exact division.

•Consider the division 5/3 within a set S. If S is the set of rational numbers, which is a field, then the result is simply expressed as 5/3 and is an element of S. Now suppose that S is the field Z7, then

  5/3 = (5 * 3-1)mod7 = (5 * 5)mod7 = 4

•Finally, suppose that S is the set of integers, which is a ring but not a field. Then 5/3 produces a quotient of 1 and a remainder of 2:

  5/3 = 1 + 2/3 5=1*3+2

•Thus, division is not exact over the set of integers.

•Now, if we attempt to perform polynomial division over a coefficient set that is not a field, we find that division is not always defined.

•If the coefficient set is the integers, then (5x2)/(3x) does not have a solution, because it would require a coefficient with a value of 5/3, which is not in the coefficient set.

•Suppose that we perform the same polynomial division over Z7. Then we have (5x2)/(3x) = 4x, which is a valid polynomial over Z7.

•Given polynomials f(x) of degree n and g(x) of degree (m), (n >= m), if we divide f(x) by g(x), we get a quotient q(x) and a remainder r(x) that obey the relationship

  f(x) = q(x)g(x) + r(x)

with polynomial degrees:

–Degree f(x) = n
Degree g(x) = m
Degree q(x) = n - m
Degree r(x) <= m - 1

•With the understanding that remainders are allowed, we can say that polynomial division is possible if the coefficient set is a field.

•In an analogy to integer arithmetic, we can write f(x) mod g(x) for the remainder r(x). That is,

  r(x) = f(x) mod g(x)

•If there is no remainder [i.e., r(x) = 0], then we can say g(x) divides f(x), written as g(x) | f(x).

•Equivalently, we can say that g(x) is a factor of f(x) or g(x) is a divisor of f(x).

•Example [f(x) = x3 + x2 + 2 and g(x) = x2 - x + 1], f(x)/g(x) produces a quotient of q(x) = x + 2 and a remainder r(x) = x.

•This is easily verified by noting that

q(x)g(x) + r(x)

= (x+2) (x2 -x+1) + x

= (x3 +x2 -x+2) + x

= x3 +x2 +2

= f(x)

•For our purposes, polynomials over GF(2) are of most interest.

•In GF(2), addition is equivalent to the XOR operation, and multiplication is equivalent to the logical AND operation.

•Further, addition and subtraction are equivalent mod 2:
1 + 1 = 1 - 1 = 0;
1 + 0 = 1 - 0 = 1;
0 + 1 = 0 - 1 = 1.

•A polynomial f(x) over a field F is called irreducible if and only if f(x) cannot be expressed as a product of two polynomials, both over F, and both of degree lower than that of f(x).

•By analogy to integers, an irreducible polynomial is also called a prime polynomial.

•The polynomial f(x) = x4 + 1 over GF(2) is reducible, because x4 + 1 = (x + 1)(x3 + x2 + x + 1).