Question: does `FastAggregateVerify` accept point of infinity PK (i.e., `SK=0`)?

Question

Question: does `FastAggregateVerify` accept point of infinity PK (i.e., `SK=0`)?

Opened this issue 4 years ago · 10 comments

hwwhww commented 4 years ago

(Thanks to @mratsim for pointing out this.)

Hi @kwantam and co.

#26 disallows point at infinity PK in KeyValidate. Therefore, it's also disallowed in CoreVerify, CoreAggregateVerify, AggregateVerify, and PopVerify.
FastAggregateVerify does not use KeyValidate to check the PKs before aggregating the PKs. So having a point at infinity PK is valid.
That also means FastAggregateVerify doesn't check pubkey_subgroup_check before calling pubkey_to_point. I'm not sure if it's required for the formal spec. (I suppose implementations return False when pubkey_to_point raises exceptions anyway?)

Questions:

Is this inconsistent behavior intended?
If not, a reminder that most implementations have implemented their own AggregatePKs, or more generic AggregateG1 APIs to deal with aggregation inside FastAggregateVerify. So adding KeyValidate to FastAggregateVerify may increase more overhead than what it looks like in the IETF document. It would be nice if it can be figured out with minimum changes.

Thanks for your time. :)

Answer 1 · 2020-09-16T19:31:22.000Z

Hi @hwwhww:

Thanks for the question---it certainly indicates that the document could be clearer, which is very helpful feedback 👍

That said, there is no inconsistency here. The reason is, per Section 3.3,

   All public keys used by Verify, AggregateVerify, and
   FastAggregateVerify MUST be accompanied by a proof of possession, and
   the result of evaluating PopVerify on the public key and proof MUST
   be VALID.

PopVerify (Section 3.3.3) calls KeyValidate(PK) (step 4).

So any conforming implementation will have called KeyValidate on all PKs supplied to FastAggregateVerify, and therefore identity PKs are not allowed.

Does this make sense? Would it be clearer if we reiterated the PopVerify requirement in the section where FastAggregateVerify is defined?

Answer 2 · 2020-09-16T21:53:22.000Z

Does this make sense?
Would it be clearer if we reiterated the PopVerify requirement in the section where FastAggregateVerify is defined?

@kwantam Thank you for your reply, it is much more clear now! 👍

I understand that PopVerify is used to stipulate the PKs formally and strictly, but I still have some concerns about using PopVerify rather than KeyValidate as a precondition checker in implementation:

If I understand Section 3.3 correctly, in realistic, PopVerify should have been checked in application level?
For the BLS library implementations, we implement FastAggregateVerify as a pure function that returns INVALID or VALID based on input parameters.
If PoP-verified is a strict precondition, we couldn't check it when this FastAggregateVerify is called since proof is not one of the input parameters.

In applications, it's probably fine since PKs are filtered before calling FastAggregateVerify. But for APIs fuzz testing, we want to have a certain way to verify it as a pure function.

Let me know if I missed anything or anything is unclear. :)

Answer 3 · 2020-09-16T22:09:55.000Z

Sorry, I think I don't quite understand the concern or the suggested fix.

A little more background:

PopVerify is a strict precondition for FastAggregateVerify because the security of the signature scheme against rogue key attacks requires verifying a proof of possession for each public key. FastAggregateVerify must not be called on public keys for which a valid proof of possession is not known, because this allows malicious users to trivially falsify aggregate signatures.

This means that adding KeyValidate for each PK as a precondition to FastAggregateVerify is not necessary, because it is already a precondition by way of PopVerify; meanwhile, executing KeyValidate inside FastAggregateVerify cannot remove that precondition.

In sum: to implement PureFastAggregateVerify, you would need to pass in both public keys and corresponding proofs of possession. If you wanted, you could implement this as a wrapper around FastAggregateVerify for fuzzing purposes.

Sorry if I have misunderstood what you are saying!

Answer 4 · 2020-09-17T04:04:13.000Z

@kwantam Sorry I didn’t describe it well. 😅
I understand why PopVerify should be a precondition before calling FastAggregateVerify, but I’m not sure how to implement this precondition in the FastAggregateVerify API implementation correctly.

This is how we implemented the FastAggregateVerify:

def FastAggregateVerify((PK_1, ..., PK_n), message, signature):
    # precondition
    If n < 1: return INVALID

    # Run procedure
    1. aggregate = pubkey_to_point(PK_1)
    2. for i in 2, ..., n:
    3.     next = pubkey_to_point(PK_i)
    4.     aggregate = aggregate + next
    5. PK = point_to_pubkey(aggregate)
    6. return CoreVerify(PK, message, signature)

This is the pseudo code of what you meant by the FastAggregateVerify and PureFastAggregateVerify in my mind:

def PureFastAggregateVerify((PK_1, ..., PK_n), message, signature, (proof_1, ...., proof_n)):
    # precondition 1
    If n < 1: return INVALID
    # precondition 2
    for i in 2, ..., n:
        If PopVerify(PK_i, proof_i) is INVALID, return INVALID

    return FastAggregateVerify((PK_1, ..., PK_n), message, signature)


def FastAggregateVerify((PK_1, ..., PK_n), message, signature):
    # Run procedure
    1. aggregate = pubkey_to_point(PK_1)
    2. for i in 2, ..., n:
    3.     next = pubkey_to_point(PK_i)
    4.     aggregate = aggregate + next
    5. PK = point_to_pubkey(aggregate)
    6. return CoreVerify(PK, message, signature)

If the above logic is correct, when we only look at FastAggregateVerify, I can input two public keys: [valid_PK, infinity_point_PK], where valid_PK has been PoP-verified, and infinity_point_PK is the point at infinity. This rogue attack is a valid case for the FastAggregateVerify implementation above.

Thanks for your time again. 🙏

edited: I understand that FastAggregateVerify should be called with the PKs that are verified by PopVerify, but for the API implementation, FastAggregateVerify has to determine the given input is INVALID or VALID by itself.

Answer 5 · 2020-09-17T06:04:09.000Z

I understand that FastAggregateVerify should be called with the PKs that are verified by PopVerify, but for the API implementation, FastAggregateVerify has to determine the given input is INVALID or VALID by itself.

From my perspective---and from the document's perspective---this is a false statement. FastAggregateVerify cannot detect whether or not the caller knows a valid PoP proof for a public key.

The document says (or, intends to say!) that PopVerify is a precondition for FastAggregateVerify. The behavior of a function that imposes preconditions on its inputs is undefined if those preconditions are violated. In the case of FastAggregateVerify, all security guarantees are void if the PopVerify precondition is violated.

This is morally equivalent, for example, to a function that requires the caller to ensure that a pointer supplied as an argument is valid. It doesn't make any sense to try and test such a function on an invalid pointer: of course we would not expect it to work (and, needless to say, it is not possible in the general case---in C, say---for a function to determine for itself whether or not a pointer is valid).

We might ask, how can we rewrite the API to avoid this issue? The only answer I can see is to specify something like PureFastAggregateVerify (but I'd definitely welcome other ideas!). Then, as an optimization, we might observe that PopVerify is a pure function and thus safe to memoize. (I believe the document already more or less says this, at least about KeyValidate.)

But: I don't think this is would be a good API, because it seems to prescribe (or at least to prefer) a particular implementation (namely, memoizing PopVerify). Meanwhile, depending on the programming language, there are plenty of other valid ways to enforce the precondition without resorting to the PureFastAggregateVerify API.

For example, one way to ensure that the precondition is never violated is for implementations to (1) use different types for public keys with and without proofs of possession, (2) ensure that a public key is only instantiated as the SafePK type when PopVerify has returned VALID, and (3) make FastAggregateVerify operate only on the SafePK type. Assuming the type system is sound and the types are defined correctly, a program that typechecks cannot violate the precondition. Notice how in this case we wouldn't need to memoize PopVerify or use PureFastAggregateVerify, because we would be statically guaranteed that only verified public keys are provided as inputs to FastAggregateVerify.

Does all of this make sense? I would of course welcome suggestions for other solutions!

Answer 6 · 2020-09-17T07:43:12.000Z

If you're using a language that supports session types like Rust, then you could create some certificate type for which the verification function returned the public key, and write serialization code only for the certificate type, so users are forced into checking their proofs-of-possession when deserializing.

//! All BLS keys require proof-of-possession certificates that
//! consist of two layers:  An inner layer `RoleCert` certifies
//! the key's role, while an outer layer `PoPCert` signs that
//! the key accepts this role, and provides proof-of-possession.

#[derive(Encode,Decode,Clone,Debug,..)]
pub struct UnverifiedPublicKey<E: EngineBLS>(E::PublicKeyGroup)

#[derive(Clone,Debug,..)]
pub struct VerifiedPublicKey<E: EngineBLS>(E::PublicKeyGroup)

pub trait RoleCert : Encode+Decode {
    type E: EngineBLS;
    type Issuer;
    fn verify_role(&self) -> Option<(Self::Issuer,UnverifiedPublicKey<E>)>;
}

#[derive(Encode,Decode,Clone,Debug,..)]
pub struct PoPCert<RC: RoleCert> {
    role_cert: RC,
    c: Scalar,
    s: Scalar,
}
impl<RC: RoleCert> PoPCert<IC> {
    pub fn verify_pop(&self) -> Option<(RC::Issuer,VerifiedPublicKey<E>)> {
        let (issuer,UnverifiedPublicKey(pk)) = self.verify_role() ?;
        .. schnorr verifier ..
        (issuer,VerifiedPublicKey(pk)
    }
}

You cannot make the human readable pseudo-code compiler enforce this, even though you can express the constraint. ;)

Also, you're code becomes slow because users do not understand that they must deserialize once and keep the deserialized and validated keys around in memory, but maybe such users should not really be using BLS anyways, so..

Answer 7 · 2020-09-17T08:10:45.000Z

FYI this is my implementations of fastAggregateVerify

Using Miracl as a backend: https://github.com/status-im/nim-blscurve/blob/86d151d7/blscurve/miracl/bls_signature_scheme.nim#L451-L500

func fastAggregateVerify*[T: byte|char](
        publicKeys: openarray[PublicKey],
        proofs: openarray[ProofOfPossession],
        message: openarray[T],
        signature: Signature
      ): bool =
  ## Verify the aggregate of multiple signatures on the same message
  ## This function is faster than AggregateVerify
  ## Compared to the IETF spec API, it is modified to
  ## enforce proper usage of the proof-of-posession
  # 1. aggregate = pubkey_to_point(PK_1)
  # 2. for i in 2, ..., n:
  # 3.     next = pubkey_to_point(PK_i)
  # 4.     aggregate = aggregate + next
  # 5. PK = point_to_pubkey(aggregate)
  # 6. return CoreVerify(PK, message, signature)
  if publicKeys.len == 0:
    return false
  if not publicKeys[0].popVerify(proofs[0]):
    return false
  var aggregate = publicKeys[0]
  for i in 1 ..< publicKeys.len:
    if not publicKeys[i].popVerify(proofs[i]):
      return false
    aggregate.point.add(publicKeys[i].point)
  return coreVerify(aggregate, message, signature, DST)

func fastAggregateVerify*[T: byte|char](
        publicKeys: openarray[PublicKey],
        message: openarray[T],
        signature: Signature
      ): bool =
  ## Verify the aggregate of multiple signatures on the same message
  ## This function is faster than AggregateVerify
  ##
  ## The proof-of-possession MUST be verified before calling this function.
  ## It is recommended to use the overload that accepts a proof-of-possession
  ## to enforce correct usage.
  # 1. aggregate = pubkey_to_point(PK_1)
  # 2. for i in 2, ..., n:
  # 3.     next = pubkey_to_point(PK_i)
  # 4.     aggregate = aggregate + next
  # 5. PK = point_to_pubkey(aggregate)
  # 6. return CoreVerify(PK, message, signature)
  if publicKeys.len == 0:
    return false
  var aggregate = publicKeys[0]
  for i in 1 ..< publicKeys.len:
    aggregate.point.add(publicKeys[i].point)
  return coreVerify(aggregate, message, signature, DST)

And with BLST as a backend: https://github.com/status-im/nim-blscurve/blob/86d151d7/blscurve/blst/bls_sig_min_pubkey_size_pop.nim#L628-L687

func fastAggregateVerify*[T: byte|char](
        publicKeys: openarray[PublicKey],
        proofs: openarray[ProofOfPossession],
        message: openarray[T],
        signature: Signature
      ): bool =
  ## Verify the aggregate of multiple signatures on the same message
  ## This function is faster than AggregateVerify
  ## Compared to the IETF spec API, it is modified to
  ## enforce proper usage of the proof-of-posession
  # 1. aggregate = pubkey_to_point(PK_1)
  # 2. for i in 2, ..., n:
  # 3.     next = pubkey_to_point(PK_i)
  # 4.     aggregate = aggregate + next
  # 5. PK = point_to_pubkey(aggregate)
  # 6. return CoreVerify(PK, message, signature)
  if publicKeys.len == 0:
    return false
  if not publicKeys[0].popVerify(proofs[0]):
    return false
  var aggregate {.noInit.}: blst_p1
  aggregate.blst_p1_from_affine(publicKeys[0].point)
  for i in 1 ..< publicKeys.len:
    if not publicKeys[i].popVerify(proofs[i]):
      return false
    # We assume that the PublicKey is in on curve, in the proper subgroup
    aggregate.blst_p1_add_or_double_affine(publicKeys[i].point)

  var aggAffine{.noInit.}: PublicKey
  aggAffine.point.blst_p1_to_affine(aggregate)
  return coreVerify(aggAffine, message, signature, DST)

func fastAggregateVerify*[T: byte|char](
        publicKeys: openarray[PublicKey],
        message: openarray[T],
        signature: Signature
      ): bool =
  ## Verify the aggregate of multiple signatures on the same message
  ## This function is faster than AggregateVerify
  ##
  ## The proof-of-possession MUST be verified before calling this function.
  ## It is recommended to use the overload that accepts a proof-of-possession
  ## to enforce correct usage.
  # 1. aggregate = pubkey_to_point(PK_1)
  # 2. for i in 2, ..., n:
  # 3.     next = pubkey_to_point(PK_i)
  # 4.     aggregate = aggregate + next
  # 5. PK = point_to_pubkey(aggregate)
  # 6. return CoreVerify(PK, message, signature)
  if publicKeys.len == 0:
    return false
  var aggregate {.noInit.}: blst_p1
  aggregate.blst_p1_from_affine(publicKeys[0].point)
  for i in 1 ..< publicKeys.len:
    # We assume that the PublicKey is in on curve, in the proper subgroup
    aggregate.blst_p1_add_or_double_affine(aggregate, publicKeys[i].point)

  var aggAffine{.noInit.}: PublicKey
  aggAffine.point.blst_p1_to_affine(aggregate)
  return coreVerify(aggAffine, message, signature, DST)

Answer 8 · 2020-09-17T10:18:04.000Z

@kwantam Thanks for the clarification! And hello @burdges 👋

I should have given more context of why I was asking this question originally:

For Eth2 use cases, although we don’t use the IETF BLS standard proof of possession format, we also assume the PKs should be PoP-verifiable before FastAggregateVerify is called.
Since there are many Eth2 client teams and BLS library implementations, we created some BLS APIs test vectors for the edge cases (only for the APIs that Eth2 core specs are using)— that was also where the #25 issue was found. Thus I was keen to know the correct input/output of FastAggregateVerify.
Personally, I want to have simple and sessionless *Verify API implementations.

IMHO adding SafePK notation is better than adding PureFastAggregateVerify for describing the valid input domain in the spec. 👍

Question: As for the implementation, does it make sense if we provide test vectors with the non-SafePK values?

The behavior of a function that imposes preconditions on its inputs is undefined if those preconditions are violated. In the case of FastAggregateVerify, /all security guarantees are void/ if the PopVerify precondition is violated.

^^^ The PK=inf case is "undefined" in the above definition, but it’s not a usual type error that can be caught by the programming languages easily. I see the value of including PK=inf in the test vectors and expect it returns INVALID, especially, because it’s a new consensus change between draft-03 and draft-04.

For our Python implementation (py_ecc, an experimental ECC lib), we may add a KeyValidate check in FastAggregateVerify to pass the above test vector. It's not violating the spec anyway. :)

Answer 9 · 2020-09-17T23:29:44.000Z

My opinion is that it does not make sense to test FastAggregateVerify on inputs that violate its preconditions, because by definition any behavior is conforming for such inputs. But of course, since any behavior is conforming, y'all are free to force implementations to use a particular one if you want.

Answer 10 · 2020-09-17T23:31:50.000Z

And, to be clear: there will be no SafePK in the spec. That is an implementation detail. We may clarify/reiterate the precondition on PKs passed to FastAggregateVerify, but I do not think any other change is necessary or appropriate.

(I'm of course happy to discuss other proposed changes! Not trying to close the door on the conversation. But neither changing the API nor attempting to enforce some kind of typing discipline in pseudocode seem reasonable.)