<- CRYPTO

Interception

12 minutes to read

We are given the Python source code of the server. This is server.py:

#!/usr/bin/env python3

import signal
import random, os
from hashlib import sha256
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
from pool import GREET, ANS
from secret import RESTRICTED

class GRAS:
    def __init__(self, m, p, q):
        self.m = m
        self.a = 0xdeadbeef
        self.p = p
        self.q = q

    def generate_key(self):
        ct = 0x1337
        # this loop runs in milliseconds in our super computer
        for _ in range(self.m):
            ct = pow(ct, self.a, self.m)
        return long_to_bytes(ct)[:16]

class OumaraSystem:
    def __init__(self, bits):
        self.BITS = bits
        self.LIMIT = 2
        self.p = getPrime(self.BITS//2)
        self.q = getPrime(self.BITS//2)
        self.N = self.p * self.q
        self.e = 0x10001
        self.d = pow(self.e, -1, (self.p-1)*(self.q-1))
        self.prng = GRAS(self.N, self.p, self.q)

    def encrypt(self, m):
        m = bytes_to_long(m.encode())
        assert 0 < m < self.N
        enc_msg = long_to_bytes(pow(m, self.e, self.N))
        return enc_msg

    def encrypt_plans(self):
        self.symmetric_key = self.prng.generate_key()
        cipher = AES.new(self.symmetric_key, AES.MODE_ECB)
        enc_plans = [cipher.encrypt(pad(r.encode(), 16)) for r in RESTRICTED]
        return enc_plans

    def send_encrypted_message(self, c):
        if c > 1:
            m = pow(c, self.d, self.N)
            try:
                msg = long_to_bytes(m).decode()
                return True
            except:
                pass
        return False

    def reveal_internal_plans(self, encrypted_plans, key):
        cipher = AES.new(key, AES.MODE_ECB)
        plans = [unpad(cipher.decrypt(ep), 16).decode() for ep in encrypted_plans]
        return plans
        
    def hash_verified(self, h):
        return h == sha256(str(self.N).encode()).digest()
    
    def generate_token(self):
        d = self.q.bit_length() - 643
        return ((self.q >> d) << d) | random.getrandbits(d)

def show_banner():
    print('''
   ___                                    ____                              ____ _                            _ 
  / _ \ _   _ _ __ ___   __ _ _ __ __ _  / ___|  ___  ___ _   _ _ __ ___   / ___| |__   __ _ _ __  _ __   ___| |
 | | | | | | | '_ ` _ \ / _` | '__/ _` | \___ \ / _ \/ __| | | | '__/ _ \ | |   | '_ \ / _` | '_ \| '_ \ / _ \ |
 | |_| | |_| | | | | | | (_| | | | (_| |  ___) |  __/ (__| |_| | | |  __/ | |___| | | | (_| | | | | | | |  __/ |
  \___/ \__,_|_| |_| |_|\__,_|_|  \__,_| |____/ \___|\___|\__,_|_|  \___|  \____|_| |_|\__,_|_| |_|_| |_|\___|_|
''')

def menu():
    print('=======================================')
    print('||                                   ||')
    print('||   [S]end your encrypted message   ||')
    print('||   [R]eveal internal plans         ||')
    print('||   [F]orgot decryption key         ||')
    print('||                                   ||')
    print('=======================================')
    return input('> ').upper()[0]

def print_plans(plans):
    print('==================== CLASSIFIED CONTENT! DO NOT SHARE! ====================')
    for i, p in enumerate(plans):
        print(f'Plan {i+1} : {p}')
    print('===========================================================================')


def main():
    crypto = PopperSystem(2048)
    encrypted_plans = crypto.encrypt_plans()

    show_banner()

    print('This channel aims at secure communication via asymmetric encryption.')
    print(f'We say : {crypto.encrypt(random.choice(GREET)).hex()}')

    while True:
        ch = menu()
        if ch == 'S':
            enc_msg = int(input('You say : '), 16)
            verified = crypto.send_encrypted_message(enc_msg)
            if verified:
                print(f'Nice! We say : {crypto.encrypt(random.choice(ANS)).hex()}')
            else:
                print(f'Nice! We say : {os.urandom(256).hex()}')

        elif ch == 'R':
            print('Our plans are encrypted via symmetric encryption and protected with our unique super computer that will take us to the Red Planet!')  
            key = bytes.fromhex(input('Enter decryption key : '))
            plans = crypto.reveal_internal_plans(encrypted_plans, key)
            print_plans(plans)
            exit(0)
        
        elif ch == 'F':
            h = bytes.fromhex(input('Before giving you the token, you must prove me that you know the public key : '))
            if crypto.hash_verified(h):
                token = crypto.generate_token()
                print(f'Here is your token : {token}')
                print('Make sure you do not forget it next time!')
            else:
                print('Get out!')

        else:
            print('Hey, this is suspicious! Terminating the channel...')
            exit(0)

if __name__ == '__main__':
    signal.alarm(900)
    main()

And this is pool.py:

GREET = [
    'Is there an emergency?',
    'How you doing?',
    'Hey!'
]

ANS = [
    'Great news, but use this channel responsibly.',  
    'I will inform the governor.',
    'Bye!'
]

We are given three options:

$ nc 94.237.62.195 47360

   ___                                    ____                              ____ _                            _
  / _ \ _   _ _ __ ___   __ _ _ __ __ _  / ___|  ___  ___ _   _ _ __ ___   / ___| |__   __ _ _ __  _ __   ___| |
 | | | | | | | '_ ` _ \ / _` | '__/ _` | \___ \ / _ \/ __| | | | '__/ _ \ | |   | '_ \ / _` | '_ \| '_ \ / _ \ |
 | |_| | |_| | | | | | | (_| | | | (_| |  ___) |  __/ (__| |_| | | |  __/ | |___| | | | (_| | | | | | | |  __/ |
  \___/ \__,_|_| |_| |_|\__,_|_|  \__,_| |____/ \___|\___|\__,_|_|  \___|  \____|_| |_|\__,_|_| |_|_| |_|\___|_|

This channel aims at secure communication via asymmetric encryption.
We say : 5753adf1fb98f6dadd29631df780b6af712f99681b234da1598251a155d7549ecd8661355a2449fe341258b391225a1dc10f85e775311b5b56f07e678eea89ebce581e1badc7472c09e8639d0b406f314aaf603bc7674a17725546d1dfaeec93ace74b69c876e0d524709bd7d751939a1f6caaebd0ac5b410e4c4f409d71ffb9cf5a9ccd78eefed3174bdf5a5f715c1beb5a4ab578e20ca25e389514db9905905b298a8f84f1b5157b94241c0c22c196effe6563f3b20af1be6afde29eedceddea550d552a2fbb7fe105a0bc3d2254049d7ba204fe9db5f595b38bc73236c8ae832888f7ded43d05e179715839326c6ded91e2d62dacb2304bf544a2b364d4b0  
=======================================
||                                   ||
||   [S]end your encrypted message   ||
||   [R]eveal internal plans         ||
||   [F]orgot decryption key         ||
||                                   ||
=======================================
>

To use option F we need to have the public key, and to use option R we need to have a decryption key, so, we need to use option S first.

Option S

In this option, we will be given a random ANS encrypted message or just 256 random bytes depending on the message we input:

        if ch == 'S':
            enc_msg = int(input('You say : '), 16)
            verified = crypto.send_encrypted_message(enc_msg)
            if verified:
                print(f'Nice! We say : {crypto.encrypt(random.choice(ANS)).hex()}')  
            else:
                print(f'Nice! We say : {os.urandom(256).hex()}')

The crypto object is an instance of class OumaraSystem (although the code shows PopperSystem). We see that the encrypt method uses RSA to encrypt a given message m. All RSA parameters are correct:

class OumaraSystem:
    def __init__(self, bits):
        self.BITS = bits
        self.LIMIT = 2
        self.p = getPrime(self.BITS//2)
        self.q = getPrime(self.BITS//2)
        self.N = self.p * self.q
        self.e = 0x10001
        self.d = pow(self.e, -1, (self.p-1)*(self.q-1))  
        self.prng = GRAS(self.N, self.p, self.q)

    def encrypt(self, m):
        m = bytes_to_long(m.encode())
        assert 0 < m < self.N
        enc_msg = long_to_bytes(pow(m, self.e, self.N))
        return enc_msg

Notice that we are not given any RSA parameters. We only have a ciphertext from a random GREET message:

    print('This channel aims at secure communication via asymmetric encryption.')  
    print(f'We say : {crypto.encrypt(random.choice(GREET)).hex()}')

For option S to work we need to send an message encrypted with their RSA public key. So, we can simply send back the ciphertext we already have. With this, the server will send us a random ANS message encrypted and not just 256 random bytes.

As a result, for some indices $0 \leqslant i, j \leqslant 2$ we have this:

$$ \begin{cases} c_1 = (\mathrm{GREET}[i]) ^ e \mod{n} \\ c_2 = (\mathrm{ANS}[j]) ^ e \mod{n} \end{cases} $$

GCD

The idea is to pre-compute $(\mathrm{GREET}[2]) ^ e$ and $(\mathrm{ANS}[2]) ^ e$, which are the smallest messages, and connect to the server until the server encrypts $\mathrm{GREET}[2]$.

The aim is to find $n$, which can be done using the Greatest Common Divisor (GCD), because:

$$ \begin{cases} (\mathrm{GREET}[2]) ^ e - c_1 \equiv 0 \pmod{n} \\ (\mathrm{ANS}[2]) ^ e - c_2 \equiv 0 \pmod{n} \end{cases} $$

So,

$$ n = \gcd{\Big((\mathrm{GREET}[2]) ^ e - c_1, \quad (\mathrm{ANS}[2]) ^ e - c_2\Big)} $$

Actually, it is possible that we don’t get exactly $n$ but some small number times $n$. We can overcome this by trying to divide the GCD result with some few prime numbers.

As a result, we can guess that the server is sending us the encrypted $\mathrm{GREET}[2]$ and we just need to use option S several times until we have all the three possible encrypted $\mathrm{ANS}[j]$. Then, we compute the GCD with all combinations using the pre-computed $\mathrm{ANS}[2]) ^ e$ until we find $n$, which is an odd 2048-bit number. If we don’t find $n$, then we repeat the process because the server has not sent the encrypted $\mathrm{GREET}[2]$:

e = 65537

guessed_greet = bytes_to_long(b'Hey!')
guessed_greet_e = guessed_greet ** e

guessed_ans = bytes_to_long(b'Bye!')
guessed_ans_e = guessed_ans ** e

while True:
    io = get_process()
    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(enc_greet).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:
        io.success(f'Found {n = }')
        break

    io.close()

Option F

Once we have the RSA public key $(n, e)$, we can use option F, because it asks for the SHA256 hash of $n$ as a decimal string:

            if crypto.hash_verified(h):
                token = crypto.generate_token()
                print(f'Here is your token : {token}')
                print('Make sure you do not forget it next time!')  
            else:
                print('Get out!')

The hash_verified method just checks the hash:

    def hash_verified(self, h):
        return h == sha256(str(self.N).encode()).digest()

We already have $n$, so there is not issue with the verification process. After that, we are given a token, which is the output of generate_token:

    def generate_token(self):
        d = self.q.bit_length() - 643
        return ((self.q >> d) << d) | random.getrandbits(d)

This token contains some information about the prime number $q$ (which is part of the RSA private key). Actually, we are given $643$ bits of information (they hide $381$ bits).

Coppersmith method

To recover $q$ we can use Coppersmith method. For this, we create a polynomial $f(x) = x + q_H \pmod{p}$. Let $q_L = q - q_H$, then $f(q_L) = 0$, so $q_L$ is a root. Moreover, the root is small because it must be a 381-bit number. For more information on the implementation, you can take a look at Bank-er-smith.

To implement the attack, SageMath has a method called small_roots:

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 : ')
d = 1024 - 643
token = int(io.recvline().decode())
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.5)[0])

q = q_H + q_L
assert n % q == 0 and 1 < q < n
p = n // q

io.success(f'Found {p = }')
io.success(f'Found {q = }')

We need to specify the upper bound for the small root ($2^{381}$) and $\beta = 0.5$ because $q \approx n^{0.5}$.

Once we have $q$ it is trivial to find $p$, so we have the RSA private key.

Option R

For this option, we need to provide a decryption key:

        elif ch == 'R':
            print('Our plans are encrypted via symmetric encryption and protected with our unique super computer that will take us to the Red Planet!')  
            key = bytes.fromhex(input('Enter decryption key : '))
            plans = crypto.reveal_internal_plans(encrypted_plans, key)
            print_plans(plans)
            exit(0)

This key is used to decrypt some plans using AES:

    def reveal_internal_plans(self, encrypted_plans, key):
        cipher = AES.new(key, AES.MODE_ECB)
        plans = [unpad(cipher.decrypt(ep), 16).decode() for ep in encrypted_plans]  
        return plans

We know how these plans were encrypted:

    def encrypt_plans(self):
        self.symmetric_key = self.prng.generate_key()
        cipher = AES.new(self.symmetric_key, AES.MODE_ECB)
        enc_plans = [cipher.encrypt(pad(r.encode(), 16)) for r in RESTRICTED]  
        return enc_plans

And self.symmetric_key comes from self.prng.generate_key:

    def generate_key(self):
        ct = 0x1337
        # this loop runs in milliseconds in our super computer  
        for _ in range(self.m):
            ct = pow(ct, self.a, self.m)
        return long_to_bytes(ct)[:16]

Remember that prng is an instance of GRAS, initialized as GRAS(self.N, self.p, self.q) from OumaraSystem:

class GRAS:
    def __init__(self, m, p, q):  
        self.m = m
        self.a = 0xdeadbeef
        self.p = p
        self.q = q

So, the symmetric AES key is the result of performing this recurrence relation:

$$ \begin{cases} \mathrm{ct}_0 = \mathtt{0x1337} \\ \mathrm{ct}_{i + 1} = (\mathrm{ct}_i) ^ \mathtt{0xdeadbeef} \mod{n}, \quad 0 \leqslant i < n \end{cases} $$

This recurrence relation is not affordable to do it as such, because $n$ iterations are just too much to handle. But we can try to transform the recurrence relation into into a closed expression. Let’s start with the first rounds:

$$ \begin{cases} \mathrm{ct}_0 & = \mathtt{0x1337} \\ \mathrm{ct}_1 & = (\mathrm{ct}_0) ^ \mathtt{0xdeadbeef} \mod{n} \\ & \quad = \mathtt{0x1337} ^ \mathtt{0xdeadbeef} \mod{n} \\ \mathrm{ct}_2 & = (\mathrm{ct}_1) ^ \mathtt{0xdeadbeef} \mod{n} \\ & \quad = (\mathtt{0x1337} ^ \mathtt{0xdeadbeef}) ^ \mathtt{0xdeadbeef} \mod{n} \\ & \quad = \mathtt{0x1337} ^ {\mathtt{0xdeadbeef} ^ 2} \mod{n} \\ \mathrm{ct}_3 & = (\mathrm{ct}_2) ^ \mathtt{0xdeadbeef} \mod{n} \\ & \quad = (\mathtt{0x1337} ^ {\mathtt{0xdeadbeef} ^ 2}) ^ \mathtt{0xdeadbeef} \mod{n} \\ & \quad = \mathtt{0x1337} ^ {\mathtt{0xdeadbeef} ^ 3} \mod{n} \\ \dots \end{cases} $$

So, by induction, we see that

$$ \mathrm{ct}_i = \mathtt{0x1337} ^ {\mathtt{0xdeadbeef} ^ i} \mod{n} $$

Hence, the symmetric key is the value of $\mathrm{ct}_n$, which is

$$ \mathrm{ct}_n = \mathtt{0x1337} ^ {\mathtt{0xdeadbeef} ^ n} \mod{n} $$

Euler’s Theorem

Again, computing $\mathtt{0xdeadbeef} ^ n$ is not affordable. However, we know from Euler’s Theorem that:

$$ a^{\phi(n)} \equiv 1 \pmod{n} $$

For all $a$ that is coprime with $n$. Notice that in our case, $\phi(n) = (p - 1) \cdot (q - 1)$, we know its value.

As a result, we can express $\mathtt{0xdeadbeef} ^ n = k \cdot \phi(n) + r$ for some $r, k \in \mathbb{Z}$ with $0 \leqslant r < \phi(n)$. This means that

$$ \begin{align} \mathrm{ct}_n & = \mathtt{0x1337} ^ {\mathtt{0xdeadbeef} ^ n} \mod{n} \\ & = \mathtt{0x1337} ^ {k \cdot \phi(n) + r} \mod{n} \\ & = \mathtt{0x1337} ^ {k \cdot \phi(n)} \cdot \mathtt{0x1337} ^ r \mod{n} \\ & = (\mathtt{0x1337} ^ {\phi(n)})^k \cdot \mathtt{0x1337} ^ r \mod{n} \\ & = 1^k \cdot \mathtt{0x1337} ^ r \mod{n} \\ & = \mathtt{0x1337} ^ r \mod{n} \\ \end{align} $$

So, we can easily find $\mathrm{ct}_n$ by calculating $\mathtt{0x1337} ^ r \mod{n}$, where $r = \mathtt{0xdeadbeef} ^ n \mod{\phi(n)}$.

Finally, we compute the value to get the AES key and send it to the server to get the decrypted plans, where we will get the flag:

phi_n = (p - 1) * (q - 1)

r = pow(0xdeadbeef, n, phi_n)
key = long_to_bytes(pow(0x1337, r, n))[:16]

io.sendlineafter(b'> ', b'R')
io.sendlineafter(b'Enter decryption key : ', key.hex().encode())  
io.success(io.recvall())

Flag

If we run the script, we will eventually get the flag:

$ python3 solve.py 94.237.62.195:47360
[+] Opening connection to 94.237.62.195 on port 47360: Done
[*] Closed connection to 94.237.62.195 port 47360
[+] Opening connection to 94.237.62.195 on port 47360: Done
[+] Found n = 21828146529253275647528009268961483917051427953072577306400212670783019877630592727742182289463031611647097861086320726593126769979528665193048139486760894654690438277251180052193057515070370801418498585589171513684267978232583787004127360151128840623431139630252021535654195838570606968632681095031823079824965797727053272091392851725752523879162831055146384238685312134668411531994622000792062370758867536394634102913088089786880545130192783530519953571718954658995201918458155388045089276232631781288844941398393317786447871785850810213239753970564827735726630395643445385451025512627762738759777002612894573124779  
[+] Found p = 138914161634423579755973890643073661570844937467514466292807268924640588600508463767512520820631207681003342696298915409507816838560655431962752418410182732334881168218381565403199082791198460278491813223075820718287282969472364968722297813493964939725554441884621069455843858556284476182996052034694182305499
[+] Found q = 157134062304589100449250495092477382712810341772835720236404481783671949518284747291908024847223653945202337368600411462252602380456101761563657012208023722487110626000059267031658199648905100702047735660944313210898947637050045958141628827881758216447663733390406115171560673050045606192734569616598139140721
[+] Receiving all data: Done (590B)
[*] Closed connection to 94.237.62.195 port 47360
[+] ==================== CLASSIFIED CONTENT! DO NOT SHARE! ====================
    Plan 1 : Their governor goes to sleep at 23:30 PM. We can then break in their warehouses tomorrow night and steal some fuels and water.
    Plan 2 : Listen to the plan carefully! When you are done with the aforementioned invasion, make sure you come back silently and whisper the passphrase HTB{0ur_c0mput3r_1s_t00_f4st___w3_d0nt_3v3n_n33d_3u13r!} to the guards so you can enter.
    Plan 3 : WE will conquer the red planet and get the Vitalium!
    ===========================================================================

The full script can be found in here: solve.py.