Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

A quick introduction to CBRNGs

By Katharina •

Counter-Based Random Number Generators (CBRNGs), wow, that’s a mouthful, are a special kind of PRNG. They give you stateless, reproducible random numbers.

You are probably already somewhat familiar with Random Number Generators (RNGs). Here’s a quick recap:

import random

for i in range(10):
    print(random.randint(0, 10))
Output 
>>> 6
>>> 6
>>> 0
>>> 4
>>> 8
>>> 7
>>> 6
>>> 4
>>> 7
>>> 5

Pretty useful for a lot of things, in many cases you want real randomness, which is surprisingly hard to obtain. Most RNGs are actually pseudorandom. And almost all common PRNGs depend on the previous state to calculate the next round. This means it’s very impractical to calculate values in parallel, and you also can’t jump into the series at value N without calculating all states between 0..N.

To avoid this, we will need to take a:

Tiny detour into hashing

Good hashing functions have a few features.

  • Any length of input returns a constant-length output.
  • The output is uniformly distributed, e.g., any outcome is just as likely.
  • And, of course, they are stable, so the same input always produces the same output.
import hashlib

for i in range(4):
    print(f"cycle {i}")
    for j in range(4):
        print(hashlib.sha256(str(j).encode()).hexdigest())
Output 
>>> cycle 0
>>> 5feceb66ffc86f38d952786c6d696c79c2dbc239dd4e91b46729d73a27fb57e9
>>> 6b86b273ff34fce19d6b804eff5a3f5747ada4eaa22f1d49c01e52ddb7875b4b
>>> d4735e3a265e16eee03f59718b9b5d03019c07d8b6c51f90da3a666eec13ab35
>>> 4e07408562bedb8b60ce05c1decfe3ad16b72230967de01f640b7e4729b49fce
>>> cycle 1
>>> 5feceb66ffc86f38d952786c6d696c79c2dbc239dd4e91b46729d73a27fb57e9
>>> 6b86b273ff34fce19d6b804eff5a3f5747ada4eaa22f1d49c01e52ddb7875b4b
>>> d4735e3a265e16eee03f59718b9b5d03019c07d8b6c51f90da3a666eec13ab35
>>> 4e07408562bedb8b60ce05c1decfe3ad16b72230967de01f640b7e4729b49fce
>>> cycle 2
>>> 5feceb66ffc86f38d952786c6d696c79c2dbc239dd4e91b46729d73a27fb57e9
>>> 6b86b273ff34fce19d6b804eff5a3f5747ada4eaa22f1d49c01e52ddb7875b4b
>>> d4735e3a265e16eee03f59718b9b5d03019c07d8b6c51f90da3a666eec13ab35
>>> 4e07408562bedb8b60ce05c1decfe3ad16b72230967de01f640b7e4729b49fce
>>> cycle 3
>>> 5feceb66ffc86f38d952786c6d696c79c2dbc239dd4e91b46729d73a27fb57e9
>>> 6b86b273ff34fce19d6b804eff5a3f5747ada4eaa22f1d49c01e52ddb7875b4b
>>> d4735e3a265e16eee03f59718b9b5d03019c07d8b6c51f90da3a666eec13ab35
>>> 4e07408562bedb8b60ce05c1decfe3ad16b72230967de01f640b7e4729b49fce

Please be aware that SHA-256 here is only used as an example, since most people will already have some familiarity. In practice, you’d use a more lightweight hashing algorithm like Blake3.

Now you might ask, how do explicitly non-random values help with obtaining random values?

CBRNGs

We can generate a small seed, combine it with a deterministic value (e.g., a counter), and then throw it into a hashing function. With this method, we can start and stop at any point in the sequence because none of the values depend on each other’s output for computation, which in turn means this procedure is embarrassingly parallel.

import random
import hashlib

seed = random.randint(0, 2048)
print(f"Our seed: {seed}")

for i in range(10):
    print(hashlib.sha256(f"{seed}:{i}".encode()).hexdigest())
Output 
>>> Our seed: 894
>>> 0ad61801839d4e6a7b34d047c0b4fe4daa1fd4f838c5f31627c118e69867e226
>>> 9ae3f8ae82f431fa4d550ba5e69532b7d666078c60aa64a497267256f2467678
>>> 3b945e6ac6d0ef7a3f1a0bbf6b2245d1e4b435e04a385f9a09e9ba84af03f0b6
>>> 6f187f433d749054dd1a03aa8afa21f229f765dac3698316a4780b58b674ffbc
>>> 2fe81e34f70af5ea7f907b095b0a1a927efb46fb9be793d1c85a625ffd0ed3ac
>>> 74935e3808917e21242df7a6807b7bf3b0a4ee42e4d195069359c62a21661a6d
>>> 873e488cd4380cf74039a06878d731a3497fcaf1bc75b6354802b1a2996bb4b6
>>> b48aa001858263fa405fecfc1c3f9c4881c09a415cd1011b4fb490132bb05745
>>> 2889f2a8fd758d7f09d1bd7063e2019610c9d65d260097b00cb9bb4330e6177b
>>> 84de7fed0ea2824275994393869c6187db76c35c4822d2e53993296785ac94b3

This way of generating random numbers is pretty useful for simulations.

However, I’m particularly fond of using this method for repeatable, continuous performance testing. Let’s say you wanted to bench a data plane implementation like VPP. You could use this technique to generate a tuple of {src_ip,dest_ip,src_port,dest_port,proto}, and the length of a packet. Then, instead of hauling around giant PCAP files to do multi-hour stress tests, all you need is the generator binary and a seed. When you want to compare a new and previous version, you just run both of them with the same seed.

A trivial way to bound the range of random numbers is to just take them modulo your maximum. Note that you are introducing a slight bias if your CBRNG output range isn’t a multiple of your modulo value. Take a look at rejection sampling if this isn’t acceptable for your use case.

If you ever find yourself in a situation where your “Device Under Test” (DUT), or more realistically, process, is being starved for more flow, you can crunch the packets ahead of time and just iterate through a vector, instead of computing them on the fly.

All code here is just for illustrating the high-level concepts. If you want something fast, correct, and cheap, just use a library with the Philox algorithm.

Further reading