Search for true random number generators

Know yourself the numbers generated on the basis of unpredictable data of the physical world - this simple idea pursues a person throughout the entire path of modern cryptography. Pseudo-random number generators (PRNG), based on mathematical algorithms alone, are predictable or subject to external influence, therefore, hardware generators using different entropy sources are considered the gold standard of safety.

However, even real-time random number generators (RNGs) that collect unpredictable data from physical phenomena have drawbacks: they can be cumbersome, slow, and expensive to produce. There is no guarantee that the proprietary system is not open to special services - therefore, the FreeBSD developers have refused to directly use hardware generators built into Intel chips.

The evolution of encryption methods has led to the need to create more advanced generators - they will be discussed today.

100 years ago, to get random numbers, they threw dice, distributed cards, collected numbers from a hat. In 1927, Leonard Henry Caleb Tippett, a statistician, published the world's first "table of chance" - 41,600 numbers - obtained by collecting data on the area of ​​English churches.

In 1955, RAND Corporation published a book, which for many years became one of the main sources of data on random data - “ Million random numbers with a standard deviation of 100,000 ”. Perhaps no one has read the book from cover to cover — almost all of its text consists of five-digit numbers.

With the development of the computer era, meaningful and non-meaningful user actions began to be used for RNG: keystrokes on the keyboard, mouse clicks, etc. However, this approach gives a small rate of random bits. The problem is that everything that happens inside a computer cannot be considered truly random. Computers from the very beginning were designed to be predictable. Sources from the environment - for example, user actions - also have their limits, at least in time.

High security requirements have given life to several new complementary approaches to generating random numbers.

"Toy" generator

The Electronic Frontier Foundation ( EFF ), which is engaged in the struggle for universal rights in matters related to communication technologies, proposed a simple way to create secure passwords based on the use of a physical random number generator.

The method is really simple - it is based on the dice.

We throw five playing dice at the same time, and write the resulting numbers. Suppose the cubes are located from left to right like this: 4, 3, 4, 6, 3. Open the EFF's Long Wordlist list to find the corresponding word next to 43463. This word is “panoramic”.

The procedure is repeated five times. As a result, we get something like a panoramic nectar precut smith banana handclap - a passphrase that has about 221,073,919,720,733,357,899,776 variations.

With the help of mnemonic phrase easy to remember. Given the availability of 2⁷⁷ alternatives to brute force, it will be extremely difficult to pick up your password.

Chaoskey

Kate Packard, active Debian developer, X.Org project leader, creator of XRender, XComposite and XRandR, together with well-known supporter of open data, head of Linux projects at Hewlett-Packard Bdale Garby, developed an inexpensive but reliable random number generator ChaosKey.

The open source device ChaosKey 1.0 was introduced at the Debian DeConf16 conference. The goal of the development is to add real entropy to a random number generator, to ensure a high level of security and to reduce the price to a minimum.

ChaosKey cannot be accessed remotely and the firmware cannot be overwritten, even when the device is connected via USB to a computer. To do this, you need to get physical access, open the gadget and connect the two contacts inside.

The full-featured RNG itself is like a small USB flash drive and takes up one USB connector. The design of the board is minimalist - in fact there is only a processor and transistors for generating noise. The transfer rate of random values ​​is about a megabyte per second.

And about the price. The device can be ordered, but all the schemes and firmware are laid out in open access - the developers themselves recommend everyone to create and improve ChaosKey.

Z1FFER

Another inexpensive open source random number generator that will appeal to all DIY lovers. Everyone can assemble and disassemble the device, and also make sure that it does not have built-in backdoors.

Z1FFER is not a complete product and does not come with any software (the authors share only a few scenarios and instructions for getting started). It is designed to work on the arduino platform, but does not have proven reliability from hacking from the outside. The device is primarily for those who want to personally "touch" the technology of generating numbers using iron.

Z1FFER uses thermal noise from a resistor, doubling the signal, which leads to an exponential increase in the complexity of predicting the bit sequence.

QRBG121

It would be a sin not to mention in this topic a random number generator QRBG121, which for some unknown reason once became the mascot of one of the runet imageboard. QRBG121 (Quantum Random Bit Generator), perhaps, indeed, someone causes affection, but the most interesting thing is hidden inside the box.

The effect of randomness in the device depends on the quantum physical process of photon radiation in semiconductors and the subsequent detection of individual photons using a photomultiplier . In this process, photons are detected randomly, independently of each other. Synchronization information of detected photons is used to generate bits. A unique feature of this method is that it uses only one photon detector to produce both zeros and ones.

Lava lamps at cloudflare

The company CloudFlare, which itself declares that “about 10% of global traffic” passes through its network, protects Internet projects from DDoS attacks, but it also needs protection. The traffic that passes through the CloudFlare network is encrypted - and this is helped by hundreds of multi-colored lava-lamps on the “Wall of Entropy”.

The lava lamp is a glass container filled with clear oil and translucent paraffin. An incandescent bulb located at the bottom of the tank heats and illuminates the contents of the cylinder, and a “lava-like” paraffin movement in the oil occurs. Paraffin is slightly heavier than oil, but with a slight heat it becomes lighter and floats.

Fluid movement is monitored by several cameras taking snapshots. Snapshots are converted to numbers, from which encryption keys are then generated. 16384 bits of entropy are obtained in one frame.

The other two offices of CloudFlare use other ways to get random values. In London, the camera captures the movements of three chaotic pendulums, while in Singapore they installed a Geiger counter, measuring the radioactive decay of a small piece of uranium. In the latter case, uranium is used as a “data source”, since radioactive radiation is characterized by randomness of each individual decay event.

