1
$\begingroup$

If I have 256 bits of handwavium "perfectly random data" and I hash these 256 bits of data with a secure hash function (possibly SHA-256).

Could the resulting hash be considered "perfectly random data" as well? I am assuming the answer is "no", but don't know why.

What information / keywords would I use to find out more information about this?

Interesting seemingly related topics:

$\endgroup$
3
  • $\begingroup$ Some background, I was looking into one-time-pads and am trying to figure out what would prevent you from generating an inf one-time-pad from a random seed. $\endgroup$ Mar 5 at 4:21
  • 2
    $\begingroup$ From our reading list. $\endgroup$
    – DannyNiu
    Mar 5 at 4:27
  • 1
    $\begingroup$ The hashing is expected to loose 0.8272… bit of the original 256 bits of entropy. $\endgroup$
    – fgrieu
    Mar 5 at 10:44

3 Answers 3

2
$\begingroup$

Suppose you take your 256 bits of handwavium "perfectly random data" and use it to seed a handwavium "perfect cryptographic seed expansion algorithm", such as the SHAKE XOF -- but it really makes no difference which algorithm you choose. You then generate 257 (or in general any $n > 256$) bits of "random data". In principle, if this was really random data, you'd have $2^n$, for $n > 256$, different bit strings.

However, suppose you cycled through all $2^{256}$ bit strings of "only" 256 bits. Evidently one of these would match the 256 bits of handwavium "perfectly random data" mentioned at the beginning, and having found it, then you'd be able to generate exactly the same $n$ supposedly random bits.

Thus, by brute-forcing "only" 256 bits (a computational effort of $2^{256}$ operations), you can find all $n$ bits, while if they were actually random, you'd need an actual computational effort of $2^n$ (for, again, $n > 256$), which is general is much greater than $2^{256}$.

So don't fool yourself: you only have 256 bits of randomness. Any bit coming after that is a 100% deterministic function of those 256 bits, and thus adds no randomness at all.

$\endgroup$
2
  • $\begingroup$ I think I understand what your saying, and agree with it. Argument for argument sake ... let say the orig 256 bits of handwavium "perfect random data" is destroyed/forgotten/never transmitted after the hash algo created a new 256 bits of deterministic data. How is this new data less "random" than the entire rest of the key space? $\endgroup$ Mar 5 at 5:24
  • 1
    $\begingroup$ Assuming you really throw away your "perfect random data", and that you use a "perfect" hash function, for which no attacks that reduce its preimage resistance exist, then your first 256 bits of deterministic data should be OK. Once you generate a 257th, you're back to the same problem. But if you can only securely generate the exact same 256 bits you started with (which, recall, you threw away), then why go to the trouble and computational expense of hashing it? Just use the random data directly. $\endgroup$
    – swineone
    Mar 5 at 5:31
1
$\begingroup$

Why cant you use randomness to seed more randomness?

Obviously you can, that's what any (Cryptographically Secure) Pseudo Random Number Generator or (CS)PRNG does after all.

Could the resulting hash be considered "perfectly random data" as well? I am assuming the answer is "no", but don't know why.

"Perfect random data" does not really have a formal definition. However, let's assume that we want to use this data as a key stream in an OTP, a use case that is more or less implied by using "perfect" in the term. In that case an attacker should not be able to find out any information about the values of the plaintext (bits) nor by extension of the key stream.

It is easy to see that the random data created by the hash function doesn't have this property: only specific messages (say of the same size as the hash output) are possible as the set of ciphertexts are limited by the amount of hash values available - 256 in this case. So no, in that sense the hash output certainly is not perfectly random.


The above assumes that every bit within the hash result should be considered random, and this assumption would generally be true for most use cases. However, the hashes are still perfectly random within the group created by the 256 unique hash values. There is a known 1:1 mapping between "seed" and hash output in this case.

This won't hold for any seed size due to overlapping hash output values (the pigeonhole principle). It should not be possible to generate a hash collision so this is of no practical concern. However, for perfect security we're not limited to practical concerns.

So the answer relies on the output domain; the answer is no-but-maybe-yes. This shows that it is impossible to have a rigorous answer without a well defined question.

$\endgroup$
0
$\begingroup$

I was looking into one-time-pads and am trying to figure out what would prevent you from generating an inf one-time-pad from a random seed.

One time pads.

Let me respond to a quote with another quote:-

It seems natural to call a chain random if it cannot be written down in a more condensed form, i.e., if the shortest program for generating it is as long as the chain itself.

-Andrey N. Kolmogorov.

Seeds have no place in OTPs. None. You suggest iterating $s' \leftarrow H(s)$. I just wrote that down yet that's in total opposition to the quote above. So no. Read about Kolmogorov complexity and how to encode the nice piccy on that web page. And these two .SE tags 1 & 2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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