search

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.

hashtag
Full Implementationarrow-up-right

hashtag
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

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

file-pdf
752KB
cjloss.pdf
PDF
arrow-up-right-from-squareOpen

hashtag
Exploit

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

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

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

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

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

PreviousGPN CTF 2024NextWANICTF 2024

Last updated