jbp.io Archive
16 January 2014

Analysis of the OpenSSL random API

This analysis is in four parts. First, there’s an introduction for readers not familiar with the API. Next, there’s a review of the implementation of the functions in OpenSSL. Third, the callers of these functions are analysed. Lastly, there’s a set of recommendations and patches.

This analysis concentrates on the API to the random generator, not the PRNG algorithm itself. For a description and analysis of that, see section 3.8 of ‘Cryptographic Security Architecture: Design and Verification’ by Peter Gutmann or the description in the documentation.


1. Introduction

OpenSSL provides two functions for obtaining a sequence of random octets: RAND_bytes and RAND_pseudo_bytes. RAND_bytes guarantees to provide high quality random material; RAND_pseudo_bytes does not, but instead tells the caller if the returned material is low quality.

Their function prototypes are:

int RAND_bytes(unsigned char *buf, int num);
int RAND_pseudo_bytes(unsigned char *buf, int num);

These are backed by a configurable set of providers – ‘RAND methods’. There are methods for CPU hardware RNGs, hardware security modules, and so on.

First stop: documentation

Excerpts from the documentation:

Description

RAND_bytes() puts num cryptographically strong pseudo-random bytes into buf. An error occurs if the PRNG has not been seeded with enough randomness to ensure an unpredictable byte sequence.

RAND_pseudo_bytes() puts num pseudo-random bytes into buf. Pseudo-random byte sequences generated by RAND_pseudo_bytes() will be unique if they are of sufficient length, but are not necessarily unpredictable. They can be used for non-cryptographic purposes and for certain purposes in cryptographic protocols, but usually not for key generation etc.

Return values

RAND_bytes() returns 1 on success, 0 otherwise. The error code can be obtained by ERR_get_error(3). RAND_pseudo_bytes() returns 1 if the bytes generated are cryptographically strong, 0 otherwise. Both functions return -1 if they are not supported by the current RAND method.

The return values and implied state of the buffer on return are important and bear repeating:

RAND_bytes:

RAND_pseudo_bytes:

WTF

“byte sequences […] will be unique if they are of sufficient length”

My interpretation of this is that i requests for sequences of n bytes each where n ≥ threshold yield unique sequences (where threshold is presumably less than 256 i - 1).

This would be fine, except nothing could reasonably provide this uniqueness guarantee: instead, any two n byte sequences will be non-unique with probability 256 -n, just as you’d expect from a source of uniformly distributed bytes.


2. Implementation

Evaluation of all RAND methods

The meat of this work: I tracked down all the RAND_METHOD definitions I could find, in OpenSSL and elsewhere.

For each one, I noted down whether RAND_pseudo_bytes was usefully different from RAND_bytes, what the error behaviour was, and any other bugs that came to light.

OpenSSL

In Bind 9

Heimdal

Round up

That’s a big list. The main point to note is:

All RAND_pseudo_bytes implementations are broken in their error cases, (except one (fips/rand/fips_drbg_rand.c) which misses out by returning the ‘not implemented’ error code). This is frighteningly dangerous error behaviour.

Here’s a test program:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <openssl/rand.h>

int main(void)
{
    unsigned char buf[28] = { 0 };
    int err = RAND_pseudo_bytes(buf, sizeof buf);

    if (err == 1)
        printf("strong randomness: ");
    else if (err == 0)
        printf("weak randomness: ");
    else {
        printf("RAND_pseudo_bytes failed: %d\n", err);
        return 1;
    }

    for (size_t i = 0; i < sizeof buf; i++)
        printf("%02x", buf[i]);
    printf("\n");
    return 0;
}

This performs as you’d expect using the default RAND_METHOD (crypto/rand/md_rand.c):

$ ./simple-randtest 
strong randomness: 38799d450b619ccaa05e0265a7b35c293aec6f4ef314665e75c57871
$

However, if we arrange for a certain malloc(3) invocation to fail, we get:

$ MALLOC_FAILS=57 LD_PRELOAD=./brokenmalloc.so ./simple-randtest 
failed malloc 57 by request
weak randomness: 00000000000000000000000000000000000000000000000000000000
$ 

That’s really not healthy.


3. Callers

Review of RAND_bytes callers

The scheme for RAND_bytes’s return value is a bad idea, because it makes the natural way to write a call incorrect1:

if (!RAND_bytes(...))
    /* handle error ... */

That this is incorrect didn’t stop people calling it that way. Debian code search gives us some culprits, including OpenSSL (yes, really: OpenSSL calls its own API incorrectly), Ruby, net-snmp, ZNC, DACS, and dnsval/dnssec-tools2. Github code search gives 1456 results for the same query. Android also called this incorrectly in versions before 4.4.

These are of particular concern where other modules existing in the same process space, and could plausibly install a RAND method which doesn’t support RAND_bytes – like language runtimes and libraries.

Review of RAND_pseudo_bytes callers

We can divide callers of RAND_pseudo_bytes into a few classes:

In other words, calling RAND_pseudo_bytes is always either unreliable, or merely pointless.

Dangerous: BN_pseudo_rand

BN_pseudo_rand can return bits of heap converted to a bignum if RAND_pseudo_bytes fails. The same bug spreads to BN_pseudo_rand_range, BN_generate_prime_ex (when choosing Rabin-Miller witnesses), etc.

Pointless: SSL and TLS server code (ssl/s3_srvr.c)

Behold!

1
2
3
4
/* should be RAND_bytes, but we cannot work around a failure. */
if (RAND_pseudo_bytes(rand_premaster_secret,
              sizeof(rand_premaster_secret)) <= 0)
    goto err;

This call should be RAND_bytes, but it isn’t because we can’t deal with errors. Except then we handle failures from RAND_pseudo_bytes in a way which makes it equivalent to RAND_bytes.

Hopeful: TLS server code (ssl/s3_srvr.c)

In ssl3_send_newsession_ticket in the codepath without tctx->tlsext_ticket_key_cb set, a buffer on the stack is filled with 16 bytes from RAND_pseudo_bytes, but the return code isn’t checked. That buffer is the IV for TLS ticket encryption, so if this call fails some stack is sent over the wire in plaintext (maybe containing old key material) and confidentiality of the resulting encryption is broken in a limited way if the stack contents are the same for different clients.


4. Recommendations and patches

Calling RAND_bytes

Public service announcement: the only correct way to call RAND_bytes is equivalent to:

1
2
if (RAND_bytes(buf, size) != 1)
{ /* handle error ... */ }

Improving RAND_bytes semantics to fix downstream code

OpenSSL could improve matters by guaranteeing that RAND_bytes never returns -1 from now on: this would make existing code (of which there is a sizeable chunk, see above) which does if (!RAND_bytes(...)) safe.

This patch simplifies the error behaviour to:

The old ‘not implemented’ error is reported with a return code of 0, and a distinctive reason code on the error stack (RAND_R_FUNC_NOT_IMPLEMENTED).

RAND_pseudo_bytes is not altered by this change.


Deprecate RAND_pseudo_bytes

RAND_pseudo_bytes should be deprecated, for the following reasons:


  1. Recall that in C, non-zero values are ‘true’ expressions, so this includes both success and failure cases. 

  2. Note: I haven’t verified that each one of these is actually a bug, or in an important (or even used!) bit of code.