https://app.hackthebox.com/challenges/521

Description

In the midst of escalating conflict between the nations of Luson and Oumara, a recent invasion by Oumara has sparked suspicions about the existence of an internal communication channel. Fearing further strikes, the Luson government takes proactive measures to counter Oumara's attacks. You were assigned the task of investigating their secure channel and determining whether you can obtain any sensitive information. Eventually, you gain access to the channel and even manage to send encrypted messages of your own. Can you reveal Oumara's secret plans to safeguard your nation from potential future invasions?

Exploitation

#!/usr/bin/env python3
from hashlib import sha256
from math import gcd
from pwn import process, remote, sys, context
from sage.all import PolynomialRing, primes, Zmod
from Crypto.Util.number import bytes_to_long, long_to_bytes

context.log_level = 'error'

def get_process():
    if len(sys.argv) > 1:
        ip, port = sys.argv[1].split(':')
        remote(ip, int(port))
    else:
        print(f"Usage: {sys.argv[0]} <ip:port>.")
        sys.exit(1)

def exploit_channel():
    e = 65537
    guessed_greet = bytes_to_long(b'Hey!')
    guessed_greet_e = pow(guessed_greet, e)
    guessed_ans = bytes_to_long(b'Bye!')
    guessed_ans_e = pow(guessed_ans, e)
    n = 0
    while True:
        io = get_process()
        try:
            io.recvuntil(b'We say : ')
            enc_greet = int(io.recvline().decode(), 16)
            enc_anss = set()
            while len(enc_anss) < 3:
                io.sendlineafter(b'> ', b'S')
                io.sendlineafter(b'You say : ', hex(guessed_greet_e).encode())
                io.recvuntil(b'Nice! We say : ')
                enc_anss.add(int(io.recvline().decode(), 16))
            n = max(gcd(guessed_greet_e - enc_greet, guessed_ans_e - enc_ans) 
                    for enc_ans in enc_anss)
            for p in primes(100):
                if n % p == 0:
                    n //= p
            if n.bit_length() == 2048 and n & 1:
                break
            io.close()
        except Exception:
            io.close()
            continue
    io.sendlineafter(b'> ', b'F')
    io.sendlineafter(
        b'Before giving you the token, you must prove me that you know the public key : ',
        sha256(str(n).encode()).hexdigest().encode(),
    )
    io.recvuntil(b'Here is your token : ')
    token = int(io.recvline().decode())
    d = 1024 - 643
    q_H = (token >> d) << d
    x = PolynomialRing(Zmod(n), names='x').gens()[0]
    q_L = int((x + q_H).small_roots(X=2 ** d, beta=0.499)[0])
    q = q_H + q_L
    assert n % q == 0 and 1 < q < n
    p = n // q
    phi_n = (p - 1) * (q - 1)
    exp = pow(0xdeadbeef, n, phi_n)
    key = long_to_bytes(pow(0x1337, exp, n))[:16]
    io.sendlineafter(b'> ', b'R')
    io.sendlineafter(b'Enter decryption key : ', key.hex().encode())
    return io.recvall().decode()

def main():
    try:
        print(exploit_channel())
    except Exception as e:
        print(f"Exploit failed: {e}")

if __name__ == '__main__':
    main()

Summary

Interception: model the leak as a small lattice problem, recover the secret, and verify the flag.