bip-taproot/tapscript: Prevention length-extension attacks in public key tweaking

[dr-orlovsky]

According the scripts in the section https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki#constructing-and-spending-taproot-outputs a simple SHA256 hash is used over concatenated internal public key and tapbranch merkle root, which (as I assume) prevents multiple script commitments. However, a simple hash of concatenated public key and a tweaking factor (message) may be subjected to a length extension attack. So I propose to use instead of a simple SHA256 digest, a HMAC-SHA356, which has no risk for any known attacks on the hash value alike was proposed in your sidechains paper https://blockstream.com/sidechains.pdf on the page 18.

We have addressed the similar issue during our work on the RGB project and have developed a spec/standard for collision-resistant tagged key tweaking: https://github.com/LNP-BP/lnpbps/blob/master/lnpbp-0001.md. May be it worth merging Some parts of it nto the proposed BIPs?

[sipa]

Length extension attacks are only relevant in case part of the input to the hash is secret, and if the input is variable length. I believe that neither is the case for the bip-taproot tweaking, so I'd rather avoid the extra computational cost.

Do you see more concrete arguments why this may be desirable?

[dr-orlovsky]

No, it seems that all the participants know that whole input to the Merkle root hash used for tweaking the internal key, and nobody outside of the participatns are involved in the verification/check. Again, during the spending, the spending party provides all necessary information to reconstruct the Merkle root hash... So it seems to be unnecessary computational overhead, you are right

[dr-orlovsky]

I can't say that I am 100% sure that the length-extension attacks are impossible for Taproot... I was not able to construct the valid attach vector yet, but I was not able to find some sort of proof ("formal proof"?) that the attack is actually impossible.

Anyway, for RGB, which is client-side validated project, not putting high requirements on the computational performance, I decided to prefer HMAC, just to exclude the possibility of some attacks vectors appearing later down the road.

[elichai]

As sipa says, there's no point in a length extension attack if the inputs are public. You can easily do H(INOUTS ||NEW_ADVERSARY_DATA) and you'll get the same result.

Anyway there's no ambiguity for the commitments here because everything is constant length (a 32 byte pubkey and a 32byte sha256 output)

[dr-orlovsky]

Anyway there's no ambiguity for the commitments here because everything is constant length (a 32 byte pubkey and a 32byte sha256 output)

Theoretically, yes. Practically, I know how people can mess up with an implementation, opening a way for very odd attack vectors. So at least I think that it worth adding to the spec that the inputs for the SHA256 function in the tweaking procedure should be exactly of 64 bit length.

[sipa]

Even if you are concerned about length extension attacks, they're never a concern when the length of data hashed is self-descriptive (i.e. if I'd give you the data fed to the hash function and append garbage to it, you'd still know where the garbage starts). Having fixed length data is one way of it being self-descriptive, but it's not the only one (other ways include having flag bits that determine what optional features are present, prefixing elements with their length, or having a terminator element at the end). I believe that all the hashes in bip-schnorr/bip-taproot/bip-tapscript have data with self-descriptive lengths.