In this post, we’ll crack the following challenge:

#!/usr/bin/env python3

# pip install pycryptodome
from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
import hashlib
from math import gcd
import os
from random import randint
from secrets import message, order, p, q

# Addition formula for elliptic curves in short Weierstrass form
def add(P, Q, E):
     n,A = E
     X1,Y1 = P
     X2,Y2 = Q
     if X1 == 0 and Y1 == 0:
          return Q
     if X2 == 0 and Y2 == 0:
          return P
     double = False
     if X1 == X2:
          if Y1 == (- Y2) % n:
               return (0,0)
          else:
               double = True
     if double:
          l = (3*X1**2 + A)*inverse(2*Y1, n) % n
     else:
          l = (Y2-Y1)*inverse(X2-X1, n) % n
     X3 = (l**2-X1-X2) % n
     Y3 = (l*(X1-X3)-Y1) % n
     return (X3, Y3)

# Scalar-point elliptic curve multiplication
def mul(n, P, E):
    Q = P
    R = (0,0)
    for bit in bin(n)[::-1][:-2]:
        if bit == "1":
            R = add(R, Q, E)
        Q = add(Q, Q, E)
    return R

# AES encryption
def encrypt(secret, message):
     sha256 = hashlib.sha256()
     sha256.update(str(secret).encode())
     key = sha256.digest()
     iv = os.urandom(16)
     aes = AES.new(key, AES.MODE_CBC, iv)
     ciphertext = aes.encrypt(pad(message, 16))
     return (ciphertext.hex(), iv.hex())

# The elliptic curve parameters
n = p*q
A = 0x1115160ded643518fc0b46ad430da8e5c15f85fe03d0b6b181060f8c167714c650b31b4850b2f06430903acabcee293a8f88eb2a94554636fe823e6b6e753f7de3b6436b32518715df94030bf910993d5158cf47c83042e3fff16181819155f4
E = (n, A)

# The base point
G = (0x858cd5e8856db40d611f0c8a605296b64146118a5112bd5f25333eecbcb0b22ba689491990304ac0c709e99af8cc0c789131f940ec79936f4c75a24ef7165eb1e53f0ffb46a931d2ec95ba678b5825cb3649ab4d4e4b206dcbc62236fefa3bc1, 0x461e32608d4000477828abe7e900882d9864d3792b38a332b6fab213a9bf840fe3cb7b3be185266143c493e8d10d9cf37ea8f90695b7e6bdc17938cb7d11dd4e40f7f4037e9e0e3307e4e1de207f56a51e62eab3bb21ca6ebbc3f9bc8e4be604)
assert~(gcd(n,order) == 1)
assert (mul(order, G, E) == (0,0))

# Alice's keypair
alice_priv = randint(2, order-2)
alice_pub = mul(alice_priv, G, E)

# Bob's keypair
bob_priv = randint(2, order-2)
bob_pub = mul(bob_priv, G, E)

# Diffie-Hellman between Alice and Bob keys
shared_secret = mul(alice_priv, bob_pub, E)
assert (shared_secret == mul(bob_priv, alice_pub, E))

# Encrypting the message using the Alice and Bob's shared secret
enc = encrypt(shared_secret, message)

# public parameters for the challenge
# alice_pub = (0x8a7fe719d98da61cba2b5abdd2c7461b792222f823cd14858692b19b946800a1c510d831247d49c26b52cedf4726263307b2487726210382e37ce882c93141cba24881ce2b5e4815f18370b5c6443116aa1f4f02001c09cf3947f2decd07c6, 0x5e4c3391c7c8d3ab7ce8328cbd456c8d852a87f86a683ee102c7d6fe52fdf10a8d9cf48e14fdb4e2b40ba4078e154e3a50e3d3d9ab886968dea5dc1b73b0c995d27fcc20181f671aff4cd2d68fceda73da3c99e48df70ace5d6051b4fb4d9abd)
# bob_pub = (0x7f6723b21ab7350fb244f260e197dec47d241818216d77e6f1d8fabf11aa7d1b37d382629668d63823ef6b46351eac3ba0b8eed3676b7b0ea6355df9841ecd37d053d4124eb869effd2d8f5960917f34fbc1adee5130669a458b1bc612f22dcf, 0x63c0c62f2c1f799f87e0e77fcef4445c68374b488672bb2d20049f866594db691f4163477c6c2471cb8c053a2209966ab91522aae1f2c5c86e3cd74d77ac12957393ac59c969a7fb14626a0c1b1d37de3ed1db86105f3c58af742c9b67fa641e)
# enc = ('c60e342afb987f8d5d690a75296e908c875e3ceb3476a8a900e2a0aaec947ba89f072dae4ce555fe898bba44702bc9a87affe8731542d5fde899cc7669195537', '1e3ea9e079af6467077c042277f456a9')

