HITCON 2018 - Lost Modulus (Crypto)
#-*- coding:utf-8 -*- | |
from sock import Sock | |
from libnum import invmod, n2s, s2n | |
f = Sock("13.112.92.9 21701") | |
f.read_until("flag!") | |
f.read_line() | |
ENC = int(f.read_line().strip(), 16) | |
print "ENC = 0x%X" % ENC | |
NQ = [0, 0] | |
def oracle_enc(x): | |
NQ[0] += 1 | |
print "oracle enc" | |
f.send_line("A") | |
f.send_line(n2s(x).encode("hex")) | |
f.read_until("input:") | |
return int(f.read_line().strip(), 16) | |
def oracle_dec(y): | |
NQ[1] += 1 | |
print "oracle dec" | |
f.send_line("B") | |
f.send_line(n2s(y).encode("hex")) | |
f.read_until("input:") | |
return int(f.read_line().strip(), 16) | |
# 0. find n % 2**8 | |
# for more stable solution allow n < 2**1023 | |
t = 2**1020 | |
while True: | |
res = oracle_dec(oracle_enc(t)) | |
if res != 0: | |
break | |
t *= 2 | |
n8 = 2**8 - res | |
print hex(res), "->", hex(n8) | |
assert n8 & 1 | |
# assert n8 == n % 2**8 | |
# 1. recover full n | |
# by finding k = floor(2**2048 / n) byte-by-byte | |
# let t = n * k + r, r < n | |
# then n = floor(t / k) - floor(r / k) | |
# if k > r (i.e. is large enough) then n = floor(t / k) | |
t //= 2 # t < n | |
k = 0 | |
itr = 0 | |
while t < 2**2048: | |
itr += 1 | |
print itr | |
t = t * 2**8 | |
k = k * 2**8 | |
res = oracle_dec(oracle_enc(t)) | |
klow = (t - k * n8 - res) * invmod(n8, 2**8) % 2**8 | |
k += klow | |
# assert k = t / n | |
n = t / k # floor | |
n2 = n**2 | |
print "n =", n | |
# 2. decrypt flag | |
# by using homomorphic operations | |
def ctadd(c1, c2): | |
return (c1 * c2) % n2 | |
def ctmulconst(ct, k): | |
return pow(ct, k, n2) | |
E1 = oracle_enc(1) # we don't know g... | |
pt = 0 | |
mod = 1 | |
for i in xrange(128): | |
ct = ENC | |
print i | |
ct = ctadd(ct, pow(E1, (-pt) % n, n**2)) | |
ct = ctmulconst(ct, invmod(mod, n)) | |
low = oracle_dec(ct) | |
pt += mod * low | |
mod *= 2**8 | |
print `n2s(pt)` | |
# hitcon{binary__search__and_least_significant_BYTE_oracle_in_paillier!!} | |
print "Queries:", NQ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment