xaptum / ecdaa

A C implementation of elliptic-curve-based Direct Anonymous Attestation (DAA) signatures. Created to support the Xaptum Edge Network Fabric, an IoT Network Solution.
https://www.xaptum.com
Apache License 2.0
45 stars 8 forks source link

Check for identity during hashing-to-point #139

Closed zanebeckwith closed 3 years ago

zanebeckwith commented 3 years ago

While little-by-little trying to update this project to the newest literature, I noticed an issue with our hashing-to-a-curve-point in the case of curves with a cofactor not-equal to 1.

As before, if the cofactor is not-equal to 1, we multiply a putative point by the cofactor to ensure we're on the prime-order sub-group. However, I believe the resulting prime-order point could wind up being the identity (basically, if the initial point has no component in the prime-order subgroup, as a direct sum)! So, in the original version of this code, I forgot to explicitly check that we haven't ended up with the identity.

This is a pretty rare (~ 1/subgroup-prime-order probability) outcome if given random hash input. However, that hash input comes from the user (it's the basename), so it's not random and it's even possible that input could be maliciously influenced.

As explained in the commit message, this identity check only needs to be done when multiplying by a non-unit cofactor, so in the typical case of cofactor==1 we don't do the identity check (it's computationally non-trivial, involving modular reduction and bignum normalizing, so good to avoid if unnecessary).

This PR also adds better fuzzing to the Schnorr primitive, especially to randomize the basename (and thus the input to the hash-to-curve-point function). As mentioned above, the check added here would trigger rarely in the case of such random input, so these new fuzz tests wouldn't have caught this. But, just figured this is a good time to improve the fuzzing (don't know why I hadn't randomized that input previously...).

NOTE: The curve used by the TPM and thus in production at Xaptum has cofactor=1, so this issue wouldn't have affected Xaptum customers. I believe the only cofactor!=1 curve currently supported by this project is BLS383.

coveralls commented 3 years ago

Coverage Status

Coverage increased (+0.006%) to 80.035% when pulling 4186cc9ff0ea10dbf91ab0e372fee71618b215ed on zanebeckwith/fix-point-from-hash-cofactor into cf83b623396ab8d231c35e74d8582f1f7881fe91 on master.