CryptoPals Crypto Challenges Using Rust: Single-byte xor cipher
Tags: programming, rust, cryptography
Published: 2021-12-31 14:10:37

This is [Challenge 3](https://cryptopals.com/sets/1/challenges/3) of [Cryptopals](https://cryptopals.com) 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](https://en.wikipedia.org/wiki/Letter_frequency) scoring would suffice for our purpose. You can learn more about it [here](https://crypto.stackexchange.com/questions/30209/developing-algorithm-for-detecting-plain-text-via-frequency-analysis).

Here's one implementation in Rust:

```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.

```rust
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)
}

```
And in a snap, cipher is broken! 😎

See code on [Github](https://github.com/theNvN/cryptopals-crypto-challenges/blob/master/src/set_1_basics/c3_single_byte_xor_cypher.rs)

Find me on:
Twitter - [@heyNvN](https://twitter.com/heyNvN)

[naveeen.com](https://naveeen.com)