Subject: [Cfrg] BLS - proofs of possession may not be enough?

From: Kobi Gurkan <[email-masked]>
Date: Sun, 17 Nov 2019 15:12:44 +0200

Hello all,

I stumbled upon a property of BLS-based protocols which use proofs of possession which seems to break an expected behaviour of aggregated BLS signatures.

In a nutshell, a malicious signer might register multiple keys, together with proofs of possession, that sum up to zero and therefore claim they participated in a signature while they haven't.

I have a small write-up about it here: https://www.overleaf.com/read/kgjyvjzktcdv <https://www.overleaf.com/read/kgjyvjzktcdv>

It seems that delinearization, as described in https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html <https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html>, is strictly stronger than proofs of possession in terms of security - as this attack does not effect protocols that use them.

To be clear - it's not a rogue public key attack nor a forgery. It breaks the expectation that if I receive a signature such that the aggregated of some public keys verifies it, then I know that this signature was the result of an aggregation of individual signatures by each of the signers corresponding to those public keys.

Would appreciate your opinion on it and whether we should reflect this in the IETF BLS signature document, so that protocols wouldn’t be vulnerable to it.

Best,
Kobi

---

From: Jeff Burdges <[email-masked]>
Date: Sun, 17 Nov 2019 20:48:32 +0100

I’d still characterise sum_i sk_i = 0 as an unusual DGK that changes the properties of the signature similarly to any other DKG does.  In particular, any proof-of-possesion security proof should show this does not impact other signers under normal threat models.

As we discussed, there are threat models with non-standard interactions between signatures in which sum_i sk_i = 0 does facilitate attacks, namely when a signer waits for other signers and can be punished for signing too early.  I’ll note however that BLS cannot achieve security for that signer anyways because the earlier signers can subtract their signatures even without any relationship among the secret keys.

> On 17 Nov 2019, at 14:12, Kobi Gurkan <[email-masked]> wrote:
> It seems that delinearization, as described in https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html, is strictly stronger than proofs of possession in terms of security - as this attack does not effect protocols that use them.

I suspect it’s strictly stronger but actually nobody proved this.  An approach for showing that delinearization is stronger than proof-of-possesion might be working in some composability framework, but this gets delicate because classically these handle state poorly.

Jeff

---

From: Kobi Gurkan <[email-masked]>
Date: Mon, 18 Nov 2019 23:04:46 +0200

Hey Jeff,

Thanks for the comment, also in our one-to-one chat.

I think that the practical impact of the property that I describe are not catastrophic. Some comment I got recently was that it could been achieved just as well by publishing the secret keys.

Kobi

> On 17 Nov 2019, at 21:48, Jeff Burdges <[email-masked]> wrote:
> 
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg