Skip to content

Instantly share code, notes, and snippets.

@hellman

hellman/lostmodulus.py

Last active Oct 22, 2018
Embed
What would you like to do?
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
You can’t perform that action at this time.