search

ethereum / py_ecc

Python implementation of ECC pairing and bn_128 and bls12_381 curve operations
MIT License
191 stars 82 forks source link

Address `prime_field_inv(a: int, n: int)` a == n case #114

Closed hwwhww closed 3 years ago

hwwhww commented 3 years ago

What was wrong?

Bounty hunter Nguyen Thoi Minh Quan found this issue:

  1. By https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-09 "inv0(x): This function returns the multiplicative inverse of x in F, extended to all of F by fixing inv0(0) == 0" I.e. inv(0, 7) = inv(7, 7) = 0 In finite field F_7: 0 = 7.
  2. Reproduction: 
    prime_field_inv(7, 7)
prime_field_inv(0, 7)

    Output:

    1
0
  3. Security impact is not clear, but let's fix the issue to avoid potential security.
  4. Also see https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-09#section-6.5

    Mappings may have have exceptional cases, i.e., inputs u on which the mapping is undefined. These cases must be handled carefully, especially for constant-time implementations. For each mapping in this section, we discuss the exceptional cases and show how to handle them in constant time. Note that all implementations SHOULD use inv0 (Section 4) to compute multiplicative inverses, to avoid exceptional cases that result from attempting to compute the inverse of 0.

How was it fixed?

Nguyen Thoi Minh Quan: https://github.com/ethereum/py_ecc/blob/dd38b1f1b092989095b75baec4987347086fd962/py_ecc/utils.py#L24 Assign a = a % n in the 1st line of the function prime_field_inv

  1. My first quick scan is that this edge case would not happen via BLS API calls. Also, py-ecc is not a constant-time implementation. Anyway, good to be more careful. 👍

  2. secp256k1 also has an inv function.

https://github.com/ethereum/py_ecc/blob/dd38b1f1b092989095b75baec4987347086fd962/py_ecc/secp256k1/secp256k1.py#L46-L56

However, unlike BLS, the a == n case is undefined here so I didn't change this function.

/cc @JustinDrake

pipermerriam commented 3 years ago

Can you look at giving me some guidance on whether we should be backporting this to older releases?

hwwhww commented 3 years ago

@pipermerriam IMHO no need to backport it to the older releases since we haven't found this edge case in our normal usage.

pipermerriam commented 3 years ago

Are ya'll ready for a release with this in it?

hwwhww commented 3 years ago

@pipermerriam

I may have some minor updates in the queue that could be included in the next release together this week.