All these ways of working with data draw attention to the activities of the company, whose work is often invisible to ordinary customers.

Hotbits

HotBits is a site that provides everyone with true random numbers generated by a Geiger counter that records ionizing radiation. You fill out a request form on the website indicating the number of random bytes and choose the preferred method of obtaining data. Provisional application is necessary because the HotBits hardware allows you to create data at a modest speed of about 100 bytes per second.

After random numbers are provided to the client, they are immediately removed from the system - the same data will never be sent to different users (unless, of course, you trust HotBits).

To obtain even more reliable data, there is the EntropyPool resource, which collects and “mixes” random bits from various sources, including HotBits and random.org (this resource, in turn, “extracts” the entropy of atmospheric radio noise). People who are experiencing quantum security to the maximum extent can add the Quantum Random Bit Generator online service to the above resources.

Quantum vacuum fluctuations

Schematic representation of the space-time deviations from the level of unperturbed vacuum fluctuations of the electric field

A source

Vacuum, contrary to the name (“vacuus” - empty), cannot be considered truly empty, because virtual particles are constantly born and die in it due to the Heisenberg uncertainty principle - so-called quantum fluctuations, fluctuations of energy level per unit volume of space-time occur.

Canadian physicists have constructed a fast and structurally simple random number generator based on vacuum fluctuations. The generator consists of a pulsed high-frequency laser, a medium with a high refractive index (diamond), and a detector. Passing through a diamond, each pulse at the detector shows different characteristics, depending on the vacuum fluctuations of the field, which are encountered along the path of the photons. In the spectrum of the scattered radiation, spectral lines appear at the output that are not in the spectrum of the primary light, and because of the unpredictability of vacuum fluctuations, these lines differ in an unpredictable way every time.

Physicists say that there is not even a concept of how theoretically one could develop a device for predicting the energy fluctuations of the appearance and annihilation of virtual particles - this is one of the most random events that we observe in the Universe.

It remains to make this generator compact and cheap enough to begin its mass use.

ANU Quantum random number server

An alternative, based on the measurement of quantum fluctuations of vacuum, offers the site ANU Quantum . Random numbers laid out in open access are generated in real time in the laboratory of the Center for Quantum Computing and Communication Technologies of the University of New South Wales (Sydney, Australia).

By measuring the fluctuations of the electromagnetic field of a vacuum, ANU Quantum allows everyone to see , listen to or download random quantum numbers and evaluate the quality of the generated numbers in real time.

Serial quantum randomness

There are not many companies creating QRNG devices (Quantum Random Number Generator). The leader in this direction is now called the Swiss startup ID Quantique (IDQ) , which since 2001 has been creating commercial generators of quantum random numbers. IDQ offers many QRNG formats, as shown in the image above. One of the company's most popular devices is USB Quantum , which generates more random numbers than you probably need in this lifetime.

Another well-known company in this area is QuintessenceLabs . The company claims that their version of the QRNG device is so powerful that it is equivalent to 60 IDQ devices.

ComScire has been in the market for QRNG devices since 1994. The image above shows a top source of random numbers, giving a stream of data from mixing different types of transistor noise at 128 Mbps.

Carbon nanotube generator

Existing hardware and software generator solutions are not particularly suitable for wearable devices. Northwestern suggested a different approach combining compactness with generated thermal noise.

The researchers built a random number generator from a static random access memory cell ( SRAM ) printed with special inks containing semiconductor carbon nanotubes. A memory cell uses thermal noise fluctuations to generate random bits.

The carbon nanotube generator can be printed on flexible plastic substrates, which allows it to be integrated into tiny flexible electronics devices - wearable sensors, disposable labels, smart clothing items. Printing SRAM cells with nanotubes is a relatively inexpensive process, which allows them to be used in consumer electronics manufacturing.

Quantum Random Number Generator from Smartphone

In 2014, the University of Geneva was marked with a QRNG device, which uses the eight-megapixel camera of the Nokia N9 smartphone.

The camera of the smartphone counts the number of photons falling on each pixel. The light source is a normal LED. The operation of the camera and the LED is adjusted so that each pixel in the 8 MP camera detects about 400 photons in a short time. The number of photons on all pixels is converted into a sequence of random numbers at a speed of 1.25 Gbit / s.

This speed is not a record. Back in 2011, Intel showed that their processor generator creates a stream of random numbers at a speed of about 3 Gbit / s. However, all QRNG components can be integrated on a chip costing a few dollars and easily added to any portable electronic devices, including smartphones.

True chance

With so many data sources, it is logical to ask: how do you actually check the randomness of bits?

The National Institute of Standards and Technology of the United States proposed a “statistical test suite for random and pseudo-random number generators for cryptographic applications.” It consists of 15 statistical tests , the purpose of which is to determine the measure of the randomness of bits generated by either hardware or software generators.

One of the most stringent statistical tests proposed by Professor George Marsalla of the University of Florida. The diehard tests include 17 different checks, some of which require very long sequences: at least 268 megabytes.

Randomness can be tested using the TestU01 library provided by Pierre L'Ecuyet and Richard Simard of the University of Montreal, including the classic tests and some original ones, as well as through the publicly available library SPRNG .

Another useful service for quantifying randomness is http://www.fourmilab.ch/random .

And let's not forget about the most important criterion - every next bit in a sequence of random data must be predicted with a probability that does not exceed the probability of meeting a dinosaur on the street;)