Fast-key erasure RNG using AES-NI

[vks]

I ported my implementation to this repository: https://github.com/vks/CSRNGs

Unfortunately, I cannot fork and submit a PR, because the repository is empty.

See RustCrypto/stream-ciphers#1 for previous discussions.

[newpavlov]

Ah, sorry for that. I've pushed the first commit.

[cemeyer]

This seems to conflate fast key-erasure (i.e., forward secret) RNG with a specific PRF implementation (AES-NI implementation of a non-specific "AES-PRF," which turns out to be essentially AES128 CTR mode, keystream only).

Both the PRF construction and fast key erasure RNG scheme are broadly reasonable designs, but they're distinct algorithms. For example, the same key-erasure RNG could be used with any other CTR-mode keystream / PRF on non-AES-NI hardware. Additionally, AES128 CTR mode (or the keystream-only subset with zero message) is plausibly useful independent of the RNG design. I think that's a decent argument for separating the two.

As far as implementation, I have three suggestions:

1. DJB explicitly advises not to use 128-bit key AES. AES256 is fine.

2. Care should be taken to ensure sensitive data like AES internal state, old keys, or generated random values are not leaked on the stack after the RNG routines return. Program flow is a little difficult to follow; I think there's probably excessive use of classes / inheritance.

3. One requirement of a CSPRNG is indistinguishability from true randomness.

AES is a 128-bit block cipher (regardless of key size). With a 128-bit counter, AES will not produce repeated outputs until saturating the counter. However, true randomness with uniform distribution will have repeated outputs at some probability, and 16 byte collisions should be fairly likely after only 2^64 blocks are generated due to the birthday problem. This allows distinguishing long AES-PRF outputs from true randomness. The Fortuna authors suggest re-keying AES-PRF every 2^16 blocks (= 2^20 bytes = 1MiB) to make it more difficult to distinguish an AES-PRF from true randomness.

This second bullet does not apply if you (?)continue (comments say it is limited, but the generation function has no length assertion and is public) to restrict generation to 128 bytes at a time. I think an assertion that the requested length is <= 1MB would be fine. (Performance note: re-keying every 128 bytes probably severely impacts performance; AES key-scheduling is pretty expensive. Even DJB's scheme calls for a 736 byte buffer.)

[Artoria2e5]

If the intent for using AES-128 instead of AES-256 is just performance concerns from round count (10 vs 14), it's probably okay to use the desired key size with a round count lower than 14 (too much crypto suggests 11).