# EDDH - zer0pts CTF 2022
###### tags: `zer0pts CTF 2022`

Writeups: https://hackmd.io/@ptr-yudai/rJgjygUM9

## overview

The challenge implements Diffie-Hellman key exchange protocol on the Twisted Edwards Curve. The challenge server calculates $sG$ with secret $s$, which we want to know, and sends us $sG$. Normally, we calculate $tG$ with our secret $t$ and send $tG$ to the server. Then both side shares their own secret $stG$.

## solution

The mathematics on the Twisted Edwards Curve is originally implemented. Additionaly, there isn't the check that given $tG$ is on the curve. So it is the chance of degenerate attack.

Let's focus to the addition algorithm.

$$
x_3 = \frac{x_1y_2 + y_1x_2}{1 + dx_1x_2y_1y_2} \pmod p\\
y_3 = \frac{y_1y_2 - ax_1x_2}{1 - dx_1x_2y_1y_2} \pmod p
$$

The calculation on the curve can be reduced to linear algebra in specific case. If we calculate $(0, y_1) + (0, y_2)$, the result comes to $(0, y_1y_2)$.

In this challenge, if we send a $(0, y)$ as the $tG$, the server calculates $s * tG = (0, y^s \mod p)$

Because $p-1$ consists of many small factors, discrete logarithm of $y^s \mod p$ can be calculated by Pohligh-Hellman algorithm.

## exploit

from ptrlib import Socket, Process
from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
from Crypto.Cipher import AES
from hashlib import sha256
import ast
import os

n = 256
p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 1
q = 64141017538026690847507665744072764126693080268699847241685146737444135961328
c = 4
gx = 36618472676058339844598776789780822613436028043068802628412384818014817277300
gy = 9970247780441607122227596517855249476220082109552017755637818559816971965596

def xor(xs, ys):
    return bytes(x^^y for x, y in zip(xs, ys))

def pad(b, l):
    return b + b"\0" + b"\xff" * (l - (len(b) + 1))

def unpad(b):
    l = -1
    while b[l] != 0:
        l -= 1
    return b[:l]

def add(P, Q):
    (x1, y1) = P
    (x2, y2) = Q

    x3 = (x1*y2 + y1*x2) * inverse(1 + d*x1*x2*y1*y2, p) % p
    y3 = (y1*y2 - a*x1*x2) * inverse(1 - d*x1*x2*y1*y2, p) % p
    return (x3, y3)

def mul(x, P):
    Q = (0, 1)
    x = x % q
    while x > 0:
        if x % 2 == 1:
            Q = add(Q, P)
        P = add(P, P)
        x = x >> 1
    return Q

def to_bytes(P):
    x, y = P
    return int(x).to_bytes(n // 8, "big") + int(y).to_bytes(n // 8, "big")


sock = Socket("localhost", 10929)

sg = ast.literal_eval(sock.recvlineafter("sG = ").decode())
sock.sendlineafter("tG = ", "{}".format((0, 2)))

msg = b"\0"
sock.sendline(msg.hex())

res = bytes.fromhex(sock.recvline().decode())
y = bytes_to_long(xor(res[-n//8:], b"\xff" * 256))
s = discrete_log(GF(p)(y), GF(p)(2))
assert pow(2, s, p) == y
print("s = {}".format(s))

share = to_bytes(mul(int(s), (0, 2)))
sock.sendline(xor(pad(b"flag", 2*n//8), share).hex())

r = bytes.fromhex(sock.recvline().decode())
msg = unpad(xor(r, share))
aes = AES.new(key=sha256(long_to_bytes(s)).digest(), mode=AES.MODE_ECB)
print(aes.decrypt(msg))