Reduced Entropy in rand() and random()

TL;DR: Don't rely on undefined behavior, even when you think it should work.

---

I recently reported a minor issue to the FreeBSD security team.

The libc random functions had code^1,2 designed to run when /dev/random is not available. This can easily occur in a chroot or jail environment.

if (!done) {
        struct timeval tv;
        unsigned long junk;

        gettimeofday(&tv, NULL);
        srandom((getpid() << 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk);
        return;
}

This code is designed provide a minimal amount of entropy in the "failure" case. Unfortunately, it doesn't even provide the entropy it claims to. This is a minor issue because getpid, getimeday, and a single long variable don't provide a lot of entropy in the first place: (only $log_2{sizeof(long)}$ bits).

The point of the junk value is to add entropy by using uninitialized memory. This relies on the compiler being "stupid" enough not optimize it away.

Unfortunately clang and newer versions of gcc are smart enough to use the undefined behavior in undesired ways.

clang ³ removes any computation which relies on the undefined behavior and so produces the following object code:

 af0:   e8 5f fc ff ff          callq  754 <gettimeofday@plt>
 af5:   e8 7a fc ff ff          callq  774 <getpid@plt>
 afa:   e8 65 fc ff ff          callq  764 <srandom@plt>

Note that the junk variable is entirely unused and that the xor operation between gettimeofday and getpid is non-existent.

gcc 4.6 ⁴ outputs:

 ce8:   e8 03 fa ff ff          callq  6f0 <gettimeofday@plt>
 ced:   e8 4e fa ff ff          callq  740 <getpid@plt>
 cf2:   48 8b 7c 24 08          mov    0x8(%rsp),%rdi
 cf7:   48 33 3c 24             xor    (%rsp),%rdi
 cfb:   c1 e0 10                shl    $0x10,%eax
 cfe:   48 98                   cltq
 d00:   48 31 c7                xor    %rax,%rdi
 d03:   e8 28 fa ff ff          callq  730 <srandom@plt>

Note that in this case the junk value appears to be (%rsp) which isn't all that random.

gcc 4.2⁵ produces the following code

with the junk variable

 d9f:   e8 18 fa ff ff          callq  7bc <gettimeofday@plt>
 da4:   e8 43 fa ff ff          callq  7ec <getpid@plt>
 da9:   48 8b 3c 24             mov    (%rsp),%rdi
 dad:   48 33 7c 24 08          xor    0x8(%rsp),%rdi
 db2:   c1 e0 10                shl    $0x10,%eax
 db5:   48 98                   cltq
 db7:   48 31 c7                xor    %rax,%rdi
 dba:   48 31 df                xor    %rbx,%rdi
 dbd:   e8 1a fa ff ff          callq  <srandom@plt>

and without:

 d9f:   e8 18 fa ff ff          callq  7bc <gettimeofday@plt>
 da4:   e8 43 fa ff ff          callq  7ec <getpid@plt>
 da9:   48 8b 3c 24             mov    (%rsp),%rdi
 dad:   48 33 7c 24 08          xor    0x8(%rsp),%rdi
 db2:   c1 e0 10                shl    $0x10,%eax
 db5:   48 98                   cltq
 db7:   48 31 c7                xor    %rax,%rdi
 dba:   e8 1d fa ff ff          callq  7dc <srandom@plt>

The base version of gcc isn't vulnerable. However, with the upcoming switch to the clang compiler the FreeBSD does become vulnerable.

The first proposed fix was to add the volatile type qualifier to the junk variable. While this seemed to fix the code generation issue I didn't believe this to be a valid fix as the behavior is still undefined⁶ (I misread text of the standard). Additionally, the value is likely have be very predictable. A preference was expressed to remove the junk variable as using it may leak a small amount of stack data.

I proposed the simple and obvious fix of removing the use of the junk variable⁷

In a brief survey of other libraries I noticed similar issues. I will attempt to notify the vendors

It should be obvious, but undefined behavior is undefined and can't be relied on to ever to give a sensible result.

1. random.c r165903 (line 316)
2. rand.c r241046 (line 131)
3. FreeBSD clang version 3.1 (branches/release_31 156863) 20120523 compiled with -O2 or -O3
4. gcc46 (FreeBSD Ports Collection) 4.6.4 20120608 (prerelease) compiled with -O2
5. gcc (GCC) 4.2.1 20070831 patched [FreeBSD] compiled with -O3
6. sections 5.1.2.2.3 and 6.7.2.4 of ISO9899
7. svn commit r241373

Edit 2010-10-10: update the paragraph referring to undefined behavior of volatile.