Crypto-Boombox

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

Full Implementation

Challenge

Given is a Rust file and output text file

use rand::Rng;
use rand::rngs::ThreadRng;
use num::integer::gcd;
use num_bigint::BigUint;
use std::convert::TryInto;

fn rndint(rng: &mut ThreadRng, a: &BigUint, b: &BigUint) -> BigUint {
    let range = b - a + 1u32;
    let mut buf = vec![0u8; ((range.bits() + 7) / 8).try_into().unwrap()];
    loop {
        rng.fill(&mut buf[..]);
        let num = BigUint::from_bytes_be(&buf);
        if num < range {
            return a + num;
        }
    }
}

fn compose(n: usize, rng: &mut ThreadRng) -> ((Vec<BigUint>, BigUint, BigUint), Vec<BigUint>) {
    let two = BigUint::from(2u32);
    let ps: Vec<BigUint> = (0..n).map(|i| {
        let lower = (&two.pow(i as u32) - 1u32) * &two.pow(n as u32);
        let upper = &two.pow(i as u32) * &two.pow(n as u32);
        rndint(rng, &lower, &upper)
    }).collect();

    let m_lower = &two.pow((2 * n + 1) as u32) + 1u32;
    let m_upper = &two.pow((2 * n + 2) as u32) - 1u32;
    let m = rndint(rng, &m_lower, &m_upper);

    let tune = rndint(rng, &BigUint::from(2u32), &(m.clone() - 2u32));
    let t = &tune / gcd(tune.clone(), m.clone());

    let mictape: Vec<BigUint> = ps.iter().map(|a| (&t * a) % &m).collect();
    if gcd(t.clone(), m.clone()) != BigUint::from(1u32) {
        return compose(n, rng);
    }
    ((ps, t, m), mictape)
}

fn record(msg: &[bool], mic: &[BigUint]) -> BigUint {
    msg.iter().zip(mic).filter(|(&msg_bit, _)| msg_bit).map(|(_, mic_val)| mic_val.clone()).sum()
}

fn main() {
    let n: usize = 42;
    let mut rng = rand::thread_rng();
    let ((ps, t, m), mic) = compose(n, &mut rng);
    // stop thread
    println!("{:?}", mic);

    let msg_str = "GPNCTF{fake_flag}";
    let msg_bytes = msg_str.as_bytes();
    let msg_bin: Vec<bool> = msg_bytes.iter()
                                      .flat_map(|&byte| format!("{:08b}", byte).chars().map(|c| c == '1').collect::<Vec<bool>>())
                                      .collect();
    for chunk in msg_bin.chunks(n) {
        let mut msg_chunk = chunk.to_vec();
        if msg_chunk.len() < n {
            msg_chunk.resize(n, false);
        }
        let c = record(&msg_chunk, &mic);
        println!("{}", c);
    }
}

I'm pretty bad at Rust, so I converted the code to Python to make it easier to understand

# Shamelessly copied from ChatGPT
import random
import math
from typing import List, Tuple

def rndint(a: int, b: int) -> int:
    """Generates a random integer within the specified range (inclusive)."""
    return random.randint(a, b)

def gcd(a: int, b: int) -> int:
    """Calculates the greatest common divisor of two integers."""
    while b:
        a, b = b, a % b
    return a

def compose(n: int) -> Tuple[Tuple[List[int], int, int], List[int]]:
    """Generates the public and private keys for the knapsack cryptosystem."""
    ps = [rndint(2**(i + n), 2**(i + n + 1) - 1) for i in range(n)]
    m = rndint(2**(2 * n + 1) + 1, 2**(2 * n + 2) - 1)
    tune = rndint(2, m - 2)
    t = tune // gcd(tune, m)

    mictape = [(t * a) % m for a in ps]

    if gcd(t, m) != 1:
        return compose(n)  # Retry if gcd is not 1

    return (ps, t, m), mictape

def record(msg: List[bool], mic: List[int]) -> int:
    """Encrypts a message using the public key."""
    return sum(mic_val for msg_bit, mic_val in zip(msg, mic) if msg_bit)

def main():
    """Demonstrates the knapsack cryptosystem."""
    n = 42
    (ps, _, _), mic = compose(n)
    print("Public Key (Mic):", mic)

    msg_str = "GPNCTF{fake_flag}"
    msg_bytes = msg_str.encode()
    msg_bin = [
        int(bit) for byte in msg_bytes for bit in format(byte, "08b")
    ]

    for chunk in range(0, len(msg_bin), n):
        msg_chunk = msg_bin[chunk : chunk + n]
        if len(msg_chunk) < n:
            msg_chunk.extend([0] * (n - len(msg_chunk)))
        c = record(msg_chunk, mic)
        print("Ciphertext Chunk:", c)

