RdRand

Last updated

RDRAND (previously known as Bull Mountain [1] ) is an instruction for returning random numbers from an Intel on-chip hardware random number generator which has been seeded by an on-chip entropy source. [2] RDRAND is available in Ivy Bridge processors [lower-alpha 1] and is part of the Intel 64 and IA-32 instruction set architectures. AMD added support for the instruction in June 2015. [4]

Intel American semiconductor chip manufacturer

Intel Corporation is an American multinational corporation and technology company headquartered in Santa Clara, California, in the Silicon Valley. It is the world's second largest and second highest valued semiconductor chip manufacturer based on revenue after being overtaken by Samsung Electronics, and is the inventor of the x86 series of microprocessors, the processors found in most personal computers (PCs). Intel ranked No. 46 in the 2018 Fortune 500 list of the largest United States corporations by total revenue. Intel is incorporated in Delaware.

Hardware random number generator device that generates random numbers from physical processes, rather than by means of an software algorithm

In computing, a hardware random number generator (HRNG) or true random number generator (TRNG) is a device that generates random numbers from a physical process, rather than by means of an algorithm. Such devices are often based on microscopic phenomena that generate low-level, statistically random "noise" signals, such as thermal noise, the photoelectric effect, involving a beam splitter, and other quantum phenomena. These stochastic processes are, in theory, completely unpredictable, and the theory's assertions of unpredictability are subject to experimental test. This is in contrast to the paradigm of pseudo-random number generation commonly implemented in computer programs.

Ivy Bridge (microarchitecture) Intel processor family

Ivy Bridge is the codename for the "third generation" of the Intel Core processors. Ivy Bridge is a die shrink to 22 nanometer manufacturing process based on the 32 nanometer Sandy Bridge - see tick–tock model. The name is also applied more broadly to the 22 nm die shrink of the Sandy Bridge microarchitecture based on FinFET ("3D") Tri-Gate transistors, which is also used in the Xeon and Core i7 Ivy Bridge-EX (Ivytown), Ivy Bridge-EP and Ivy Bridge-E microprocessors released in 2013.

Contents

The random number generator is compliant with security and cryptographic standards such as NIST SP 800-90A, [5] FIPS 140-2, and ANSI X9.82. [2] Intel also requested Cryptography Research Inc. to review the random number generator in 2012, which resulted in the paper Analysis of Intel's Ivy Bridge Digital Random Number Generator. [6]

NIST SP 800-90A is a publication by the National Institute of Standards and Technology with the title Recommendation for Random Number Generation Using Deterministic Random Bit Generators. The publication contains the specification for three allegedly cryptographically secure pseudorandom number generators for use in cryptography: Hash_DRBG, HMAC_DRBG, and CTR_DRBG.

The Federal Information Processing Standard (FIPS) Publication 140-2,, is a U.S. government computer security standard used to approve cryptographic modules. The title is Security Requirements for Cryptographic Modules. Initial publication was on May 25, 2001 and was last updated December 3, 2002.

RDSEED is similar to RDRAND and provides higher level access to the entropy hardware. The RDSEED generator and processor instruction rdseed are available with Intel Broadwell CPUs [7] and AMD Zen CPUs. [8]

Broadwell (microarchitecture) Intel processor family

Broadwell is Intel's codename for the 14 nanometer die shrink of its Haswell microarchitecture. It is a "tick" in Intel's tick–tock principle as the next step in semiconductor fabrication. Like some of the previous tick-tock iterations, Broadwell did not completely replace the full range of CPUs from the previous microarchitecture (Haswell), as there were no low-end desktop CPUs based on Broadwell.

Zen (microarchitecture) AMD processor microarchitecture

Zen is the codename for a computer processor microarchitecture from AMD, and was first used with their Ryzen series of CPUs in February 2017. The first Zen-based preview system was demonstrated at E3 2016, and first substantially detailed at an event hosted a block away from the Intel Developer Forum 2016. The first Zen-based CPUs codenamed "Summit Ridge" reached the market in early March 2017, Zen-derived Epyc server processors launched in June 2017 and Zen-based APUs arrived in November 2017.

Overview

