1
$\begingroup$

Consider the following system

1 - fixed string as a seed, example "something"

2 - concat an increment number "something-1"

3 - hash it, assume it is "9f2054ea4d2c"

4 - take the first 3 digits to get a number between 0 and 4095 for example

The next number will be taken from the hash of "something-2" and so on

$\endgroup$
  • $\begingroup$ Define random! That's certainly not "true random". That's computationally indistinguishable (from true random) under appropriate hypothesis on the hash and the seed. $\endgroup$ – fgrieu Oct 9 at 7:06
  • $\begingroup$ By random I meant, the next number in the sequence cannot be predicted $\endgroup$ – Mocas Oct 9 at 7:10
  • $\begingroup$ What is the size of the input? It must be larger than 70 bits. Also, hash outputs are bits, if you convert the output into base 10, you will get a biased output. $\endgroup$ – kelalaka Oct 9 at 7:24
  • $\begingroup$ Note that using a (PB)KDF on the (large, secret) fixed string and then using a stream cipher to create the deterministic numbers would be much more efficient. That is, if you are trying to create a deterministic generator that depends on just the seed / fixed string. $\endgroup$ – Maarten Bodewes Oct 9 at 10:58
  • $\begingroup$ Rereading this question, it seems like you're trying to define a poor mans KDF here. I'd certainly read into Key Derivation Functions and how they can be used. $\endgroup$ – Maarten Bodewes Oct 9 at 15:36
2
$\begingroup$

No, the next number in the sequence of the generator in the question cannot be safely considered unpredictable. At least one reason for that: we can infer from the example seed value "something" that the seed is not entropic enough. An adversary knowing the method, the hash, and the first 3 outputs or so could very plausibly enumerate likely seeds from a dictionary of common English words, find one that matches known output, and use that to predict further outputs with fair confidence. Even with less output, the adversary can get a slight advantage compared to a random guess.

The scheme proposed would be computationally indistinguishable from true random under some reasonable but unstated hypothesis:

  • The counter never cycles or otherwise resets, which is not trivial to ascertain in practice (e.g. when adversaries can cut power at any time).
  • The computations are performed secretly and correctly; no untold leak of seed or intermediary results, or fault, occurs. This is hard to ascertain in practice (for a start, who knows there's no trojan in that computer? Also, side-channel/fault attacks are a real thing).
  • The seed is secret, large and random-enough that it can not in practice be found by enumeration using the computational power available to an adversary. It is acknowledged that 128-bit entropy is safe with current technology, and twice that more than safe enough even assuming hypothetical quantum computers usable for cryptanalysis. 128-bit entropy can be obtained with $\lceil128/\log_2(26)\rceil=28$ lowercase letters chosen independently and uniformly at random.
  • The hash is computationally indistinguishable from a Pseudo Random Function. As far as we know SHA-256 would be good enough in practice, especially with truncation of the output as we have here. SHA-512 would be even safer. Further, the HMAC construction could be used (instead of hashing the hash of a concatenation) to combine seed (used as key) and counter (used as the data input) in a manner giving more assurance against hypothetical attacks on the hash.
    Note; standard properties of hash funcions are lesser than being a PRF, and do not even include having near equidistributed output for random input.
  • Leading zeroes in the hash are kept (which is not entirely clear in the question's statement), so that integers less than 256 are not underrepresented.
$\endgroup$
  • $\begingroup$ A random seed isn't enough, look at my example with the $h(x||k) := h(x) \oplus h(k)$, at least if we assume any hash (which might be impractical but the questioneer just asked for hash). $\endgroup$ – Martin Kromm Oct 9 at 9:21
  • $\begingroup$ @Martin Kromm: Yes. That's a reason why my first paragraph uses "at least", and why my last bullet asks for a hash computationally indistinguishable from a Pseudo Random Function, which is a stronger condition than the four you state. $\endgroup$ – fgrieu Oct 9 at 9:38
  • $\begingroup$ It sounds missleading or still not enough to me. Let's say h with input length n is indistinguishable from a pseudorandom function and XOR of two hashes is used as length-extension, the attack would still work to me, wouldn't it? $\endgroup$ – Martin Kromm Oct 9 at 9:49
  • $\begingroup$ I'm just concerned about the statement 'except perhaps for the length-extension property, which is of no use to an attacker here'. Even if we assume h is defined as $h(x||k) := rand_1(x) \oplus rand_2(k)$ with length of x always higher than length of k and $rand_1$ and $rand_2$ random functions taken randomly from the set of all possible functions the attack works. I would just delete that statement and your answer is fine then. $\endgroup$ – Martin Kromm Oct 9 at 11:11
  • $\begingroup$ @Martin Kromm: Ah I now get what you mean. Right. Removed that statement, which was less than correct, which by definition is wrong. $\endgroup$ – fgrieu Oct 9 at 11:14
1
$\begingroup$

Let us repeat the properties for a hash function:

  1. Given h(x) but not x, the adversary can't compute x in polynomial time but a negligible chance (preimage-resistance).
  2. Given a pair x and h(x), the adversary can't compute y such that h(y) = h(x) in polynomial time but a negligible chance (second-preimage resistance).
  3. The adversary can't compute any x and y such that h(y) = h(x) in polynomial time but a negligible chance (collision resistance).
  4. Given x, the adversary can always compute h(x) in polynomial time.

Now let us assume H a function which is defined as an oracle which computes $h(x||x_i)$ at the ith query of H. If H is a pseudorandom generator, then the distribution $(t_1, ..., t_n)$ of n queries of H must be indistinguishable from the distribution $(r_1, ..., r_n)$ of n queries of a real random function R.

Let us assume x and $x_1, ..., x_n$ are known and fixed. Now we run into our first problem. Since both x and $x_1, ..., x_n$ is known to the distinguisher, the distinguisher can simply compute $z := h(x||x_1)$ himself and then can check if $y_1$ of the distribution $(y_1, ..., y_n)$ (which is either generated by H or by R) is equal to $z$ to see if the distribution is from H or from R.

Now assume x is chosen randomly given a security parameter $1^n$ and $x_1,..., x_n$ is still fixed and known to the distinguisher. On first sight, one would believe that since the distinguisher can't compute $x||x_i$ given $h(x||x_i)$ in polynomial time but a negligible chance any hash would be a pseudorandom generator. However, this is doesn't need to be the case: Let us assume $h(x||k) := h(x) \oplus h(k)$ holds if the length of x is higher than the length of k. Then a distinguisher can distinguish by computing $z := h(x_1) \oplus h(x_2)$ and check if $z$ is equal to $y_1 \oplus y_2$ from the given distribution $(y_1, ..., y_n)$ to distinguish H and R.

Please note that the strategy with XOR above doesn't work for most used practical used hashes like SHA256 since the assumption doesn't hold. However, you must be careful to choose a hash function which is resistant against such attacks (for example SHA256 is weak against length message attacks which might also work).

A strategy which could work is to choose a random seed (which is not publicly known) and use a part of the output of the hash which is not used as the actual output as the next input (but be careful to use a large enough output length then!).

$\endgroup$

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.