### 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

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 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>.

## Comments

a good layman description of the attack?

My rough understanding is to fix this bug, one just need to add "if (x, y) are invalid, reject sending back q*(x, y)'. Is this correct?

Practically, how hard it is to deploy this fix on all Bluetooth devices in your opinion?