The CPUID instruction can be used to check whether the central processing unit (CPU) supports the RDRAND instruction on both AMD and Intel CPUs. If supported, bit 30 of the ECX register is set after calling CPUID standard function 01H. [9] AMD processors are checked for the feature using the same test. [10] RDSEED availability can be checked on Intel CPUs in a similar manner. If RDSEED is supported, the bit 18 of the EBX register is set after calling CPUID standard function 07H. [11]

The CPUID instruction is a processor supplementary instruction for the x86 architecture allowing software to discover details of the processor. It was introduced by Intel in 1993 when it introduced the Pentium and SL-enhanced 486 processors.

Central processing unit Central component of any computer system which executes input/output, arithmetical, and logical operations

A central processing unit (CPU), also called a central processor or main processor, is the electronic circuitry within a computer that carries out the instructions of a computer program by performing the basic arithmetic, logic, controlling, and input/output (I/O) operations specified by the instructions. The computer industry has used the term "central processing unit" at least since the early 1960s. Traditionally, the term "CPU" refers to a processor, more specifically to its processing unit and control unit (CU), distinguishing these core elements of a computer from external components such as main memory and I/O circuitry.

The opcode for RDRAND is 0x0F 0xC7, followed by a ModRM byte that specifies the destination register and optionally combined with a REX prefix in 64-bit mode. [12]

Intel Secure Key is Intel's name for both the RDRAND instruction and the underlying random number generator (RNG) hardware implementation, [2] which was codenamed "Bull Mountain" during development. [13] Intel calls their RNG a "digital random number generator" or DRNG. The generator takes pairs of 256-bit raw entropy samples generated by the hardware entropy source and applies them to an Advanced Encryption Standard (AES) (in CBC-MAC mode) conditioner which reduces them to a single 256-bit conditioned entropy sample. A deterministic random-bit generator called CTR_DRBG defined in NIST SP 800-90A is seeded by the output from the conditioner, providing cryptographically secure random numbers to applications requesting them via the RDRAND instruction. [2] [13] The hardware will issue a maximum of 511 128-bit samples before changing the seed value. Using the RDSEED operation provides access to the conditioned 256-bit samples from the AES-CBC-MAC.

Advanced Encryption Standard block cipher standard

The Advanced Encryption Standard (AES), also known by its original name Rijndael, is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.

CBC-MAC message authentication code algorithm

In cryptography, a cipher block chaining message authentication code (CBC-MAC) is a technique for constructing a message authentication code from a block cipher. The message is encrypted with some block cipher algorithm in CBC mode to create a chain of blocks such that each block depends on the proper encryption of the previous block. This interdependence ensures that a change to any of the plaintext bits will cause the final encrypted block to change in a way that cannot be predicted or counteracted without knowing the key to the block cipher.

The RDSEED instruction was added to Intel Secure Key for seeding another pseudorandom number generator, [14] available in Broadwell CPUs. The entropy source for the RDSEED instruction runs asynchronously on a self-timed circuit and uses thermal noise within the silicon to output a random stream of bits at the rate of 3 GHz, [15] slower than the effective 6.4 Gbit/s obtainable from RDRAND (both rates are shared between all cores and threads). [16] The RDSEED instruction is intended for seeding a software PRNG of arbitrary width, whereas the RDRAND is intended for applications that merely require high-quality random numbers. If cryptographic security is not required, a software PRNG such as Xorshift is usually faster. [17]

Performance

On an Intel Core i7-7700K, 4500 MHz (45 x 100 MHz) processor (Kaby Lake-S microarchitecture), a single RDRAND or RDSEED instruction takes 110ns or 463 clock cycles, regardless of the operand size (16/32/64 bits). This number of clock cycles applies to all processors with Skylake or Kaby Lake microarchitecture. On the Silvermont microarchitecture processors, each of the instructions take around 1472 clock cycles, regardless of the operand size; and on Ivy Bridge processors RDRAND takes up to 117 clock cycles. [18]

On an AMD Ryzen CPU, each of the instructions takes around 1200 clock cycles for 16-bit or 32-bit operand, and around 2500 clock cycles for a 64-bit operand.[ citation needed ]

