Validating randomness

In my previous post, I demonstrated the viability of a format-preserving encryption construction used to generate a random permutation of a set, using FNV as the PRF in a four-round Feistel network. While it does generate permutations that look reasonable at first glance, looks can be deceiving, so I decided to run more tests on the quality of that randomness.

There are two desirable properties of a pseudorandom bitstream. The first is that the bitstream should be uniform; that is, as infinitely many bits are sampled, the probability of encountering any bit in the bitstream should converge to 50% for 0 and 50% for 1.

Potential bit sequences that meet this quality might start like this:

00001111000011110000111100001111
10101010101010101010101010101010
01110001011101011010111101100001

While the first two sequences are uniform, since the bits appear with equal probability, they probably are not pseudorandom sequences. So while being uniform is a good start, it isn't sufficient. The second requirement is that the bitstream should be unpredictable. Given knowledge of the entire history of bits seen in the sequence, it should be computationally indistinguishable from randomness what the next bit will be. This is ideal for applications like hash tables since it prevents a once-common attack vector known as HashDoS, where predictability in the output of common hash functions could be used to bring simple hash table implementations to their knees.

So, how can we test for these things? One idea to test uniformity might be to measure the probability of a single bit flipping on each consecutive output of a function. If it does not converge to 50%, it is biased and therefore not uniform.

#[test]
fn test_reasonable_entropy() {
    let mut v: Vec<u64> = vec![0; 256];
    let mut p: Vec<f64> = vec![0.; 8];
    let rnd = fnv_1a(1);

    for j in 0..256 {
        v[j] = cycle_walking_fpe(j as u64, 256, rnd);
    }

    // Calculate probability of each bit flipping
    for j in 1..256 {
        let x = v[j] ^ v[j - 1];

        for i in 0..8 {
            p[i] += ((x >> i) & 0x1) as f64 / 256.;
        }
    }

    for i in 0..8 {
        assert!((0.5 - p[i]).abs() < 0.125);
    }
}

So let's do that with our FNV hash-based Feistel cipher, over an example block size of 8 bits...

0.9375
0.46875
0.234375
0.1015625
0.99609375
0.49609375
0.24609375
0.49609375

thread 'tests::test_reasonable_entropy' panicked at 'assertion failed: (0.5 - p[i]).abs() < 0.125', src/main rs:136:13

... oops. That's terrible. The probability distributions for each bit flipping (in the sequence of 8 bits) are extremely skewed. Compare that to the probability of bits flipping from a known random sequence:

In fact, this weakness in the constructed cipher is so obvious that patterns readily appear in its output (arranged in a table for clarity):

4 21 38 55 64 81 98 115 140 157 174 191 200 217 234 251
5 20 39 54 65 80 99 114 141 156 175 190 201 216 235 250
6 23 36 53 66 83 96 113 142 159 172 189 202 219 232 249
7 22 37 52 67 82 97 112 143 158 173 188 203 218 233 248
0 17 34 51 68 85 102 119 136 153 170 187 204 221 238 255
1 16 35 50 69 84 103 118 137 152 171 186 205 220 239 254

What went wrong?

Well, the Feistel cipher construction is guaranteed to be correct for any round compression function you use, since it uses the property of the invertibility of addition over GF(2) to guarantee its correctness rather than the invertibility of the round function. That doesn't mean it will be secure, just that it will be decryptable.

But the Feistel network itself clearly isn't an awful construction; for example, it was used in DES, which has mainly been abandoned due to its short key length, not due to the poor quality of its output. The difference is that DES uses a much stronger round function, which incorporates substitution (S-boxes) and permutation (P-boxes) to produce Shannon confusion and diffusion.

So is there a fast round function that might have these desirable properties? Actually, yes; most modern processors have support for hardware-accelerated AES, and the hardware acceleration comes in the form of one or two instructions which complete a single round of the AES cipher. The AES round function looks something like the following:

AddRoundKey - bitwise xor the input with the key
SubBytes - switch around the input bytes using S-boxes
ShiftRows - rotate the state rows by an input-dependent manner
MixColumns - permute the bytes in the state columns

This sequence of steps, which provides significant confusion and diffusion, is implemented by a single hardware instruction on modern Intel and AMD processors (aesenc) and by two hardware instructions on AArch64 processors supporting SVE (aese, aesmc). However, there is no need to implement a new cryptographic construction around this, as there are already libraries like AHash which provide a hash function based on an AES round.

I've added AHash to the format-preserving encryption algorithm from last time. First, I add a function to set up with a deterministic key, chosen to be fixed random bytes (this will be needed to ensure that the cipher behavior is deterministic) and run the hash function:

// AES-round based hasher
fn hash_ahash(input: u64) -> u64 {
    let mut hasher = AHasher::new_with_keys(0x5f7788c56cb54593, 0x76fa89eb1eef921d);
    hasher.write_u64(input);
    hasher.finish()
}

And validate the probability distribution:

As intended, it has a very good distribution. But maybe we would be okay with a worse distribution if it meant the computation was faster. So, we need to look at how it performs. Let's run the benchmarks:

Before:

test tests::bench_100_2500000_cycle_walking_fpe ... bench:       4,820 ns/iter (+/- 205)
test tests::bench_100_fnv_1a                    ... bench:         752 ns/iter (+/- 61)

After:

test tests::bench_100_2500000_cycle_walking_fpe ... bench:       2,211 ns/iter (+/- 157)
test tests::bench_100_ahash                     ... bench:         301 ns/iter (+/- 15)

AHash is clearly superior both in terms of distribution and in terms of performance. Due to being implemented by hardware instructions on modern processors, it runs extremely quickly, and easily beats the old FNV based approach by 2-3x. That means AHash should always be used where hardware acceleration is available.

As usual, source code.

Disclaimer

I am not a cryptographer. The application of using cryptographic techniques to generate pseudorandom permutations is an interesting avenue for amateur exploration due to not possessing any risk if the encryption is too weak to provide meaningful security or has issues such as side-channels. Do not use this as an excuse to implement your own cryptographic primitives; always reuse standard implementations as they will almost certainly cover your usecase if you need real security, and if they don't, think twice before blindly implementing anything you read on the internet—you will probably do it insecurely.