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.
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
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
Last updated