An astrophysical Monte Carlo simulator examined the time to generate 107 64-bit random numbers using RDRAND on a quad-core Intel i7-3740 QM processor. They found that a C implementation of RDRAND ran about 2x slower than the default random number generator in C, and about 20x slower than the Mersenne Twister. Although a Python module of RDRAND has been constructed, it was found to be 20x slower than the default random number generator in Python. [19]

Compilers

GCC 4.6+ and Clang 3.2+ provide intrinsic functions for RdRand when -mrdrnd is specified in the flags, [20] also setting __RDRND__ to allow conditional compilation. Newer versions additionally provide immintrin.h to wrap these built-ins into functions compatible with version 12.1+ of Intel's C Compiler. These functions write random data to the location pointed to by their parameter, and return 1 on success. [21]

Applications

It is an option to generate cryptographically-secure random numbers using RDRAND and RDSEED in OpenSSL, to help secure communications.

The first[ citation needed ][ dubious – discuss ] scientific application of RdRand can be found in an astrophysics. Radio observations of low-mass stars and brown dwarfs have revealed that a number of them emit bursts of radio waves. These radio waves are caused by magnetic reconnection, the same process that causes solar flares on the Sun. RdRand was used to generate large quantities of random numbers for a Monte Carlo simulator, to model physical properties of the brown dwarfs and the effects of the instruments that observe them. They found that about 5% of brown dwarfs are sufficiently magnetic to emit strong radio bursts. They also evaluated the performance of the RdRand instruction in C and Python compared to other random number generators. [19]

Reception

In September 2013, in response to a New York Times article revealing the NSA's effort to weaken encryption, [22] Theodore Ts'o publicly posted concerning the use of RdRand for /dev/random in the Linux kernel: [23]

I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction. To quote from the [New York Times article [22] ]: 'By this year, the Sigint Enabling Project had found ways inside some of the encryption chips that scramble information for businesses and governments, either by working with chipmakers to insert back doors....' Relying solely on the hardware random number generator which is using an implementation sealed inside a chip which is impossible to audit is a BAD idea.

Linus Torvalds dismissed concerns about the use of RdRand in the Linux kernel, and pointed out that it is not used as the only source of entropy for /dev/random, but rather used to improve the entropy by combining the values received from RdRand with other sources of randomness. [24] [25] However, Taylor Hornby of Defuse Security demonstrated that the Linux random number generator could become insecure if a backdoor is introduced into the RdRand instruction that specifically targets the code using it. Hornby's proof-of-concept implementation works on an unmodified Linux kernel prior to version 3.13. [26] [27] [28] The issues was fixed in the linux kernel in 2013. (https://twitter.com/DefuseSec/status/862104797369036802?s=20)

Developers changed the FreeBSD kernel away from using RdRand and VIA PadLock directly with the comment "For [FreeBSD] 10, we are going to backtrack and remove RDRAND and Padlock backends and feed them into Yarrow instead of delivering their output directly to /dev/random. It will still be possible to access hardware random number generators, that is, RDRAND, Padlock etc., directly by inline assembly or by using OpenSSL from userland, if required, but we cannot trust them any more" [24] [29]

See also

Notes

  1. ↑ In some Ivy Bridge versions, due to a bug, the RdRand instruction causes an Illegal Instruction exception. [3]

Related Research Articles

In computer architecture, 64-bit integers, memory addresses, or other data units are those that are 64 bits wide. Also, 64-bit CPU and ALU architectures are those that are based on registers, address buses, or data buses of that size. 64-bit microcomputers are computers in which 64-bit microprocessors are the norm. From the software perspective, 64-bit computing means the use of code with 64-bit virtual memory addresses. However, not all 64-bit instruction sets support full 64-bit virtual memory addresses; x86-64 and ARMv8, for example, support only 48 bits of virtual address, with the remaining 16 bits of the virtual address required to be all 0's or all 1's, and several 64-bit instruction sets support fewer than 64 bits of physical memory address.

x86-64 type of instruction set which is a 64-bit version of the x86 instruction set