Breaking the given Diffie-Hellman key exchange

The objective is to recover the encrypted message by finding the symmetric key, equivalent to discovering the common secret established with Diffie-Hellman.

The code provided in the Python module above implements a Diffie-Hellman key exchange conducted over a pseudo elliptic curve $E$ that is defined over the commutative ring $Z / n Z$ , where $n$ is the product of two primes, $n = pq$ .

We call $E$ a pseudo elliptic curve as the projection modulo $p$ (or $q$ ) sends a point with coordinates in $Z / NZ$ , which is a solution to $y^{2} = x^{3} + a x + b$ , to a solution with coordinates in $Z / pZ$ (or $Z / qZ$ ). The bijection on the points with coordinates in $Z / NZ$ to $Z / pZ \times Z / qZ$ , which is provided by the Chinese Remainder Theorem, allows, by iterating an element of $E_{N}$ , to iterate its image in $E_{p}$ and $E_{q}$ .

Addition is not a closed operation as starting from an element $(x_{p}, x_{q}) \in E_{N}$ , we can potentially obtain through successive iterations of $t * (x_{p}, x_{q})$ (with $t \in N$ ), an element of the form $(O_{p}, y_{q})$ with $y_{q} \neq = O_{q}$ , resulting in a failure to inverse modulo $n$ . This fact is leveraged by the Elliptic Curve Factorization method.

The attacker has access to the cryptographic scheme in use, the public keys of Alice and Bob, the base point, the AES ciphertext along with the initialization vector for CBC mode, certain invariants (such as the order of the base not dividing $n$ and the order of the base dividing the secret variable $order$ ), and a coefficient $A$ from the elliptic curve equation in short Weierstrass form (that we infer from the code of addition, in particular point doubling), as defined in the code.

The first step is to identify the parameters of the elliptic curve to apply the elliptic curve group laws. Given the bit size of the coefficients from the public keys and $A$ , we can estimate that $n$ is approximately 767 bits long ( $lo g_{2} (A) = 767$ ), suggesting that we can factor it.

We assume that the base $(x_{g}, y_{g})$ lies on the curve so that the public keys $(x_{a}, y_{a})$ , $(x_{b}, y_{b})$ verify the equation of the curve:

$y^{2} = x^{3} + A * x + B mod n .$

This gives us the system of equations for $k_{g}, k_{a}, k_{b} \in Z / n Z$ :

y_{g}^{2} y_{a}^{2} y_{b}^{2} = x_{g}^{3} + A x_{g} + B + k_{g} n = x_{a}^{3} + A x_{a} + B + k_{a} n = x_{b}^{3} + A x_{b} + B + k_{b} n

where

A=103596425889377080164915482358617002041351954378211200507698464287267467562102579138879849938743818618578260913955663880916017853259801947354394587117876114197386603605261897797482230209417925870653877783699198858204764631072855540

To solve the system, we can cancel $B$ and get two multiples of $n$ , so that the GCD must contain $n$ :

We subtract equation (1) from equation (2): $y_{g}^{2} - y_{a}^{2} = x_{g}^{3} - x_{a}^{3} + A_{x} g - A x_{a} + (k_{1} - k_{2}) n$ and subtract equation (2) from equation (3): $y_{a}^{2} - y_{b}^{2} = x_{g}^{3} - x_{b}^{3} + A x_{a} - A x_{b} + (k_{2} - k_{3}) n .$

We obtain

