Boombox

I have no clue of rust and no clue of crypto, but then with no challenge I stood crying in the rain and rusted.

Category: Crypto

Solver: SchizophrenicFish2nds, Greenscreen23

Flag: GPNCTF{backp4ck_r4p_crap,_yap-yap,_yack1ty-yack}

Writeup

Context

We are given a file with Rust source code and an output file. To get around my limited Rust knowledge, I asked ChatGPT to translate the challenge source doe into Python [4]. Here we can more easily see that the output consists of a subset sum problem, more precisely it closely resembles a Merkle-Hellman scheme.

sum(mic_val for msg_bit, mic_val in zip(msg, mic) if msg_bit)

Here we can see the core of the problem. The problem statement, a ciphertext c is a sum of a subset of the public list mic, where the summands are chosen according to the 1-bits of the secret message, which in our case corresponds to flag chunks.

You can read more on the theory of the cryptosystem and the cryptanalysis in the links [1,2]. An important observation is that, despite the relation to NP-completeness through the subset sum problem, knapsack based schemes are often vulnerable to attacks that use LLL.

Decryption

We can visually see how LLL can give us a valid decryption in [2]. For a more practical attack, we have referred to [3], which shows some sage code for a similar CTF challenge. You can find our adaptation for boombox in [5].

We mainly adapted the Python 2 syntax and added an automatic filter for negative entries in the solution, as [3], similar to [2], relies on manual, visual inspection to find a solution (i.e. a vector of 1s and 0s). Since we have multiple flag chunks, we filtered out all negative values, as those could not possibly be the binary encoding of the flag.

Initially, we were not able to find a perfect parameter that decrypted the flag as a whole. Instead, we manually adjusted the delta parameter of sage’s LLL algorithm, until we got different flag parts. Then we manually pieced together the full flag. We later found delta = 0.992, which produced the whole flag.

Mitigations

The Merkle-Hellman scheme is a good example to teach the relations between complexity-theoretic problems and cryptography, but also a good way to teach LLL-based attacks! There are more modern public key systems that are much more suited for asymmetric encryption now.

Other resources

[1] https://web.eecs.umich.edu/~cpeikert/lic13/lec05.pdf

[2] https://mathweb.ucsd.edu/~crypto/Projects/JenniferBakker/Math187/

[3] https://ctftime.org/writeup/2236

Scripts

[4] ChatGPT generated Python version

import random
from math import gcd
from sympy import nextprime
from sympy.ntheory.generate import randprime
from sympy import lcm, mod_inverse
from sympy.core.numbers import igcd
from sympy.ntheory.factor_ import totient