x86-64 is the 64-bit version of the x86 instruction set. It introduces two new modes of operation, 64-bit mode and compatibility mode, along with a new 4-level paging mode. With 64-bit mode and the new paging mode, it supports vastly larger amounts of virtual memory and physical memory than is possible on its 32-bit predecessors, allowing programs to store larger amounts of data in memory. x86-64 also expands general-purpose registers to 64-bit, as well extends the number of them from 8 to 16, and provides numerous other enhancements. Floating point operations are supported via mandatory SSE2-like instructions, and x87/MMX style registers are generally not used ; instead, a set of 32 vector registers, 128 bits each, is used. In 64-bit mode, instructions are modified to support 64-bit operands and 64-bit addressing mode. The compatibility mode allows 16- and 32-bit user applications to run unmodified coexisting with 64-bit applications if the 64-bit operating system supports them. As the full x86 16-bit and 32-bit instruction sets remain implemented in hardware without any intervening emulation, these older executables can run with little or no performance penalty, while newer or modified applications can take advantage of new features of the processor design to achieve performance improvements. Also, a processor supporting x86-64 still powers on in real mode for full backward compatibility, as x86 processors have done since the 80286.

Memory-mapped I/O (MMIO) and port-mapped I/O (PMIO) are two complementary methods of performing input/output (I/O) between the central processing unit (CPU) and peripheral devices in a computer. An alternative approach is using dedicated I/O processors, commonly known as channels on mainframe computers, which execute their own instructions.

In computing, Physical Address Extension (PAE), sometimes referred to as Page Address Extension, is a memory management feature for the x86 architecture. PAE was first introduced by Intel in the Pentium Pro, and later by AMD in the Athlon processor. It defines a page table hierarchy of three levels (instead of two), with table entries of 64 bits each instead of 32, allowing these CPUs to directly access a physical address space larger than 4 gigabytes (232 bytes).

In the 80386 microprocessor and later, virtual 8086 mode allows the execution of real mode applications that are incapable of running directly in protected mode while the processor is running a protected mode operating system. It is a hardware virtualization technique that allowed multiple 8086 processors to be emulated by the 386 chip; it emerged from the painful experiences with the 80286 protected mode, which by itself was not suitable to run concurrent real mode applications well.

In Unix-like operating systems, /dev/random, /dev/urandom and /dev/arandom are special files that serve as pseudorandom number generators. They allow access to environmental noise collected from device drivers and other sources. /dev/random typically blocks if there is less entropy available than requested; /dev/urandom typically never blocks, even if the pseudorandom number generator seed was not fully initialized with entropy since boot. /dev/arandom blocks after boot until the seed has been securely initialized with enough entropy, and then never blocks again. Not all operating systems implement the same methods for /dev/random and /dev/urandom and only a few provide /dev/arandom.

In computer security, executable-space protection marks memory regions as non-executable, such that an attempt to execute machine code in these regions will cause an exception. It makes use of hardware features such as the NX bit, or in some cases software emulation of those features. However technologies that somehow emulate or supply an NX bit will usually impose a measurable overhead; while using a hardware-supplied NX bit imposes no measurable overhead.

The Time Stamp Counter (TSC) is a 64-bit register present on all x86 processors since the Pentium. It counts the number of cycles since reset. The instruction RDTSC returns the TSC in EDX:EAX. In x86-64 mode, RDTSC also clears the higher 32 bits of RAX and RDX. Its opcode is 0F 31. Pentium competitors such as the Cyrix 6x86 did not always have a TSC and may consider RDTSC an illegal instruction. Cyrix included a Time Stamp Counter in their MII.

SSE4 is a SIMD CPU instruction set used in the Intel Core microarchitecture and AMD K10 (K8L). It was announced on September 27, 2006, at the Fall 2006 Intel Developer Forum, with vague details in a white paper; more precise details of 47 instructions became available at the Spring 2007 Intel Developer Forum in Beijing, in the presentation. SSE4 is fully compatible with software written for previous generations of Intel 64 and IA-32 architecture microprocessors. All existing software continues to run correctly without modification on microprocessors that incorporate SSE4, as well as in the presence of existing and new applications that incorporate SSE4.

