Random Number Generators

Introduction

Random Number Generators (RNGs) are used in many fields to create randomness. In cryptography, they are often used for generating cryptographically secure keys and padding. For example, take RSA key pair generation and OAEP.

RNG categories

RNGs can be categorized into two:

• Non-deterministic Random Bit Generators (NRBGs) 
• Deterministic Random Bit Generators (DRBGs)

A NRBG generates a sequence of bits non-deterministically using a physical process that is unpredictable. For this reason it is said to produce true random bits, and often called a True Random Number Generator (TRNG).
In contrast, a DRBG uses an algorithm to generate a sequence of random bits from a secret initial value called the seed. Because of this deterministic nature, it is said to produce pseudorandom bits, and often called a Pseudo-Random Number Generator (PRNG). The output will be unpredictable as long as the seed has sufficient entropy and it is kept secret.

NIST recommendations

In their SP 800-90 special publications NIST provides recommendations on the construction and validation of RBGs that can be used for cryptographic applications. Very brief description of each is given below. Please refer to their latest revisions for details.

• SP 800-90A
  Addresses the construction of approved DRBG mechanisms. The latest revision (revision 1 at the time of this writing) provides following DRGB algorithm specifications based on hash functions and block ciphers that use NIST approved hash functions, keyed hash functions and block ciphers in counter mode respectively.

• HASH DRBG
• HMAC DRBG
• CTR DRBG

• SP 800-90B
  Specifies how to design and test entropy sources that can be used by RBGs.

• SP 800-90C
  Addresses the construction of RBGs from the mechanisms in SP 800-90A and the entropy sources in SP 800-90B.

RNGs and Linux

Linux makes its RNGs available to user space as character devices and the kernel APIs provide access to random numbers in the kernel space.

If a hardware RNG is available it will be available from /dev/hwrng. Linux kernel PRNG is available from /dev/urandom for non-blocking pool and from /dev/random for blocking pool.

Kernels APIs get_random_bytes_arch and get_random_bytes provide access to random bytes from hardware RNG and the PRNG non-blocking pool respectively.

Linux kernel PRNG implementation is found in /drivers/char/random.c in the source. It is characterized by entropy pool mixing, entropy estimation and the output generation functions as discussed in the paper The Linux Pseudorandom Number Generator Revisited by Lacharme, Roeck, Strubel, and Videau.

General structure of Linux PRNG

See the source file for the details of mixing and output generation as it contains details for a specific kernel version. Older kernels used LFSRs for mixing and SHA-1 for output generation whereas new ones (4.8 onward) seem to use ChaCha20.

The Linux rngd can be used to feed random data to kernel input pool. It will check the data to ensure that it has sufficient entropy and by default will use hardware RNG, if available, as the source.

OpenSSL RNGs

One can use APIs available in OpenSSL to obtain random data for their applications, specially if cryptographically secure random data is needed. By default OpenSSL uses a MD5 based random number generator.
To use NIST SP800-90 approved generators one should use an FIPS enabled OpenSSL library. In FIPS mode it supports HASH, HMAC and AES-CTR mode DRBGs, 256-bit AES-CTR based DRBG being the default. Refer OpenSSL FIPS Object Module user guide for DRBG API details.

Evaluating the randomness of RNGs

NIST special publication SP 800-22 describes a set of statistical tests for randomness, specifically focusing on randomness required for cryptographic purposes. These tests are made available through a free software called the NIST Statistical Test Suite (NIST STS Tool) that one can download from NIST site, build and use for performing these tests. The suite includes 15 tests. Refer the latest revision of the publication for test details and how to use the software.

References:

• NIST special publications SP 800-90A, SP 800-90B, SP 800-90C, SP 800-22
• The Linux Pseudorandom Number Generator Revisited by Lacharme, Roeck, Strubel, and Videau
• LWN article LCE: Don't play dice with random numbers
• OpenSSL FIPS Object Module v2.0 User Guide

Hardware security features of modern secure processors

Modern secure processors offer a wide range of hardware security features that are essential for embedded systems such as secure payment terminals. Listed below are some common such features found in secure processors in today's market. The list was compiled based on the secure processors available from NXP, Microchip and Maxim Integrated. You can find all the details mentioned here in publically available documentation (processor reference manuals, datasheets and application notes), or publically available source code (U-boot and Linux). It is also possible to obtain all the security related details pertaining to a processor from the vendor using an NDA.

Secure boot 

Secure boot feature in the processor internal boot ROM makes sure the processor is running authenticated code. This is done by digitally signing the firmware. Signing provides integrity (an attacker cannot modify the firmware) and authenticity (firmware comes from a trusted party). The process is shown in the figure below.

