Insecure implementation of BLS threshold signatures

[OrestisAlpos]

Hello. I was using the program and observed some possible issues in crypto/bls12/bls12/go.

Namely, the methods CreateThresholdSignature() and VerifyThresholdSignature() actually create (and verify) an aggregate, not threshold, signature, which is insecure when partial signatures sign the same message. That is explained in Section 5.1 of the BLS paper: https://link.springer.com/content/pdf/10.1007/s00145-004-0314-9.pdf
What we actually want is described on Section 5.3 of the BLS paper.

The implemented version could be seen as a multi-signature, but still it is susceptible to the rogue-key attack, because it just adds the public keys and signatures. The correct implementation would be as in Section 3.1 of the BDN paper: https://eprint.iacr.org/2018/483.pdf

Even if one is only interested in benchmarking (and does not plan to use this in production), I am afraid the results might still be misleading, since the computations behind a threshold signature (or a correct implementation of multi-signature) are different than what the code currently does.

[johningve]

Hi!

Namely, the methods CreateThresholdSignature() and VerifyThresholdSignature() actually create (and verify) an aggregate, not threshold, signature, which is insecure when partial signatures sign the same message.

Indeed, the bls12 implementation is not "production-grade" and does not protect against rogue-key attacks. The main reason I implemented it in the first place was to figure out how to support different crypto technologies in the module system, and to experiment with aggregate signatures.

What we actually want is described on Section 5.3 of the BLS paper.

If I understand this correctly, these signatures would not validate at all unless the threshold is met, as opposed to our current implementation which verifies an aggregate and then checks that the number of participants meets the threshold?

I am currently working on implementing Handel as an alternative way to aggregate the signatures. My implementation relies on being able to verify an aggregate signature even before it meets the threshold for consensus. Would this be possible with true threshold signatures?

[leandernikolaus]

Hi,

I wonder if we should at least rename CreateThresholdSignature and VerifyThresholdSignature to CreateMultiSignatureandVerifyMultiSignature`.

Based on https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html I believe the rogue-key attack can be prevented if signers prove possession of private keys before signatures are aggregated. Is that correct?

[OrestisAlpos]

Hello,

If I understand this correctly, these signatures would not validate at all unless the threshold is met

Yes, that is right. The threshold signature can be created iff at least t valid partial signatures are received. But in that case, if you have a signature that verifies under the global public key, then you know that at least t participants have contributed, so you do not have to check that number.

The Handel approach seems interesting, I was not aware of this. If I get this correctly, each node verifies two signatures, aggregates them (by adding the EC points), and the sends the aggregate to the next party. So this will result in a multi-signature as in equation (1) of https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html, right?
Doing this with threshold signatures is interesting but definitely not trivial. As you said, the threshold signature will not even exist...
Are you aware of this https://arxiv.org/abs/2103.12112 work? They do something similar, and I think again it results in a similar aggregate signature.

I believe the rogue-key attack can be prevented if signers prove possession of private keys before signatures are aggregated.

That should work. And I think nodes can prove the possession once and for all, for example by posting a signature on their public key on the first block, right? That would help things a lot.

I think the renaming makes sense, yes. I plan to experiment with this code, so maybe at some point I will also implement the actual threshold BLS.

[johningve]

I wonder if we should at least rename CreateThresholdSignature and VerifyThresholdSignature to CreateMultiSignatureandVerifyMultiSignature.

I discussed this issue with @meling yesterday, and he suggested refactoring the CryptoImpl interface such that we have only three methods: Sign, Verify, and Combine. The Verify and Combine methods should be smart enough to accept both single signatures and multi/aggregate/threshold signatures depending on the implementation. That way we can avoid these naming problems.

[johningve]

Also, we should have a new name for the interface that abstracts the multi/threshold signatures. Does QuorumSignature make sense?

Edit: Or maybe we can just call it Signature

[OrestisAlpos]

I think these are good ideas. Probably QuorumSignature would be better in terms of disambiguation.

[meling]

@johningve have all the issues above been addressed in #36? Or are there outstanding things to deal with? Perhaps we can close this issue and open another one if there are other crypto issues that we should fix.