How should I generate secure random numbers deterministically?

Question

I have a 256-bit seed; call it P. From P, I need to derive 2¹⁹ 256-bit numbers deterministically.

There's a catch, however: I want to derive them in any order. For example, I might need the 7878th number, followed by the 51st number. For that reason, deriving them with a stream cipher is inappropriate for me. Also, if one output is revealed to the attacker, it should not be possible to derive a different output.

My intuition is that I could use a hash function to derive each number, but I'm concerned that it wouldn't have the properties necessary to prevent an attacker from deriving one output from a different output.

What type of cryptographic construction should I use?

Answer 1

Your idea of using a hash function to expand your seed is a reasonable one. If you want a standardized method of doing so, try HKDF from RFC 5869. Specifically, I'd suggest something like the following:

PRK = HKDF-Extract("custom salt value", P)

output[i] = HKDF-Expand(PRK, string(i), 256/8)

where "custom salt value" is a unique string identifying your application and, where applicable, any other relevant context, so that reusing the same seed P in different contexts won't yield the same output. (If you already know that the seed P is unique, entropy-dense and only known to your application, you can skip the HKDF-Extract step and just set PRK = P; see the RFC for more information.)

Of course, any other secure key derivation function, such as the counter, feedback and double-pipeline mode KDFs from NIST SP 800-108, could be used in a similar way.

---

Alternatively, since your seed P is a random 256-bit string, and the number of outputs you require is relatively small (≪ 2⁶⁴), you could simply generate your outputs using a block cipher with a 256-bit key (e.g. AES-256) in counter mode, using P as the key, e.g. like this:

output[i] = AES-256(P; 2*i) || AES-256(P; 2*i+1)

where || denotes bitstring concatenation, and AES-256(P; c) denotes the encryption of a 128-bit block encoding the counter value c with AES-256 using the key P.

Note that, since a block cipher like AES is a pseudorandom permutation, not a pseudorandom function, the output of this method will never contain duplicate blocks. Fortunately, in your use case, this bias will not be practically detectable, since (per the birthday problem) the expected number of random 128-bit blocks one would need to observe to actually see a duplicate is approximately 2⁶⁴, i.e. far more than the number you intend to generate.

Answer 2

What you request is exactly what the CTR cipher mode is doing. I'd implement it as follows:

Lets call the index $i$ for now and assume it is a 32bit Integer. We will also use a hash algorithm $H$ which has an output size that is a multiple of 256bit. Let's use a block cipher which has a block size of 128 and can work with a 256bit key (e.g. AES).

1. Split $H(i)$ into its $n$ 128bit parts $b_0 ... b_{n-1}$
2. Encrypt $b_0$ to $b_{n-1}$ using $P$ as the key: $e_k=C(b_k, P)$
3. Combine two subsequent ciphertexts to 256bit blocks and XOR the groups. The result is the random 256 bits. $r=(e_0 || e_1) \oplus ... \oplus (e_{n-2} || e_{n-1})$