22.6 Random number generation

In Chapter 3 A Secret to Share, we learned that the security of most protocols and mechanisms depends on the generation of random sequences of bits or numbers. These sequences must have a sufficient length and be random in a very specific sense: We do not want an attacker to be able to guess part of or the whole sequence.

Why? Recall the example from Chapter 3 A Secret to Share: The size of the key space of the AES-256 encryption algorithm is 2256. If the AES-256 key was selected using a truly random source, Eve would have to try on average 2255 candidate keys before she found the correct key.

However, if Alice generates the key by first choosing a 32-bit random number and then turning it into a 256-bit key using some complicated but deterministic expansion algorithm E, then Eve needs to try only 231 possible keys on average (obtained by running every possible 32-bit random number through E). To prevent this, Alice and Bob must generate the keys using bits from truly random sources. Cryptographers use the concept of entropy to describe the randomness of a source.

Implementation bugs can undermine TLS security by affecting entropy used in TLS’s cryptographic operations. An example of such vulnerability is a bug introduced in Debian, a very popular Linux distribution, in September 2006 and discovered by Debian developer Luciano Bello in 2008.

Listing 22.4: Implementation bug in Debian etch

/* Don’t add uninitiatilised data.
   MD_Update(&m, buf, j);
*/
   MD_Update(&m, (unsigned char *)&(md_c[0]), sizeof(md_c));
   MD_Final(&m, local_md);
   md_c[1]++;

As shown in Listing 22.4, Debian developers accidentally commented out – effectively, removed – the code line MD˙Update(m, buf, j); that was feeding entropy into Debian’s pseudo-random number generator [150]. As a result, the input to the pseudo-random number generator had only 16 bits of entropy. All Eve had to do is to try merely 215 possible values on average for any cryptographic operation, for instance, to guess private keys generated by Alice using the vulnerable software:

22.7 BERserk attack

In 2014, Intel’s advanced threat research team and the French security researcher Antoine Delignat-Lavaud discovered a critical vulnerability in the then-current version of Mozilla’s Network Security Services (NSS) cryptographic library [85]. The attack was assigned the CVE number CVE-2014-1569.

The researchers gave the vulnerability the name BERserk, which is a pun on the Basic Encoding Rules (BER) encoding format. BER is a set of rules specified in International Telecommunications Union’s ASN.1 standard for encoding data into binary form.

NSS versions vulnerable to BERserk do not ensure that the BER encoding of an ASN.1 length is correctly formed. This, in turn, allows Mallory to forge RSA signatures using the PKCS#1 v1.5 RSA Signature Forgery attack published earlier by Daniel Bleichenbacher.

According to the PKCS#1 v1.5 standard, a plaintext’s hash to be signed must be padded as follows:

00 01 FF FF ..
FF FF 00 DigestInfo MessageDigest

where DigestInfo is the ASN.1 encoding of the hash algorithm used to compute the hash of the plaintext message.

In 2006, Bleichenbacher published a signature forgery attack against implementations of RSA signature verification with a low public exponent that do not completely validate PKCS#1 v1.5 padding when decrypting the encoded message from an RSA signature [85].

Suppose the RSA signature verification uses a public key with a small encryption exponent e = 3. A vulnerable implementation scans the DER-encoded message for padding bytes 0xFF .. 0xFF until it finds the separator byte 0x00. It then continues to validate DigestInfo and MessageDigest without verifying that there are no extra bytes after MessageDigest.

As a result, Mallory can insert extra bytes after MessageDigest:

00 01 FF FF FF FF FF FF FF FF 00 DigestInfo MessageDigest ExtraBytes

In a man-in-the-middle scenario, Mallory can make Alice process that modified encoded message. It turns out that ExtraBytes allows Mallory to forge RSA signatures – without knowing the RSA private key d – for arbitrary messages when the public exponent is small.