// This is a quick analysis of Linux's use of RDRAND. All double-slash (//)

// style comments are my own, all slash-star (/*) style comments are from the

// original code. This was written by Taylor Hornby (@DefuseSec).

// This is part of the drivers/char/random.c file.

// I have re-ordered the procedures for clarity. Everything inside them (except

// comments) is exactly as you will find it in linux-3.11.tar.xz

// This comment says it 'does not use' the hardware RNG. It actually does.

/*

* This function is the exported kernel interface. It returns some

* number of good random numbers, suitable for key generation, seeding

* TCP sequence numbers, etc. It does not use the hw random number

* generator, if available; use get_random_bytes_arch() for that.

*/

void get_random_bytes ( void * buf , int nbytes )

{

extract_entropy ( & nonblocking_pool , buf , nbytes , 0 , 0 ) ;

}

EXPORT_SYMBOL ( get_random_bytes ) ;

// This one is called by get_random_bytes above.

static ssize_t extract_entropy ( struct entropy_store * r , void * buf ,

size_t nbytes , int min , int reserved )

{

ssize_t ret = 0 , i ;

__u8 tmp [ EXTRACT_SIZE ] ;

unsigned long flags ;

/* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */

if ( fips_enabled ) {

spin_lock_irqsave ( & r -> lock , flags ) ;

if ( ! r -> last_data_init ) {

r -> last_data_init = true ;

spin_unlock_irqrestore ( & r -> lock , flags ) ;

trace_extract_entropy ( r -> name , EXTRACT_SIZE ,

r -> entropy_count , _RET_IP_ ) ;

xfer_secondary_pool ( r , EXTRACT_SIZE ) ;

extract_buf ( r , tmp ) ;

spin_lock_irqsave ( & r -> lock , flags ) ;

memcpy ( r -> last_data , tmp , EXTRACT_SIZE ) ;

}

spin_unlock_irqrestore ( & r -> lock , flags ) ;

}

trace_extract_entropy ( r -> name , nbytes , r -> entropy_count , _RET_IP_ ) ;

xfer_secondary_pool ( r , nbytes ) ;

nbytes = account ( r , nbytes , min , reserved ) ;

while ( nbytes ) {

// Each iteration of this loop:

// - Extracts 'EXTRACT_SIZE' bytes from extract_buf

// - Panic if the just-extracted bytes are the same as the

// previously-extracted bytes.

// - Copy either EXTRACT_SIZE or nbytes into the output.

extract_buf ( r , tmp ) ;

if ( fips_enabled ) {

spin_lock_irqsave ( & r -> lock , flags ) ;

if ( ! memcmp ( tmp , r -> last_data , EXTRACT_SIZE ) )

panic ( "Hardware RNG duplicated output!

" ) ;

memcpy ( r -> last_data , tmp , EXTRACT_SIZE ) ;

spin_unlock_irqrestore ( & r -> lock , flags ) ;

}

i = min_t ( int , nbytes , EXTRACT_SIZE ) ;

memcpy ( buf , tmp , i ) ;

nbytes -= i ;

buf += i ;

ret += i ;

}

/* Wipe data just returned from memory */

memset ( tmp , 0 , sizeof ( tmp ) ) ;

return ret ;

}

// This fills 'out' with EXTRACT_BYTES random bytes. It's what extract_entropy

// uses to fill its output buffer.

static void extract_buf ( struct entropy_store * r , __u8 * out )

{

// Skip all this stuff because it doesn't matter for the point I want to

// make...

int i ;

union {

__u32 w [ 5 ] ;

unsigned long l [ LONGS ( EXTRACT_SIZE ) ] ;

} hash ;

__u32 workspace [ SHA_WORKSPACE_WORDS ] ;

__u8 extract [ 64 ] ;

unsigned long flags ;

/* Generate a hash across the pool, 16 words (512 bits) at a time */

sha_init ( hash. w ) ;

spin_lock_irqsave ( & r -> lock , flags ) ;

for ( i = 0 ; i < r -> poolinfo -> poolwords ; i += 16 )

sha_transform ( hash. w , ( __u8 * ) ( r -> pool + i ) , workspace ) ;

/*

* We mix the hash back into the pool to prevent backtracking

* attacks (where the attacker knows the state of the pool

* plus the current outputs, and attempts to find previous

* ouputs), unless the hash function can be inverted. By

* mixing at least a SHA1 worth of hash data back, we make

* brute-forcing the feedback as hard as brute-forcing the

* hash.

*/

__mix_pool_bytes ( r , hash. w , sizeof ( hash. w ) , extract ) ;

spin_unlock_irqrestore ( & r -> lock , flags ) ;

/*

* To avoid duplicates, we atomically extract a portion of the

* pool while mixing, and hash one final time.

*/

sha_transform ( hash. w , extract , workspace ) ;

memset ( extract , 0 , sizeof ( extract ) ) ;

memset ( workspace , 0 , sizeof ( workspace ) ) ;

/*

* In case the hash function has some recognizable output

* pattern, we fold it in half. Thus, we always feed back

* twice as much data as we output.

*/

hash. w [ 0 ] ^= hash. w [ 3 ] ;

hash. w [ 1 ] ^= hash. w [ 4 ] ;

hash. w [ 2 ] ^= rol32 ( hash. w [ 2 ] , 16 ) ;

// Ah, here we are. Finally, we found RDRAND.

// This XOR's RDRAND *directly* into the output buffer, right before

// returning.

/*

* If we have a architectural hardware random number

* generator, mix that in, too.

*/

for ( i = 0 ; i < LONGS ( EXTRACT_SIZE ) ; i ++ ) {

unsigned long v ;

// arch_get_random is RDRAND.

if ( ! arch_get_random_long ( & v ) )

break ;

hash. l [ i ] ^= v ;

}

// SIMPLICIO: Why is that a problem? I thought if you XOR a non-random

// stream with a random one, you get a random one? Remember,

// one-time-pads and such?

//

// SALVIATI: Right, that's true. Even if RDRAND returns all zeroes, or some

// completely predictable sequence, the output will be random as

// long as it was random before the XOR.

//

// SIMPLICIO: So what's the problem, then? It seems like having RDRAND here

// can only make things better...

//

// SALVIATI: Ah, that's true if RDRAND might only be a weak source of

// entropy, but if it's *actively* malicious, it could seriously

// compromise the security of the output. For example, it could

// purposely return the inverse of the bits it's going to be

// XORed with, resulting in this function filling 'out' with zero

// bytes.

//

// SIMPLICIO: That's rediculous! How could RDRAND know which bits it's going

// to be XORed with? There's no way one instruction could figure

// all of that out.

//

// SALVIATI: Actually, it's quite possible. The procesor wouldn't even have

// to be smart about it. Chances are, the bits it's going to be

// XORed with are in cache (which is inside the CPU), so if the

// CPU had RDRAND return the XOR of all longs in the cache, it

// would cancel out and information about the state of the cache

// would leak out through the RNG. There are plenty of other

// ways. This is the CPU, remember. It can pretty much do

// anything it wants.

//

// SIMPLICIO: Ok, I see how this use of RDRAND could *in theory* weaken the

// whole RNG. But wouldn't that be pretty easy to detect, and

// can't we trust Intel? If the NSA has their hand up Intel's

// ass, wouldn't there be easier ways of backdooring a system?

//

// SALVIATI: The RDRAND backdoor could be made so that it only activates

// under certain, very specific, conditions. For example, it

// might only activate when RAX contains 0x632472F72B3FB507,

// which is extremely unlikely to happen during normal use, but

// could be made to happen by sending the system a TCP packet,

// web page, etc, containing that value. So, if it existed, it

// would be extremely difficult to detect. It's possible in

// principal to reverse engineer the CPU itself, but it's

// extremely expensive -- and destructive -- so you can't check

// all of the CPUs you actually use for backdoors. Sure, if the

// NSA controlled Intel, there would be easier ways to backdoor

// a system, but backdooring the RNG is nice, because it's

// passive: You don't have to *do* anything to a system in order

// to break it. You can just listen to the system's network

// traffic and use your RNG backdoor to decrypt it. Futher, it's

// bad design to combine two RNGs by XORing them together. They

// may be correlated (by accident or on purpose) in subtle ways

// that cancel out security. To be honest, I'm not exactly sure

// what the best way would be, but it certainly isn't XOR.

//

memcpy ( out , & hash , EXTRACT_SIZE ) ;

memset ( & hash , 0 , sizeof ( hash ) ) ;