CryptoPals Crypto Challenges Using Rust: Single-byte xor cipher

#programming #rust #cryptography

This is Challenge 3 of Cryptopals challenges implemented in Rust language.

Context 💡

So, things are starting to get interesting now.
We're given a hex encoded string. This string has been XORed against a single character. We don't know what character. We have to find this character (aka "key" of this encryption) & decrypt the message.

Let's say the message was somesecret (length 10) then it was XORed against let's say char k, then:

somesecret ^ kkkkkkkkkk ('k' repeated 10 times) = somecypher

Now, if we want to decipher the given encrypted message - somecypher, we can XOR it with the same key:

somecipher ^ kkkkkkkkkk ('k' repeated 10 times) = somesecret

We're going to exploit this property of XOR encryption to decipher the message here.

Crack 🕶

The way we're going to break is by brute-forcing with all chars. By looping through each char - c & using repeated c as key, we'll get a message. Now none of the decrypted messages would make sense. Except only one - the one with the actual key! All other would spit out some stupid random sequence of characters.

somecipher ^ aaaaaaaaaa = axow&)!923 (nah!)
somecipher ^ bbbbbbbbbb = cgow*&=8u2 (nah!)
somecipher ^ cccccccccc = yz!6w+)#93 (nah!)
.
.
somecipher ^ kkkkkkkkkk = somesecret (looks like a secret!)

We'd need to devise some method to programmatically detect sense-making English text by scoring each message corressponding to each char c as key. Scoring by letter frequency scoring would suffice for our purpose. You can learn more about it here.

Here's one implementation in Rust:

const LETTER_FREQ: [f64; 27] = [
    0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, // A-G
    0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749, // H-N
    0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758, // O-U
    0.00978, 0.02360, 0.00150, 0.01974, 0.00074, 0.19181, // V-Z & space char
];

pub fn calc_letter_freq_score(s: &str) -> f64 {
    let mut counts = vec![0_u32; 27];
    let mut score: f64 = 0_f64;

    s.chars().for_each(|c| match c {
        'a'..='z' => {
            counts[c as usize - 97] += 1;
        }
        'A'..='Z' => {
            counts[c as usize - 65] += 1;
        }
        ' ' => counts[26] += 1,
        _ => {}
    });

    for i in 0..27 {
        score += (counts[i] as f64) * LETTER_FREQ[i];
    }

    score
}

Note that for the challenge I've also included a frequency of space character at the very end.

Now to the core problem. We loop through every char as byte, xor this byte with every byte of given cipher. Convert XORed bytes to a text (String), then calculate this text's (potentially message) letter frequency score. Retain the deciphered message producing the best score & corresponding key char.

use hex;

pub fn decipher_message(hex_cipher: &str) -> (String, f64) {
    let cipher_bytes = hex::decode(hex_cipher).unwrap();
    let mut key_byte: u8;

    let mut message = String::new();
    let mut best_score = f64::MIN;
    for c in 0..=255 {
        key_byte = c as u8;

        let msg_bytes: Vec<u8> = cipher_bytes.iter().map(|&b| b ^ key_byte).collect();

        let msg = String::from_utf8_lossy(&msg_bytes);
        let score = calc_letter_freq_score(&msg);

        if score > best_score {
            best_score = score;
            message = String::from(msg);
        }
    }

    (message, best_score)
}