Score:3

How would a malicious group of co-signers use a hash collision to sign an unintended message?

ar flag

According to BIP340:

However, a major drawback of this optimization is that finding collisions in a short hash function is easy. This complicates the implementation of secure signing protocols in scenarios in which a group of mutually distrusting signers work together to produce a single joint signature (see Applications below). In these scenarios, which are not captured by the SUF-CMA model due its assumption of a single honest signer, a promising attack strategy for malicious co-signers is to find a collision in the hash function in order to obtain a valid signature on a message that an honest co-signer did not intend to sign.

In the version of Schnorr used by BIP340, the arguments to the hash function are given by the following:

$e=\text{hash}(R || P || m)$

In order to sign an unintended message, a malicious signer would need to find a collision between two different messages:

$e=\text{hash}(R||P||m_0)=\text{hash}(R||P||m_1)$

But this implies $m_0$ is not committed to before calculating $R$. It seems strange that this "attack" requires convincing the honest signer to sign a particular message $m_0$ after they already calculated their particular $R_H$ value. If $m$ were committed before generating $R$ is this type of attack still possible?

Score:1
in flag

The point is you (and me) did not read the document properly;

In your quoted part they consider attacking Schnorr signature variant, To simplify I will use a shorter notation as $H(m)$

Yes, they consider the collision for the attack. If there is a signature $sign(prv,H(m))$ and you want to forge you need the pre-image attacks on the hash function $H$ so that you can claim that $m'$ is was the intended message.

In the quoted part of the Bip340 document, this is the case. You want your co-signer to sign a message that they normally don't want to sign. So you find some collision pairs $m_i \neq m'_i$ such that $H(m_i) = H(m'_i)$ with additional property; your cosigner will sign for $m_i$ but not for $m'_i$ for which the second one is on your benefit but not their. They will not be suspicious of $m_i$ to sign and they will sign and you will use the $m'_i$ as the signed message to gain an advantage against your co-signer.

later they wrote as;

Since we would like to avoid the fragility that comes with short hashes, the $e$ variant does not provide significant advantages. We choose the $R$-option, which supports batch verification.

If you commit $m$ before signature, then neither collision nor pre-images will work. Let see;

  • $commit = H(m)$

  • calculate $R$

  • prepare the hash for signature

    $\text{hash}(R || P || m)$

In this case, the malicious co-signer need to attack the $commit$ to find another second message $m'$ such $H(m) = H(m')$, i.e. execute a second pre-image attack and this will hold for $\text{hash}(R || P || m) = \text{hash}(R || P || m')$, too. Quite not possible.

kelalaka avatar
in flag
@knaccc It is too hard to find that work both. I've no information about multi-preimage attacks probability for such cases. At least it should be harder than 128-bit search.
knaccc avatar
es flag
I think the reason this question has caused so much confusion is that they are indicating that the problem is that an $(e, s)$ signature pair with short hashes would "complicate the implementation of secure signing protocols in scenarios in which a group of mutually distrusting signers work together to produce a single joint signature". However, since they never explained what the signing protocol would be for the $(e, s)$ variant that they rejected, we need to figure out ourselves what that protocol would have been, in order to see how it would be vulnerable to birthday collisions.
kelalaka avatar
in flag
@knaccc I found some of the BIP very badly written not close to rfcs.
ar flag
I found this [blog post](https://medium.com/blockstream/insecure-shortcuts-in-musig-2ad0d38a97da) from a researcher at Blockstream to be quite helpful. It seems like there might be situations in which $m$ is shared *after* the exchange of nonces. For example, nonces may be pre-shared in lightning as an optimization to reduce the number of communication rounds. Note, however, the blog post said this optimization was insecure and only nonce-commitments should be pre-shared, so I'm not sure if sending messages after the nonce would ever happen in practice.
mangohost

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.