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 cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 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 cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y're eating cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 world!

--

On Wed, Sep 26, 2018 at 6:34 PM 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
cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 form (x,0).  How to interpret Semi-Passive Attack outlined in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365
Biham-Neumann paper? How do we confine cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 victim's final point scaling to a
small subgroup/invalid curve while only manipulating cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 y-coordinate to be 0?
When do I calculate and use b'? What are some things I should be asking myself
to better understand cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Fixed Coordinate Invalid Curve Attack? Thank you.  I
appreciate you taking cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 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 ,

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 cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 P-256 equation. If you look at point addition
or doubling formula, you'd notice that it doesn't depend on b. This means cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 scalar
multiplication would take (x, 0) and produce a point at infinity if cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 scalar is even. This
point at infinity is on E'. But all curves in short Weierstrass form have cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 same point at
infinity (in projective coordinate it is cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 point (0, 1, 0)).

Does it make sense?

--

On Wed, Sep 26, 2018 at 8:47 PM 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 cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 cycle through its five possible values
including cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 point at infinity when multiplied by any scalar [2,q-2] in my
experiments.

Unfortunately my confusion persists...how many points of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 form (x,0) land on
invalid curves? Suppose cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 attacker knows a unique b' which defines an invalid
curve with points of order two.  I still do not understand how cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 attacker can
force cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 victim to compute over cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 invalid curve if cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365y have no control over
cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 x-coordinate? If no points of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 form (x,0) exist on P-256, how can cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365
attacker rely on essentially random choices of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 x-coordinate by cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365
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 cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 methods outlined in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Offline-Computations section of
Jager-Schwenk-Somorovsky Practical Invalid Curve Attacks on TLS-ECDH paper? And
if I did, what would I do with cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 knowledge of b'?

Simply changing cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 y-coordinate to 0 in my experiments has not once produced
cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 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 cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 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 cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 form (x,0) exist on P-256, how can cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365
attacker rely on essentially random choices of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 x-coordinate by cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 
victims initial computation PKv = [SKv]G to satisfy E': y^2 = x^3 + a*x + b'?

This is racá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365r counter-intuitive, but cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 attacker doesn't have to do anything else. When cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 victim
computes (x, 0) * k, cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 computation is performed on cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 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 cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 y-coordinate to 0 in my experiments has not once produced 
cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 point at infinity.

What did you get?

Which point addition formula did you use?

--

From:
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 cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 test vectors I used
passed--which btw is one of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 lessons I'm taking away from this.  It turns out my
PointInvert function was not producing cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 correct value for points of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 form
(x,0).  I have now rewritten it along with new Add and Double functions.  I translated
cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 point addition and doubling formulas for short Weierstrass curves using
C/GMP from cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 Explicit-Formulas Database--
this part of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 attack is working.  Using my implementation any point of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365
form (x,0) multiplied with a random scalar produces cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 expected results.  I am
grateful that you took cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 time to entertain and moreover answer my questions.
Forcing myself to write cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365m, and reading your responses pushed me in cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 right
direction and demystified many notions that I had. I could not find anyone else
to ask. Thank you!  .

Comments

Ned said…
Is https://blog.trailofbits.com/2018/08/01/bluetooth-invalid-curve-points/
a good layman description of cá cược thể thao bet365_cách nạp tiền vào bet365_ đăng ký bet365 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?