Building a Deterministic Random Bit Generator
Tags: cryptography, rng
Published: 2021-03-13 16:45:19

---
title: Building a Deterministic Random Bit Generator
published: true
date: 13/03/2021
tags: cryptography, rng
canonical_url: https://musigma.blog/2021/01/30/drbg.html
---

As part of developing the [O(1) Cryptography library](https://github.com/o1c-dev/o1c), I initially relied upon the standard Java cryptography APIs for cryptographic random bit generation. Unlike most of the cryptographic APIs in Java that are frequently misused, [java.security.SecureRandom](https://docs.oracle.com/javase/8/docs/api/java/security/SecureRandom.html) is about as simple as it gets for defining all the relevant operations of a secure random number generator. Naturally, like most of the standard APIs, this one, too, can be misused if configured incorrectly, most importantly in the underlying seed generation strategies which are platform-specific. Java provides a few different strategies out of the box, and in [pure Java code](https://github.com/o1c-dev/o1c/blob/81c2248a5ed696f11a1784ceb90afd573ab35822/src/main/java/dev/o1c/internal/SystemSeedGenerator.java#L29), I rely on this API to seed the O(1) Cryptography deterministic random bit generators. In C, there are some nicer integrations with OS-specific system calls and even hardware-specific integrations more readily available, though Java can access some of these if they’re provided via some PKCS11 library. As a technical note, the only relevant limitation we have in Java compared to C is that the Java operations will generally require opening a file or accessing some resource which can potentially fail due to file descriptor leaks or other resource exhaustion, while the C code can make use of system calls that bypass the file interface entirely. Depending on the underlying threat model, this can be a vulnerability if the process cannot open `/dev/random` or equivalent device files. With that in mind, let’s take a look at how a random bit generator works.

<!-- more -->

The canonical U.S. standard for cryptographic random bit generators is [NIST Special Publication 800-90A Revision 1](https://doi.org/10.6028/NIST.SP.800-90Ar1) which specifies three mechanisms to do so using standard cryptographic primitives. These mechanisms include one based on plain hash functions, one based on keyed hash functions (HMAC specifically), and a third based on block ciphers such as AES. In O(1) Cryptography, I’ve implemented two strategies using the primitives available here: one based on a [keyed BLAKE3](https://github.com/o1c-dev/o1c/blob/81c2248a5ed696f11a1784ceb90afd573ab35822/src/main/java/dev/o1c/modern/blake3/Blake3RandomBytesGenerator.java#L30) hash function, and another [using ChaCha20](https://github.com/o1c-dev/o1c/blob/81c2248a5ed696f11a1784ceb90afd573ab35822/src/main/java/dev/o1c/modern/chacha20/ChaCha20RandomBytesGenerator.java#L32) as a pseudo-block cipher. Both strategies have some commonality beyond their underlying permutations (BLAKE3 uses the same quarter-round mixing function as ChaCha20).

First, a DRBG instance is lazily initialized on a per-thread basis using system-specific seed entropy. Java makes this fairly simple with the [ThreadLocal](https://docs.oracle.com/javase/8/docs/api/java/lang/ThreadLocal.html) class and relying on `SecureRandom` for accessing system-specific entropy sources for generating a seed. C raises the challenge of not having a standard runtime, though it does have standardized thread-local storage support. On the other hand, C gives us access to lower level APIs which have their own advantages to the Java equivalents.

One of these APIs is the function [getentropy](https://man7.org/linux/man-pages/man3/getentropy.3.html) which uses the Linux system call [getrandom](https://man7.org/linux/man-pages/man2/getrandom.2.html), a function that is used as the basis for `/dev/random` and `/dev/urandom`. On BSDs and macOS, `getentropy` is itself the system call with the same signature that libc borrowed. For older POSIX platforms that don’t expose a system call, reading seed data from `/dev/random` can be supported, though I’ve elided support for it currently as it involves file IO which starts to bloat the C library beyond what’s minimally necessary to support the Java API. On Windows, there appears to be a long history of APIs here, the most promising sufficiently low level one being [RtlGenRandom](https://docs.microsoft.com/en-us/windows/win32/api/ntsecapi/nf-ntsecapi-rtlgenrandom), a function from the advapi32 library which has been a fairly standard base library on Windows since the XP days. An interesting source to look at would be non-standard hardware entropy sources like the [OneRNG](https://onerng.info/), an open source hardware RNG which is typically accessible in a platform-independent manner via serial port access APIs besides any of the integrations offered specifically for Linux.

Each implementation uses this seed data slightly differently, but they both use the seed as an initial key. The ChaCha20 implementation also uses the seed for a nonce and initial counter. In order to generate random bytes, this uses the keystream output (the resulting ciphertext of encrypting null bytes) for each request and then ratchets itself by using an incrementing nonce to provide forward secrecy. The BLAKE3 implementation generates bytes by finalizing the hash output of an empty input with the first 32 bytes being used solely to rekey the hash function as its ratchet after using the subsequent bytes as the output bytes. Both implementations maintain internal counters to track when reseeding is necessary.

It may be interesting to note how simply the concepts from the underlying stream cipher and extensible output function primitives made implementing a DRBG much simpler than the required steps to do the same with AES or HMAC-SHA2. Since O(1) Cryptography is an opinionated cryptography library with the goal of being easy to use and hard to misuse, this philosophy is apparent in both its APIs and its choice of cryptographic primitives. Using the current NIST standards, there is currently only one primitive available that can be as easily used: [SHAKE128/SHAKE256](https://en.wikipedia.org/wiki/SHA-3). SHAKE is the extensible output function variant of SHA-3 which has a comparable API to BLAKE3 while being fairly slower. Using this same pattern, it’s fairly simple to build a DRBG using any cryptographic sponge function such as [Xoodyak](https://keccak.team/xoodyak.html) or any sponge-style permutation like [Ascon](https://ascon.iaik.tugraz.at/) as either cipher-based generators or keyed hash ones. Some of these ideas are also included, though it remains to be seen where lightweight cryptography standards converge, so they are only available as experimental implementations.

I hope this helps demystify how a cryptographic random bit generator can be made using cryptographic primitives. DRBGs can get more complicated than this by adding an interface to accept user-provided seed data to include in its seed input, maintaining buffers, and gathering various system state to use in the reseed algorithm, though I’ve tried to keep things simple by standing on the shoulders of operating systems and hardware support instead. Plus, Java’s standard `SecureRandom` implementation already handles this for us where necessary.

These random generators will be an important tool in our cryptographic toolbox later on when I go over the design of other parts of O(1) Cryptography in subsequent blog posts. Random data are integral to our ability to generate keys and challenges, and the strength of our cryptosystem is only as good as its fundamental parts. Ensuring that random data can be generated fast and in parallel is a clear requirement for any proper use of cryptography, so perhaps it may help to keep in mind one of the implicit design goals of O(1) Cryptography: speed. Performance problems are a common source of security vulnerabilities when security measures get disabled due to interference with core application logic. Using high performance cryptographic primitives prevents the need to tweak security parameters improperly; using primitives that avoid overly complex configuration options goes a step further by preventing insecure tweaks in the first place.