RdRand

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[a] and is part of the Intel 64 and IA-32 instruction set architectures. AMD added support for the instruction in June 2015.[4]

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]

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]

Overview[edit]

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 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.

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.4Gbit/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[edit]

On an Intel Core i7-7700K, 4500 MHz (45 x 100MHz) 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 it 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.

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[edit]

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]

Sample x86 asm code to check upon RDRAND instruction[edit]

; using NASM syntax

section .data
	msg db "0x00000000",10

section .text
global _start
_start:
	mov eax,1
	cpuid
	bt ecx,30
	mov edi,1 ; exit code: failure
	jnc .exit

	; rdrand sets CF=0 if no random number
	; was available. Intel documentation
	; recommends 10 retries in a tight loop
	mov ecx,11
.loop1:
	sub ecx, 1
	jz .exit ; exit code is set already
	rdrand eax
	jnc .loop1

	; convert the number to ASCII
	mov edi,msg+9
	mov ecx,8
.loop2:
	mov edx,eax
	and edx,0Fh
	; add 7 to nibbles of 0xA and above
	; to align with ASCII code for 'A'
	; ('A' - '0') - 10 = 7
	xor r9d, r9d
        lea r8d, [r9+7] ; r8=7
	cmp dl,9
	cmova r9,r8
	add edx,r9d
	add [rdi],dl
	shr eax,4
	sub edi, 1
	sub ecx, 1
        jnz .loop2

	mov eax,1 ; SYS_WRITE
	mov edi,eax ; stdout=SYS_WRITE=1
	mov esi,msg
	mov edx,11
	syscall

	xor edi,edi ; exit code zero: success
.exit:
	mov eax,60 ; SYS_EXIT
	syscall

Applications[edit]

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

The first 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[22].

Reception[edit]

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

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[23]]: '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.[25][26] 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.[27][28][29]

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"[25][30]

See also[edit]

Notes[edit]

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

References[edit]

  1. ^ Hofemeier, Gael (2011-06-22). "Find out about Intel's new RdRand Instruction". Intel Developer Zone Blogs. Retrieved 30 December 2013. 
  2. ^ a b c d "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. 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. ^ a b 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. ^ Route, Matthew (August 10, 2017). "Radio-flaring Ultracool Dwarf Population Synthesis". The Astrophysical Journal. 845: 66. 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. ^ Route, Matthew (August 10, 2017). "Radio-flaring Ultracool Dwarf Population Synthesis". The Astrophysical Journal. 845: 66. doi:10.3847/1538-4357/aa7ede. 
  23. ^ a b 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. 
  24. ^ Ts'o, Theodore (September 6, 2013). "I am so glad I resisted pressure from Intel engineers to let /dev/random rely.." 
  25. ^ a b Richard Chirgwin (2013-12-09). "FreeBSD abandoning hardware randomness". The Register. 
  26. ^ Gavin Clarke (10 September 2013). "Torvalds shoots down call to yank 'backdoored' Intel RdRand in Linux crypto". theregister.co.uk. Retrieved 12 March 2014. 
  27. ^ 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. 
  28. ^ 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. 
  29. ^ Daniel J. Bernstein; Tanja Lange (16 May 2014). "Randomness generation" (PDF). Retrieved 9 April 2015. 
  30. ^ "FreeBSD Quarterly Status Report". Freebsd.org. Retrieved 2014-01-30. 

External links[edit]