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$ Commented 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$ Commented 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$ Commented 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$ Commented Nov 23, 2022 at 23:18

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.