Cryptographically Secure

Secure

Cryptographically Secure Pseudo-Random Number Generator

A Cryptographically Secure Pseudo-Random Number Generator (CSPRNG) will produce a random number suitable for cryptographic usage. The number will always appear random, since it cannot be predicted or be reliably reproduced after generation.

A CSPRNG has a strength that is is directly proportional to the source of entropy (unpredictable input) used for seeding it as well as re-seeding it. The cryptosystem security therefore depends on seeding a CSPRNG algorithm with the highest level of entropy.

Some classes of CSPRNGs include the following:

  • Stream ciphers.
  • Block ciphers running in output or counter feedback mode.
  • PRNGs specifically designed to be cryptographically secure, such as Microsoft's Cryptographic Application Programming Interface function CryptGenRandom, the Yarrow algorithm (incorporated in Mac OS X), and Fortuna.
  • Combination PRNGs that try to combine several PRNG primitive algorithms with the aim of removing any non-randomness.
  • Special designs based on mathematical hardness assumptions, such as MicaliSchnorr.
  • The Blum-Blum-Shub algorithm, which provide strong security, though they are slower in comparison to traditional constructions, and therefore impractical for many applications.

Variations

Variation of the Santha-Vazirani design

Santha and Vazirani proposed the notion of a semi-random source of bits (also known as Santha-Vazirani sources), and proved that it is impossible to extract an almost-uniform random bit from such a source. A 2015 study by Beigi et al., looked at the generalisation of SV sources for non-binary sequences. The report showed that deterministic randomness extraction in the generalised case is sometimes possible, which is different to the binary case. The authors presented a necessary condition and a sufficient condition for the possibility of deterministic randomness extraction.

Standards

When the maximum number of bits output from a PRNG is equal to the 2^blocksize, the resulting output delivers the mathematically expected security level that the key size would be expected to generate, but the output can be distinguished from a true random number generator. When the maximum number of bits output from this PRNG is less than 2^blocksize, the expected security level is delivered and the output appears to be indistinguishable from a true random number generator. In the next revision, limiting the total number of generate requests and the bits provided per generate request will show security strength.

Dual_EC_DRBG is part of the standard though it is not cryptographically secure due to a kleptographic NSA backdoor.

NIST SP 800-90A Rev.1 is essentially NIST SP 800-90A with the Dual_EC_DRBG removed.

CTR_DRBG, another PRNG, is based on a block cipher running in counter mode and whilst its design is uncontroversial, it has been proven to be weaker than others in distinguishing an attack.

The standards for statistical testing of new CSPRNG designs are maintained by NIST along with a good reference of standard CSPRNGs.

Work

How does a cryptographically secure random number generator work?

A cryptographically secure number random generator How does a cryptographically secure random number generator work?by gathering entropy from a source that others cannot see. The system must first gather a sequence of n truly random bits. n shall be large enough to thwart an exhaustive search, so that it is impossible to calculate all 2^n combinations of n bits (when n is greater than 90, but it is customary to use n = 128).

The most common entropy gathering schemes include the variation in timing of hardware interrupts from sources such as hard disks returning data, key-presses and incoming network packets, provided there is not an overestimation of how much entropy has been collected. The system encodes these events and then "compresses" them by applying a cryptographically secure hash function such as SHA-256 (output is then truncated to yield the n bits). The encoding of the physical events should have collectively assumed at least 2^n combinations. The hash function, by its definition, should make a good job at concentrating that entropy into an n-bit string.

Entropy gathering schemes can also be obtained from hardware RNGs. Examples include sampling from the difference between a pair of oscillators that are running at almost the same speed, but whose rates are slightly varied according to thermal noise. Other schemes include sampling the noise on a CCD (lavaRND), radioactive decay (hotbits) or atmospheric noise (random.org).

Random number generation

Random Random number generation is the generation of a numerical sequence that cannot possibly be predicted by chance. They are usually created by a random-number generator (RNG). This can be as simple as rolling dice, flipping a coin or shuffling a deck of cards. With computers able to act as random-number generators it is now possible to generate high volume to determine outcomes of lotteries, slot machines and more.

Whilst there are several computational methods for random-number generation, many are not truly random, since they show patterns that can be discerned. Carefully designed cryptographically secure computationally based methods of generating random numbers do exist, including those based on the Yarrow algorithm, the Fortuna (PRNG), and others.

Practical applications and uses

Random number generation has allowed casinos to move from being mechanised to being computerised. Traditional slot machines require the simple pulling of a handle to play. The original slot machines feature three reels each with various numbers and images. When a player pulls the machine's handle, the internal mechanisms of levers and brakes keep the reels spinning until the handle returns to its original position when a brake stops the disks attached to those reels, to reveal a random generation of reel combinations. Each pull of the handle keeps the combinations random and the odds fair. With the invention of digital slots machines that were designed to look like their original forerunners, the process for creating random combinations was computerised.

Today, both land-based and online casinos computerised slot machines have software generating RNGs to give a fair chance at a winning combination. The software's RNG produces numbers at several hundred combinations per second to ensure sequences are random, even without game play. When a player presses the "spin" button to start the game, the next number combination tells the programme when the virtual reels will stop spinning.