Walid Sabihi's Blog

Cryptopals Crypto Challenge - Set 1

Exams are coming up in a couple weeks, and instead of preparing, I am procrastinating solving a set of crypto challenges I stumbled upon. I've decided to use Rust for the challenges. I'll keep it short and nice, but you'll see all the code down below!

Set up

We first set up a new rust project using cargo:

(base) ➜ cargo init cryptopals
     Created binary (application) package

I'll be using VSCode with Rust Analyser to edit the code.

Convert hex to base64

We need to write a function that, given a hex string, returns a base64 string. cargo generated a simple main.rs, which I then modified to call a function that will accomplish this first task for us, using the test string they provided:

// main.rs
fn hex2base64(hex: &str) -> String {
    
}

fn main() {
assert!(hex2base64("49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d") == "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t");
}

This won't compile yet, as hex2base64 doesn't return a string yet.

Not reinventing the wheel

It is possible to write a base64 encoder from scratch, but I don't believe this is necessary, as a fast and correct crate called base64 exists already. We'll still have to first convert the hex string to a vector of bytes before using the encoder.

fn hex2base64(hex: &str) -> String {
    let mut bytes = Vec::new();
    for i in 0..hex.len()/2 {
        let res = u8::from_str_radix(&hex[2*i..2*i+2], 16);
        bytes.push(res.expect("Invalid hex sequence"));
    }
}

Since in a hex string, every 2 characters represent one byte, we iterate through every pair of characters and use u8's from_str_radix function to parse it from hexadecimal (hence the 16 radix/base argument).

Now, we can use base64 by first adding it using cargo add:

(base) ➜ cargo add base64
    Updating crates.io index
      Adding base64 v0.21.0 to dependencies.
             Features:
             + std
             - alloc

The crate is quite extensive, and provides several engines for encoding, which I found surprising for a seemingly simple task, but we only care about the general purpose one. To use it, we need to add these imports at the top:

use base64::{Engine as _, engine::general_purpose::STANDARD_NO_PAD};

The Engine trait import is not directly used in our code, but we need it to be able to use the engine we imported for encoding (not entirely sure why!).

We can then use the engine to encode our byte vector into base64:

fn hex2base64(hex: &str) -> String {
    let mut bytes = Vec::new();
    for i in 0..hex.len()/2 {
        let res = u8::from_str_radix(&hex[2*i..2*i+2], 16);
        bytes.push(res.expect("Invalid hex sequence"));
    }
    STANDARD_NO_PAD.encode(&bytes)
}

To run this, we use the command cargo run which automatically (re)builds the binary, and runs it. Since we have an assert, running it without errors means that our code works! Let's give it a try:

(base) ➜   cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.05s
     Running `target/debug/cryptopals`
(base) ➜

And it works!

Problem 2: Fixed XOR

Breaking up hex and base64 conversion

This section gives us two buffers, and asks us to write code to calculate their XOR. This should be quite simple, as it only involves converting the hex strings to byte vectors, and then bitwise-XORing every ith byte into a result vector. It might have become clear that we need to split the code we wrote earlier, as we won't need the base64 conversion for this part.

fn from_hex(hex: &str) -> Vec<u8> {
    let mut bytes = Vec::new();
    for i in 0..hex.len()/2 {
        let res = u8::from_str_radix(&hex[2*i..2*i+2], 16);
        bytes.push(res.expect("Invalid hex sequence"));
    }
    bytes
}

fn to_base64(vec: &Vec<u8>) -> String {
    STANDARD_NO_PAD.encode(vec)
}

Now, we can work with byte vectors directly for this exercise (and future ones). For convenience, I also experimented with keeping hex2base64 by writing a macro that defines it as a composition of the two separate functions:

macro_rules! compose {
    ($name:ident = $f1:ident . $f2:ident :: ($tp:ty) -> $rt:ty) => {
        pub fn $name(input: $tp) -> $rt {
            $f1(&$f2(input))
        }
    }
}

compose!(hex2base64 = to_base64.from_hex :: (&str) -> String);

This is overkill, and I probably wouldn't do it in a production environment, but it was worth experimenting with to understand how basic macros work. (Docs: https://doc.rust-lang.org/rust-by-example/macros.html).

XOR on two Vec<u8>s

If we define two vecs, hex1 and hex2, we can perform bitwise-XOR in a more functional way:

let hex1 = from_hex("1c0111001f010100061a024b53535009181c");
let hex2 = from_hex("686974207468652062756c6c277320657965");
let ret: Vec<u8> = hex1.iter().zip(hex2).map(|(v1, v2)| v1^v2).collect();
assert!(ret == from_hex("746865206b696420646f6e277420706c6179"));

Hopefully it is clear what the code does, but for guidance:

We add the assert to confirm that our code returns the correct result.