3
$\begingroup$

I have a 256-bit seed; call it P. From P, I need to derive 219 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?

$\endgroup$
  • 2
    $\begingroup$ HMAC-SHA256(seed as key, counter) should suffice provided the seed is generated from a good randomness source. $\endgroup$ – Artjom B. Dec 26 '15 at 23:04
6
$\begingroup$

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 (≪ 264), 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 264, i.e. far more than the number you intend to generate.

$\endgroup$
1
$\begingroup$

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})$
$\endgroup$
  • $\begingroup$ The hash doesn't seem necessary, because a block cipher should be known-plaintext secure. Is there some reasoning behind it? You could also use $r_i = C(i||0, P) || C(i||1, P)$ where $||$ denotes concatenation provided $C$ has a 128 bit block size. Or you could use a block cipher with a 256 bit block size to do this without any concatenation. $\endgroup$ – Artjom B. Dec 26 '15 at 23:42
  • $\begingroup$ The hash is not required. I dont know about Any padding techniques for the counter in CTR; i added the hash to be on the safe side. I frickled the 128bit cipher in there because i believe AES is the most battle-tested cipher available - and it has 128bit (yes, Rihjandel 256 would work, too, but again i'd rather be on the safe side) $\endgroup$ – marstato Dec 26 '15 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.