Tags: dh
Rating: 4.0
The first crypto challenge of this year was rather simple, a weird Diffie-Hellman type thing where not only the private key is private, but also the generator, which is randomly generated from a password every three runs.
def enc(a):
f = {str: str.encode, int: int.__str__}.get(type(a))
return enc(f(a)) if f else a
def H(*args):
data = b'\0'.join(map(enc, args))
return SHA256.new(data).digest()
def F(h, x):
return pow(h, x, q)
password = random.randrange(10**6)
def go():
g = int(H(password).hex(), 16)
privA = 40*random.randrange(2**999)
pubA = F(g, privA)
print(f'{pubA = :#x}')
pubB = int(input(),0)
if not 1 < pubB < q:
exit('nope')
shared = F(pubB, privA)
verA = F(g, shared**3)
print(f'{verA = :#x}')
verB = int(input(),0)
if verB == F(g, shared**5):
key = H(password, shared)
flag = open('flag.txt').read().strip()
aes = AES.new(key, AES.MODE_CTR, nonce=b'')
print(f'flag:', aes.encrypt(flag.encode()).hex())
else:
print(f'nope! {shared:#x}')
signal.alarm(2021)
go()
go()
go()
I think we have solved this challenge quite differently than [other](https://github.com/cscosu/ctf-writeups/tree/master/2021/hxp_ctf/gipfel) [teams](https://ctftime.org/writeup/31869). We realized that after one run of the protocol in which the $verB$ check fails the server shares the used $shared$ value which together with $verA$ allows for constructing an offline oracle for testing guesses of the generator $g$ and thus also the `password`. The oracle is based on the equation:
\\[ verA = g^{shared^3} \mod q\\]
which we can check for all password guesses once we have $verA$ and $shared$ from one `go()` run.
#!/usr/bin/env python3
# Requires pwntools, tqdm, pycryptodome
from pwn import *
from tqdm import tqdm
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from binascii import unhexlify
q = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5
def enc(a):
f = {str: str.encode, int: int.__str__}.get(type(a))
return enc(f(a)) if f else a
def H(*args):
data = b'\0'.join(map(enc, args))
return SHA256.new(data).digest()
def F(h, x):
return pow(h, x, q)
def solve_pow(server):
pow_regex = re.compile(r"\"([0-9a-f]+)\"")
bits_regex = re.compile("([0-9]+) zero")
pow_line = server.recvline()
pow_challenge = pow_regex.search(pow_line.decode()).groups()[0]
pow_bits = bits_regex.search(pow_line.decode()).groups()[0]
pow_proc = subprocess.run(["./pow-solver", pow_bits, pow_challenge], capture_output=True)
pow_res = pow_proc.stdout.strip()
server.sendline(pow_res)
def decrypt(password, shared, data):
key = H(password, shared)
aes = AES.new(key, AES.MODE_CTR, nonce=b'')
return aes.decrypt(unhexlify(data))
if __name__ == "__main__":
log.info("Precomputing gs")
g_options = {}
for pw in tqdm(range(10**6)):
h = int(H(pw).hex(), 16)
g_options[pw] = h
server = remote("65.108.176.66", 1088)
log.info("Solving PoW")
solve_pow(server)
log.success("Solved PoW")
pubA = int(server.recvline().strip().decode().split(" = ")[1], 16)
server.sendline(b"2")
verA = int(server.recvline().strip().decode().split(" = ")[1], 16)
server.sendline(b"2") # This will fail and we will get shared.
shared = int(server.recvline().strip().decode().split("! ")[1], 16)
exp = shared**3 % (q-1)
for password, g in tqdm(g_options.items()):
if verA == F(g, exp):
break
log.success(f"We got the g: {g}")
log.success(f"We got the password: {password}")
log.info("--- Second run ---")
pubA = int(server.recvline().strip().decode().split(" = ")[1], 16)
privB = 10
pubB = F(g, privB)
server.sendline(str(pubB).encode())
verA = int(server.recvline().strip().decode().split(" = ")[1], 16)
shared = F(pubA, privB)
assert verA == F(g, shared**3)
verB = F(g, shared**5)
server.sendline(str(verB).encode())
encrypted_flag = server.recvline().strip().decode().split(": ")[1]
log.success(f"The flag is {decrypt(password, shared, encrypted_flag)}")
server.close()
The code above gets the flag in the time limit, as it incorporates a simple speedup to reduce the $shared^3$ exponent modulo $q-1$.