In simple terms, once the firmware is ready, it is digitally signed using the private key. The signature and the certificate is attached to the firmware. On the device, the digital signature is verified at load time using the public key. Usually the public key hash (rather than the key itself) is stored in device OTP memory. In the verification phase, the public key embedded in the certificate is hashed and compared against the one stored in OTP to verify the public key.
Find more about secure boot in [1] and [2].

Firmware signing and verification

Tamper detection circuitry

A tamper can trigger immediate erasure of sensitive data stored in a tamper protected memory. This may also put the processor into a failure state where the operations it can perform are limited. An external battery source is often used to keep the tamper circuitry active during a primary power failure/removal.
Tamper can be categorized into two: internal and external.

• Internal tamper
  This is the monitoring of the behavior of properties internal to the chip such as voltage, temperature and RTC clock for anomalies. Stability and reliability of the system is questionable when these properties are not within their desired operating ranges.

•  External tamper
  This is provided through a chip input pin where the tamper circuitry compares the received signal with the desired signal. Tamper is triggered when the input signal differs from the expected signal. External tamper can be used to detect an unauthorized tampering such as opening a device enclosure.
  External tamper can be categorized into two: passive and active.
  
  • Passive tamper
    The desired signal to which the input is compared is fixed, that is, it expects the input signal to have a fixed level (0 or 1).
  • Active tamper
    The desired signal to which the input is compared varies with time. An active tamper output pin generates a waveform. This is fed to the active tamper input pin. The input signal is then compared against the original waveform by the active tamper circuitry.
  • Another type of tamper detects the tampering of an on-chip ultra-fine mesh, also known as a shield. This is usually used to prevent microprobing of on-chip non-volatile secure memory.Find more about secure shields in [3] and [4].

Tamper protected on-chip secure memory

Secure memory is used for storing sensitive information, long-term (e.g. keys) or short-term (e.g. keys, payment card data) depending on their type.
This is usually a limited amount of battery backed non-volatile secure memory, ranging from few hundred bits to few Kbs, supplemented with volatile secure memory, usually having few Kbs of storage. Their contents are rapidly erased on the event of a tamper.
As stated in the tamper detection section, the non-volatile memory can be tamper protected with an on-chip ultra-fine mesh to prevent microprobing.

Secure real-time clock (RTC), monotonic counters and watchdogs

RTCs are used for system time keeping.
Monotonic counters are either decrement-only or increment-only counters. They are useful for applications that require a counter that does not repeat any of its previous values, and are often used for preventing replay attacks.
Watchdog timers are available in secure and non-secure processors. They are often used for recovering from processor malfunctions. Limiting the CPU time available for a code is another use where they can be used as a security measure against running unnecessary and potentially harmful/untrusted code.
RTCs and monotonic counters are very low power and have battery backup to retain their values over power cycles, and, they are often tamper protected.

Memory encryption, bus encryption and memory integrity checkers

Memory and bus encryption can be used for further strengthening the security of the data exchanged between the CPU and external memory by providing authenticity.
Integrity checkers are used for validating the integrity of memory regions during run time.

NIST compliant true and pseudo random number generators

Any process that requires randomness integrated to it can use random numbers. They are often used for generating cryptographically secure keys and padding.
A common configuration would be the construction of a NIST SP 800-90C compliant RBG (Random Bit Generator) from a NIST SP 800-90B compliant entropy source and a NIST SP 800-90A compliant DRBG (Deterministic Random Bit Generator).

Hardware cryptographic accelerators 

These can include acceleration for hashing (e.g SHA), block ciphers (e.g. TDES/AES), AEAD (e.g. AES-CCM, AES-GCM), MAC (e.g. HMAC) and public-key cryptography (e.g. RSA, DSA, EC).
Block ciphers and public key cryptography modules may also provide additional protection against side-channel attacks such as power and timing analysis.  

 

In addition to the above features ARM provides ARM TrustZone for its Cotex-A and some of its latest Cortex-M based systems. I don't have experience using it to comment on it here.

You can find more about these and additional security features from processor manuals and application notes from the processor vendor. Specifically, Maxim Integrated provides a wealth of valuable information on their embedded security application notes. 

 

References:

[1] Maxim Integrated application note Secure the IoT: Part 2, A Secure Boot, the "Root of Trust" for Embedded Devices

[2] NXP application note Secure Boot on i.MX50, i.MX53, i.MX 6 and i.MX7 Series using HABv4