In computing, entropy is the randomness collected by an operating system or application for use in cryptography or other uses that require random data. This randomness is often collected from hardware sources, either pre-existing ones such as mouse movements or specially provided randomness generators. A lack of entropy can have a negative impact on performance and security.

In computing, PSE-36 refers to a feature of x86 processors that extends the physical memory addressing capabilities from 32 bits to 36 bits, allowing addressing to up to 64 GB of memory. Compared to the Physical Address Extension (PAE) method, PSE-36 is a simpler alternative to addressing more than 4 GB of memory. It uses the Page Size Extension (PSE) mode and a modified page directory table to map 4 MB pages into a 64 GB physical address space. PSE-36's downside is that, unlike PAE, it doesn't have 4-KB page granularity above the 4 GB mark.

Advanced Vector Extensions are extensions to the x86 instruction set architecture for microprocessors from Intel and AMD proposed by Intel in March 2008 and first supported by Intel with the Sandy Bridge processor shipping in Q1 2011 and later on by AMD with the Bulldozer processor shipping in Q3 2011. AVX provides new features, new instructions and a new coding scheme.

An Advanced Encryption Standard instruction set is now integrated into many processors. The purpose of the instruction set is to improve the speed of applications performing encryption and decryption using Advanced Encryption Standard (AES). They are often implemented as instructions implementing a single round of AES along with a special version for the last round which has a slightly different method.

There are various implementations of the Advanced Encryption Standard, also known as Rijndael.

Intel Math Kernel Library is a library of optimized math routines for science, engineering, and financial applications. Core math functions include BLAS, LAPACK, ScaLAPACK, sparse solvers, fast Fourier transforms, and vector math. The routines in MKL are hand-optimized specifically for Intel processors.

Second Level Address Translation (SLAT), also known as nested paging, is a hardware-assisted virtualization technology which makes it possible to avoid the overhead associated with software-managed shadow page tables.

References

  1. ↑ Hofemeier, Gael (2011-06-22). "Find out about Intel's new RdRand Instruction". Intel Developer Zone Blogs. Retrieved 30 December 2013.
  2. 1 2 3 4 "Intel Digital Random Number Generator (DRNG): Software Implementation Guide, Revision 1.1" (PDF). Intel Corporation. 2012-08-07. Retrieved 2012-11-25.
  3. ↑ Desktop 3rd Generation Intel Core Processor Family, Specification Update (PDF). Intel Corporation. January 2013.
  4. ↑ "AMD64 Architecture Programmer's Manual Volume 3: General-Purpose and System Instructions" (PDF). AMD Developer Guides, Manuals & ISA Documents. June 2015. Retrieved 16 October 2015.
  5. ↑ Barker, Elaine; Kelsey, John (January 2012). "Recommendation for Random Number Generation Using Deterministic Random Bit Generators" (PDF). National Institute of Standards and Technology . Retrieved September 16, 2013.
  6. ↑ Hamburg, Mike; Kocher, Paul; Marson, Mark (2012-03-12). "Analysis of Intel's Ivy Bridge Digital Random Number Generator" (PDF). Cryptography Research, Inc. Archived from the original (PDF) on 2014-12-30. Retrieved 2015-08-21.
  7. ↑ Hofemeier, Gael (2012-07-26). "Introduction to Intel AES-NI and Intel SecureKey Instructions". Intel Developer Zone. Intel. Retrieved 2015-10-24.
  8. ↑ "AMD Starts Linux Enablement On Next-Gen "Zen" Architecture - Phoronix". www.phoronix.com. Retrieved 2015-10-25.
  9. ↑ "Volume 1, Section 7.3.17, 'Random Number Generator Instruction'" (PDF). Intel® 64 and IA-32 Architectures Software Developer’s Manual Combined Volumes: 1, 2A, 2B, 2C, 3A, 3B and 3C. Intel Corporation. June 2013. p. 177. Retrieved 24 June 2013. All Intel processors that support the RDRAND instruction indicate the availability of the RDRAND instruction via reporting CPUID.01H:ECX.RDRAND[bit 30] = 1
  10. ↑ "AMD64 Architecture Programmer's Manual Volume 3: General-Purpose and System Instructions" (PDF). AMD. June 2015. p. 278. Retrieved 15 October 2015. Support for the RDRAND instruction is optional. On processors that support the instruction, CPUID Fn0000_0001_ECX[RDRAND] = 1
  11. ↑ "Volume 1, Section 7.3.17, 'Random Number Generator Instruction'" (PDF). Intel® 64 and IA-32 Architectures Software Developer’s Manual Combined Volumes: 1, 2A, 2B, 2C, 3A, 3B and 3C. Intel Corporation. June 2013. p. 177. Retrieved 25 October 2015. All Intel processors that support the RDSEED instruction indicate the availability of the RDSEED instruction via reporting CPUID.(EAX=07H, ECX=0H):EBX.RDSEED[bit 18] = 1
  12. ↑ "Intel® Digital Random Number Generator (DRNG) Software Implementation Guide | Intel® Developer Zone". Software.intel.com. Retrieved 2014-01-30.
  13. 1 2 Taylor, Greg; Cox, George (September 2011). "Behind Intel's New Random-Number Generator". IEEE Spectrum .
  14. ↑ John Mechalas (November 2012). "The Difference Between RDRAND and RDSEED". software.intel.com. Intel Corporation. Retrieved 1 January 2014.
  15. ↑ Mechalas, John. "Intel Digital Random Number Generator (DRNG) Software Implementation Guide, Section 3.2.1 Entropy Source (ES)". https://software.intel.com . Intel. Retrieved 18 February 2015.External link in |website= (help)
  16. ↑ https://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide says 800 megabytes, which is 6.4 gigabits, per second
  17. ↑ The simplest 64-bit implementation of Xorshift has 3 XORs and 3 shifts; if these are executed in a tight loop on 4 cores at 2GHz, the throughput is 80 Gb/sec. In practice it will be less due to load/store overheads etc, but is still likely to exceed the 6.4 Gb/sec of RDRAND. On the other hand, the quality of RDRAND's numbers should be higher than that of a software PRNG like Xorshift.
  18. ↑ http://www.agner.org/optimize/instruction_tables.pdf
  19. 1 2 Route, Matthew (August 10, 2017). "Radio-flaring Ultracool Dwarf Population Synthesis". The Astrophysical Journal. 845: 66. arXiv: 1707.02212 . doi:10.3847/1538-4357/aa7ede.
  20. ↑ https://gcc.gnu.org/onlinedocs/gcc-4.8.5/gcc/X86-Built-in-Functions.html
  21. ↑ https://software.intel.com/en-us/node/523864
  22. 1 2 Perlroth, Nicole; Larson, Jeff; Shane, Scott (September 5, 2013). "N.S.A. Able to Foil Basic Safeguards of Privacy on Web". The New York Times. Retrieved November 15, 2017.
  23. ↑ Ts'o, Theodore (September 6, 2013). "I am so glad I resisted pressure from Intel engineers to let /dev/random rely..."
  24. 1 2 Richard Chirgwin (2013-12-09). "FreeBSD abandoning hardware randomness". The Register.
  25. ↑ Gavin Clarke (10 September 2013). "Torvalds shoots down call to yank 'backdoored' Intel RdRand in Linux crypto". theregister.co.uk. Retrieved 12 March 2014.
  26. ↑ Taylor Hornby (6 December 2013). "RDRAND backdoor proof of concept is working! Stock kernel (3.8.13), only the RDRAND instruction is modified" . Retrieved 9 April 2015.
  27. ↑ Taylor Hornby [@DefuseSec] (10 September 2013). "I wrote a short dialogue explaining why Linux's use of RDRAND is problematic. http://pastebin.com/A07q3nL3 /cc @kaepora @voodooKobra" (Tweet). Retrieved 11 January 2016– via Twitter.
  28. ↑ Daniel J. Bernstein; Tanja Lange (16 May 2014). "Randomness generation" (PDF). Retrieved 9 April 2015.
  29. ↑ "FreeBSD Quarterly Status Report". Freebsd.org. Retrieved 2014-01-30.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.