if __name__ == "__main__":
    main()

In main, we see that the compose function takes an integer(42) and returns the private and public key. The public key is a list of multiplication of 2 unknown numbers in a list, modulo an unknown number

The flag is then formatted into bits, and split into chunks of 42 bits. The record function then encrypts the chunks by multiplying the values of public key with its corresponding bit chunk value and takes the sum of all the final values.

This is an implementation of the knapsack cryptosystem, in which bruteforcing all the bits has 2^n complexity, so while it may seem secure, we can use a different method to break this cryptosystem by using the LLL algorithm.

To do this, we refer to this paper

752KB

cjloss.pdf

pdf

Exploit

We construct the lattice as follows, where mic is the public key and c is the ciphertext chunk

from sage.all import *
M = identity_matrix(QQ,42)
M = M.augment(vector(mic))
M = M.stack(vector([-1/2 for i in range(42)]+[-c]))

For example, this is how the matrix looks like for the first ciphertext chunk

[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 26164716679782610683071400]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18179536354421749943360181]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5665675605611009327234952]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 50306696368015064022136043]
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9760129112235435790997053]
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 55666059844053563833206217]
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16844592035444290437017126]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 38380596544512184351649759]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8422829610606521010459307]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 61991593557938451876941660]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 39790447025261860761497646]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 48017326044343373440883482]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 56020453465553890215405886]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 33717630577181456697432100]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 38446470352430301120764167]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11956286975976159307849939]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 47803055605410068453065938]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 45915004803511711931436810]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 24482601816186282662870243]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 25803830771195376281772430]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 35407508732033692038517544]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 61180319487483561607584508]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 25231125861794574504466017]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8313835456593256084156278]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17127389362891025344120144]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21245871665329880303420019]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 38878412244851399679662521]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 38873829041129616412914108]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 55803139319518810427462325]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4480398056669715718609757]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16723813500382973499318355]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 46788850793793785768241956]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18363270968918184887203944]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2919614635435884742895127]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 38003982387728441304493811]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 5066781076320234588607777]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2160276302660722051676110]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 47965211574081273776856665]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 14735899017054553490198493]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 14455868058721210953072395]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 59777806226033755809142580]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 43667948754413413362501037]
[-1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -591191755265294600006904240]

After applying LLL on the matrix, we get the target vector in first row of the reduced matrix

[-1/2, 1/2, -1/2, -1/2, -1/2, 1/2, 1/2, 1/2, -1/2, 1/2, -1/2, 1/2, -1/2, -1/2, -1/2, -1/2, -1/2, 1/2, -1/2, -1/2, 1/2, 1/2, 1/2, -1/2, -1/2, 1/2, -1/2, -1/2, -1/2, -1/2, 1/2, 1/2, -1/2, 1/2, -1/2, 1/2, -1/2, 1/2, -1/2, -1/2, -1/2, 1/2, 0]

On adding 1/2 (because we did -1/2 to each entry in the last row of the matrix) to each entry, we get the plaintext of the first ciphertext chunk

0100011101010000010011100100001101010100011

Similarly, on decrypting all the ciphertexts and decoding 8 bits at a time, we get the flag

ans=""
for k in t2:
    M = identity_matrix(QQ, len(arr))
    M = M.augment(vector(arr))
    M = M.stack(vector([-1/2 for _ in range(len(arr))] + [-int(k)]))
    M1 = M.LLL()
    for row in M.LLL():
        for row in (row, -row):
            if row[-1] == 0:
                subset = [t1[i] for i, x in enumerate(row[:-1]) if x+1/2==1]
                if int(sum(subset)) == int(k):
                    r=(vector(row)[:-1] +vector([1/2 for i in range(len(arr))]))
                    ans+=''.join(list(map(str,r)))

print(ans)
#010001110101000001001110010000110101010001000110011110110110001001100001011000110110101101110000001101000110001101101011010111110111001000110100011100000101111101100011011100100110000101110000001011000101111101111001011000010111000000101101011110010110000101110000001011000101111101111001011000010110001101101011001100010111010001111001001011010111100101100001011000110110101101111101000000000000000000000000000000000000

a1=[]
for i in range(52):
    a1.append(ans[8*i:8*i+8])
for i in a1:
    print(chr(int(i,2)),end='')
#GPNCTF{backp4ck_r4p_crap,_yap-yap,_yack1ty-yack}