0
$\begingroup$

Let $A$ denote a sequence of bits.

Let $H$ denote a cryptographic hash function that has no limit on the length of its input (for example, SHA-3).

Consider the following infinite sequence of bits: $$B = H(A) \mathbin\Vert H(0 \mathbin\Vert A) \mathbin\Vert H(1 \mathbin\Vert A) \mathbin\Vert H(00 \mathbin\Vert A) \mathbin\Vert H(01 \mathbin\Vert A) \mathbin\Vert H(10 \mathbin\Vert A) \mathbin\Vert \ldots$$ (that is, the prefix goes through all possible bitstrings, sorted by their lengths).

Can we assume that for any chosen $A$, its corresponding $B$ is unique and contains all possible finite bitstrings (similarly to a binary representation of a fractional part of Pi)? If yes, can we use such technique as a cryptographically secure pseudo-random number generator that has no theoretical period?

$\endgroup$
  • $\begingroup$ What do you mean by B is unique? that whatever $A_1$, $A_2$ you pick, the correspondings $B_1$ and $B_2$ will be different? $\endgroup$ – Florian Bourse Mar 7 '18 at 9:29
  • $\begingroup$ @FlorianBourse: Starting from some (even arbitrarily large!) finite offset, yes, the corresponding $B_1$ and $B_2$ will be different. I mean that any $A$ corresponds to an unique $B$, and each unique $B$ can be regarded as a binary representation of a fractional part of some normal irrational number. $\endgroup$ – lyrically wicked Mar 7 '18 at 9:37
1
$\begingroup$

Can we assume that for any chosen A, its corresponding B is unique and contains all possible finite bitstrings

No. Due to your requirement $H$ is compressing. This means that collisions must exist. Depending on your hash function construction, a collision might lead exactly the same output sequence. As a constructed example assume a hash function that processes input blocks from right to left and feeds them to SHA3. Any SHA3 collision would then work. Indeed, you cannot argue that your assumption above holds just with standard properties of a hash function.

However, finding such messages is extremely hard. Already finding two messages that lead one identical block of B is hard by the collision resistance of the hash function.

can we use such technique as a cryptographically secure pseudo-random number generator that has no theoretical period?

No. There are also several arguments against building a PRG this way. For example with common hash functions like SHA3 this construction would be extremely expensive as you cannot reuse previous results in computing B.

$\endgroup$
  • $\begingroup$ But I thought that one of the basic properties of a random oracle is that if all inputs are different, all outputs are chosen independently with uniform random distribution? Doesn't this mean that a concatenation of these ouputs contains all possible bitstrings (as in all normal irrational numbers)? But if my assumption is wrong, then the chosen $H$ cannot be regarded as a simulator of a random oracle? $\endgroup$ – lyrically wicked Mar 7 '18 at 8:59
  • $\begingroup$ How is the existence of a collision a contradiction to OP's statement? $\endgroup$ – Florian Bourse Mar 7 '18 at 9:28
  • $\begingroup$ @lyricallywicked Sure, if the hash function is a random oracle, this is a perfect PRG. But the best we can hope for is a hash function that is indifferentiable from a RO up to a certain amount of queries. I understood your question as refering to the statistical properties. $\endgroup$ – mephisto Mar 8 '18 at 9:45
  • $\begingroup$ @FlorianBourse In the example hash function I give, a collision means that the computed $B$'s for the two colliding messages are identical while OP asked if the $B$'s are unique. $\endgroup$ – mephisto Mar 8 '18 at 9:50
  • $\begingroup$ @mephisto: Are you referring to state collisions (as described on page 2 of keccak.team/files/SpongeFunctions.pdf)? Surprisingly, I forgot to take them into account for this question... $\endgroup$ – lyrically wicked Mar 8 '18 at 10:47

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.