1
$\begingroup$

A user of this forum said that the whole entropy of a seed goes to the hashed result if using a counter and also that is suitable for key generation even if the internal state or digest size of the hash function is smaller of that of seed.

Let's suppose I have a seed with an entropy of 512-bits and hash it with a counter using a hash function with half of the seed size in bits as Blake2s (256-bits digest size).

I hash the seed in this way

$$H(S||00) || H(S||01) || H(S||02) || H(S||03) || \cdots$$

$H$ is the hash function, $S$ is the seed and $00, 01, 02, 03$ the block counter.

After this I make an encipherment scheme just XOR'ing the result in the plaintext.

My question is:

Will I have the same cryptographic strength of the seed used even if the seed size is larger than the hash output or its internal state?

$\endgroup$
1
  • 2
    $\begingroup$ One cannot increase the input entropy without additional entropy where Hash functions are actually reduce the entropy, well a little see. You may consider that your security at most is $\min\{\text{input},\text{output}\}$ $\endgroup$
    – kelalaka
    Oct 18, 2022 at 5:39

1 Answer 1

2
$\begingroup$

will $H(S\mathbin\|\mathtt{00})\mathbin\|H(S\mathbin\|\mathtt{01})\mathbin\|H(S\mathbin\|\mathtt{02})\mathbin\|H(S\mathbin\|\mathtt{03})\mathbin\|\ldots$ have the same cryptographic strength of the seed used even if the seed size is larger than the hash output or its internal state?

If we model $H$ as an ideal hash, that is as a random function with fixed size output: essentially† yes. For that model of the hash, each segment $H(S\mathbin\|\mathtt{uv})$ of the overall result for a particular input $F$ is independent of the others segments for that particular input $F$, and of every other segments for other inputs $F$.

For $H$ a practical hash: not quite, at least because the hash structure limits the number of possible outputs for any fixed size of $S$. For SHA-256 or any Merkle–Damgård hash with block size much larger than the state/output size, the worst case is when $S$ is exactly a multiple of the block size of the hash (512-bit for SHA-256): the Merkle–Damgård structure "limits" the number of states of the hash after processing $S$ to $2^{256}$, the multiple instances of $H$ are in the same 256-bit state at this point, thus there are at most $2^{256}$ output states for the overall output.

On the other hand, that's purely theoretical: 256-bit entropy is plenty enough, SHA-256 generally aims at "only" 128-bit security, and if we want more there's SHA-512.

Note that if we use $H(\mathtt{00}\mathbin\|S)\mathbin\|H(\mathtt{01}\mathbin\|S)\mathbin\|H(\mathtt{02}\mathbin\|S)\mathbin\|H(\mathtt{03}\mathbin\|S)\mathbin\|\ldots$ we somewhat improve things, because the multiple hashes no longer are in the same state, thus there can be much more entropy in the overall output.


† Even a perfect hash is bound to reduce entropy, but that's only slightly, see this; and this effect is very small in the context of the question.

$\endgroup$
3
  • $\begingroup$ You say about Merkle–Damgård constructions, does the same applies to Merkle tree based hash functions? $\endgroup$ Oct 19, 2022 at 1:54
  • $\begingroup$ @phantomcraft: It think the situation with a Merkle tree based hash is in between that for a Merkle–Damgård hash $H(S\mathbin\|\mathtt{00})\mathbin\|H(S\mathbin\|\mathtt{01})\mathbin\|H(S\mathbin\|\mathtt{02})\mathbin\|H(S\mathbin\|\mathtt{03})\mathbin\|\ldots$ (minimum entropy, potentialy down to the hash size) and $H(\mathtt{00}\mathbin\|S)\mathbin\|H(\mathtt{01}\mathbin\|S)\mathbin\|H(\mathtt{02}\mathbin\|S)\mathbin\|H(\mathtt{03}\mathbin\|S)\mathbin\|\ldots$ (maximum entropy, near the output width). $\endgroup$
    – fgrieu
    Oct 19, 2022 at 5:44
  • $\begingroup$ And about H(H(F) || 00) || H(H(F) || 01) || H(H(F) || 02) || H(H(F) || 03) || .. ? How does it compare to H(00||S) || H(01||S) || H(02||S) || H(03||S) || ... ? -- If I use H(00||S) || H(01||S) || H(02||S) || H(03||S) || ... instead of H(S||00) || H(S||01) || H(S||02) || H(S||03) || ..., the answer to my question would be "yes"? $\endgroup$ Nov 23, 2022 at 23:18

Your Answer

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

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