search

celo-org / celo-bls-snark-rs

Implements SNARK-friendly BLS signatures
https://celo.org
Apache License 2.0
83 stars 24 forks source link

Prove security of BLS aggregation #208

Closed mstraka100 closed 3 years ago

mstraka100 commented 3 years ago

Auditors have raised concerns with the security of our BLS aggregation with bitmap scheme. In particular, an adversary could generate two keys with an algebraic relation such that signing with one key causes the resulting signature to verify against the aggregate of both public keys. We should provide a security proof using a model that gives an adversary control over a minority subset of validator keys.

kobigurk-clabs commented 3 years ago

https://eprint.iacr.org/2021/323 and https://eprint.iacr.org/2021/323 are relevant for the discussion.

psivesely commented 3 years ago

@kobigurk-clabs you posted the same link twice. I have a feeling you meant to post https://eprint.iacr.org/2020/1478.pdf [GL20] as well.

Anyway, I would close this issue. The aggregation algorithm we use is from https://eprint.iacr.org/2002/175 [BGLS03] and contains proofs in both [BGLS03] and https://eprint.iacr.org/2007/264.pdf [RY07], where the former uses the knowledge-of-secret-key (KOSK) assumption and the latter is set in the plain public-key model and thus covers their proof-of-possession (PoP) algorithms (they present multiple) in the aggregate multisignature unforgeability analysis. Our PoP is basically the same as one of the ones in [RY07]--I think @kobigurk-clabs can speak to the specifics with relation to the context of our system. The aggregate multisignature unforgeability game guarantees that it can never be claimed an honest party signed something they didn't, and that's all we need.

With respect to the "splitting zero" paper https://eprint.iacr.org/2021/323.pdf [Q21], the main observation here is new tricks to avoid detecting an adversary controls a number of public keys whose private exponents sum to zero--specifically in the context of aggregate signature verification. This could allow a signer or signers to say the same signature was for a message m at one point and m' at another. I don't think this can be used for any malicious validator behavior because they could also just create a new signature for m' if they hadn't split zero. Nevertheless, if you want to ensure there's a one-to-one correspondence between messages and signatures so long as you can't find a hash function collision you could do the following:

I'm pretty confident this would give the desired property, and while I don't think there's an attack here, there's no good reason not to implement it because anytime an (a)pk is 0*g that's an indicator that every one of the public keys that compromises it should be slashed.

psivesely commented 3 years ago

