TRUE RANDOM NUMBER GENERATION Choosing the right TRNG
Table of Contents
1. CONTEXT
In the near future, in a world of devices interconnected in the Cloud (the Internet of Things or the Internet of Everything), each and every object could be a threat to the whole network. This will be ever more critical. Starting from there, Secure-IC assesses that security represents the most important asset of the digital world.
Going forward, all devices will need to integrate a Secure Element as a basis for trust.
Secure-IC has chosen to support its clients throughout and beyond the IC design process and during the entire life-time of their product. Relying on a unique approach called PESC (Protect, Evaluate, Service & Certify), we provide Silicon-proven protection technologies, integrated Secure Elements and security evaluation platforms to reach compliance with the highest level of certification for different markets (such as automotive, AIoT, defense, payments & transactions, memory & storage, server & cloud).
2. GLOBAL OVERVIEW
“Digital True Random Number Generator” is an entity whose purpose is to generate a sequence of numbers or bits that is purely random. This sequence must be unpredictable and unbiased. This means that this sequence does not depend on anything, and any possible result has an equal probability, just like an unloaded dice.
Alongside this fundamental property, there are many other important aspects to be taken into account to qualify a good TRNG: Randomness quality and its resilience are the main function of a TRNG, but the compliance to standards and the convenience of integration and usage are also important aspects to consider.
2.1. Standards and recommendations
A user can trust its TRNG only if there is a common baseline for performances. Standards give this baseline, and compliance to them is therefore essential.
Different standards describe the requirements for a TRNG, and are linked either to different geographical areas or different functionalities. As a non-exhaustive list of standards related to Random Number Generators (RNGs), we may cite:
- AIS-31 PTG.1, AIS-31 PTG.2 and AIS-31 PTG.3 that are used in Europe and describe three levels of security, PTG3 being the most stringent level.
- NIST SP 800-90B, NIST SP 800-90C that are used in the USA and will characterize design principles and requirements for entropy sources used in TRNG (NIST SP-800-90B) and the construction of random bit generators combining a TRNG and a DRBG (NIST SP-800-90C).
- NIST FIPS 140-2 and FIPS 140-3 that describe generally cryptographic modules and will refer to NIST SP-800-90A, B and C for their DRBG and TRNG parts.
- CAVP is the Cryptographic Algorithm Validation Program from NIST which lists all the validated cryptographic modules and algorithms that have been validated by NIST (see for example Secure-IC’s Random number generator validation: https://csrc.nist.gov/projects/cryptographic-algorithm-validation-program/details?product=9815).
- GM/T 0005-2012 & GM/T 0062-2018 are Chinese standards that describes the performances requirements of TRNGs and random bit sequences
- OSCCA which is a certification scheme for Chinese market. It requires multiple different entropy source based on different rationales in its higher levels.
- NIST SP 800-22 describes the different tests that characterize the quality of the output sequence of a TRNG and that must be run periodically on a TRNG in order to ensure a good output quality.
2.2. Use-cases
Random numbers are used and needed in a wide variety of applications. Cryptography is one of the most important and most obvious of them, since encrypting data basically requires the use of a non-guessable secret code. Those applications include:
- Nonce generation in digital signatures,
- Keys generation in key exchanges (Diffie-Hellman, Key Encapsulation Mechanisms, etc.),
- Unpredictable seeds creation to implement random masking or shuffling schemes.
Other use-cases may concern some algorithms initializations or timer applications:
- Optimization problems based on simulated annealing or genetic algorithms,
- Neural networks training,
- Numerical recipes, such as Monte-Carlo simulation or multidimensional integration,
- Random timers in communications protocols.
3. TYPES OF RANDOM NUMBER GENERATORS AND ASSOCIATED QUALITY
3.1. PRNG or TRNG
The intrinsic quality of a Random Number Generator is the randomness of the bit sequence itself. This randomness is extracted from an entropy source, which is based on an unpredictable physical phenomenon. The bit-sequence must also have statistical properties, which means that they must basically be unbiased.
There are two types of random number generators: Pseudo-Random Number Generators (PRNG, also known as Deterministic Random Bit Generator, DRBG) and True Random Number Generators (TRNG).
The first category will output a sequence that has good statistical properties (unbiased), but that is theoretically predictable. It uses a seed as a relatively short input and generates a long output from this seed (usually based on a cryptographic algorithm). Since this bit-sequence generation is purely algorithmic, the throughput is virtually unlimited, but the drawback is that if the same seed is used as input, the same output will be generated. Therefore, an attacker can theoretically predict the output of a PRNG, thanks to modeling. Only TRNG can prevent this.
Indeed, on the contrary, a TRNG extracts its output from an unpredictable physical entropy source, based on a given random physical phenomenon. Since those physical phenomena are not predictable, it is not possible to calculate the output of a TRNG, even with a high level of information about the system state. Therefore, the use of a TRNG ensures a higher level of security for the device. However, in order to generate this true random number sequence, entropy must be physically harvested, and this process is limited in term of throughput.
To combine the advantages of the two categories, it is possible to chain a TRNG with a DRBG, using the output of the first as a seed for the second. With such an approach, designer benefits from both a high quality entropy and virtually unlimited throughput.
3.2. Entropy Sources
The way of gathering entropy and turning it into a stream of bits is the base of a TRNG IP. This part of the TRNG is called entropy source. Different physical principles may be used for this purpose, and the choice of a type of entropy source may be based on several criteria that will be described later in this paper. However, even random physical phenomenon or its collection can be influenced by external sources. This may lead to the bias of the TRNG output and a lower sequence quality. Therefore, unless TRNGs are designed with robustness in mind, total failures can happen, as have already been seen in some ID cards or with the ROCA Vulnerability.
More advanced variations (eg. harmonic injections) can also be induced by an attacker, who can eventually predict the output of the TRNG by imposing external conditions on it. It is therefore essential that the TRNG remains protected against such influences.
To achieve this, one possible countermeasure is to embed multiple different entropy sources. Since each entropy source will be unique, they will behave differently in front of this external influence which will make the prediction of the output impossible, even under influence.
3.3. Availability of Stochastic model
In order to be able to correctly tune the TRNG and formally proof proper randomness, the availability of stochastic model for entropy sources is an asset. This allows full modeling of the system for proper configuration and will discriminate odd circuitry that gives apparently erratic results (that may not be truly random) from real TRNG that will output reliable results. The availability of a stochastic model is an element that cannot be obtained without careful quality oriented design. This quality proof is required by ISO 180314 and becomes more and mode mandatory in validation schemes, and governmental agencies now start to ask for post-silicon stochastic models proof, which is even more demanding in terms of quality and reliability.
4. INTEGRATION MADE EASY, AT EVERY LEVEL
In addition to the good statistical properties a TRNG must have, it is the integration of this TRNG into the chip that has to be considered as a real asset. Indeed, easy integration will allow to benefit from the full potential of the TRNG while difficult integration can quickly lead to additional costs or performance hits.
4.1. Hardware integration
4.1.1. Analog or digital entropy source
There are many different types of entropy harvesting, each having its pros and cons. However, one major differentiator is whether the entropy source is based on analog or digital electronics. This choice may have an impact on the TRNG stability and its resilience against external influence since analog electronic is more sensitive to EMI. Both analog and digital-based TRNG can have very high quality output. But choosing one or the other may have important impacts when it comes to the integration of the TRNG on the chip. Indeed, TRNG are integrated in digital circuits, and integration of analog parts into digital circuits is way tougher than their digital counterparts since their implementation will be technology-dependent. On the contrary, using purely digital TRNG and entropy sources ensures independence from technology node and foundry, meaning much less integration efforts.
4.1.2. Usage of Standard cells
To be more specific, the smoothest integration will be obtained with Standard Cells based TRNGs. Not only using standard cells will make the integration and design much easier, but it will also ensure compatibility and portability to different process and technology nodes. And since standard cells are very widely used, their behavior towards external conditions, aging, etc. are very well known and predictable. These characteristics transposed in the circuits that are made with those cells turn to be a big advantage. This standard composition also diminishes or even suppresses the need for calibration.
4.1.3. Post silicon adjustment and silicon usage
Using fully digital design and standard cells leave little margin for unexpected behavior. Therefore, only fine tuning remains necessary post-silicon. If this capability is embedded directly into the TRNG then the reliability of the TRNG is among the highest. All those elements lead to the insurance that no hardware rework nor additional costs are to be expected when using such a TRNG. Finally, using fully digital and standard cell based design also provides very compact TRNGs that benefit from all foundry technological advances. All those assets combined leads to a very cost efficient integration of TRNG, which greatly reduces the total cost of ownership.
4.2. Software integration configuration
System and software integration is also a very important subject to take into account in the performance and integration cost of the whole system.
4.2.1. Configuration and self-tests
To be sure that the TRNG functions properly and that the outputs have the right statistical properties, TRNG outputs must be statistically tested. Those tests may consist in balance tests, consistency checks, bad or repeated sequence detections, etc. The results of those tests are used as feedbacks to finely tune the TRNG and correct potential misbehavior. This correction can be made by software, using computation external to TRNG, but can also be embedded directly inside the TRNG design. This second option is the most effective one since it lowers the feedback time, allows continuous health-tests to be run and effectively blocks any bad sequence. This design also allows real-time configuration correction, and suppress the need to integrate external feedback to the TRNG. This integrated approach provides unequalled security since the TRNG remains completely independent from the outside world: there is no need for data output nor risks of manipulated configuration data. This integration of tests and configuration also leads to much simpler integration process since the TRNG can be integrated as easily as a standalone block.
4.2.2. Software integration: ISA and API
In order to be used in different situations, the TRNG needs to be integrated in the instruction sets and in software. Most CPU common types will provide ISA (Instruction Set Architecture) extensions to use TRNG: Intel, AMD, ARM and RISC-V processors provide TRNG ISA extensions. The later differentiate itself from the others as it separates the entropy functions from the DRBG part. This allows to easily interface directly with the entropy source. This approach can be extended to the API provided with the random number generator. An example of this API use is the function PollEntropy that, coupled with its ISA extension instruction, allows to get directly the entropy from the TRNG in one clock cycle. With this ability, it is now possible to efficiently validate the stochastic model and to enable custom post-processing. Customized post-processing is required for sovereign applications where no black box can be integrated. This prevents backdoors integration inside the TRNG, as already seen with Dual EC DRBG5.
This allows those functions to be integrated in OS (such as Linux), so that the system can get true random number through a simple efficient and vendor independent driver.
5. CONCLUSION
True Random Number Generators (TRNGs) are critical parts of systems, especially those embedding cryptographic functions. Their quality is the key to the high-level cryptographic algorithms that use them. Beyond the quality of the entropy itself, the hardware integration can widely influence the total integration costs. Finally, software integration also provides assets for efficiently using the full potential of a high quality entropy source.
Because the ability to generate random number represents the very essence of every security mechanism, we have chosen our “Digital True Random Number Generator” IP to be the first we share on the platform.
Secure-IC’s “Digital True Random Number Generator” IP is available on platforms and will allow designers to integrate a high quality TRNG. As all IPs provided by Secure-IC, this TRNG is fully customizable and fully verified using our Virtualizr and Catalyzr tools, the latter embedding specific TRNG test functions. Eventually, it integrates all the state-of-the-art functionalities that have been mentioned above:
- CAVP validated TRNG and DRBG which can be chained to provide the desired throughput,
- Multiple entropy sources to ensure non-lockability and possibility to use different entropy source
types with independent rationale, - Compact design with built-in self-tests, optimization, and post-silicon configuration and adjustments,
- Availability of stochastic model, and quality API to be used with the different ISA extensions.
- Purely digital and standard-cells-based entropy sources ensure a cost and time effective integration
for high quality and reliable result.
Share on:
