The Importance of True Randomness in Cryptography


INTRODUCTION


In the world of information security, we often see statements such as ‘secured by 128-bit AES’ or ‘protected by 2048-bit authentication’. We are used to people asking about the strength of the cryptographic algorithms deployed in a security solution. Algorithms such as the AES, RSA and ECC have a proven track record of being difficult to break. They are successfully deployed in protocols that protect on a daily basis our identity and the integrity and confidentiality of our data. Consider as examples the use of SSL or TLS when you buy a book at Amazon or when you connect to your bank account to transfer a sum of money. Or the use of IKE and IPsec when you connect your laptop to the company network to check on your email and read documents stored on the company network.

What we see very rarely are statements about the strength of the random number generator used by a security system. System designers are typically more concerned with the power consumption and bit generation speed, than with the actual randomness of the bits generated.

The quality of the random numbers used directly determines the security strength of the system. This means that all modern security algorithms and protocols have their ‘cryptographic strength’ expressed in the number of (key) bits that an attacker needs to guess before he can break the system. This expression of strength implicitly assumes that the attacker has no knowledge of the bits of the original key used. The ‘effective strength’ of an algorithm is diminished when better attacks against it are found and more key bits can be derived from looking at (a limited amount) of output data.

Take, for example, the effective strength of 3DES. Although it uses 3 keys of 56 bits each, 3DES is currently only expected to provide 112 bits of ‘effective’ security, since the best attack against it today has a complexity of 2112 bits. This still assumes that all 168 bits of the key used, are unknown and unpredictable by the attacker. So, what happens if we start with key material that is partly predictable to the attacker? Immediately, the security of the system is weakened, regardless of the algorithm or protocol used. If your 128-bit key contains 16 predictable bits, using it in AES-128 does not give you 128-bit protection; it only gives you 112 bits of protection, making the security of your system ‘only’ as strong as 3DES today.

Many security protocols require random bits to remain secure, even though the protocol definition will not always call it random; typically, a protocol description will use the term ‘unpredictable’ to indicate that a certain value should be difficult to guess by an attacker. True random numbers may be required if your application uses one of the following:

  • keys and initialization values (IVs) for encryption

  • keys for keyed MAC algorithms

  • private keys for digital signature algorithms

  • values to be used in entity authentication mechanisms

  • values to be used in key establishment protocols

  • PIN and password generation

Exactly for the reasons mentioned above, the IETF has written a ‘Best Practices’ document (RFC 4086) to explain the importance of true randomness in cryptography, and to provide guidance on how to produce random numbers. NIST has a section on Random Number Generation in their Cryptographic Toolbox pages, and a number of standards bodies such as IETF, IEEE, NIST, ANSI, and ISO have, or are working on, standards related to random number generation. This shows the importance of proper random number generation.
 

RANDOM NUMBER GENERATION


Creating Random Numbers is hard. Especially if all you have available to do it, is digital hardware and deterministic software. Where is the randomness in that? Both are designed to behave predictably, each time, every time. Therefore, hardware and software designers, trying to find unpredictability, have to look outside of their normal operating environment to find it. Software typically uses external events (hard disk seek timing, keyboard/mouse clicks, Ethernet packet arrival intervals). Digital hardware designers have to ‘fall back’ to the analog world from which their digital environment normally tries to shield them. This typically means somehow translating the noise from a diode p-n junction, a resistor, or some other semiconductor component, into ‘unpredictable’ bit values.


But even if you have found a proper source of unpredictability, you are not home free. There are still questions to ask, such as:

  • How much ‘unpredictability’ does my source generate

  • How do I translate this unpredictability, into random bit streams or numbers?

  • How efficient is this translation? Am I loosing unpredictability?

  • Is the resulting data biased or not?

  • Do I get sufficient unpredictable output for my purpose?

  • Are all the output bits I am getting, unpredictable, or only a portion?

 

Some organizations, such as NIST, have defined statistical tests to be run on the output of a random number generator to provide answers to some of the questions above. The challenge is, however, that statistical tests cannot really ‘prove’ that a source is random. At best, these tests can determine that a source is not, or only partially, unpredictable. As we will see below, it is very well possible to create a module that creates a bit string that will pass all the statistical tests available, but still generates a completely predictable bit stream, once you know the internal state of the module. For this reason, standardization and certification organizations tend to require that a random number generator design is not tested by passing its output through a statistical test; rather, these organizations require that the design of the generator is reviewed, and its randomness generation properties explained and proven.


The general idea here is that True Random Number Generation is surprisingly difficult to do right. One of the results is that even now, there is no ‘approved’ or ‘standardized’ method for generating true random numbers. All that is available today are statistical tests (NIST, DIEHARD, etc.) or evaluation criteria, such as the German AIS-31 specification.


INTRINSIC RANDOMNESS VS. EXTERNAL NOISE


When selecting a source of randomness, it is essential to understand whether the randomness of the source is caused by an integral property of the system itself, or if the source really is ‘just’ a measure of events external to, and unpredictable by, the system itself. The former is typically called ‘intrinsic’ randomness, the latter has different names but since the ‘signal’ in question is typically not part of the ‘desired’ operation of the system, in this whitepaper we shall refer to it as ‘external noise’. The difference is important, since, by definition, sources of intrinsic randomness cannot be influenced by an adversary, whereas sources using external noise can typically be influenced.


Although sources of external randomness can be often be easily recognized (one can imagine an attacker influencing packet arrival rates, or keystroke timing), they may often not be too easily disregarded. In the case of thermal noise above, for instance, an application wishing to extract unpredictable bits by sampling the noise current or voltage, also has to deal with the presence of voltage noise on the power lines, which, although it is considered noise, is predictable and, more importantly, controllable by an adversary. Thus, the sampling process must ensure that the intrinsic randomness is not ‘drowned’ by the external noise. For example, an attacker could ground an antenna that was meant to be used as a source of noise, or block a camera sensor to zero all or most bits at the seed.


The conclusion with respect to random number generators is that in most systems, it is desirable that the RNG uses (or is characterized by) purely intrinsic sources of randomness, but that unfortunately this cannot always be guaranteed.


DETERMINISTIC RANDOMNESS?


In literature, two classes of random number (or bit) generators are identified: the Non-Deterministic (or True) Random Number Generators, and the Deterministic (or Pseudo) Random Number Generators. The two types differ by the fact that a TRNG uses some source of randomness to generate its output, whereas a PRNG does not – the output of a PRNG is therefore completely predictable (or deterministic) once its internal state is known. If this is the case, then why are PRNGs still so important? Some of the reasons are:

  • As long as a PRNG’s internal state is unknown to an attacker, the output it generates is unpredictable by the attacker – the same quality we need from the output of our TRNG. PRNGs are much easier to construct in digital hardware than a TRNG.

  • A well-constructed PRNG only leaks a limited amount of data about its internal state through the output it produces. So as long as the PRNG’s internal state is refreshed by new unpredictable data (the PRNG is ‘reseeded’) often enough, its output remains unpredictable. Thus, you can generate a lot of unpredictable data from a limited amount of truly random data – as long as you keep your internal PRNG state secret. 

  • Once a PRNG is properly seeded, it can generate unpredictable output very fast – a useful property for systems that need a lot of unpredictable data in a short amount of time. Collecting random bits from a source of randomness typically is a difficult, and often slow, process.

We shall see that many of the assurance requirements on random number generators are based around the protection of this internal state.


In many cases, a random bit generator is constructed from a combination of a source of true randomness, which is used to seed the internal state of a PRNG. These types of random number generators are called ‘Hybrid’ RNGs.


BIAS


Most sources of random data generate ‘biased’ output, i.e. the chance that an output bit is ‘1’ or ‘0’ is not equal to 0.5. In other words, the source generates more ‘1’s than ‘0’s, or vice versa. If this is the case, the output of the random data source must be post-processed such that the output bits after post-processing have an equal chance of being ‘1’ or ‘0’. This post-processing is often called ‘whitening’ after the term in image noise processing, which transforms the frequency spectrum of some random variable into a flat spectrum with equal power in all frequencies (thus, ‘white’ light). In the context of random number generators, ‘whitening’ means transforming the output of the random data source, to a bit stream with a zero mean and ‘normal’ distribution. The whitening function is typically combined with the PRNG function, for instance by the ‘Hybrid’ RNGs discussed above.

INSIDE SECURE’S TRUE RANDOM NUMBER GENERATOR
MOSFET CHANNEL NOISE AS A SOURCE OF RANDOMNESS


The Inside Secure SafeXcel-IP-76 True Random Number generator uses the current noise, present in the channel of a MOSFET transistor, as its source of intrinsic randomness. This noise causes a small amount of uncertainty on the transition time of an inverter cell when it switches from low to high. This uncertainty is accumulated by placing an odd number of inverters in a ring, creating what is called a Free Running Oscillator (FRO). The uncertainty on the individual inverter transitions causes a small amount of phase jitter on the output of the FRO, which builds up over time, until at some point in time it can no longer be predicted if a certain point in the FRO ring has the value ‘0’ or ‘1’. By sampling the output of the FRO at such a point in time, the state of the captured bit cannot be predicted and thus, we have created a single bit of randomness.


The sampled bits are subsequently passed through an LFSR for initial whitening, after which they are subjected to numerous tests to verify that the output of the LFSR is indeed unpredictable (or at least, cannot be easily predicted because something has broken). Optionally, the output of the LFSR can be post-processed by a PRNG for further whitening and expansion, for instance if more unpredictable data is required than the entropy collection circuitry can provide. The Inside Secure TRNG uses the FIPS 140-3 approved ‘CTR_DRBG’ with AES-256 as post processor.


FIPS COMPLIANCE


