aggregate signatures and subgroup validation

[kwantam]

Hi folks (@hoeteck @sergeynog @zhenfeizhang):

I have a concern about subgroup checks in the aggregate signature case.

• The Aggregate function (defined in Section 2.8) does not validate subgroup membership of each signature.

• Instead, CoreAggregateVerify checks subgroup membership of the sum of all signatures output by Aggregate.

• This is fine from the perspective of the pairing operation---it ensures that the inputs are in the proper subgroups, and thus that the pairing function is defined.

• But it doesn't rule out crafting two signatures that contain low-order components that cancel once they are Aggregated, which breaks uniqueness.

Unless I'm crazy, this is a problem, and I think the fix is to check the subgroup of each signature before summing in Aggregate. Does this seem correct?

(Sorry to bear bad news...)

(By the way, a question from @dot-asm turned this up. Thank you!)

[kwantam]

I'm guessing @burdges has thought about this corner case. Thoughts?

[hoeteck]

I guess it depends on what the security requirements are for aggregate signatures.

• The standard unforgeability requirement does not make any assumption about Aggregate, so modifying Aggregate does not affect whether the scheme satisfies unforgeability.

• I think the requirement (and attack) you are thinking about here is uniqueness should hold even against parties that know the corresponding secret keys? I'll have to think a bit more about this, namely (i) how to formalize the requirement and (ii) whether the subgroup check during Aggregate is sufficient.

[kwantam]

Not even clear to me that I need to know the secret keys. For example, if I see signatures s_a on m_a and s_b on m_b, then I can pick a low-order point, add it to s_a, subtract it from s_b, and now I've got two "fresh" signatures on m_a and m_b that verify when run through Aggregate. So as long as I can predict that two signatures will be aggregated, I can break uniqueness. Isn't this already enough of a problem?

[burdges]

You might break soundness for someone's blind signature deployment doing do, although blind signatures should do double spending protections on the messages, not the signatures.

Among rust crates, I think zcash has firmly established doing subgroup checks when deserializing group elements. I think zexe/arkworks added some non-cannonical serialization for passage around within the same machine. If folks wish to skip subgroup checks somewhere within one system, then maybe they should do so using methods explicitly marked "not wire safe".

There might exist reasons for internally using curve points not inside the subgroup: If you accumulate (h + sum_i b[i] pk[i]) - h inside a SNARK using only two-three constraint Affine addition, where h is hashed-to-coset so intermediate sums never equal the identity. In this, you depend upon the pk[i] living inside the subgroup however and you'd never do this without proofs-of-possession, so h being inside a coset is way overkill, but maybe similar reasons exist.

[hoeteck]

Not even clear to me that I need to know the secret keys. For example, if I see signatures s_a on m_a and s_b on m_b, then I can pick a low-order point, add it to s_a, subtract it from s_b, and now I've got two "fresh" signatures on m_a and m_b that verify when run through Aggregate. So as long as I can predict that two signatures will be aggregated, I can break uniqueness. Isn't this already enough of a problem?

If I understand the threat model correctly, then having Aggregate check subgroup membership doesn't solve the problem. The "mauled" signatures could be (s_a + c, s_b - c) for any c, not necessarily a low-order point.

[kwantam]

If I understand the threat model correctly, then having Aggregate check subgroup membership doesn't solve the problem. The "mauled" signatures could be (s_a + c, s_b - c) for any c, not necessarily a low-order point.

Good point.

On the other hand, this sort of thing would be prevented whp by aggregating a random linear combination of signatures (not something the document describes, but it seems like folks are thinking about doing this), whereas that approach doesn't detect whp for c in a small subgroup since the probability that the randomizer is congruent to 0 mod the subgroup order is inversely proportional to subgroup order.

At the least, it seems like we should discuss this in Security Considerations, right? And probably it would also make sense to strongly recommend just doing subgroup checks as part of deserialization.

Is there something else we should be recommending in addition or instead?

[hoeteck]

Yes, having a discussion in Security Considerations sounds good. Thanks for noticing this subtlety!

[kwantam]

Actually, would it make sense to just define the deserialization process to include subgroup checks? That seems like what a lot of people are already doing (as @burdges points out), it would let us get rid of explicit subgroup checks in a few places in the pseudocode, and it would make it very unlikely that conforming implementations fall to attacks involving low-order points.

On the other hand, in principle that could eliminate certain optimization opportunities (maybe not so bad). Should we worry about what might happen to someone who misses that detail in the deseralization routine and ends up with no subgroup checks anywhere? Not sure how paranoid we can get about people selectively omitting parts of the specification, though.

[burdges]

Should we worry about what might happen to someone who misses that detail in the deseralization routine and ends up with no subgroup checks anywhere? Not sure how paranoid we can get about people selectively omitting parts of the specification, though.

¯\(ツ)/¯

You could remind them briefly deserialization enforces important constraints wherever you do it now.

I'd assume deserialization enables more optimization than it obstructs, although not really sure.

Another question is: If you use deserialization then what do you assume from language type systems? Or how many people really love byte oriented interfaces for specs?

You could also just suggest a little "deserialization boundary line" into your existing stuff that presumably provides a byte oriented interface.

[asanso]

@kwantam is this issue taken into consideration for the next version release?

cc @burdges @JustinDrake

[kwantam]

Yes, we'll try to address this in the next update.

[zhenfeizhang]

Actually, would it make sense to just define the deserialization process to include subgroup checks? That seems like what a lot of people are already doing (as @burdges points out), it would let us get rid of explicit subgroup checks in a few places in the pseudocode, and it would make it very unlikely that conforming implementations fall to attacks involving low-order points.

On the other hand, in principle that could eliminate certain optimization opportunities (maybe not so bad). Should we worry about what might happen to someone who misses that detail in the deseralization routine and ends up with no subgroup checks anywhere? Not sure how paranoid we can get about people selectively omitting parts of the specification, though.

I think having subgroup check on deserialization by default is good practice.
I also want to propose separate APIs to allow people to by pass the checks.
Concretely, somewhat borrowing ideas from arkworks:

• deserialize = deserialize + curve check + subgroup check <- default option
• deserialize_curve_check = deserialize + curve check
• deserialize_unchecked = deserialize only
  presumably people who invokes the second or the third API know what they are doing...

Speaking from my own experience, and this is kind of irrelevant to BLS signature per se, I do think that by-passing those checks are quite important for performance critical applications.

[dot-asm]

propose separate APIs

I'd argue that it's a mistake to view this document as an actual API specification. Conversely it would be inappropriate to word it as if it is one. It should describe algorithms, not interfaces. Otherwise, where would you draw the line? At internal data representation? At multi-threading?

[dot-asm]

On a potentially more constructive note. Formally speaking, what is essential is to stipulate that point data that crossed non-trusted boundary, most notably received over the network, have to be subgroup-checked. But it's not unreasonable to leave the decision exactly when to the application. I understand the concern that developers can be sloppy, yet, should you actually operate under assumption that they are? The best you can do is to spell out things in a way that would shift the burden of holding developers accountable to developer community or users.

Just in case, on a practical note. The thing is that subgroup-check is not exactly a cheap operation, ~1/5 of the Miller loop, and it's not unreasonable to leave room for "maneuver." For example, an application can cache the results of subgroup checks while keeping data serialized as platform-neutral format, which would make repetitive checks excessive. Even if the results are not cached, it might be appropriate to postpone the check, say, till the parallel phase...