Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Google CTF 2017 Quals - Crypto Backdoor
def I(s):
val = 0
for i in range(len(s)):
digit = ord(s[len(s) - i - 1])
val <<= 8
val |= digit
return val
def Sn(i, length):
s = ''
while i != 0:
digit = i & 0xff
i >>= 8;
s += chr(digit)
return s
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, p):
a %= p
g, x, y = egcd(a, p)
if g != 1:
raise Exception('No inverse exists for %d mod %d' % (a, p))
else:
return x % p
def add(a, b, p):
if a == -1:
return b
if b == -1:
return a
x1, y1 = a
x2, y2 = b
x3 = ((x1*x2 - x1*y2 - x2*y1 + 2*y1*y2)*modinv(x1 + x2 - y1 - y2 - 1, p)) % p
y3 = ((y1*y2)*modinv(x1 + x2 - y1 - y2 - 1, p)) % p
return (x3, y3)
def double(a, p):
return add(a, a, p)
def mul(m, g, p):
r = -1
while m != 0:
if m & 1:
r = add(r, g, p)
m >>= 1
g = double(g, p)
return r
def encrypt(message, key):
return message ^ key
# Modulus
p = 606341371901192354470259703076328716992246317693812238045286463
# g is the generator point.
g = (160057538006753370699321703048317480466874572114764155861735009, 255466303302648575056527135374882065819706963269525464635673824)
# Alice's public key A:
A = (460868776123995205521652669050817772789692922946697572502806062, 263320455545743566732526866838203345604600592515673506653173727)
# Bob's public key B:
B = (270400597838364567126384881699673470955074338456296574231734133, 526337866156590745463188427547342121612334530789375115287956485)
if __name__ == "__main__":
from secret_data import aliceSecret, bobSecret, flag
assert A == mul(aliceSecret, g, p)
assert B == mul(bobSecret, g, p)
aliceMS = mul(aliceSecret, B, p)
bobMS = mul(bobSecret, A, p)
assert aliceMS == bobMS
masterSecret = aliceMS[0]*aliceMS[1]
length = len(flag)
encrypted_message = encrypt(I(flag), masterSecret)
print "length = %d, encrypted_message = %d" % (length, encrypted_message)
# length = 31, encrypted_message = 137737300119926924583874978524079282469973134128061924568175107915062758827931077214500356470551826348226759580545095568667325
'''
The arithmetic is probably some masked Elliptic Curve arithmetic.
p is factored into many small primes so Pohlig-Hellman method should work (with Baby-Step-Giant-Step inside).
Probably it is easy to unmask arithmetic to get the usual equations. Then Sage can do discrete_log nicely automatically.
Otherwise, we can reuse the arithmetic functions and code PH and BSGS ourselves. This is done in this script.
One tricky point is determining order of g modulo prime factors of p:
For elliptic curves the order is close to P (the error is about sqrt(P)), so we can check it exhaustively.
Interestingly, all orders are (p-1). Maybe the arithmetic is actually masked multiplication in GF(P), no elliptic curves?
'''
from sage.all import *
from crypto_backdoor import add, mul
# Modulus
p = 606341371901192354470259703076328716992246317693812238045286463
# g is the generator point.
g = (160057538006753370699321703048317480466874572114764155861735009, 255466303302648575056527135374882065819706963269525464635673824)
# Alice's public key A:
A = (460868776123995205521652669050817772789692922946697572502806062, 263320455545743566732526866838203345604600592515673506653173727)
# Bob's public key B:
B = (270400597838364567126384881699673470955074338456296574231734133, 526337866156590745463188427547342121612334530789375115287956485)
def discrete_log(g, v, mod, order):
lim = int(sqrt(mod)) + 10
table = {}
g = g[0] % mod, g[1] % mod
v0 = v = v[0] % mod, v[1] % mod
cur = g
cure = 1
table[-1] = 0
for x in xrange(lim):
table[cur] = cure
cure += 1
cur = add(cur, g, mod)
step = mul(order-1, cur, mod)
stepe = cure
for e2 in xrange(lim):
if v in table:
e1 = table[v]
ans = (e1 + e2 * stepe) % order
assert mul(ans, g, mod) == v0
return ans
v = add(step, v, mod)
assert 0
def calc_order(g, mod):
g = g[0] % mod, g[1] % mod
lim = int(sqrt(mod)) + 10
cur = mul(mod - lim, g, mod)
cure = mod - lim
for test in xrange(2*lim):
try:
cure += 1
cur = add(cur, g, mod)
except Exception as err:
assert mul(cure+1, g, mod) == g
return cure
assert 0
def n2s(n):
s = hex(n)[2:].rstrip("L")
if len(s) % 2 != 0:
s = "0" + s
return s.decode("hex")
rems = []
mods = []
for (mod, mod_e) in factor(p):
assert mod_e == 1
order = calc_order(g, mod)
assert mul(order+1, g, mod) == (g[0] % mod, g[1] % mod)
print "order", factor(order)
cofactor = 1
for pp, e in factor(order):
for de in reversed(xrange(1, e + 1)):
if mul(order//pp**de + 1, g, mod) == (g[0] % mod, g[1] % mod):
order //= pp**de
cofactor *= pp**de
break
print "reduced", factor(order), "cofactor", cofactor
x = discrete_log(g, A, mod, order)
print "X", x, "ORD", order, "MOD", mod
rems.append([x + i * order for i in xrange(cofactor)])
mods.append(order)
print
from itertools import product
for rems in product(*rems):
rems = list(rems)
try:
secret = crt(rems, mods)
print "SECRET", secret
ms = mul(secret, B, p)
ms = ms[0] * ms[1]
msg = 137737300119926924583874978524079282469973134128061924568175107915062758827931077214500356470551826348226759580545095568667325 ^ ms
print `n2s(msg)[::-1]`
except ValueError:
pass
'''
SECRET 6621005115841589341021728146593578127178145692816888878
'CTF{Anyone-can-make-bad-crypto}'
'''
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment