key_generator

Debian weak key generator.

Introduction

CABForum Baseline Requirements 4.9.1.1 (Reasons for Revoking a Subscriber Certificate) and 6.1.1.3 (Subscriber Key Pair Generation) expect Certification Authorities (CAs) to check that there is not a proven method that can easily compute the Subscriber's Private Key based on the Public Key, citing the example of Debian weak keys (CVE-2008-0166). Due to CVE-2008-0166, OpenSSL 0.9.8c-1 up to versions before 0.9.8g-9 on Debian-based operating systems can only produce 294,912 possible RSA keys of any given keysize.

Back in 2008, Debian published an openssl-blacklist package, which contained complete blocklists for RSA keysizes that were commonly in use at the time, as well as an openssl-vulnkey tool for checking whether or not any given key is blocklisted.

Problems

It's not an easy task to correctly set up old, vulnerable Debian versions, for all 3 word size / endianness combinations, in order to generate complete weak key blocklists for RSA keysizes that aren't detected by openssl-vulnkey (as shipped by Debian). Additionally, many modern Linux systems no longer even provide the openssl-blacklist package. Nonetheless, CAs should expect that they will need to check for Debian weak keys indefinitely.

In 2022 Hanno Böck pointed out that the vulnerable Debian versions also generated predictable elliptic curve (EC) keys.

Purpose

This repository provides tools - to generate complete sets of Debian weak keys (for all of the affected architectures), and to generate the corresponding blocklists - that can be run on a modern 64-bit Linux system. The key_generator tool uses a bundled version of OpenSSL 0.9.8f that has been modified to make it vulnerable to CVE-2008-0166. Multiple architectures are simulated thanks to 64-bit Linux being able to execute 32-bit binaries and with the help of a further modification that provides a mechanism to emulate the opposite endianness by reversing the byte order of certain variables used within the affected OpenSSL RNG code.

Pregenerated Keys and Blocklists

The private_keys repository contains complete sets of Debian weak keys for various RSA keysizes (using the PKCS#1 private key format with public exponent 65537) and EC curves (using the SEC1 private key format). Using these key sets, CAs can implement weak/compromised key checks without having to be tied to the blocklist format used by openssl-vulnkey. When designing these key checks, it is important for CAs to note that 65537 is not the only public exponent that a predictable RSA modulus might be used with.

The openssl_blocklists repository contains complete blocklists of Debian weak keys for various RSA keysizes, using the same format as openssl-vulnkey. Since this file format only supports RSA, it is not possible to produce compatible blocklists for EC keys.

The dwk_blocklists repository contains complete blocklists of Debian weak keys for various RSA keysizes and ECC curves.

Key Generator Tools

Prebuilt key_generator Binaries

bin/linux contains a 32-bit key_generator binary that was prebuilt on Debian Buster (i386), and a 64-bit key_generator binary that was prebuilt on Ubuntu 22.04 (x64).

To be able to run the 32-bit key_generator binary on Ubuntu 22.04 (x64), do this:

sudo apt install libc6:i386

These prebuilt binaries have been tested on Ubuntu 22.04 (x64) and Gentoo Linux (x64).

Build key_generator from Source

To build the bundled version of OpenSSL and the key_generator tool from source, run

make

To cleanup the key_generator build, run

make clean

To cleanup both the key_generator and bundled OpenSSL builds, run

make distclean

Testing key_generator

To check that key_generator functions correctly in your environment, run

./run_tests.sh

You should see the following output:

Generating weak RSA-2048 keys for process ID 32767 of 32767: le64(rnd,nornd,noreadrnd) le32(rnd,nornd,noreadrnd) be32(rnd,nornd,noreadrnd)
Generating test blocklist
Tests Successful

(IMPORTANT: If you see "Tests FAILED!", then unfortunately key_generator will not produce Debian weak keys in your environment).

Using the Tools

To use key_generator to generate all of the Debian weak keys for a particular RSA keysize or supported elliptic curve (secp256r1 or secp384r1), run

./generate_weak_keys.sh <key_size_in_bits_or_curve_name>

To put those keys into a set of .zip files, run

./zip_weak_keys.sh <key_size_in_bits_or_curve_name>

To generate blocklists for those keys (RSA only) that are compatible with openssl-vulnkey, run

./generate_vulnkey_blocklists.sh <key_size_in_bits>

To generate blocklists for those keys in a different format that supports both RSA and ECC, build the dwk_blocklist_generator application, then run

./generate_dwk_blocklists.sh <key_size_in_bits_or_curve_name> <private_keys_directory>

NOTE: Key and blocklist generation takes a long, long time!