Composite Hash or Dual Hash for extra protection (hybrid hashing)

[Doge Protocol]

Dear PQC Community,

While there are no known "significant" quantum computer vulnerabilities in hashing schemes, for certain use-cases, it might be safer (for future protection) to use multiple  hash schemes (like both SHA256, SHA3).

The motivation is that if one algorithm is broken in the future, at-least the second one gives the protection.

Two ways to do this, where X is input:

Composite Hash = concat(sha256(x), sha3(x)) 

(or)

Dual Hash = sha3(concat(sha256(x), x))

Will be helpful if community can help identify which of the approaches is safer (compared to single hash scheme) or critique this plan.

Note:

1) For sha256, the first 20 bytes will be used to mitigate any length extension attacks.

2) Due to certain backward compatibility reasons of hash sizes, the 2nd option is preferred for a specific use-case, since hash size doesn't change.

[Bas Westerbaan]

Hi Doge,

Let me answer your question, as the symmetric cryptographers in this room seem to be preoccupied.

Both proposals are bad in general. (Both wouldn't be robust against a break of either for Bitcoin's proof-of-work for instance.) The academic term you're looking for is a hash function combiner, see eg [1].

The history of cryptanalysis suggests though, that you'd be better off picking a single decent hash function and doubling its rounds.

Best,

 Bas

