Hashing a seed together with a block counter and using as a encipherment scheme: Will this have the same security in bits as the seed used?

pf flag

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?

kelalaka avatar
in flag
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}\}$
ng flag

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.

phantomcraft avatar
pf flag
You say about Merkle–Damgård constructions, does the same applies to Merkle tree based hash functions?
fgrieu avatar
ng flag
@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).
phantomcraft avatar
pf flag
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"?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.