BIP340: clarify impact of pre-hashed messages, or support variable-length messages

[sipa]

Context: bitcoin-core/secp256k1#558 (comment)

Right now, BIP340 specifies that imputs are strictly 32-byte messages. This implies that for typical use cases, the message needs to be pre-hashed, and the GGM/rpp/rpsp proof doesn't exactly apply (collision resistance is required too). This is fine for our intended use case, as the message contains inevitable hashes anyway (the signature data contains the txid of outputs being spent), and thus indirectly the security is already based on collision resistance.

Apart from that, there are few technical reasons to not support variable length messages (which in some cases might not have this problem) instead, as the message is always the last input to a hash function anyway.

So we should either:

• Explain the choice for 32-byte messages, and the effect on the security assumption that implies.
• Support variable-length messages, explaining that the lack of reliance on collision resistant only really holds if the message doesn't contain any hashes itself.

[sipa]

Ping @jonasnick, @real-or-random.

[gmaxwell]

Or you should do both. The choice of 32 bytes messages is the one in Bitcoin and isn't going to change, in particular to gain from not prehashing you'd totally break all sighash cache, so it is by no means a free choice.

However, in other applications that don't have that sighashing tradeoff, aren't hashing messages that substantially consist of hashes, I think non-prehashing is clearly preferable. (E.g. if we used SHA1 a non-prehashing version would still be apparently secure now, while a prehashing version would be actually broken).

So I think instead it wouldn't be a problem to say non-prehashing is a variation that an implementation could validly accept but that it isn't used in Bitcoin.

[sipa]

@gmaxwell Right; of course, that's what I meant by the second option. Just because BIP340 is adapted to support variable-length messages doesn't mean that its use in BIP341 would change.

[LLFourn]

This is fine for our intended use case, as the message contains inevitable hashes anyway (the signature data contains the txid of outputs being spent), and thus indirectly the security is already based on collision resistance.

A thought crossed my mind when I read this: What about ANYPREVOUT? If you don't sign the input txids and don't hash the other data before signing it then perhaps you could avoid CR altogether as a requirement assuming ANYPREVOUT becomes the default spend (for key spend as well as taproot spend). This doesn't seem to be a silver bullet though because there is always a duplicate txid attack where the attacker who controls some of the data that determines a joint tx can create another one with the same id and broadcast it first making the first one invalid surreptitiously. For example you could create a collision with the other party's HTLC timeout transaction to stop it being broadcasted (no signature forgery needed). There may be clever ways around this like making sure only the refunding party fully decides the timeout transaction but this puts quite a burden on the protocol designer and these things are already complicated enough as they are (not to mention the implementation complexity of this in bitcoin core).

So for me, just slightly modifying BIP-340 to allow messages of any length and following this up in the implementation would solve my present design dilemma. I don't think there is any impact on the DPA resistance.

[sipa]

@LLFourn Right, there are other reasons why CR is already needed; for one, if you can make a valid and invalid transaction or block hash collide, you can fork the network. So even ignoring anything signature related, I think it's fair to say that Bitcoin inherently relies on (double-)SHA256 collision resistance.

Another reason is the ability to precompute parts of the transaction data in the sighash; without it, you inevitably run into the O(n^2) hashing complexity we had in pre-segwit signing (where large transactions can require a substantial amount of time to just to compute the sighashes).

So yes, I think permitting variable-length messages would work. But it won't affect any usage in transaction signing, I think. The only change would be a few test vectors, and amending the BIP.

[jonasnick]

I can see the a use case for schnorr signatures for arbitrary-sized messages. In particular, oracles that make use of "committed R-point signatures" to be able to atomically sell a signature (on-chain or Lightning) can not easily use another signature scheme to sign arbitrary messages. They want their users to take their R to compute sG and then use a pay-for-DL scheme. If bip-schnorr would support this, specs building on it would be (a bit) simpler and implementations wouldn't have to include a third party lib for hashing.

On the other hand, if messages are long, then users may want to pre-hash anyway to reduce the number of unnecessarily hashed bytes as as the message is also hashed in the nonce derivation function.

[real-or-random]

There's a chance that people will want to do this (inside and outside of the Bitcoin ecosystem), and in that case I'd prefer that we specify how this should be done. And I agree, it's a simple change that doesn't really add complexity to the BIP.

You can also make a case for hashing shorter messages. If I want to hash variable-length messages of up to 16 bytes for example, it's easy to get the encoding wrong if you're forced to pass a 32-byte array.

Here's one strange observation though: It's unlikely but not impossible that someone specifies a cryptographic protocol interacting with Schnorr signatures in a non-blackbox way (we have seen many of those, e.g., Taproot itself :P) where the signer needs to reveal either the secret nonce k or the signature (but not both!) for some message m. This seems fine but if you combine this with variable-length messages and our nonce derivation function, you'd run into a very subtle length-extension attack. The attacker can then obtain k for a message m and predict k' for some message m||m'. That's bad if the attacker gets a signature on m||m' too.

