HITCON 2018 - Lost Modulus (Crypto)

lostmodulus.py

#-*- 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