When discussing TRNGs (or more appropriately, NDRBGs but the acronym TRNG reads easier) we often get asked the question what is needed to ‘be FIPS compliant’. As stated earlier, until the release of the SP 800-90 specifications, NIST does not recognize ‘approved’ TRNGs, however to be prepared for the final release of the SP 800-90 documents, the Inside Secure TRNG already includes the following features:

  • The TRNG needs to use an approved post processor. The Inside Secure TRNG solution implements the SP 800-90A CTR_DBRG (approved for FIPS 140-3, allowed for FIPS 140-2).

  • The construction of the EIP-76 is compliant to one of the approved mechanisms set forth in SP 800-90C

  • The TRNG’s entropy source must be explained and a model must be provided for its entropy generation rate (available from Inside Secure under NDA).

  • The internal state of the TRNG (in particular, the post processor) must be protected. This is a system level constraint, similar to the requirement that the key material generated from the output of the TRNG must be protected. The Inside Secure TRNG solution provides an internal re-seed function where the random data used for the re-seeding is not revealed outside the module boundary.

  • Various operational health checks should be present or supported. This is actually a requirement from the SP 800-90B draft which is referenced by FIPS 140. The Inside Secure TRNG solution (SafeXcel-IP-76) specifically implements the ‘continuous’ tests that cannot be triggered or executed by software. The SafeXcel-IP-76 supports this by providing state zeroisation functionality.

  • The conditioning function used is one of the approved conditioning functions from SP 800-90B

  • It is possible, through a special test mode, to access the data from the raw entropy source (sampled FRO outputs) directly to enable CAVP statistical testing and min-entropy estimation.

In addition, the TRNG employs patented circuitry to detect frequency locking of the free running oscillators, including a mechanism to break to lock and generate an alarm if locking occurs too often. Detecting if a FRO is locked to a system frequency is important since this can cause the accumulation of jitter on the frequency of the ring to be reduced or even negated completely, to a point where the sampling mechanism only samples a constant bit value or a recurring pattern of values. If multiple FRO rings show locking in this way, the TRNG is automatically stopped and further output is disabled. This test can be considered an ‘entropy source breakdown’ detection mechanism as required by AIS-31.


INTEGRATION IN MODERN SoCs


When using a TRNG in your design, there are a number of things to consider (in addition to the topics from the previous sections). For instance:

  • How many random bits does your application need per time unit?

  • How much ‘randomness’ is needed in your application? Does it need to be fully random every time, or is it sufficient to occasionally re-seed the PRNG and create unpredictable data from there?

  • How much power can the TRNG consume? More entropy gathering requires more FROs running simultaneously, so there is a relationship between entropy generation rate and power consumption.

  • What frequency (range) to use for the individual FROs? Higher frequencies make it easier to collect entropy faster – but run a FRO too fast and there’s a risk it stops running at all. Similarly, you want to avoid running FROs at frequencies that are ‘multiples’ of any of the other (clock) frequencies in the design. In smaller technologies, however, the PVT range is typically so large that this constraint cannot be easily met over the complete range. In this case, the only remedy is to use more FRO’s – so even if some of them lock some of the time, there is still enough entropy generated by the others.

  • Is the TRNG (scan) testable? By design, a TRNG contains constructs that violates typical design constraints, especially those for testability. A TRNG should provide a mechanism to allow it to be included in the regular scan test, regardless of all the health tests mentioned above.

  • What SoC bus interfaces are available?

  • Is software integration available?

 

Inside Secure took all the above considerations into account when designing the latest state of the art version of the SafeXcel-IP-76 True Random Number Generator core family. The SafeXcel-IP-76 TRNG core family is provided with integrated AXI, AHB, PLB, or any other system bus interface and comes with Driver’s Developer’s Kit (DDK) to facilitate software development and easy porting to other platforms.


Licensing semiconductor IP from Inside Secure, the world’s largest provider of silicon-proven security IP, makes it easy and cost-effective for chip designers to integrate the most advanced security functionality into semiconductor designs, including NPUs, communications processors, and custom ASICs and FPGAs. Inside Secure provides high-performance, highly integrated security engines that support cryptographic algorithms and protocol-related security operations for a wide range of applications. Silicon-proven and ready-to-use, the SafeXcel IP security engines are a reliable security solution for chip designers - delivering quick time-to-market while reducing design and engineering cost. Inside Secure OEM products also include security stack software and security processors. This complete HW/SW security platform enables vendors to build integrated networking security solutions while reducing total cost and time to market.


In order to obtain the full Inside Secure White Paper on TRNG (PDF file), clik in the link below:
https://www.insidesecure.com/Company/More/whitepapers/The-importance-of-true-Randomness-in-Cryptography

For more information, please drop me a note.

With best regards,

/Mauro

IPro   -   Great Silicon IP

Your virtual one-stop shop for advanced   digital   IP   in   Israel.

Packet Protocols - Security - CPUs

IPro Silicon IP Ltd.

+972 (545) 441579

mauro@ipro-great-ip.com

www.ipro-great-ip.com

C o p y r i g h t    (C)    I P r o    S i l i c o n    I P    L t d .   -    a l l    r i g h t s    r e s e r v e d .