Sun Jun 25 2023

Breaking news: Rust is fast

I recently discovered a puzzle site that brought me back to the early days of the internet. I fondly remember a website from my youth (the name of which has been lost to time) where I had to dig through the source, find hidden images and links, and use all of my meager web sleuthing skills to solve puzzles. While Oxf.at isn't quite the same, it's still in the same spirit, and it's simple: Use what you know about the web to figure out the password, over and over again for 38 (at the time of this writing) levels of difficulty.

Level 20 is a bit different from the previous levels. You're given an MD5 hash and a list of words, and the goal is to figure out which two words were combined to make the hash. Simple enough, except the list is long. My goal was to brute force it by creating a hash out of every combination of words and comparing it against the given hash.

If you want to try it yourself, here's the challenge. Spoilers ahead, so go try it before reading on if you like!

const wordlist = fs.readFileSync('./wordlist.txt').toString().split('\n'); for (let i = 0; i < wordlist.length - 1; i++) { const word1 = wordlist[i]; console.log('word1', word1); for (let j = 0; j < wordlist.length; j++) { const word2 = wordlist[j]; const hash = crypto .createHash('md5') .update(word1 + word2) .digest('hex'); if (hash === 'df6acb722be001fb293fb282e488c496') { console.log('The words are:', word1 + word2); return; } } }

The first time I ran this I realized it wasn't going to work. Well, it might work eventually but I would have to start it running and come back the next day to check it.

I've got a few extra cores laying around, let's put them to use. Node has a few ways to use multiple cores, I went with the cluster module which forks as many new processes as you tell it to.

Much faster... but still not that fast. I was logging out word1 so I could see how quickly the code was working its way through the list, and while the words were now coming in chunks of 8, the chunks were coming about once per second so it still looked like it would take a couple hours to get through the list.

This looks like a job for Rust! I know Rust is fast, but I've never done a direct 1:1 comparison like this: same job, two different languages.¹

Here's my first (single-threaded) attempt:

fn single_thread() { let file = fs::read_to_string("./wordlist.txt").expect("Could not read file"); let words = file .trim() .split('\n') .collect::<Vec<&str>>(); for word1 in &words { println!("{:?}", word1); for word2 in &words { let digest = md5::compute(word1.to_string() + word2); if format!("{:x}", digest) == "3df7c3057e540cbe9244561a2d4345f7" { println!("{}{}", word1, word2); return; } } } }

Not super fast, and in fact without an optimized build (cargo run rather than cargo build --release) this seemed to run a bit slower than the first JS version. Let's see how this goes with multiple threads:

fn multi_thread() { let file = fs::read_to_string("./wordlist.txt").expect("Could not read file"); let file_words = file .trim() .split('\n') .map(|w| w.to_string()) .collect::<Vec<String>>(); let words = Arc::new(file_words); let done = Arc::new(Mutex::new(false)); let mut handles = vec![]; for i in 0..8 { let words = Arc::clone(&words); let done = Arc::clone(&done); let handle = thread::spawn(move || { let offset = words.len() / 8; let start = i * offset; let end = start + offset; for word1 in &words[start..end] { if *done.lock().unwrap() { return; } println!("{:?}", word1); for word2 in &words[..] { let digest = md5::compute(word1.to_string() + word2); if format!("{:x}", digest) == "3df7c3057e540cbe9244561a2d4345f7" { println!("{}{}", word1, word2); let mut is_done = done.lock().unwrap(); *is_done = true; return; } } } }); handles.push(handle); } for handle in handles { handle.join().unwrap(); } }

There's a bit more going on here. Threads in Rust aren't as concise as in Node, but the Rust book has a great chapter on using threads here. I've also heard good things about the crossbeam crate, but didn't try it for this experiment. I went straight for the optimized --release build, fired it up, and immediately saw those same logs from before scrolling up my screen faster than I could read them. In under 2 minutes I had my match and saw just how fast Rust is. It should come as no surprise to anyone, but... it's one thing to understand that Rust is fast and another thing to apply it to a problem and watch it in action.

Onto the next challenge!

1: To be fair, I probably could have optimized the JS a bit more. I might try that as a next step, but at that point it's getting to be less apples-to-apples comparison with the Rust version.

<< Previous