Password Generator

Challenge Contents

The challenge "password generator" includes a ZIP file as well as source-code to a password-generator used to generate the password for the ZIP file. The notes state, that the author of this challenge was using Windows.

The Password-Protected ZIP-File contains a .txt file, which has a Timestamp of when it was packaged.

Examining the source code of the password generator, we can see that the seed to rand() is set doing srand(time(nullptr));

The description of the challenge mentions that the author was using windows, so we should look into the implementation of srand() / rand() in Windows' CRT.

How does the RNG work

Given you have selected the installation of the CRT source-code when setting up Visual Studio, the Implementation of rand() can be found on your machine at C:\Program Files (x86)\Windows Kits\10\Source\N.N.N.N\ucrt\stdlib\rand.cpp -- which I sadly cannot share for copyright reasons.

Looking at the aforementioned file however, reveals that the RNG is just a Linear congruential generator (LCG) with mod=2^{31}, multiplier=214013 and increment=2531011, that truncates the output of rand() to bits 30..16. Effectively locking the range of rand() to 0..32767

Luckily, this description is everything we need to fully reconstruct it. Below is a rust reimplementation of MS UCRT's RNG.

struct UcrtRng {
    state: u32,
}

impl UcrtRng {
    pub fn new(seed: u32) -> UcrtRng {
        UcrtRng { state: seed }
    }

    fn step(&self) -> Self {
        Self {
            state: self
                .state
                .overflowing_mul(214013)
                .0
                .overflowing_add(2531011)
                .0
        }
    }

    pub fn take(&self) -> u32 {
        const RAND_MAX: u32 = 0x7fff;
        (self.state >> 16) & RAND_MAX
    }
}

A smart approach to Brute-force

Because we do not know, whether the password has been generated prior or after the Text file inside the ZIP has been created, we should consider going both backwards and forwards in time, to do this, I chose to just use zig-zag integer ordering like this:

This can be implemented as a neat iterator in rust like this:

fn zigzag() -> impl Iterator<Item = i32> {
    (0u32..).map(|n| {
        if n % 2 == 0 {
            (n / 2) as i32
        } else {
            -((n / 2 + 1) as i32)
        }
    })
}

So, to implement our guided brute-forcing, we can simply take the timestamp extracted from the ZIP file (176143200) and zig-zag around it, until we find a password to successfully decrypt the ZIP file.

let time: u32 = 1761429313;
for i in zigzag(){
	let seed = time.checked_add_signed(i).unwrap();

	let pw = (0..32).fold(
	    (String::with_capacity(32), UcrtRng::new(seed).step()),
	    |(mut pw, rng), _| {
	        pw.push(alphabet.as_bytes()[(rng.take() as usize) % alphabet.len()] as char);
	        (pw, rng.step())
	    },
	).0;

	try_password(pw);
}

As for our try_password() function, this will suffice:

fn try_password(pw: String, zipfile: &Path) -> bool
{
    match sevenz_rust::decompress_file_with_password(&zipfile, "output/", pw.as_str().into()) {
            Ok(_) => {
                // `sevenz_rust` has an issue where extraction succeeds
                // even when a bad password is supplied, the resulting file will
                // be size=0, let's filter that. 
                // (7-zip(.org) just rejects the password)
                // note to myself: fix this and file a PR :)
                std::fs::File::open("output/Cargo.toml")
                    .unwrap()
                    .metadata()
                    .unwrap()
                    .len()
                    != 0
            }
            Err(_) => {
                false
            }
        }
}

After around 7000 attempts, you should be greeted with the correct password A655rUd3g3IkRMZX8fq1AyefYw4EfwXO which can be used to decrypt the flag.