[3] Cryptographically secure shields by Jean-Michel Cioranesco, Jean-Luc Danger, Tarik Graba, Sylvain Guilley, Yves Mathieu, David Naccache, Xuan Thuy Ngo

[4] Random Active Shield by Sébastien Briais, Jean-Michel Cioranesco, Jean-Luc Danger, Sylvain Guilley, David Naccache, Thibault Porteboeuf

 

Protecting against buffer overflows (using gcc)

We try our best to avoid buffer overflows, but still it is possible that one creeps into our code. When this happens, there are some gcc compiler options and macros that we can use to protect our program from buffer overflow exploits.
Sometimes these features may be enabled by default. But this has not been the case for the cross toolchains that I have used.

• -fstack-protector gcc option and its variants
  • Works by placing a small integer, the value of which is randomly chosen at program start, in memory just before the stack return pointer (stack canaries)
  • Attacker has to write past this value to run his code using a buffer overflow attack
  • Applicable only to stack (not heap)
  • When detected, aborts the program
    *** stack smashing detected ***: ./overflow terminated
     Aborted
  • Chooses any function that declares a character array of eight bytes or more in length on its stack  
  • -fstack-protector-all is similar to -fstack-protector, but applied to every function
  • This option comes with a cost on program size and performance
  • See "Strong" stack protection for GCC LWN article for more details

• _FORTIFY_SOURCE macro
  • Defining this macro causes some lightweight checks to be performed to detect some buffer overflow errors when employing various string and memory manipulation functions. See feature test macros for more details.
    e.g. When this is defined, instead of calling memcpy, it will call a object size checking function __builtin___memcpy_chk
  • Need to enable optimization to define this
    e.g. gcc -D_FORTIFY_SOURCE=1 -O0 -o overflow overflow_test.c
    will say
    #  warning _FORTIFY_SOURCE requires compiling with optimization (-O)
  • Can detect both stack and heap buffer overflows
  • When detected, aborts the program
    *** buffer overflow detected ***: ./overflow terminated
    Aborted
    

Mitigating software security vulnerabilities of your embedded system

Consumer electronics, healthcare, automotive, payment systems, industrial control and you name it, embedded system are everywhere. As someone working on embedded system firmware and applications, I think the following simple guidelines can make your embedded system more secure.

• Regularly check for security vulnerabilities of the software components of your system and apply updates/patches.
  For example, suppose you are using Linux as the OS and OpenSSL library in your secure applications. You can look up vulnerabilities of these components (and many other) in the CVE Details security vulnerability datasource. OpenSSL also maintains its own page for vulnerabilities.
• Maintain a minimum configuration for all the components.
  This means that you should remove features that are not needed for your system. For example, 
• Remove unnecessary kernel modules.
• Strip down busybox and keep only the commands that are absolutely necessary.
• Strip down 3rd-party libraries to keep only the features that your applications need.
• Use ASLR (Address Space Layout Randomization).
  Modern Linux kernels enable this by default and set it to 2 (full randomization). You can read its value from the proc filesystem entry /proc/sys/kernel/randomize_va_space.
• Configure Linux kernel to use stack protection.
  Note that this will inevitably increase the size of the kernel. The LWN article "Strong" stack protection for GCC describes stack protection in general and the configurations CONFIG_CC_STACKPROTECTOR_NONE, CONFIG_CC_STACKPROTECTOR, and CONFIG_CC_STACKPROTECTOR_STRONG available for the kernel.
• Follow secure coding practices.
  You can find lots of useful secure coding guidelines for commonly used programming languages including c and c++ at Carnegie Mellon University SEI CERT coding standards.
• Use code analysis tools to help find vulnerabilities in your code and fix them.
• Use your compiler wisely.
  Modern c/c++ compilers are smart and they can help you a lot in finding issues in your code and protecting it against vulnerabilities.
• Turn on all warnings. Pay close attention to the warnings. 
• Use options to protect your application. Here and here you can find good concise descriptions of these options, and you can always look up GCC documentation. Note however that some of these options may not be available in your cross-compiler.
• Pay attention to the optimization level that you are using and its implications. Highly optimized code can sometimes make some of your secure coding practices useless (for example, clearing buffers to limit the lifetime of sensitive data in a highly optimized code).
• This is not related to software, but worth mentioning here. It is possible that your hardware itself is vulnerable. This is evident from the recent Meltdown and Spectre attacks. So, applying software updates/patches as mentioned in the very first item helps mitigate these vulnerabilities. The processor vendor usually informs of any hardware vulnerabilities and suggests software mitigation techniques you can use until a new hardware revision is available.