1
$\begingroup$

I want to have a source of randomness for which:

  • no one but me can predict the next number in the sequence.
  • I know the entire sequence in advance, but I have no way of manipulating it once the first number in the sequence has been shared with others and everyone can verify that this is the case.
  • it's okay for this sequence to be finite, with the total length being determined in advance.

So, one idea was to take a secret and hash it a few million times. Something like this:

N1 = sha3(secret)
N2 = sha3(N1 + 1)
N3 = sha3(N2 + 2)
N4 = sha3(N3 + 3)
.....

I would then publish the sequence in reverse, starting with Nn. The +# in each step is to avoid loops.

Now the question is, is this secure? Thinking back to my information security classes I recall that one shouldn't apply encryption multiple times as this weakens security.

So,

  • A: does this mechanic of creating the pseudo-random sequence somehow facilitate it for an attacker to predict an arbitrary future element (from which he then easily could rebuild the chain down to the current element)?

  • B: does this mechanic of creating the pseudo-random sequence somehow allow me to cheat?

$\endgroup$
  • $\begingroup$ The addition doesn't really do anything to prevent cycles ("loops"); you're still just iterating what is essentially a random function and will get cycles with overwhelming probability. That said, the cycles will be huge so it's nothing to worry about if you account for them in your security bounds. $\endgroup$ – Thomas Aug 20 '18 at 8:29
  • $\begingroup$ @Thomas: the addition of a counter does reduce the probability of falling in a cycle (like exponentially with the period of the counter). The addition of a constant would not. $\endgroup$ – fgrieu Aug 20 '18 at 8:32
1
$\begingroup$

A: No, an attacker can not guess an earlier number. That would amount to a preimage attack for the hash. S/he can not even gain a sizable advantage towards such guess. Arguments (not proofs)

  • Assuming $\text{secret}$ is full-entropy, the first hashing causes a sizable entropy loss ($0.827\ldots$ bit, see this), and each further hash causes a further entropy loss, but by an heuristic argument, after $k$ iterations, only $\approx\log k$ entropy is lost, thus plenty enough remains (for SHA3-224 and a million millions iterations, >195 bits).
  • Because it is added a counter rather than a constant, the $N_i$ falling into a short cycle becomes next to impossible, rather than very improbable.

B: The first number disclosed $N_k$ should come with it's index $k$, so that verification of the next number disclosed $N_{k-1}$ is possible by checking $N_k=\text{SHA3}(N_{k-1}+k-1)$ without guesswork on $k$. You can't manipulate the sequence once $N_k$ and $k$ have been shared with others. If you could, that would break the collision resistance of the hash.

Without $k$ published you would have a narrow possibility of fraud: on the second day you can publish $N_{k-1}+j$ and pretend $k$ was $j$ less than it really is; you wont be caught until the next day, and can't be caught if $j=k-1$.

Note: you could manipulate the $N_i$ when choosing the secret, e.g. so that $N_{987}$ is odd; and of course you know all the $N_i$.

$\endgroup$
  • $\begingroup$ Thank you for your reply. So that also means that sha3(1+sha3(2+sha3(3+sha3(4+(....1000000000+sha3(secret))))) is in no way weaker than sha3(secret)? I just wonder whether knowing that this counter is somehow part of the hashing function makes it more easy to crack it $\endgroup$ – user1282931 Aug 20 '18 at 9:51
  • $\begingroup$ @user1282931: I mean what you state, with for practical purposes where there is in no way. I added some justification. $\endgroup$ – fgrieu Aug 20 '18 at 12:12

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.