Understand group membership checks

[zanebeckwith]

It's very important to check that a curve point that was received externally is a member of the expected group.

So, we need to make sure we're doing these checks in all the places where we should. Also, we need to audit our code for membership checking (currently, it's just a copy-paste of AMCL's code).

Relatedly, is there a good way of structuring the API so we ensure these checks are always made.

[drbild]

For the API, will externally received points always pass through a deserialization function? If so, that seems like the place to do the validation.

So a deserialization function would look like

int ecp2_BN254_deserialize(char* buf, size_t len, struct ecp2_BN254 point_out) {
      // do deserialization here

      if (ret)
         return ret; // deserialization failed

      return ecp2_BN254_check_membership(point_out);
}

If the expected group can change, then specialize the deserialization methods and check membership functions:

int ecp2_BN254_deserialize_for_G2(char* buf, size_t len, struct ecp2_BN254 point_out);

[zanebeckwith]

Yea, this is exactly what I'm planning (and, what I think I currently have). I'm just not confident that my current implementation does this correctly.

[drbild]

Does the current version actually do this?

For example, ecp_BN254_deserialize doesn't call ecp_BN254_check_membership. Instead, ecdaa_credential_BN254_deserialize_with_signature calls ecdaa_credential_BN254_validate which calls ecp_BN254_check_membership.

But ecdaa_credentia_BN254_deserialize doesn't call a validate or check_membership function.

Moving the validation call into the curve point deserialization functions (possibly specialized to the curve) would ensure that no point is deserialized without checking its membership.

[zanebeckwith]

Note: currently, we do the standard (x9.62) membership checks for a G1 point upon deserialization (then assume that any points passed to other functions have undergone this check, and thus we don't perform them again).

Currently, for G2 points, we do the same checks as for G1 except we don't do the small-subgroup check. This was due to the fact that I wasn't sure how to do this check for G2 (in G1, I'm currently doing the standard shortcut of ensuring that cofactor point != inf, but I wasn't sure how to find the cofactor for G2). However, Chen Page and Smart's paper (doi: 10.1007/978-3-642-12510-2_16) explicitly says G2 group checks can be done by checking that the point is on the curve (that is, the sextic-twist of the curve, over F_p^2), and then that curve_orderpoint == inf. That is, all we have to do is add the curve_order*point == inf check.

A PR with this change is forthcoming.

[zanebeckwith]

Fixed in PR #47

[zanebeckwith]

For future reference: the subgroup check for G1 points is not actually necessary for the Barreto-Naehrig curves, since they have cofactor=1. It seems likely we will continue to use prime-order (thus cofactor=1) curves, but let's leave this check in there for now, and come back to this issue later.