Bug: multiplication of Point by negative const produces wrong results

[hellman]

from fastecdsa.curve import P256
from fastecdsa.point import Point

xs = 0xde2444bebc8d36e682edd27e0f271508617519b3221a8fa0b77cab3989da97c9
ys = 0xc093ae7ff36e5380fc01a5aad1e66659702de80f53cec576b6350b243042a256
S = Point(xs, ys, curve=P256)

print(S)
# X: 0xde2444bebc8d36e682edd27e0f271508617519b3221a8fa0b77cab3989da97c9
# Y: 0xc093ae7ff36e5380fc01a5aad1e66659702de80f53cec576b6350b243042a256
# (On curve <P256>)
print((-1)*S)
# X: 0xde2444bebc8d36e682edd27e0f271508617519b3221a8fa0b77cab3989da97c9
# Y: 0xc093ae7ff36e5380fc01a5aad1e66659702de80f53cec576b6350b243042a256
# (On curve <P256>)
print(-S)
# X: 0xde2444bebc8d36e682edd27e0f271508617519b3221a8fa0b77cab3989da97c9
# Y: 0x3f6c517f0c91ac8003fe5a552e1999a68fd217f1ac313a8949caf4dbcfbd5da9
# (On curve <P256>)
print((-1-P256.q)*S)
# X: 0x2754ffb5ff6ff19af1bb2fe0ef25a22d3a28731031d319afa9bf707c3595d58d
# Y: 0x3832af93a61dc91177c094f3c1723e5a3f4e29cc9fbc862da05be393b54a9a9e
# (On curve <P256>)

version 2.1.5

[AntonKueltz]

This does look like a bug for the -1 * S case. I think in general multiplication by negatives isn't handled well ever since the scalar %= self.curve.q was removed in this commit. @bbbrumley @JJChiDguez - do you remember why this modular reduction was removed in the aforementioned commit?

[JJChiDguez]

I am agreed with you, scalar %= self.curve.q must be included... I guess it was removed by accident, those commits are concerning on the special case when the output point is degenerated (in short Weierstrass, the point at infinity does not have affine representation).

[AntonKueltz]

Fix is in commit d394335b6b6f71604a50f0c8336e62abd45936ff. Added a test and also double checked in the command line -

In [1]: from fastecdsa.curve import P256
   ...: from fastecdsa.point import Point
   ...:
   ...: xs = 0xde2444bebc8d36e682edd27e0f271508617519b3221a8fa0b77cab3989da97c9
   ...: ys = 0xc093ae7ff36e5380fc01a5aad1e66659702de80f53cec576b6350b243042a256
   ...: S = Point(xs, ys, curve=P256)

In [2]: print(S)
# X: 0xde2444bebc8d36e682edd27e0f271508617519b3221a8fa0b77cab3989da97c9
# Y: 0xc093ae7ff36e5380fc01a5aad1e66659702de80f53cec576b6350b243042a256
# (On curve <P256>)

In [3]: print((-1)*S)
# X: 0xde2444bebc8d36e682edd27e0f271508617519b3221a8fa0b77cab3989da97c9
# Y: 0x3f6c517f0c91ac8003fe5a552e1999a68fd217f1ac313a8949caf4dbcfbd5da9
# (On curve <P256>)

In [4]: print(-S)
# X: 0xde2444bebc8d36e682edd27e0f271508617519b3221a8fa0b77cab3989da97c9
# Y: 0x3f6c517f0c91ac8003fe5a552e1999a68fd217f1ac313a8949caf4dbcfbd5da9
# (On curve <P256>)

I think the intention was to do print((-1+P256.q)*S) in the last case rather than print((-1-P256.q)*S)? That also gives the expected result

[bbbrumley]

I am agreed with you, scalar %= self.curve.q must be included... I guess it was removed by accident

No, it was very much on purpose.

There is no guarantee the point is an order q point. So always reducing scalars modulo q is not computationally correct.

@AntonKueltz d394335b6b6f71604a50f0c8336e62abd45936ff is a regression.

[bbbrumley]

If you want to handle negatives, I suggest

1. Do the scalar multiplication by the absolute value
2. If the scalar is negative, invert the result

[AntonKueltz]

Ah right, the reduction has to be by the order of the point being scaled if I remember correctly. I'm surprised the test suite didn't catch this regression when I added it back in, everything looks green still. @bbbrumley is there any fix for this that doesn't involve point counting? (I suppose this is also possibly indicative of a bug in the C code, either around assuming unsigned for the scalar or something in the ladder code).

Edit: Just saw your response above, thanks!

[AntonKueltz]

The above method is implemented in 184beb6bcc6e52fff98cd393c310979cb49ead44, I don't think I ever fully realized the negative unary operator is commutative when doing point multiplication, nice trick.

[bbbrumley]

The above method is implemented in

LGTM!

I'm surprised the test suite didn't catch this regression when I added it back in, everything looks green still.

Indeed ... I have to think about what the best test looks like in this case. In terms of the stock curves that come with fastecdsa, the only curves that can detect that kind of regression are W25519 and W448.

[AntonKueltz]

In terms of the stock curves that come with fastecdsa, the only curves that can detect that kind of regression are W25519 and W448.

Yes, I was thinking this too, the NIST curves all mask this issue, and I think indeed that was the origin of the %= q code as all the curves initially provided in this package were NIST curves. I can't think of a good way to test this off the top of my head either, will leave the issue open and think on it a bit. For now I'll merge the fix so that it's not causing further issues.

[hellman]

There is no guarantee the point is an order q point. So always reducing scalars modulo q is not computationally correct.

Can not we use the (precomputed) order of the curve? Useful also if somebody puts a huge scalar.

[bbbrumley]

Can not we use the (precomputed) order of the curve? Useful also if somebody puts a huge scalar.

fastecdsa doesn't have the precomputed order of the curve. It only has the (prime) order of the generator point.

[AntonKueltz]

Can not we use the (precomputed) order of the curve? Useful also if somebody puts a huge scalar.

I'm not opposed to this approach but I would need someone to point me to the relevant literature or PR this as I'm a bit rusty on the details.

[bbbrumley]

I'm not opposed to this approach but I would need someone to point me to the relevant literature or PR this as I'm a bit rusty on the details.

Ideally you'd add the cofactor h to the curve class

https://github.com/AntonKueltz/fastecdsa/blob/master/fastecdsa/curve.py

Then @hellman is correct -- you could do

        scalar %= self.curve.q * self.curve.h

h is 1 for all the NIST curves over prime fields. I believe it's 8 for W25519 and 4 for W448.

But it might be a breaking change. (Which I would selfishly be against, because I'm already working around it in another project.)

But OTOH this is, indeed, technically the better way to handle it.

It is also possible to "simply" calculate the cofactor on-the-fly for curves of cryptographic interest. I contributed the OpenSSL code for that some time ago. (In that notation, OpenSSL "n" is fastecdsa "q", and OpenSSL "q" is fastecdsa "p".)

[bbbrumley]

Just to be clear: you cannot always calculate the cofactor like I give in the pointer. So in the end, you need the fallback code anyway -- i.e. no scalar reduction, and sign considerations -- which is what you've merged already.

For curves already built into fastecdsa, this doesn't matter because h is a precomputed constant. It's only a question of custom curves instantiated with the Curve class.

[AntonKueltz]

Revisiting this issue - given that the fallback code is needed anyway I'm in favor of keeping things as they are and not introducing an additional cofactor field. If anyone has objections we can discuss here.