De1CTF 2020 - Writeup of ECDH

invalid-curve.md

ECDH invalid curve attack

We are given an elliptic curve E: y^2 = x^3 + a x + b with parameters

q = 100173830297345234246296808618734115432031228596757431606170574500462062623677
a = 34797263276731929172113534470189285565338055361167847976642146658712494152186
b = 39258950039257324692361857404792305546106163510884954845070423459288379905976

and generator point

G = (82031236592532820689585715102128084141757606384165265204422508645702672267722 : 33439355059297433276103816374972293139178479876025851884027868838522796014258 : 1)

The server let us perform a DHKE and doesn't check if the point we provide it is actually on the curve. Hence, we can perform an invalid curve attack, as explained in this presentation.

Generate low order points

First, we need to generate many low order points on the invalid curves E': y^2 = x^3 + a x + b'.

This is easy done with the help of SageMath.

sage: q = 100173830297345234246296808618734115432031228596757431606170574500462062623677
....: a = 34797263276731929172113534470189285565338055361167847976642146658712494152186
....: b = 39258950039257324692361857404792305546106163510884954845070423459288379905976
....: K = GF(q)
....: E = EllipticCurve(K, [a, b])
....: G = E(82031236592532820689585715102128084141757606384165265204422508645702672267722, 33439355059297433276103816374972293139178479876025851884027868838522796014258)
....:
sage: iE = EllipticCurve(K, [a, 1234])
sage: iG = iE.gen(0)
sage: og = iG.order()
sage: factor(og)
2^3 * 5 * 17 * 1583 * 58537 * 69255220433341 * 26472202647822897991 * 867144345585680379966985487918263
sage: iP = Integer(og / 1583)  * iG
sage: iP.order()
1583

We collect many of these points until all their orders combined are greater than the curve order.

sage: invald_points
{95257: (61525481172549840114525117922745200669389792794269611260243719157840729559472 : 2809034924006916171905777480746940507253042364532036799921314000762035700453 : 1),
 # ...
 19: (90826357625685413102183839410503089625443649738924043388208664808851592670178 : 51048533919680498928268703922394659563099571487483282157125145968401276298068 : 1),
 17: (90706697813729842331190337039684315682589477561034385988010502151409251334860 : 32022219151062179802548334507113925076356234583774923646403321484136573930502 : 1),
 13: (10204346218276547611713684248295143407405935286632923206096574487630324140835 : 42123905502990019002205812578796322891720816590849351960005586096082578252767 : 1)}

Recover the secret with CRT

Now we can send all these invalid points to the server and read the ECDH shared secret iS = secret * iP computed.

Now we solve the ECDLP for iS and obtain secret mod (iP.order()).

sage: iS = secret * iP
sage: discrete_log(iS, iP, iP.order(), operation='+')
230
sage: secret % iP.order()
230

Once we have accumulated enough equations

s1 = secret mod order1
s2 = secret mod order2
.
.
.
sN = secret mod orderN

we simply use the CRT and obtain secret.