Is Rust's MD5 Slow? Heck no!

Today I came across this post on the Rust subreddit. Basically it is comparing two MD5 Miners written in Python and Rust. The miner is written for a code challenge called Advent of Code.

To be honest, speed is one of the things I love about Rust, so seeing Rust being blown away by Python (which I also like and use a lot) made me sad. I decided to make this a bit more fair for Rust so I made a very short piece of Rust code to complete this challenge FAST.

The challenge

The challenge, as written on the Advent of Code page is as follows:

You are given a key, for example abcdef.
You are looking for a string that is made by taking the MD5 of this key plus a number. This hash has to start with 5 leading zeros. (Like abcdef609043)

Let's get right into the code, I'll explain it in detail later.

extern crate crypto;

use crypto::md5::Md5;
use crypto::digest::Digest;

fn main() {
    let mut hasher = Md5::new();

    let key = "abcdef".as_bytes();
    for i in (0..std::u64::MAX) {
        hasher.input(key);
        hasher.input(i.to_string().as_bytes());
        
        let mut output = [0; 16]; // An MD5 is 16 bytes
        hasher.result(&mut output);

        let first_five = output[0] as i32 + output[1] as i32 + (output[2] >> 4) as i32;
        if first_five == 0 {
            println!("{}", i);
            break;
        }
        hasher.reset();
    }
}

How the code works

extern crate crypto;

use crypto::md5::Md5;
use crypto::digest::Digest;

Let's start with the library, crypto. The crate is called rust-crypto, it has pure-Rust implementations of a lot of cryptographic algorithms. In the code, we use this crate to get the MD5 of our string.

The Md5 from the library provides the Md5::new part, and Digest provides the input, result and the reset functions.

let mut hasher = Md5::new();

let key = "abcdef".as_bytes();

In this part, we create an Md5 instance. We do this outside the loop because we can reuse it instead of creating a new one each time our loop runs.

We also turn the key into a byte array in order to supply it to the Md5 instance. Again, we do this outside the loop so we can get some speed benefits.

The loop is an iterator that starts from 0 and ends with u64::MAX, which is the maximum value a 64-bit unsigned integer can hold. (18,446,744,073,709,551,615)

Inside the loop, the first thing we do is to input the key and the current value of i to our MD5 instance.

hasher.input(key);
hasher.input(i.to_string().as_bytes());

Afterwards, we store the result of the MD5 hash in a 16-byte buffer. Why use a fixed-size buffer instead of a dynamic string? Because by using a fixed-size buffer, we can save time and memory wasted by allocating and converting dynamic Strings.

let mut output = [0; 16]; // An MD5 is 16 bytes
hasher.result(&mut output);

Here's a part that might look weird. The challenge description said the hash should start with 5 zeroes. But instead of something like result.starts_with("00000"), we have this addition. This, of course, is another simple optimization. And it's not complicated at all.

Think about this; if we want to go with the string operations to solve this challenge, the result of the hash should be turned into a string first. This costs time. After that, the first 5 bytes of this string will need to be compared to "00000". This also costs time.

The trick is to notice that an MD5 hash is actually just 16 bytes. But since this is hard to print, most people just use the hex representation of the hash digest. In the hex representation, each byte is shown with 2 characters. For example; the bytes [0, 0] become "00 00".

If the challenge were to find the hash with 4 leading zeros, we could just check the first two bytes of the result and be done. But since it asks for 5 leading zeros, we need to use a little bit-shifting.

I will try to explain the bit-shifting in a simple way.

The byte [1] is represented by 01 in hex.
To split this byte to its halves, we can use bitshifting like this.
0x01 >> 4 gives us 0.
0x73 >> 4 gives us 7.

We can use this to get the fifth digit from the hash without converting it to a string. After all this work, we just add the digits together and check to see if their sum is zero. This is equivalent to checking if the hash starts with five zeros.

let first_five = output[0] as i32 + output[1] as i32 + (output[2] >> 4) as i32;
if first_five == 0 {
    println!("{}", i);
    break;
}

After each loop, we need to reset the Md5 instance so that it is ready to accept another string for the next loop. We can do this by simply calling it's .reset() method.

the-nerdery-dot-info/rust_md5.md

Is Rust's MD5 Slow? Heck no!

The challenge

How the code works