? gcd(Gy^2-Ay^2-Gx^3+Ax^3-A*Gx+A*Ax, Ay^2-By^2-Ax^3+Bx^3-A*Ax+A*Bx)
1678537998198851937614822925852498196778505162818134940507328971518644228582147661422128899284629398754476732215312434498918911185606832895314242323735600539491453300922437200836220079184530073274973175265103706225264182868724826422

The GCD is even, so we divide it by two:

n=839268999099425968807411462926249098389252581409067470253664485759322114291073830711064449642314699377238366107656217249459455592803416447657121161867800269745726650461218600418110039592265036637486587632551853112632091434362413211

We obtain the factorization of $n = pq$ using factordb: http://factordb.com/index.php?query=839268999099425968807411462926249098389252581409067470253664485759322114291073830711064449642314699377238366107656217249459455592803416447657121161867800269745726650461218600418110039592265036637486587632551853112632091434362413211

p=21448884629509455597215930748900681159323242237303782800136123960324312583790994045488533691889446581945518026508097

q=39128794508258790515072383975390806261898062361839764511933549761670978999997096053314214965077731424736773956742363

Note that if it wasn’t in a database we’d have to spend at least two years trying to factor with enough money (See https://www.theregister.com/2010/01/07/rsa_768_broken/.)

Apparently, one can recover the prime factors with ECM, but I didn’t manage to do it.

Now that $n$ is known, $B$ can be recovered using the curve’s equation $y^{2} - x^{3} + A x = B mod n$ with any known point on the curve (here we’re using Alice and Bob’s public keys):

? Mod(Ay^2-(Ax^3+Ax*A),n)
Mod(143188276148589376080400041476610197861506173692308496559700284838294405080011892744046115907471065283210954269163833843227801329586206297077386545269988630631589844044047116345436451677084231942003198566750008713296535780483787698, 839268999099425968807411462926249098389252581409067470253664485759322114291073830711064449642314699377238366107656217249459455592803416447657121161867800269745726650461218600418110039592265036637486587632551853112632091434362413211)
? B=Mod(By^2-(Bx^3+Bx*A),N)
? B
Mod(143188276148589376080400041476610197861506173692308496559700284838294405080011892744046115907471065283210954269163833843227801329586206297077386545269988630631589844044047116345436451677084231942003198566750008713296535780483787698, 839268999099425968807411462926249098389252581409067470253664485759322114291073830711064449642314699377238366107656217249459455592803416447657121161867800269745726650461218600418110039592265036637486587632551853112632091434362413211)

Now, it is not yet clear that the discrete logarithm instances on the two smaller curves $E_{p}$ and $E_{q}$ are easy.

Good news! The cardinal of $E_{q}$ is smooth! And $∣ E_{p} ∣ = p$ !

? E = ellinit([A, B], N);
? Eq = ellinit([A, B], q);
? Ep = ellinit([A, B], q);
21448884629509455597215930748900681159323242237303782800136123960324312583790994045488533691889446581945518026508097
? ellcard(Ep)==p
1
? ellcard(Eq)
39128794508258790515072383975390806261898062361839764511942298258964034969666402898545021947551664725330970305070780
? factor(ellcard(Eq))

[      2 2]

[      5 1]

[  22877 1]

[  31337 1]

[  38153 1]

[  48193 1]

[  55529 1]

[  56779 1]

[ 229717 1]

[ 337691 1]

[ 470831 1]

[ 473899 4]

[ 488249 1]

[ 646073 1]

[ 830309 1]

[ 852641 1]

[ 949621 2]

[1068101 1]

[1188029 1]

So that we can solve the discrete logs in the projections mod $q$ with PARI/GP (probably using a divide-and-conquer approach like Pohlig-Hellman):

elllog(Eq,[Ax,Ay],[Gx,Gy])=6032514116083726190889204167808185562374926976335164458115721650094303733622175383598806682421201744522594964562500

elllog(Eq,[Bx,By],[Gx,Gy])=6556214363219928339956484184417336535020549980395602882169490676087611387946187279572959815987197383310891130673347

Now, let’s move on to solving the discrete logs on the $E_{p}$ curve.

Turns out that the cardinal of $E_{p}$ is equal to the prime $p$ in the RSA factorization $n = pq$ .

ellcard(Ep)=21448884629509455597215930748900681159323242237303782800136123960324312583790994045488533691889446581945518026508097

It’s folklore that these curves are insecure. One can use Smart’s attack to solve the discrete logarithm in $E_{p}$ . (See http://shiftleft.com/mirrors/www.hpl.hp.com/techreports/97/HPL-97-128.pdf, and I used the code from https://crypto.stackexchange.com/questions/70454/why-smarts-attack-doesnt-work-on-this-ecdlp.)

sage: def SmartAttack(P,Q,p):
....:     E = P.curve()
....:     Eqp = EllipticCurve(Qp(p, 2),
          [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
....:
....:     P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
....:     for P_Qp in P_Qps:
....:         if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
....:             break
....:
....:     Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
....:     for Q_Qp in Q_Qps:
....:         if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
....:             break
....:
....:     p_times_P = p*P_Qp
....:     p_times_Q = p*Q_Qp
....:
....:     x_P,y_P = p_times_P.xy()
....:     x_Q,y_Q = p_times_Q.xy()
....:
....:     phi_P = -(x_P/y_P)
....:     phi_Q = -(x_Q/y_Q)
....:     k = phi_Q/phi_P
....:     return ZZ(k)
....:
sage: p=21448884629509455597215930748900681159323242237303782800136123960324312583790994045488533691889446581945518026508097
sage: a=1035964258893770801649154823586170020413519543782112005076984642872674675621025791388798499387438186185782609139556638809160178532598019473543945871178761141973866036052
....: 61897797482230209417925870653877783699198858204764631072855540
sage: b=1431882761485893760804000414766101978615061736923084965597002848382944050800118927440461159074710652832109542691638338432278013295862062970773865452699886306315898440440
....: 47116345436451677084231942003198566750008713296535780483787698
sage: E = EllipticCurve(GF(p), [a, b])
sage: G=E(809917996085623596183155671799226683559263158876107146909552458699621102387055305121095825844975138522358357879942120959087921542081243925642852168224145563989816000023335396091780097425965058849805961388496352139647113192
....: 755837889,425232014011458506142527595923565758237059374116846210181918079377740579722472185959717171932575566276976231568877955469810862752866262607256763789452100453127567100132780023957261495248527247005031814707980953067048
....: 461384920327684)
sage: PA=E(32809931325846571369128166777972819748616034409675889429956743485854427916098750701614087922283284316303207883437835984008173228235697370592028086208138601129077961665196783280952636690516661870409512620683471991174379394
....: 68797894,5718704146167680502698576211019939329664019464380198889619958087792486224014949207772119437541601519133546121356594422675404049649655121273622352435018566389069211669869515657162102121403833215109139485046651286288815
....: 16267985279677)
sage: PB=E(77263784878436204741079832050111979221945629308616276482714727329255340542192022364859504339780480690689547064653339967404681402632940763647908136245582489916179498109380293562583795401186738480200870711678255538664733204
....: 3546045903,60495458829032289732988015820195893809080825786555882713809025616918678014682946802127494652827163653752050107760333071755072166135379627978845091407683376506608079564915817255857559702664454494527625566684298546863
....: 4159424386786334)
sage: nA=SmartAttack(G,PA,p)
sage: nA
7395663144558145880709550344115364075874322664887515308037418412277080638188778301228793645870757083284667992021649
sage: nB=SmartAttack(G,PB,p)
sage: nB
1007497335457249792290938208585157963901906486126441946799755125977718064514225444871044144062764081637106961860931

Then we recombine the solutions to the discrete logarithms in the projections $E_{p}$ and $E_{q}$ (of order $∣ E_{p} ∣$ and $∣ E_{q} ∣$ ) using the Chinese Remainder Theorem over the rings (the orders of $E_{p}$ and $E_{q}$ being coprime):

$Z / ∣ E ∣ Z ≅ Z / ∣ E_{p} ∣ Z \times Z / ∣ E_{q} ∣ Z$

? chinese(Mod(6556214363219928339956484184417336535020549980395602882169490676087611387946187279572959815987197383310891130673347, ellcard(Eq)), Mod(1007497335457249792290938208585157963901906486126441946799755125977718064514225444871044144062764081637106961860931,ellcard(Ep)))

Mod(679367181422335532670428891988987167508888694863727469722850650258875787975058367114605263775209915682093782795697504682680378736231879102969104765691003780791182170343651446477584144804352114220687150637083554968108906102993528007, 839268999099425968807411462926249098389252581409067470253852131268442447558263692299374523254799771752556368976183042141627044066712565858458114286769329059654750630479160229387540075423347651574415381500641665464811714975828105660)

? chinese(Mod(7395663144558145880709550344115364075874322664887515308037418412277080638188778301228793645870757083284667992021649, ellcard(Ep)), Mod(6032514116083726190889204167808185562374926976335164458115721 650094303733622175383598806682421201744522594964562500,ellcard(Eq))

Mod(352538409628000412208083522710417771098495734229928425702117825841176244611443099099304405793261216053057230795710237737313133671934913745592600736633023466469016957555072245400036549493431368631563672732601288892102129716156210960, 839268999099425968807411462926249098389252581409067470253852131268442447558263692299374523254799771752556368976183042141627044066712565858458114286769329059654750630479160229387540075423347651574415381500641665464811714975828105660)

So the private key for Alice is:

352538409628000412208083522710417771098495734229928425702117825841176244611443099099304405793261216053057230795710237737313133671934913745592600736633023466469016957555072245400036549493431368631563672732601288892102129716156210960

And Bob:

679367181422335532670428891988987167508888694863727469722850650258875787975058367114605263775209915682093782795697504682680378736231879102969104765691003780791182170343651446477584144804352114220687150637083554968108906102993528007

One can verify them correct against the public keys:

? ellmul(E[Gx,Gy],352538409628000412208083522710417771098495734229928425702117825841176244611443099099304405793261216053057230795710237737313133671934913745592600736633023466469016957555072245400036549493431368631563672732601288892102129716156210960)
[Mod(3280993132584657136912816677797281974861603440967588942995674348585442791609875070161408792228328431630320788343783598400817322823569737059202808620813860112907796166519678328095263669051666187040951262068347199117437939468797894, 839268999099425968807411462926249098389252581409067470253664485759322114291073830711064449642314699377238366107656217249459455592803416447657121161867800269745726650461218600418110039592265036637486587632551853112632091434362413211), Mod(571870414616768050269857621101993932966401946438019888961995808779248622401494920777211943754160151913354612135659442267540404964965512127362235243501856638906921166986951565716210212140383321510913948504665128628881516267985279677, 839268999099425968807411462926249098389252581409067470253664485759322114291073830711064449642314699377238366107656217249459455592803416447657121161867800269745726650461218600418110039592265036637486587632551853112632091434362413211)]
? Ax
3280993132584657136912816677797281974861603440967588942995674348585442791609875070161408792228328431630320788343783598400817322823569737059202808620813860112907796166519678328095263669051666187040951262068347199117437939468797894
? Ay
571870414616768050269857621101993932966401946438019888961995808779248622401494920777211943754160151913354612135659442267540404964965512127362235243501856638906921166986951565716210212140383321510913948504665128628881516267985279677
? ellmul(E,[Gx,Gy], 679367181422335532670428891988987167508888694863727469722850650258875787975058367114605263775209915682093782795697504682680378736231879102969104765691003780791182170343651446477584144804352114220687150637083554968108906102993528007)
[Mod(772637848784362047410798320501119792219456293086162764827147273292553405421920223648595043397804806906895470646533399674046814026329407636479081362455824899161794981093802935625837954011867384802008707116782555386647332043546045903, 839268999099425968807411462926249098389252581409067470253664485759322114291073830711064449642314699377238366107656217249459455592803416447657121161867800269745726650461218600418110039592265036637486587632551853112632091434362413211), Mod(604954588290322897329880158201958938090808257865558827138090256169186780146829468021274946528271636537520501077603330717550721661353796279788450914076833765066080795649158172558575597026644544945276255666842985468634159424386786334, 839268999099425968807411462926249098389252581409067470253664485759322114291073830711064449642314699377238366107656217249459455592803416447657121161867800269745726650461218600418110039592265036637486587632551853112632091434362413211)]

We implement the decryption algorithm:

#!/usr/bin/env python3

# pip install pycryptodome
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib

shared_secret = (526572924890606611697396012530907637485635710747769900449607148419307913599033206707517016551119144075709223774555572842052477818235013630817199381654462697925209092343061974127401128957339473033924126800574843461030652840877570385, 753610744600643360254454383152919726054807184753835424638525162720080865491011025819237711112694448257437597680023700894139018021926476474848504041148770651552940099217717646318700014950625977355774914995632100567952133772407078563)

enc = ('c60e342afb987f8d5d690a75296e908c875e3ceb3476a8a900e2a0aaec947ba89f072dae4ce555fe898bba44702bc9a87affe8731542d5fde899cc7669195537', '1e3ea9e079af6467077c042277f456a9')

# AES decryption function
def decrypt(secret, ciphertext_hex, iv_hex):
    # Derive the AES key from the shared secret
    sha256 = hashlib.sha256()
    sha256.update(str(secret).encode())  # Hash the shared secret to derive a key
    key = sha256.digest()

    # Convert hex-encoded IV and ciphertext back to bytes
    iv = bytes.fromhex(iv_hex)
    ciphertext = bytes.fromhex(ciphertext_hex)

    # Initialize the AES cipher in CBC mode
    aes = AES.new(key, AES.MODE_CBC, iv)

    # Decrypt the ciphertext and unpad the plaintext
    plaintext = unpad(aes.decrypt(ciphertext), 16)

    return plaintext

# Example usage:
# shared_secret is the same as used for encryption
# ciphertext_hex and iv_hex are received from the encrypted message

plaintext = decrypt(shared_secret, enc[0], enc[1])
print("Decrypted message:", plaintext.decode())

Running the above Python script we obtain that the decrypted message is: congratulations! The Magic Words are Squeamish Ossifrage.

Recommendations

Using a proper elliptic curve

Overall, the security of this scheme is hindered by the choice of an RSA group. It would have been better to pick a finite field.

Elliptic curve point addition can fail

The addition function is derived for an elliptic curve over a field, so modular inversions can fail modulo composite $n$ , potentially allowing it to fail to establish a shared secret.

Using a well-studied and standardized elliptic curve

The chosen elliptic curve should come from well-established secure standards like secp256k1 or other NIST curves (P-256 or P-521).

Not checking points to be on the right subgroup of the elliptic curve

This can allow an attack to send a point either not lying on the curve or lying on a small subgroup so that the result of the DH key exchange lies on a small subgroup where solving a discrete logarithm is computationally feasible. See https://crypto.stackexchange.com/questions/71240/elliptic-curve-cryptography-insecure-when-input-does-not-lie-on-the-curve.

Diffie-Hellman key exchange is vulnerable to man-in-the-middle attacks

The Diffie-Hellman key exchange should be authenticated with Alice and Bob’s digital signatures to prevent man-in-the-middle attacks.

Ciphertexts are malleable

Ciphertext produced with AES in CBC mode is not protected from modification because it has no MAC. AES in GCM mode should be used.

The previous approach can be simplified using Authenticated Encryption with Associated Data (AEAD). This algorithm combines a cipher and a MAC using a single key. We use AES-GCM, which is an AEAD.

Messages can be encrypted-then-authenticated, and signed, as follows (|| stands for concatenation): encrypt(message,key,nonce,additional_data=Sign(message,pubkey)) || Sign(message,pubkey). A few remarks:

the signature proves the same thing as in the unencrypted version (signature of the plaintext, and not of the ciphertext)
we also MAC the signature
we bind the signature to its message thanks to the additional_data field

This does not fall into cryptographic doom since the authentication tag is checked before (or concurrently with) the decryption.

Elliptic curve point multiplication does not run in constant-time

The multiplication function implements a naive double-and-add, whose runtime depends on the private key, opening the door to timing/side-channel attacks (see Remote Timing Attacks are Practical (Brumley & Boneh).

Notes

Explorer

Diffie-Hellman RSA challenge