Invalid curve attacks, explained

Look ma, I found a fellow donut lover!

If you don't understand what we were talking about, don't worry, very few do. The only thing you should remember is the Internet runs on donuts. Google, Facebook, WhatsApp, Instagram, Amazon, or even Bitcoin all run on donuts.

If you're a student like J., you want to study donuts. If you aren't, you also want to study donuts 'cause they're eating the world!

--

On Wed, Sep 26, 2018 at 6:34 PM <removed> wrote:
Subject: Re: https://twitter.com/XorNinja/status/1021786823524110336

Sir, undergraduate computer science student and cryptography dilettante here.
I seek your unsolicited direction--my apologies--I don't have a twitter
account. I am referencing
https://twitter.com/XorNinja/status/1021786823524110336. I have implemented
cryptopals 57/58 and have begun to understand small subgroup attacks on DH and
invalid curve attacks on ECDH.  Now, I am studying kb.cert.org/vuls/id/304725 /
CVE-2018-5383.  As far as I understand ECDH in Bluetooth4.2 uses FIPS
186-4/NIST P-256/secp256r1/P-256 which is an elliptic curve group w/ prime
order.  Hence, this group cannot contain points w/ order two--ie no points of
the form (x,0).  How to interpret Semi-Passive Attack outlined in the
Biham-Neumann paper? How do we confine the victim's final point scaling to a
small subgroup/invalid curve while only manipulating the y-coordinate to be 0?
When do I calculate and use b'? What are some things I should be asking myself
to better understand the Fixed Coordinate Invalid Curve Attack? Thank you.  I
appreciate you taking the time to read this message and I eagerly await your
response.  J.

--

From: Thai Duong
Sent: Wednesday, September 26, 2018 8:51:46 PM

Hi <removed>,

You're right that P-256 doesn't have a point of order 2. But this is an invalid curve attack.
The point (x, 0) has order two on:

E': y^2 = x^3 + a*x + b'

Where b' is unique and different from b in the P-256 equation. If you look at point addition
or doubling formula, you'd notice that it doesn't depend on b. This means the scalar
multiplication would take (x, 0) and produce a point at infinity if the scalar is even. This
point at infinity is on E'. But all curves in short Weierstrass form have the same point at
infinity (in projective coordinate it is the point (0, 1, 0)).

Does it make sense?

--

On Wed, Sep 26, 2018 at 8:47 PM <removed> wrote:

Yes, this part makes sense. And I have been able to convince myself of this
using an example point from a Somorovsky blog post,
https://web-in-security.blogspot.com/2015/09/practical-invalid-curve-attacks.html.

This point
(82794344854243450371984501721340198645022926339504713863786955730156937886079,335525218815814676708366178591785234073444719485138817189697292758
59461829010) belongs to an invalid curve with unique b' and same a as P-256
which has order 5.  I can see the cycle through its five possible values
including the point at infinity when multiplied by any scalar [2,q-2] in my
experiments.

Unfortunately my confusion persists...how many points of the form (x,0) land on
invalid curves? Suppose the attacker knows a unique b' which defines an invalid
curve with points of order two.  I still do not understand how the attacker can
force the victim to compute over the invalid curve if they have no control over
the x-coordinate? If no points of the form (x,0) exist on P-256, how can the
attacker rely on essentially random choices of the x-coordinate by the
victims initial computation PKv = [SKv]G to satisfy E': y^2 = x^3 + a*x + b'?

Should I be calculating my own invalid curves using Schoof-Elkies-Atkins with
small order using the methods outlined in the Offline-Computations section of
Jager-Schwenk-Somorovsky Practical Invalid Curve Attacks on TLS-ECDH paper? And
if I did, what would I do with the knowledge of b'?

Simply changing the y-coordinate to 0 in my experiments has not once produced
the point at infinity.  Thank you very much for you response. .

--

From: Thai Duong
Sent: Thursday, September 27, 2018 12:01:50 AM

>Unfortunately my confusion persists...how many points of the form (x,0) land on

invalid curves?

All (x, 0) points land on invalid curves with b' = -x^3 - ax. In P-256, a = -3, thus b' = -x^3 +3x.

The point (1, 0) for example belongs to y^2 = x^3 - 3x + 2. Its order is 2. Compute (1, 0) + (1, 0) and
you would end up with a point at infinity (i.e., you'd get a division by zero if you compute with affine
coordinates, or z = 0 if you compute with projective/Jacobian coordinates).

>If no points of the form (x,0) exist on P-256, how can the

attacker rely on essentially random choices of the x-coordinate by the 

victims initial computation PKv = [SKv]G to satisfy E': y^2 = x^3 + a*x + b'?

This is rather counter-intuitive, but the attacker doesn't have to do anything else. When the victim

computes (x, 0) * k, the computation is performed on the invalid curve, not on P-256. There's nothing

special about 0, if you take a random y, you'd find that (x, y) and (x, -y) belong to a unique curve with

a unique b'. The authors chose 0 because (x, 0) is always a point of order 2.

>Simply changing the y-coordinate to 0 in my experiments has not once produced 

the point at infinity.

What did you get?

Which point addition formula did you use?

--

From: <removed>

Date: Thu, Sep 27, 2018 at 10:23 PM

Sir, this attack is in fact beautiful. My previous implementation produced

random looking values anytime I made a y-coordinate zero and multiplied it by a

scalar.  This lead to a lot of confusion and I'm embarrassed to say that I had

not made my code take that path yet.  Until now all the test vectors I used

passed--which btw is one of the lessons I'm taking away from this.  It turns out my

PointInvert function was not producing the correct value for points of the form

(x,0).  I have now rewritten it along with new Add and Double functions.  I translated

the point addition and doubling formulas for short Weierstrass curves using

C/GMP from the Explicit-Formulas Database--

https://www.hyperelliptic.org/EFD/g1p/auto-shortw.html--And I'm glad to say 

this part of the attack is working.  Using my implementation any point of the

form (x,0) multiplied with a random scalar produces the expected results.  I am

grateful that you took the time to entertain and moreover answer my questions.

Forcing myself to write them, and reading your responses pushed me in the right

direction and demystified many notions that I had. I could not find anyone else

to ask. Thank you!  <removed>.