[1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=597291d0bc9da048d5315e1d5eb34dbbc2e54656

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/3df92ff4-de38-4cc7-8344-403549a83b6bn%40list.nist.gov.

[Doge Protocol (DP)]

Thanks for your valuable suggestions Bas! We will go over the paper and also take into account the two rounds suggestions.

Since the hashes will be used in a public ledger, we are looking to keep it secure even in the face of new developments in the crypt-analysis space many decades from now.

[Doge Protocol]

Dear Dr.Markku,

Thanks for your input. 

>>>(H1(x), H2(x)) -- in this case it is sufficient to find a pre-image of H1 or H2 to recover x from the composite hash.

In the use-case we are trying to protect, X is not a secret but is meta-data in a public ledger. The application layer will recalculate the hash from the provided meta-data. X is well-formed with specific maximum-lengths; it will be verified for correctness at the application layer before hashing; hence the chances of collisions are hopefully lower than, say, if X were to be an arbitrary value with arbitrary lengths.  

If one of the hashing schemes is broken in a way that meta-data of two transactions can be created for the same hash (like by a bad actor), then the original one of the two cannot be determined. Hence we were wondering what would be a reasonable hedge against one hashing algorithm broken in the long run.

>>> but I don't immediately see what you gain from truncating H2 in this instance -- especially SHA2-256 to 20 bytes, since the faster, stronger variant SHA2-512 offers a 64-byte output.

Thanks, this sounds like a good idea and we will use SHA2-512 instead of SHA2-256 with truncation. 

Trading-off performance heavily for "hopefully" better security, current line of thinking is one of the following:

SHA3-256(SHA-512(X), X)

(or)

SHA3-256(SHA3-256(SHA-512(X), X),X)

Because of an existing system we are forking, the hash has to be 32 bytes long, hence the outer is still SHA3-256.

Our goal is to preserve the integrity of the ledger even in the face of new developments in the long-run like 30 or 40 years from now. Thanks for all suggestions that we are hoping will help achieve this goal.

>>>In any case, such compositions are best analysed using proofs-based argumentation rather than casually as above -- so that the actual security properties gained are well understood. Cryptographers usually do a peer-reviewed publication before even considering using new constructs in the field; IACR FSE / ToSC would probably be the most appropriate venue for that in this instance.

Thanks, we will look into this.

On Wed, May 3, 2023 at 11:58 PM Markku-Juhani Olavi Saarinen <mj...@iki.fi> wrote:

On Thu, May 4, 2023 at 6:17 AM Doge Protocol (DP) <dogepr...@gmail.com> wrote:

Thanks for your valuable suggestions Bas! We will go over the paper and also take into account the two rounds suggestions.

Since the hashes will be used in a public ledger, we are looking to keep it secure even in the face of new developments in the crypt-analysis space many decades from now.

Hi,

Bas actually suggested increasing the number of rounds if the security of the core hash function is felt to be insufficient, rather than having two rounds. Trivial "two-round" constructions like H(H(x)) are of course equivalent to a single hash H(x) in viewpoint of collision resistance, and hybrids often have the security of the weakest part in the link; for example having collisions in MD5(m1)=MD5(m2) of course implies collisions SHA2(MD5(m1)) = SHA2(MD5(m2)) in the composite too.

Similar argument is true for your composite concat(H1(x), H2(x)) -- in this case it is sufficient to find a pre-image of H1 or H2 to recover x from the composite hash. Pre-image attacks are the sort of things that matter in password search; it is quite clear that if one has two password hashes then the attack becomes easier; you can recover the password from either one. The second offered two-round composition H1(H2(x), x) has a bit more potential, but I don't immediately see what you gain from truncating H2 in this instance -- especially SHA2-256 to 20 bytes, since the faster, stronger variant SHA2-512 offers a 64-byte output.

In any case, such compositions are best analysed using proofs-based argumentation rather than casually as above -- so that the actual security properties gained are well understood. Cryptographers usually do a peer-reviewed publication before even considering using new constructs in the field; IACR FSE / ToSC would probably be the most appropriate venue for that in this instance.

--

Now, if one wants to actually strengthen the outer hash "mu" computation for "Dilithium5++" (Section 4 of the spec, "Extended Security Parameters") the most obvious thing to do would be to simply use SHA3-512 instead of 512-bit SHAKE256 for computation of mu = H(H(pk) || M) in ( lines 10 and 28 of Fig 4 in the Dilithium spec). In this "buffed" mode the stock SHA3-512 offers basically 512-bit security against relevant attacks.

Note that for long messages SHA3-512 runs at roughly (1600-2*512)/(1600-2*256) = 53% of the speed of 512-bit SHAKE256; the SHA3 standard is designed in a way that it in a way increases the number of rounds per bytes processed with the security level (of course the security increase actually comes from increased capacity in the Sponge, as the Keccak permutation already has at least 2/3 of its rounds as a security margin). Furthermore note that SHAKE256 has a substantially higher security margin than SHA2-512, and eliminates some attacks that the latter has.

Cheers,

- markku

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/6fc5a5f4-a145-4131-9387-c9874442d24dn%40list.nist.gov.

Virus-free.www.avg.com

[Markku-Juhani O. Saarinen]

On Thu, May 4, 2023 at 6:17 AM Doge Protocol (DP) <dogepr...@gmail.com> wrote:

Thanks for your valuable suggestions Bas! We will go over the paper and also take into account the two rounds suggestions.

Since the hashes will be used in a public ledger, we are looking to keep it secure even in the face of new developments in the crypt-analysis space many decades from now.

Hi Doge, I hope the Doge business is doing well.

Bas actually suggested increasing the number of rounds if the security of the core hash function is felt to be insufficient, rather than having two rounds. Trivial "two-round" constructions like H(H(x)) are of course equivalent to a single hash H(x) in viewpoint of collision resistance, and hybrids often have the security of the weakest part in the link; for example having collisions in MD5(m1)=MD5(m2) of course implies collisions SHA2(MD5(m1)) = SHA2(MD5(m2)) in the composite too.

Similar argument is true for your composite concat(H1(x), H2(x)) -- in this case it is sufficient to find a pre-image of H1 or H2 to recover x from the composite hash. Pre-image attacks are the sort of things that matter in password search; it is quite clear that if one has two password hashes then the attack becomes easier; you can recover the password from either one. The second offered two-round composition H1(H2(x), x) has a bit more potential, but I don't immediately see what you gain from truncating H2 in this instance -- especially SHA2-256 to 20 bytes, since the faster, stronger variant SHA2-512 offers a 64-byte output.

In any case, such compositions are best analysed using proofs-based argumentation rather than casually as above -- so that the actual security properties gained are well understood. Cryptographers usually do a peer-reviewed publication before even considering using new constructs in the field; IACR FSE / ToSC would probably be the most appropriate venue for that in this instance.

--

Now, if one wants to go beyond 256-bit / Cat 5 security level and strengthen the outer hash "mu" computation for "Dilithium5++" (Section 4 of the spec, "Extended Security Parameters") the most obvious thing to do would be to simply use SHA3-512 instead of 512-bit SHAKE256 for computation of mu = H(H(pk) || M) in ( lines 10 and 28 of Fig 4 in the Dilithium spec). In this mode the stock SHA3-512 offers basically 512-bit security against relevant attacks.

Note that for long messages SHA3-512 runs at roughly (1600-2*512)/(1600-2*256) = 53% of the speed of 512-bit SHAKE256; the SHA3 standard is designed in a way that it in a way increases the number of rounds per bytes processed with the security level (of course the security increase actually comes from increased capacity in the Sponge, as the Keccak permutation already has at least 2/3 of its rounds as a security margin).

Furthermore note that a 512-bit SHAKE256 used in Dilithium2/3/5 has a substantially higher security margin than SHA2-512, and eliminates some attacks that the latter has.

Cheers,

- markku

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/6fc5a5f4-a145-4131-9387-c9874442d24dn%40list.nist.gov.