Flagyard Crypto Challange.
Normal El-Gamal
Hard
By Flagyard
Crypto
This is a totally normal ElGamal implementation, nothing can go wrong :D.
Pyhton Exploit Code.
#!/usr/bin/env python3
import socket, re, math, sys
from Crypto.Util.number import long_to_bytes
HOST, PORT = ‘tcp.flagyard.com’, 20707
class Solver:
def __init__(self):
self.sock = socket.create_connection((HOST, PORT), timeout=30)
self.buf = b’’
def read_until(self, tok):
while tok not in self.buf:
self.buf += self.sock.recv(8192)
i = self.buf.index(tok) + len(tok)
out, self.buf = self.buf[:i], self.buf[i:]
return out
def send(self, data):
self.sock.sendall(data.encode() + b’\n’)
# — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
# 1. Parse the target ciphertext
# — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
def get_target(self):
banner = self.read_until(b’>>’)
m = re.search(rb’ct=\(([^)]+)\)’, banner)
return tuple(map(int, m.group(1).split(b’,’)))
# — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
# 2. Oracle wrappers
# — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
def enc(self, m):
self.send(‘1’)
self.read_until(b’plaintext>>’)
self.send(str(m))
out = self.read_until(b’>>’)
tup = re.search(rb’\((\d+, \d+, \d+, \d+)\)’, out)
return tuple(map(int, tup.group(1).split(b’, ‘)))
def dec(self, c):
self.send(‘2’)
self.read_until(b’ciphertext>>’)
self.send(‘,’.join(map(str, c)))
out = self.read_until(b’>>’)
# output looks like: m= 123 456
m = re.search(rb’m=\s+(\d+)\s+(\d+)’, out)
if not m:
raise ValueError(f’unexpected dec output: {out!r}’)
return int(m.group(1)), int(m.group(2))
# — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
# 3. Recover the prime p from valid curve points
# — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
def recover_curve(self, points):
# points = list of (x, y) that lie on y² = x³ + a x + b (mod p)
D = [y * y — x * x * x for x, y in points]
vals = []
n = len(points)
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
for l in range(k + 1, n):
# (Di-Dj)*(xk-xl) — (Dk-Dl)*(xi-xj) ≡ 0 (mod p)
z = (D[i] — D[j]) * (points[k][0] — points[l][0]) \
— (D[k] — D[l]) * (points[i][0] — points[j][0])
vals.append(abs(z))
Get Muhammad Faizan’s stories in your inbox
Join Medium for free to get updates from this writer.
g = 0
for v in vals:
g = math.gcd(g, v)
if g == 1:
break
# strip tiny factors to get the actual prime
for f in range(2, 10000):
while g % f == 0 and g > f:
g //= f
return g
# — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
# 4. EC arithmetic (short Weierstrass)
# — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
@staticmethod
def ec_add(P, Q, p, a):
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 == y2:
if y1 == 0:
return None
m = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
else:
m = (y2 — y1) * pow((x2 — x1) % p, -1, p) % p
x3 = (m * m — x1 — x2) % p
y3 = (m * (x1 — x3) — y1) % p
return x3, y3
@staticmethod
def ec_neg(P, p):
return P[0], (-P[1]) % p
# — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
# 5. Main solve
# — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
def solve(self):
ct = self.get_target()
C1, C2 = (ct[0], ct[1]), (ct[2], ct[3])
print(‘[*] target ct:’, ct)
# collect valid curve points:
# — the two public points C1, C2
# — plaintext points of encryptions of small messages
points = [C1, C2]
plain_pts = []
encs = []
for m in range(8):
e = self.enc(m)
p = self.dec(e)
points.append((e[0], e[1]))
points.append((e[2], e[3]))
plain_pts.append(p)
encs.append(e)
print(f’[+] enc({m}) -> plaintext point {p[0] % 10**6}…’)
p = self.recover_curve(points)
print(‘[*] recovered p =’, p)
# recover a, b (mod p)
D = [y * y — x * x * x for x, y in points]
a = (D[0] — D[1]) * pow((points[0][0] — points[1][0]) % p, -1, p) % p
b = (D[0] — a * points[0][0]) % p
print(‘[*] a =’, a)
print(‘[*] b =’, b)
# sanity check
for x, y in points:
assert (y * y) % p == (x * x * x + a * x + b) % p
# — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
# Homomorphic trick:
# enc(0) -> (R, S) with plaintext P0
# dec( C1+R , C2+S ) -> M + P0
# subtract P0 to get M
# — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
e0 = self.enc(0)
R, S = (e0[0], e0[1]), (e0[2], e0[3])
P0 = self.dec(e0)
print(‘[*] P0 (plaintext of 0) =’, P0)
C1p = self.ec_add(C1, R, p, a)
C2p = self.ec_add(C2, S, p, a)
# guard against the “not that easy” checks
if C2p[0] == ct[2] or C2p[1] == ct[3]:
# retry with a different known plaintext
e0 = self.enc(1)
R, S = (e0[0], e0[1]), (e0[2], e0[3])
P0 = self.dec(e0)
C1p = self.ec_add(C1, R, p, a)
C2p = self.ec_add(C2, S, p, a)
P = self.dec((C1p[0], C1p[1], C2p[0], C2p[1]))
print(‘[*] decrypted P = M + P0 =’, P)
M = self.ec_add(P, self.ec_neg(P0, p), p, a)
print(‘[*] M =’, M)
# _point_to_int just does x >> 8
flag_int = M[0] >> 8
flag = long_to_bytes(flag_int)
print(‘\n[+] FLAG:’, flag.decode())
if __name__ == ‘__main__’:
Solver().solve()
