Rating:
# sidhe (crypto, 300p, 29 solved)
In the task we get [server code](https://raw.githubusercontent.com/TFNS/writeups/master/2020-04-17-PlaidCTF/sidhe/server.sage) and we can connect to the server.
## Task analysis
The server code impelements Supersingular isogeny Diffie–Hellman key exchange protocol.
The code is simple to follow:
1. Server randomly selects a `private secret`
2. We can perform 300 interactions with the server
3. Each time we can provide a new public key
4. Each time we can send payload encrypted using derived shared secret
5. If we send encrypted `Hello World` we get back confirmation of valid message
6. If we send encrypted `private secret` we get back a flag
7. If we send anything else, we get confirmation of invalid message
## Vulnerability
The vulnerability lies in the fact that `private secret` is selected only once per connection, and we can perform 300 key exchanges, with the same secret in place.
## Solution
The general idea behind the attack is pretty simple to understand.
The private secret (sk3) is used in:
```python
def isoex3(sk3, pk2):
Ei, P, Q = pk2
S = P+sk3*Q
for i in range(e3):
R = (3^(e3-i-1))*S
phi = Ei.isogeny(R)
Ei = phi.codomain()
S = phi(S)
return Ei.j_invariant()
```
Where `P` and `Q` values are provided as part of our public key.
Let's imagine for a moment that those are just some numbers.
Server starts off by doing `S = P+sk3*Q`.
Let's perform one exchange with some values P and Q and derive a shared secret.
Now let's modify `Q` by flipping the least significant bit, and perform another exchange.
There are 2 things which could happen:
- If `sk3` has it's own LSB as `0`, then both derived shared secrets will be identical
- If `sk3` has it's own LSB a `1`, then we effectively changed `S`, and thus rest fo calculations will differ
Of course we're not dealing with numbers, but much more complex structures, but general idea stays the same.
We want to modify `P` and `Q` in such a way, that the resulting shared secret either stays the same, or changes, depending on bits of private secret.
We can detect this by sending `Hello World` payload and checking if server is able to decrypt it (so shared secrets match) or not.
For the solution we're closely following the paper `On the security of supersingular isogeny cryptosystems` by SD Galbraith, C Petit, B Shani, YB Ti:
The paper provides clear description of recovery process in case server is the one using `2^e2`, while in our case server is using `3^e3`, so we need to adapt the solution a bit for that.
We also have to use the slightly harder version, because server is performing some `Weil Pairing` checks.
First off we need to implement the missing counterpart of operations for `2^e` for our own client, based on those for `3^e` provided with server:
```python
def isogen2(sk2):
Ei = E
P = Pb
Q = Qb
S = Pa+sk2*Qa
for i in range(e2):
phi = Ei.isogeny((2^(e2-i-1))*S)
Ei = phi.codomain()
S = phi(S)
P = phi(P)
Q = phi(Q)
return (Ei,P,Q)
def isoex2(sk2, pk3):
Ei, P, Q = pk3
S = P+sk2*Q
for i in range(e2):
R = (2^(e2-i-1))*S
phi = Ei.isogeny(R)
Ei = phi.codomain()
S = phi(S)
return Ei.j_invariant()
```
### Recovery for 2^n PoC
We start off by implementing the simpler case for `2^e`:
```python
def two():
Sa = randint(0, 2^e2-1)
print('sa',bin(Sa))
Ea, phiPb, phiQb = isogen2(Sa)
Sb = randint(0, 3^e3-1)
Eb, phiPa, phiQa = isogen3(Sb)
#phiQa = phiQa+2^(e2-1)*phiPa # simple case for lSB
R = phiPa
S = phiQa
Ki = 0
for i in range(len(bin(Sa)[2:])-2):
ZE = Zmod(2^e2)
theta = 1/ZE(1+2^(e2-1-i))
theta = theta.nth_root(2)
phiPa = (int(theta)*R-int(theta*2^(e2-i-1)*Ki)*S)
phiQa = int(theta*(1+2^(e2-i-1)))*S
# simpler case wihout scaling theta, but won't pass the assertions below
#phiPa = R-(2^(e2-i-1)*Ki)*S
#phiQa = (1+2^(e2-i-1))*S
P = phiPa
Q = phiQa
assert(P*(2^e2) == Eb(0) and P*(2^(e2-1)) != Eb(0))
assert(Q*(2^e2) == Eb(0) and Q*(2^(e2-1)) != Eb(0))
assert(P.weil_pairing(Q, 2^e2) == (Pa.weil_pairing(Qa, 2^e2))^(3^e3))
JA = isoex2(Sa,(Eb, phiPa, phiQa))
JB = isoex3(Sb,(Ea, phiPb, phiQb))
if (JA == JB):
print('even')
else:
Ki+=2**i
print('odd')
print(bin(Ki))
```
The simplest option just to recover LSB is changing `phiQa` to `phiQa = phiQa+2^(e2-1)*phiPa`.
For full recovery we could use the option:
```python
phiPa = R-(2^(e2-i-1)*Ki)*S
phiQa = (1+2^(e2-i-1))*S
```
Where `Ki` is the recovered known part of the private secret, but this won't pass we `Weil Pairing` checks.
To do that we need to include scaling factor theta metioned in the paper.
### Recovery for 3^n PoC
Now that we have a working PoC for 2, we can modify it to fit our actual case:
```python
def three():
Sb = randint(0, 3^e3-1)
tmp = Sb
coeffs = []
while tmp != 0:
coeffs.append(tmp % 3)
tmp //= 3;
print(coeffs)
print("Sb",Sb)
Eb, phiPa, phiQa = isogen3(Sb)
Sa = randint(0, 2^e2-1)
Ea, phiPb, phiQb = isogen2(Sa)
R = phiPb
S = phiQb
x = 0
for i in range(5):
ZE = Zmod(3^e3)
theta = 1/ZE(1+3^(e3-1-i))
theta = theta.nth_root(2)
found_coeff = 0
for case in range(1,3):
phiPb = (int(theta)*R-int(theta*3^(e3-i-1)*(x+case*3**i))*S)
phiQb = int(theta*(1+3^(e3-i-1)))*S
# simpler case wihout scaling theta, but won't pass the assertions below
#phiPb = R-(3^(e3-i-1)*(x+case*3**i))*S
#phiQb = (1+3^(e3-i-1))*S
P = phiPb
Q = phiQb
assert(P*(3^e3) == Ea(0) and P*(3^(e3-1)) != Ea(0))
assert(Q*(3^e3) == Ea(0) and Q*(3^(e3-1)) != Ea(0))
assert(P.weil_pairing(Q, 3^e3) == (Pb.weil_pairing(Qb, 3^e3))^(2^e2))
JA = isoex2(Sa,(Eb, phiPa, phiQa))
JB = isoex3(Sb,(Ea, phiPb, phiQb))
if (JA == JB):
found_coeff = case
break;
print('coefficient', found_coeff, 'for power 3^'+str(i))
x+=found_coeff*3**i
print(x)
three()
```
Here `x` denotes the known part of private secret and `case` is the new coefficient we're testing.
The only major difference is the fact that we're working now in base3.
This means that we can recover coefficients for consecutive powers of `3`, and that we may need to perform 2 exchanges to recover one coefficient, because we need to check coefficient `1` and if it doesn't work we need to check `2` and only then we can assume that original coefficient was `0`.
### Solver
Now that we have a working PoC for 3^n recover, we can finally implement full client to grab the flag.
Note that according to the paper, this method will not work for the highest 2 coefficients, so we need to brute-force those at the very end.
Core of the solver is:
```python
def oracle(Ei, P, Q, ciphertext, s):
pk2 = Ei,P,Q
send_key(s,pk2)
receive_until(s, ":")
send(s, ciphertext.encode("hex"))
result = receive_until(s, [".","!"])
return "Good" in result
def recover_coefficients(Ea,R,S,oracle, ciphertext, s):
x = 0
ZE = Zmod(3^e3)
for i in range(e3-2):
print("Recovering 3^%d coefficient" % i)
theta = 1/ZE(1+3^(e3-1-i))
theta = theta.nth_root(2)
found_coeff = 0
for case in range(1,3):
phiPb = (int(theta)*R-int(theta*3^(e3-i-1)*(x+case*3**i))*S)
phiQb = int(theta*(1+3^(e3-i-1)))*S
if oracle(Ea, phiPb, phiQb, ciphertext, s):
found_coeff = case
break;
print('coefficient', found_coeff, 'for power 3^'+str(i))
x+=found_coeff*3**i
return x
```
This allows us to recover all but last 2 coefficients, then we can do:
```python
limit = e3
for a in range(3):
for b in range(3):
secret = res+a*3**(limit-1)+b*3**(limit-2)
super_secret_hash = hashlib.sha256(str(secret).encode('ascii')).digest()[:16]
ciphertext = cipher.encrypt(super_secret_hash)
send_key(s, pk2)
send(s,ciphertext.encode("hex"))
response = s.recv(9999)
print(response)
```
And one of the responses where we guessed `a` and `b` correctly will contain the flag.
After a while we manage to recover: `PCTF{if_you_wish_for_postquantum_crypto_ask_a_supersingular_isogenie}`
Complete solver [here](https://raw.githubusercontent.com/TFNS/writeups/master/2020-04-17-PlaidCTF/sidhe/client.sage)
