Topic: [BOUNTY] 0.2 BTC bounty for figuring out entropy in this python app (Read 2126 times)

Done!

Yes, thank you.

Runeks - can you confirm I should send the 0.2 BTC bounty to 1runeksijzfVxyrpiyCY2LCBvYsSiFsCm?

OpenSSL

OpenSSL implements such a hash-based entropy juicer. It provides a function RAND_add(buf, n, e) that adds a buffer of length n and entropy e to the entropy pool. Internally, the entry pool is just an MD5 or SHA1 hash state: RAND_add calls MD_update to add the bytes to a running hash computation. The parameter e is an assertion made by the caller about the entropy contained in buf. OpenSSL uses it to keep a running estimate of the total amount of entropy in the buffer. OpenSSL also provides a RAND_bytes(buf, n) that returns a high-entropy random byte sequence. If the running estimate indicates that there isn't enough entropy in the pool, RAND_bytes returns an error. This is entirely reasonable.

The Unix-specific code in OpenSSL seeds the entropy juicer with some dodgy code. The essence of RAND_poll in rand_unix.c is (my words):

    char buf[100];
    fd = open("/dev/random", O_RDONLY);
    n = read(fd, buf, sizeof buf);
    close(fd);
    RAND_add(buf, sizeof buf, n);

Notice that the parameters to RAND_add say to use the entire buffer but only expect n bytes of entropy. RAND_load_file does a similar thing when reading from a file, and there the uninitialized reference is explicitly marked as intentional (actual code):

    i=fread(buf,1,n,in);
    if (i <= 0) break;
    /* even if n != i, use the full array */
    RAND_add(buf,n,i);

The rationale here is that including the uninitialized fragment at the end of the buffer might actually increase the actual amount of entropy, and in any event being honest about the amount of entropy being claimed won't break the entropy pool estimates.

Similarly, the function RAND_bytes(buf, n), whose main purpose is to fetch n high-entropy bytes from the juicer, adds the contents of buf to the entropy pool (it behaves like RAND_add(buf, n, 0)) before it fills in buf.

In at least three different places, then, the OpenSSL developers explicitly chose to use uninitialized buffers as possible entropy sources. While this is theoretically defensible (it can't hurt), it's mostly a combination of voodoo and wishful thinking, and it makes the code difficult to understand and analyze.

In particular, the RAND_bytes convention causes problems at every call site that looks like:

    char buf[100];
    n = RAND_bytes(buf, sizeof buf);

This idiom causes so many warnings with Valgrind (and its commercial cousin, Purify) that there is an #ifdef to turn the behavior off:

    #ifndef PURIFY
                MD_Update(&m,buf,j); /* purify complains */
    #endif
 

The other two cases occur much more rarely: in RAND_poll, one would have to be reading from /dev/random when the kernel had very little randomness to spare, or calling RAND_load_file on a file that reported one size in stat but returned fewer bytes in read. When they do occur, a different instance of MD_update, the one in RAND_add, is on the stack trace reported by Valgrind.

So, a 0.2 BTC bounty to anyone who can find the source(s) of entropy in this code, and describe how easily those addresses could be regenerated.