# S2DH Writeup
### RCTF 2022 - crypto 769 - 7 solves
> [下载附件](_media_file_task_2ca138ee-f38f-4783-ae50-537dc868006e.zip)
#### Analysis
After unzipping the attachment, we get [s2dh.ipynb](s2dh.ipynb) file. Apparently, the challenge implements plain [SIDH](https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exchange) protocol. Anyone who is unfamiliar with this ~broken~ protocol can first start with this great article: [Supersingular isogeny key exchangefor beginners](https://eprint.iacr.org/2019/1321.pdf). Simply speaking, SIDH relies on the assumption that finding walks between supersingular elliptic curve is hard. 
For our profit, lets inspect the codeblocks one by one.
Define constants and check `p` is prime.
```pythona = 43b = 26p = 2^a*3^b - 1assert p in Primes()```
Define supersingular elliptic curve `E: y ^ 2 = x ^ 3 + x` over `GF(p ^ 2)`.
```pythonK. = GF(p^2, modulus=x^2+1)E = EllipticCurve(K, [1, 0])```
Generate public base point `Pa`, `Qa` for Alice, and `Pb`, `Qb` for Bob. Make sure that the points are safe from [torsion point attack](https://eprint.iacr.org/2022/654.pdf).
```pythonPa = E(0)while (2^(a-1))*Pa == 0:    Pa = 3^b * E.random_point()PaQa = Pawhile Pa.weil_pairing(Qa, 2^a)^(2^(a-1)) == 1:    Qa = 3^b * E.random_point()QaPb = E(0)while (3^(b-1))*Pb == 0:    Pb = 2^a * E.random_point()PbQb = Pbwhile Pb.weil_pairing(Qb, 3^b)^(3^(b-1)) == 1:    Qb = 2^a * E.random_point()Qb```
Generate Alice's secret key `Sa`, `Ta`, and Bob's secret key `Sb`, `Tb`. Compute isogenies and make an exchange.
```pythonSb = randint(0, 3^b-1)Tb = randint(0, 3^b-1)R = Sb * Pb + Tb * Qbpsi = E.isogeny(R)Eb, psiPa, psiQa = psi.codomain(), psi(Pa), psi(Qa)Eb, psiPa, psiQa
Sa = randint(0, 2^a-1)Ta = randint(0, 2^a-1)R = Sa*Pa + Ta * Qaphi = E.isogeny(R)Ea, phiPb, phiQb = phi.codomain(), phi(Pb), phi(Qb)Ea, phiPb, phiQb```
Tip: when you run the upper code segment, computing isogeny will take forever. To overcome this, supply `algorithm="factored"` parameter to `isogeny` method to speed things up, like `E.isogeny(R, algorithm="factored")`.
Now bob can compute shared isogeny, and gain shared elliptic curve. The [j-invariant](https://en.wikipedia.org/wiki/J-invariant) will be the final shared secret.
```pythonJ = Eb.isogeny(Sa*psiPa + Ta*psiQa, algorithm='factored').codomain().j_invariant()```
Xor encrypt flag, using value of `J`. Our goal is to recover `J`.
```pythonflag = open("flag.txt","r").read()assert flag[:5] == "RCTF{" and flag[-1] == "}"flag = flag[5:-1]int.from_bytes(flag.encode()) ^^ ((int(J[1]) << 84) + int(J[0]))```
#### SIDH is broken in 2022 - Castryck-Decru Attack
Apply [Castryck-Decru Attack](https://eprint.iacr.org/2022/975), which is an efficient key recovery attack on SIDH. [issikebrokenyet.github.io](https://issikebrokenyet.github.io) shows the overview of the impact of the attack. We even have a [sagemath implementation of the attack](https://github.com/jack4818/Castryck-Decru-SageMath).
#### Change the starting curve
However we must modify the source code in order to apply to this challenge because, the starting curve used in sagemath code has the form `E: y ^ 2 = x ^ 3 + 6 * x ** 2 + x` over `GF(p ^ 2)`, which is different from problem setting.
According to the [original paper](https://eprint.iacr.org/2022/975), it says the attack can be also applied to `E`. See section 3.1: 
> `E_start: y ^ 2 = x ^ 3 + x`, we have the automorphism `i : (x, y) -> (−x, sqrt(y))` and we simply let `2i = [2] ◦ i`. 
Therefore, we use automorphism to generate endomorphism `two_i`.
```pythonK. = GF(p^2, modulus=x^2+1)PR.<x> = PolynomialRing(K)# starting curve updated, not E_start = EllipticCurve(Fp2, [0,6,0,1,0])E = EllipticCurve(K, [1, 0])E.set_order((p+1)^2)
phi = EllipticCurveIsogeny(E, x)E1728 = phi.codomain()
for iota in E1728.automorphisms():    P = E1728.random_point()    if iota(iota(P)) == -P:        two_i = phi.post_compose(iota).post_compose(phi.dual())        break```
Now apply `CastryckDecruAttack` method using `two_i` and recover `recovered`.
```pythonrecovered = CastryckDecruAttack(E, Pa, Qa, Eb, psiPa, psiQa, two_i, num_cores=num_cores)```
`recovered` satisfies the following equation:
```pythonSa * Pa + Ta * Qa == Pa + recovered * Qa```
Therefore we finally evaluate shared secret `shared` using `recovered` by computing j-invariant of codomain of isogeny.
```pythonshared = Ea.isogeny(phiPb + recovered * phiQb, algorithm='factored').codomain().j_invariant()```
Xor to recover flag:
```pythonc = 243706092945144760206191226817331300960683091878992key = ((int(shared[1]) << 84) + int(shared[0]))flag = b"RCTF{" + long_to_bytes(c ^^ key) + b"}"```
We finally get flag:
```RCTF{SIDH_isBr0ken_in_2O22}```
Full exploit code: [solve.sage](solve.sage) requiring [castryck_decru_shortcut.sage](castryck_decru_shortcut.sage.sage), [helpers.py](helpers.py), [public_values_aux.py](public_values_aux.py), [richelot_aux.sage](richelot_aux.sage), [speedup.sage](speedup.sage), [uvtable.sage](uvtable.sage): from [github.com/jack4818/Castryck-Decru-SageMath](https://github.com/jack4818/Castryck-Decru-SageMath)
Problem source: [s2dh.ipynb](s2dh.ipynb), converted to [s2dh.sage](s2dh.sage)