OpenSSL and LibreSSL PRNG, what’s different?

In July, a blog post from Andrew Ayer described the new, unsafe behaviour of portable LibreSSL 2.0.1. While it is right to say that it’s unsafe, it is still safer than baseline’s OpenSSL and portable LibreSSL 2.0.2. That’s what I’ll explain in this blog post.

OpenSSL

During March 2014, I released two CVE on OpenSSL consumers, stunnel (CVE-2014-0016) and libssh (CVE-2014-0017). I also wrote a paper about it in the french magazine MISC mag 74. Unfortunately the paper is in french and not yet released in CC-BY-NC, so here are the major points:

• OpenSSL RAND_bytes() pool can be shared by two processes that are related, e.g. with a fork().
• OpenSSL mitigates that problem by adding the result of getpid() in the entropy pool during a RAND_bytes() call. That means that two processes that share the same entropy pool and end up with the same PID will generate the same pseudorandom numbers.
• That’s what happens in stunnel in fork mode: a master process initializes the entropy pool and spawns children. As children die, PID are recycled until a PID is reused and starts generating the same sequences of pseudorandom numbers.
• Hopefuly OpenSSL uses RAND_seed() with the current unix time (time(NULL)) on every SSL handshake, so there’s only a one-second time spot to exploit that weakness, before having to start from scratch again. OSes with sequential PID generation are then less vulnerable than OSes with random PID (AFAIK only OpenBSD). This is because open OpenBSD it’s likely to have two different children have the same PID reused in the same second.
• In the end, the exploit I wrote for it didn’t work, because the OpenSSL ECDSA_sign() function calls RAND_seed() with the content of the message to be signed, and the secret number k is different every time, mitigating the exploit:

int ECDSA_sign_ex(int type, const unsigned char *dgst, int dlen, unsigned char
    *sig, unsigned int *siglen, const BIGNUM *kinv, const BIGNUM *r,
    EC_KEY *eckey)
{
    ECDSA_SIG *s;
    RAND_seed(dgst, dlen);
    s = ECDSA_do_sign_ex(dgst, dlen, kinv, r, eckey);
    if (s == NULL)
    {
        *siglen=0;
        return 0;
    }
    *siglen = i2d_ECDSA_SIG(s, &sig);
    ECDSA_SIG_free(s);
    return 1;
}

I have written exploit code for it. It doesn’t manage to extract the private key (with OpenSSL) but detects when a PRNG collision happens. Now, that’s a weakness in OpenSSL that I suggested fixing with register_atfork(). It’s different in LibreSSL.

LibreSSL 2.0.1

Portable LibreSSL-2.0.1 is based on LibreSSL-2.0.1 that changed all that code to rely on the arc4random(). On Linux, this function works more or less the same than it did with OpenSSL, with an initialized entropy pool. We see the following properties:

• fork() is detected by a change in pid (using getpid()). It is not stirred in the pool with RAND_add() and so it’s not possible for two children to share the same pool content. However as described by Ayer, a child may have the same PID as its grandfather and not detect the PID change.
• RAND_add()/RAND_seed() was removed from the source code. It’s a no-op and references were removed everywhere in libssl and libcrypto. That includes the TLS session management and the ECDSA_sign() functions.

In order to test for the strength of LibreSSL against the CVE-2014-0016 bug, I compiled stunnel 4.56 on Linux with a little addition:

int getpid(){return 31337;}

The exploit worked like a charm because LibreSSL didn’t detect the pid change and reused the same entropy content on two sessions. This is of course a lab test, but I did the same with OpenSSL and couldn’t extract the private key because of the mitigations in ECDSA_sign():

ECDSA/DSA weakness

Without going too far in the mathematical details, it is important to know that both ECDSA and DSA rely on a random big integer, k, to do the signature operation. This number should be perfectly random and not reused, because its knowledge (or reuse) would balance the ECDSA/DSA equations and make the private key easy to calculate.
OpenSSL did RAND_add() on the actual message to be signed. Most likely, this message could be public, but it would be at least different on every attack. This simple RAND_add()/RAND_seed() made my exploit impossible as the value k would be chosen differently on every attack.
On the contrary, LibreSSL removed that statement. The developers decided that the only source of randomness should be the PRNG.
While I agree that having a strong PRNG is a requirement to do strong crypto, the choice of the secret value is a very well known weakness of ECDSA/DSA. DJB explains why they chose in ed25519 not to use RNG at all for the selection of k:

Avoiding RNGs in signatures. It would be better if the signature system didn’t need new randomness for each signature in the first place. The RNG would be used much less frequently, and could afford to be designed more conservatively. We wouldn’t have to worry about the RNG taking entropy from malicious sources. We could move a long-term secret key into a highly protected hardware device for signing, without having to pay for an RNG in the hardware device and without having to worry about the quality of that RNG. We could have test vectors for signing functions, because those functions wouldn’t have a hidden RNG input.

This is exactly what was accomplished by a very simple modification to DSA suggested by George Barwood in February 1997: namely, “a prng is used to generate k, keyed with d (the private key), and seeded with e (the message digest).” Essentially the same idea was suggested by John Wigley in March 1997: “Why not derive the random number from the message to be signed therefore removing the need for a hardware rng (smartcards) or a complex and potentially fallible software attempt. … 1)Hash the message to be signed as usual and use that as the message in the signature algorithm. 2)hash the private key using the chaining variable state left by the previous hash, and use that as the random number.”

I think LibreSSL should implement a workaround such as this one to protect ECDSA against problems just like the ones we discussed, and have the secret value K generated using a function of the PRNG output, message and private key. It probably wouldn’t pass FIPS certification, but who cares 🙂

LibreSSL 2.0.2

The LibreSSL team fixed that bug by using the register_atfork() function, that gets a callback called after every fork. This function is part of POSIX and is portable enough, and better, it ensures that every fork() is detected in the right way. This is not perfect (as wrote Andrew) and an explicit way to reset the entropy pool would be welcome.

Summary

This is a little summary of the different ways of handling fork() in the PRNG and ECDSA signatures as I discussed in the post:

name	handling PID change	DSA/ECDSA
OpenSSL	RAND_add(getpid())	RAND_add(message); k=random()
portable LibreSSL 2.0.1	if(getpid()!=pid) reset()	k=random()
portable LibreSSL 2.0.2	onfork() callback	k=random()
My ideal	onfork() callback	k=hash(random() + privkey + message)

To end my point, I would say that the bug that was found is not as bad as it looks, mainly because OpenSSL had a much worse behavior for years and nobody ever complained. The way they solved it is the best I can think of, even though I think something should be done to protect the ECDSA and DSA signature process against future bugs in the PRNG.

To finish I still think it’s a little too soon to use portable LibreSSL in production, as OpenSSL was chopped down badly to fit into OpenBSD’s security model, and the portable LibreSSL team may not be aware of all the traps left in the port. The behaviour of rc4random() on Linux was one of them.