Yeah, I admit it's not likely but can this be avoided easily? Normally I'd suggest to add the message to the hash before the secret key but that undermines all our anti power analysis efforts. You can also use double SHA256 but that's slow. It seems that the simplest defense is to prepend the message with its length then. Assuming 32-byte messages, we have a few bytes left in the second compression. I'm really not sure if this is worth the hassle.

[roconnor-blockstream]

The reason we believe that SHA-256 has the rpsp property is because it follows from the assumption that the SHA-256 compression function is collision resistant. But that assumption that the SHA-256 compression function is collision resistant also implies that SHA-256 itself is collision resistant.

So while, yes, it is technically possible that SHA-256 is broken and has a collision, which in turn implies that SHA-256 compression function has a collision, while at the same time magically maintaining the rpsp property in spite of the brokenness of the compression function, it seems absurd to me to design an API around this possibility.

If people want to sign variable length messages they should hash it with SHA-256 and pass those 32-bytes as the message to Schnorr.

[LLFourn]

@real-or-random Yeah, I admit it's not likely but can this be avoided easily?

Well, adding randomness into nonce generation should do this!

@roconnor-blockstream So while, yes, it is technically possible that SHA-256 is broken and has a collision, which in turn implies that SHA-256 compression function has a collision, while at the same time magically maintaining the rpsp property in spite of the brokenness of the compression function, it seems absurd to me to design an API around this possibility.

I don't think it will take much magic. rpsp is just much harder than finding collisions (unless there is something I don't understand in particular about SHA256). CR of SHA1 is broken and yet the rpp/rpsp properties still hold. But to your point, worrying about CR of SHA256 in anything remotely related to Bitcoin is wasted effort for all the reasons @sipa mentioned and this is a Bitcoin BIP after all.

Perhaps a better solution is to leave the api as is but introduce another function which let's you pass in a variable length message + a domain separator for the tagged hashes. This function then would use "my-domain/aux" and "my-domain/challenge" etc. If you are signing non-transaction messages then you are not in the bitcoin witness domain anyway so you should probably use a different tagged hash.

[edit] I forgot to stress that the reason I want this change is not because of security properties but precisely because of API ergonomics. It will make me scream inside a little bit every time I explain in code or protocol specification "No this is not a hash for security, it's a hash for a particular library's API"

[roconnor-blockstream]

I claim that the ability to find identical-prefix collisions in SHA1 outright breaks the rpsp property of SHA1 (not to mention the chosen-prefix collisions which are only 4x more expensive). I don't believe your claim that the SHA1 rpsp property isn't broken, and if I am wrong about this I would love to be corrected.

P.S. I have no strong opinions about layering an API on top of the existing Schnorr specification that takes a variable length message and hashes it with SHA256.

[LLFourn]

I claim that the ability to find identical-prefix collisions in SHA1 outright breaks the rpsp property of SHA1 (not to mention the chosen-prefix collisions which are only 4x more expensive). I don't believe your claim that the SHA1 rpsp property isn't broken, and if I am wrong about this I would love to be corrected.

This is quite a claim! I'll have to think about that.

[gmaxwell]

@roconnor-blockstream In a few minutes I can break our scheme with pre-hashing and all hashes turned to sha1. I cannot do so without the pre-hashing. If I could, it would be a press generating additional break of sha1.

The MD structure of sha2 means that even an extremely weird and specialized CR break of one run of the compression function with a specific starting state is a generalized break for larger messages starting with that prefix.

The fact that someone uses a proof that having property X means that a hash function has property Y doesn't mean that failing X means it doesn't have Y in practice anymore, it just means that argument no longer works.

You can imagine a property along the lines of "probabilistic prefix collision resistant", where the function is has a small class of efficiently computable collisions but they're all among a very small number of prefixes that you'd never end up with by chance. And so you can't exploit a signer's because of their unknown-to-you R or forge generally because you can't find a point of known DL who's serialization matches the prefix.

I wouldn't argue that this is some radical improvement. But it is NOT conjectural with examples like sha1 and md5. In some applications, though not bitcoin, operating this way lowers hashing costs so it's better than free. Saves cycles and hardens a little against theoretical but realistic attacks on the hash function... What's not to love? It other applications prehashing is critical for performance or for some other reason so it isn't a good trade-off.

[roconnor-blockstream]

If I understand, you are saying it is free to break Schnorr-with-SHA1 because you can just download SHA1 collisions off the internet (not sure why you say a few minutes instead of a few microseconds). But to break rpsp you have to spend $11k per random value in order find a new idenitcal-prefix collision for that particular random value.

I suppose that is something, but SHA1 collisions only exist on the internet because someone (Google) paid for an identical-prefix collision for the empty prefix. However they could have found a collision starting from any particular random prefix for exactly the same price. Hence my claim that SHA1's rpsp is broken.

[roconnor-blockstream]

What is not to love is that, and perhaps I'm speaking of that which I do not know, signing hardware might appreciate the fact that the act of signing is always constant time and only requires a fixed amount of data. Obviously not a problem for Bitcoin wallets as we intend to only use BIP-340 for 32-byte messages in Bitcoin. But why would we write BIPs to support non-Bitcoin applications? If people want to make an IETF Schnorr standard with variable length messages, then they should go right ahead. If it happens to be compatible with BIP-340 on 32-byte messages, all the better.