I just skimmed through [GL20] and they a little bit reinvent the wheel of [CHP07] without citing them. Maybe they just missed it. Anyway, the problem that [GL20] sees is the fact that many (but not all as they claim) multisignature schemes provide "screening", but not "batch verification" (where I put these words in quotes to indicate the specific meaning they're given in [CHP07]). It seems to me they make a faulty proposition in the motivation of their paper:

Therefore individual signatures need to be verified before being aggregated into a multi-signature, as we simply cannot assume they are valid when the combining party runs the combining process.

Basically it doesn't matter if they're valid or not as individual signatures. We only care that it can never be claimed an honest party signed something they didn't. That's sufficient. Yes, an adversary could take two valid signatures o_1 and o_2 and modify them to o'_1 = -x g + o_1 and o'_2 = x g + o_2 and when aggregated they will verify even though they're no longer correct, but this doesn't actually matter for us as o'_1 and o'_2 will be discarded and never used again in any way.

One thing I observed is that while the "robustness" definition introduced in [GL20] ensures that the Combine algorithm (run by the coordinator in our context) either produces a multisignature that verifies or not, but they actually fail to introduce a new security definition akin to "batch verification" that guarantees that every individual signature is valid. Their Combine algorithm would satisfy "batch verification" (as it checks every signature individually), but this may very well be unnecessary (it certainly is in the KOSK model) as the Combine algorithm is more or less a derandomization of the the one presented in 5.1 of [CHP07]. So the Combine algorithm could just check the multisignature after combining and output (\emptyset,\perp) if that multisignature did not verify and it would still satisfy "robustness" and "batch verification" without needing to check each signature. Besides, it's better to have the coordinator optimistically aggregate the signatures and then do binary search for the invalid ones.

kobigurk-clabs commented 3 years ago

@kobigurk-clabs you posted the same link twice. I have a feeling you meant to post https://eprint.iacr.org/2020/1478.pdf [GL20] as well.

Yep, that's the one.

Anyway, I would close this issue.

I disagree.

The literature has been dealing with the unforgeability notions we care about, and specifically Theorem 4.2 about the security of multisignatures from https://www.cc.gatech.edu/~aboldyre/papers/bold.pdf and the similar unforgeability theorem from seem to be what we want in terms of security definitions.

That said, I have a few data points that show that the existence of the literature is not enough:

  1. The auditors, which are on our side, have brought up concerns that were not obvious to address by themselves.
  2. The authors of https://eprint.iacr.org/2020/1478.pdf seem to re-iterate some points that have been presented in previous papers from ~20 years ago.
  3. We've all spent time reading papers and discussing this to increase our confidence in the security of the system.

This shows to me that the relevant literature and methods are not yet widely understood. In turn, this puts a responsibility on us to improve the situation, either formally or informally, in order for others to have confidence in our system. This means that we should probably shine a light on the existing results and invest time in making them accessible. For example, https://eprint.iacr.org/2020/1478.pdf makes the definitions and proofs more accessible, even if we're not super satisfied with the formal treatment.

As action items, we can both formally refer to the relevant literature and also write a note/post that makes the definitions accessible and shows how they are secure against the attacks we've been thinking about.

burdges commented 3 years ago

Accountable aggregation gives only fuzzy accountability, so yes aggregateable signatures must "be discarded and never used again" and only yield conclusions one direction, which restricts consensus protocols substancially.

psivesely commented 3 years ago

and the similar unforgeability theorem from seem

@kobigurk-clabs seems like you didn't mention the second theorem you see as an example of what you consider to be a good security definition. As per Definition 4.1 of [B03], which provides the security definition for Theorem 4.2 here are my observations:

It is clear to me the property an adversary can never claim a challenge key signed a message it didn't, even with oracle access to that challenge key, very directly guarantees that there's no way verification will betray the will of an honest supermajority of validators. Can you please point out where you think there is a gap here?

kobigurk commented 3 years ago

It’s true the definition is for multsignatures. My understanding is that the lack of clarity is even at that level, which is what’s used in consensus . A theorem about aggregate multisignatures is even better, either directly to be presented or as the next step. Maybe for example we need some translation from the definitions in BGLS03 which don’t include subgroups or the construction in BDN18 that uses delinearization.

I agree it’s very direct and there’s no big theoretical gap. What we might be missing on our side is:

  1. Explicitly referring to theorems. Of course it’s not a must, but readers will appreciate it.
  2. Show attacks we’ve been thinking about in more detail and how they’re prevented, even intuitively.

Without doing this, we’re still in the clear - it seems we’re secure. The gap I see is the confidence we instill both internally in cLabs and externally. I’d like it to be better than “we’ve checked and it’s fine, try to attack us”.

On Sat, 20 Mar 2021 at 22:27 Psi Vesely @.***> wrote:

and the similar unforgeability theorem from seem

@kobigurk-clabs https://github.com/kobigurk-clabs seems like you didn't mention the second theorem you see as an example of what you consider to be a good security definition. As per Definition 4.1 of [B03], which provides the security definition for Theorem 4.2 here are my observations:

  • It is for multisignatures and not aggregate multisignatures
  • It's made to work for both interactive and non-interactive multisignature schemes
  • It uses the language of subgroups--if you want you can think of the bitmap as a subgroup identifier, but for that matter you can also think of the list of public keys output by the adversary in the unforgeability definitions of [BGLS03,RY07,BDN18] as subgroup identifiers
  • Conceptually, the same guarantee is provided as these other unforgeability definitions: an adversary cannot claim a challenge public key signed a message that it did not

It appears to me the property an adversary can never claim a challenge key signed a message it didn't, even with oracle access to that challenge key, very directly guarantees that there's no way verification will betray the will of an honest supermajority of validators. Can you please point out where you think there is a gap here?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/celo-org/celo-bls-snark-rs/issues/208#issuecomment-803458595, or unsubscribe https://github.com/notifications/unsubscribe-auth/AA23MGAQ2SYPXMONKBOMQQLTEUALJANCNFSM4YC5BURA .

cryptosubtlety commented 3 years ago

I added a new section 5 "A plausible attack scenario at the protocol layer" and its partial PoC attack (https://github.com/cryptosubtlety/zero/blob/main/0.pdf). I hope that the section can at least give you hints or ideas to improve attack or defend yourself. Cheers.

kobigurk-clabs commented 3 years ago

Done by @psivesely