class BigUint:
    def __init__(self, value):
        self.value = value

    def __add__(self, other):
        return BigUint(self.value + other.value)

    def __sub__(self, other):
        return BigUint(self.value - other.value)

    def __mul__(self, other):
        return BigUint(self.value * other.value)

    def __mod__(self, other):
        return BigUint(self.value % other.value)

    def __truediv__(self, other):
        return BigUint(self.value // other.value)

    def __lt__(self, other):
        return self.value < other.value

    def __eq__(self, other):
        return self.value == other.value

    def __str__(self):
        return str(self.value)

    @staticmethod
    def from_bytes_be(bytes_val):
        return BigUint(int.from_bytes(bytes_val, 'big'))

    def to_bytes_be(self):
        byte_len = (self.value.bit_length() + 7) // 8
        return self.value.to_bytes(byte_len, 'big')

    def bit_length(self):
        return self.value.bit_length()

def rndint(rng, a, b):
    range_val = b - a + BigUint(1)
    buf_len = (range_val.bit_length() + 7) // 8
    while True:
        buf = random.getrandbits(buf_len * 8).to_bytes(buf_len, 'big')
        num = BigUint.from_bytes_be(buf)
        if num < range_val:
            return a + num

def compose(n, rng):
    two = BigUint(2)
    ps = [
        rndint(rng, (two ** i - BigUint(1)) * (two ** n), (two ** i) * (two ** n))
        for i in range(n)
    ]
    # (2**i - 1 ) * 2**n; 2**i * 2**n
    # (2**i - 1 ) * 2**n; 2**i * 2**n

    m_lower = (two ** (2 * n + 1)) + BigUint(1)
    m_upper = (two ** (2 * n + 2)) - BigUint(1)
    m = rndint(rng, m_lower, m_upper)

    tune = rndint(rng, BigUint(2), m - BigUint(2))
    t = tune / BigUint(gcd(tune.value, m.value))

    mictape = [(t * a) % m for a in ps]
    if gcd(t.value, m.value) != 1:
        return compose(n, rng)
    return ((ps, t, m), mictape)

def record(msg, mic):
    return sum(mic_val for msg_bit, mic_val in zip(msg, mic) if msg_bit)

def main():
    n = 42
    rng = random.SystemRandom()
    (ps, t, m), mic = compose(n, rng)
    print(mic)

    msg_str = "GPNCTF{fake_flag}"
    msg_bytes = msg_str.encode('utf-8')
    msg_bin = [bit == '1' for byte in msg_bytes for bit in format(byte, '08b')]

    for chunk in (msg_bin[i:i+n] for i in range(0, len(msg_bin), n)):
        msg_chunk = chunk + [False] * (n - len(chunk))
        c = record(msg_chunk, mic)
        print(c)

if __name__ == "__main__":
    main()

[5] Decryption using LLL

from Crypto.Util.number import long_to_bytes

mic = [26164716679782610683071400, 18179536354421749943360181, 5665675605611009327234952, 50306696368015064022136043, 9760129112235435790997053, 55666059844053563833206217, 16844592035444290437017126, 38380596544512184351649759, 8422829610606521010459307, 61991593557938451876941660, 39790447025261860761497646, 48017326044343373440883482, 56020453465553890215405886, 33717630577181456697432100, 38446470352430301120764167, 11956286975976159307849939, 47803055605410068453065938, 45915004803511711931436810, 24482601816186282662870243, 25803830771195376281772430, 35407508732033692038517544, 61180319487483561607584508, 25231125861794574504466017, 8313835456593256084156278, 17127389362891025344120144, 21245871665329880303420019, 38878412244851399679662521, 38873829041129616412914108, 55803139319518810427462325, 4480398056669715718609757, 16723813500382973499318355, 46788850793793785768241956, 18363270968918184887203944, 2919614635435884742895127, 38003982387728441304493811, 5066781076320234588607777, 2160276302660722051676110, 47965211574081273776856665, 14735899017054553490198493, 14455868058721210953072395, 59777806226033755809142580, 43667948754413413362501037]
clist= [591191755265294600006904240,612990134375087714919032704,702014866447865251118799888,631408587334297368272903359,531069814353289175343659237,619506025951321329935979611,633106357798876645310170585,762239129094955827352040826,645540547612149444739609749,155982684851883997809008793]

nbit = len(mic)

result = ""

for ctr, ciphertext in enumerate(clist):

    # create a large matrix of 0's (dimensions are public key length +1)
    A = Matrix(ZZ,nbit+1,nbit+1)
    
    # fill in the identity matrix
    for i in range(nbit):
        A[i,i] = 1
        
    # replace the bottom row with your public key
    for i in range(nbit):
        A[i,nbit] = mic[i]
        # last element is the encoded message
        A[nbit,nbit] = -int(ciphertext)

    res = A.LLL(algorithm="NTL:LLL", delta=0.992)
    
    rows_without_negatives = [row for row in res.rows() if all(entry >= 0 for entry in row)]

    if rows_without_negatives != []:
        binary_string = ''.join(map(str, rows_without_negatives[0]))
        print(binary_string)
        result +=binary_string[:-1]
    else:
        result += "0"*42
        print("Decryption failed")
        
for i in range(52):
    print(long_to_bytes(int(result[i*8:(i+1)*8], 2)).decode(), end="")
        
# other solutions:
# GPNCT@p4ck_r4p_crap,_yap-yap,_y`-yack} # delta=0.98
# GPNCTF{backp4ck_r4p_crap,_@p,_yack1ty-yack} # delta=0.99875484

# Full flag with delta=0.992: "GPNCTF{backp4ck_r4p_crap,_yap-yap,_yack1ty-yack}"

Writeup#

Context#

Decryption#

Mitigations#

Other resources#

Scripts#