A good source of random numbers is critical for many cryptographic operations including most current cryptographic communications protocols and in this article we’ll look at how they’re generated in modern system-on-chips, best practice for using them and how they can be attacked.
What are cryptographically strong random numbers?
When we refer to “cryptographically strong” random numbers, we are talking about sequences of numbers that are statistically independent (i.e. you cannot determine the value of any number by looking at any other numbers) and cannot be distinguished from those produced by a truely random process such as radioactive decay times.
That doesn’t mean that they have to be generated by a truely random process, they just have look like they were and an attacker should never be able to work out what the next number in a sequence could be.
We generally want the following properties:
- Generated numbers are indistinguishable from truely random numbers
- The generation cannot be externally influenced in any way
- They can be generated quickly
It turns out that making a random number generator (or RNG, as the security world loves their acronyms) that has all of these properties isn’t easy.
Pseudo-random number generators
We are able to meet our first desirable property that generated numbers are indistinguishable from truely random numbers by either using a truely random physical process (commonly referred to as a True Random Number Generator, TRNG) OR by taking a “good enough” approach and using a computational algorithm (a Pseudo Random Number Generator, PRNG, also sometimes called a Deterministic Random Number Generator, DRNG) - but with caveats.
TRNGs usually have the disadvantage that they are relatively slow (e.g. we have to wait for the time interval between radioactive decay events), so don’t fulfil our desirable property of fast generation. PRNGs, on the other hand, can be constructed so that the quality of the sequence of “random” numbers is good enough for cryptographic use. These are referred to as Cryptographically Secure Pseudo Random Number Generators (CSPRNG) or Deterministic Random Bit Generators (DRBGs). However, as the name suggests, although the sequence of numbers that PRNGs generate appear random, they are in fact completely deterministic IF you know the algorithm and the initial conditions.
We like to use open algorithms in cryptography as we believe it actually improves the security in the long run by allowing researchers to investigate ways to break them. So to use PRNGs for cryptography, we therefore need a way of creating the initial conditions for the PRNG that an attacker cannot determine and (according to our second desirable property) cannot influence to their advantage.
Hardware TRNGs
TRNGs generate values based on real random physical effects and current devices typically use:
- Noise sampling (of thermal noise leading to Johnson’s effect, Zener noise due to quantum tunneling of carriers, inverse base-emitter breakdown in bipolar transistors, etc.)
- Free Running Oscillators (FROs)
- Chaos
- Quantum effects
Quantum Random Number Generators are optical devices that are currently in development for smaller silicon devices such as dedicated hardware security modules. They have the potential to be good, fast sources of randomness, however it is difficult to say at this point if they will provide any advantages over current methods and there has been no reported attack research yet for these devices.
Older TRNGs tended to use noise sampling methods, but these require analog circuits, are often resource-hungry, require custom silicon layout and are difficult to integrate into digital devices, particularly at ever-decreasing silicon geometries. For example, a MOSFET could be used as the thermal noise source. This then needs to be amplified by an op-amp, converted to digital by an ADC and then quantised, all without biasing the signal or disturbing the noise source. This requires significant tuning or automatic zero-biasing to ensure the quantisation results in very similar probabilities for getting a 0 or 1 value from the TRNG.
In recent system-on-chips it is more common to find random number generators based on FRO techniques as they can be implemented as purely digital designs that are better suited to smaller silicon geometries. In this case the output of a logical inverter is fed back into its input, creating a Ring Oscillator (RO) with Zeno paradox behaviour: if output is 1 then the input will be 1 and the NOT action will drive the output to 0; if the output is 0 then likewise the input will be 0 which will drive the output to 1. The real-world finite propagation delays in the inverter and stray reactance affecting the feedback phase shift in this physical circuit will result in it oscillating. The oscillation is sensitive to power supply voltage changes and temperature, but changes are slow compared to the oscillation frequency.
There are many implementations of the ring oscillator principle, but they derive their raw physical randomness (“entropy”) from either phase noise jitter or from metastability.
For phase noise jitter designs, the state of a higher-speed RO is usually sampled on the rising edge of a slower RO, with jitter in the high-speed RO due to thermal and shot noise then providing the entropy. The ratio between the oscillators can be tuned to give the best randomness, but accumulation of jitter to get good random values takes time and so this type of TRNG is relatively slow. Variants on this approach take a number of ROs and XOR their outputs to achieve higher throughput (up to ~ 100 Mbps) but the silicon area for such an implementation is large.
A metastable state is achieved when a digital circuit has signal voltage/current levels that sit in the undefined region between that used to represent a logical 0 or 1, causing it to act unpredictably. Recent designs claiming a throughput of 140 Mbps and 1 um^2 at 65nm are based on metastable ROs. The Transition Effect Ring Oscillator (TERO) evolves this further and claims greater sensitivity to intrinsic noise, making it more suitable for use on FPGAs (although at a bit rate of only 250 kbps).
Hybrid schemes attempt to combine aspects of both RO entropy methods to get smaller, high throughput TRNGs. For example, this implementation claims to achieve 160 Mbps on an Xilinx Artix-7 FPGA using 25 LUTs and 37 D type flip flops.
Hardware post-processing
TRNGs are never 100% perfect, so often some post-processing of the output bits is performed in hardware. This could be simple processing such as XORing the results of two TRNGs together or feeding the bits into LFSRs, all the way up to implementing full cryptographic hashing “whitening” functions such as SHA to try and improve the statistical properties.
In general, complex post-processing to “improve” the random numbers can indicate a weaker TRNG entropy collection stage and should be treated with suspicion.
TRNGs also commonly have a “sanity check” hardware block that looks for obvious failures such as a run of too many 0s or 1s. Although this could happen, there is a low probability of a long run of the same bit value and so these types of checks are appropriate. Some hardware even performs more complex analysis, however care has to be taken that any checks don’t end up biasing the random values.
Attacking hardware RNGs
Our second desirable property, that the TRNG can’t be influenced by an attacker, can be difficult to achieve. Given how important RNGs are for security, there is actually quite limited publically available information on attacking them.
TRNGs rely on some form of noise effects and can be affected by heating or cooling the chip or by modifying the power supply to a greater or lesser degree depending on the design. Implementations should really have countermeasures such as a temperature and voltage sensor that prevents operation outside of a safe operating region.
ROs are also susceptible to locking attacks, which attempt to bias their opeation by injecting a high-frequency signal into them. There have been sucessful attacks by injecting a signal into the power pads of a device and even from a non-invasive, active EM attack. These types of devices should incorporate countermeasures against these such as power supply filtering and tamper detection.
Best practice for using TRNGs
When Cerberus is evaluating the security of random number generation, we look for the following:
- What type of TRNG entropy collection method is used?
- Does it have complex post-processing?
- Does it have basic output checks such as runs of bits of the same value?
- Are there countermeasures against known attacks?
- How is it used?
- Are there more advanced checking methods used?
Ideally, we like to see hardware TRNGs with minimal post-processing and sufficient SoC-level countermeasures.
We also don’t recommend that software or even other parts of the hardware use a TRNG directly. Exceeding the throughput of a TRNG can result in a decrease in returned randomness and there is always still the possibility of a physical attack. A TRNG should ideally be used to seed a CSPRNG, as this can be used to generate random numbers at a high rate without degradation of the quality. Even better, the TRNG output should be tested statistically before being used as a seed.
Putting it all together…
If you’re buying TRNG IP to integrate into a silicon design then check if it is validated against BSI “Evaluation of random number generators”, NIST SP800-90 (US) or GM/T 0005-2012.
Testing random numbers
RNGs can be tested against statistical test suites:
Warning: all of these tests require very large amounts of values to be collected from the RNG and can take a very long time to run! It can also be sometimes difficult to interpret the results correctly.
Relevant international standards and documents
There are a number of standards documents regarding random numbers for cryptographic use. These include:
- NIST SP 800-90C DRAFT Recommendation for Random Bit Generator (RBG) Constructions (US)
- GM/T 0005-2010 Randomness Test Specification (China)
- Evaluation of random number generators (version 0.10) (Germany)
How can we help?
Cerberus can help with design review or audit of RNGs or advise on how best to use them. Please use the web contact form or email us for more information.