Return to Revisions

Following up on my implementation of Cryptopals Challenge 1, this is my solution to Challenge 3.

Single-byte XOR cipher The hex encoded string:

1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736

... has been XOR'd against a single character. Find the key, decrypt the message.

You can do this by hand. But don't: write code to do it for you.

How? Devise some method for "scoring" a piece of English plaintext. Character frequency is a good metric. Evaluate each output and choose the one with the best score.

The idea here is that I try to decrypt with every possible single byte repeating key (each extended ascii/utf8 character), then compare the resulting character frequency to the expected frequency with a Chi-Squared test.

$$ \chi^2 = \sum_{i=1}^n \frac{(obs - exp)^2}{exp} $$

If χ2 < the critical value, then the decrypted cipher is determined to be English text, therefore we've cracked the cipher and found the key.

I'm some data and a build script to do some code generation before compiling the rest of the project.

data/english.csv

32,17.1660
101,8.5771
116,6.3700
111,5.7701
97,5.1880
...

build.rs

use std::env;
use std::fs::File;
use std::io::BufRead;
use std::io::BufReader;
use std::io::Write;
use std::path::Path;
fn main() {
 let declaration = String::from("fn english_frequencies() -> HashMap<u8, f32> {[");
 // csv must be 2 columns, no header
 // ascii number, frequency as percentage
 // 32,17.16660
 let file = File::open("data/english.csv").unwrap();
 let reader = BufReader::new(&file);
 let formatted_lines = reader
 .lines()
 .map(|line| format!("({}),\n", line.unwrap()))
 .collect();
 let close = String::from("].iter().cloned().collect()}");
 let out_dir = env::var("OUT_DIR").unwrap();
 let dest_path = Path::new(&out_dir).join("english_frequencies.rs");
 let mut f = File::create(&dest_path).unwrap();
 f.write_all(
 &[declaration, formatted_lines, close]
 .join("\n")
 .into_bytes(),
 ).unwrap();
}

This generated table of expected frequencies is then included in a module that implements the frequency analysis.

src/frequency.rs

use std::collections::HashMap;
include!(concat!(env!("OUT_DIR"), "/english_frequencies.rs"));
pub fn english(message: &str) -> bool {
 let expected_counts: HashMap<char, f32> = english_frequencies()
 .iter()
 .map(|(k, freq)| (k.clone() as char, (freq / 100.0) * (message.len() as f32)))
 .collect();
 let actual_counts = message
 .chars()
 .fold(HashMap::new(), |mut acc: HashMap<char, isize>, c| {
 let count = match acc.get(&c) {
 Some(x) => x.clone() + 1,
 None => 1,
 };
 acc.insert(c, count);
 acc
 });
 let chi_statistic = chi_statistic(actual_counts, expected_counts);
 if cfg!(debug_assertions) {
 println!("X-statistic: {}", chi_statistic);
 }
 // Degrees of freedom = 256 - 1 = 255 (character space)
 // Usign this table:
 // https://en.wikibooks.org/wiki/Engineering_Tables/Chi-Squared_Distibution
 // We can use the approximate value for 250 degrees of fredom.
 // Given a significance factor (alpha) of 0.05, our critical value is 287.882.
 // If our chi_statistic is < the critical_value, then we have a match.
 // See this page for an explanation:
 // https://en.wikipedia.org/wiki/Chi-squared_distribution#Table_of_%CF%872_values_vs_p-values
 chi_statistic < 287.882
}
/// Calculates Pearson's Cumulative Chi Statistic
/// https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test#Calculating_the_test-statistic
///
/// This is a slight variation.
/// Technichally, if the expected value is zero and the actual is non-zero, then the statistic is infinite.
/// For the sake of ergonommics, this implementation assumes missing expected values to be small, but non-zero.
/// This allows us to only specify values in the expected frequencies that are statistically
/// significant while allowing for all valid utf-8 characters in the message.
fn chi_statistic(observed: HashMap<char, isize>, expected: HashMap<char, f32>) -> f32 {
 observed
 .into_iter()
 .map(|(key, obs)| {
 let exp = match expected.get(&key) {
 Some(x) => x.clone() as f32,
 None => 0.0000001, //non-zero, but tiny possibility
 };
 (obs as f32 - exp).powi(2) / exp
 }).sum()
}
#[cfg(test)]
mod tests {
 use super::*;
 #[test]
 fn bacon_message_is_english() {
 let message = "Cooking MC's like a pound of bacon";
 assert!(english(message));
 }
 #[test]
 fn message_with_unprintable_chars_is_not_english() {
 assert!(!english(
 "\u{7f}SSWUR[\u{1c}q\u{7f}\u{1b}O\u{1c}PUWY\u{1c}]\u{1c}LSIRX\u{1c}SZ\u{1c}^]_SR"
 ));
 }
 #[test]
 fn printable_nonsense_is_not_english() {
 assert!(!english("Yuuqst}:WY=i:vsq\u{7f}:{:juot~:u|:x{yut"));
 }
 #[test]
 fn readable_but_incorrect_is_not_english() {
 assert!(!english(
 "cOOKING\u{0}mc\u{7}S\u{0}LIKE\u{0}A\u{0}POUND\u{0}OF\u{0}BACON"
 ));
 }
}

Finally, we call it from the main program and crack the cipher.

src/main.rs

extern crate cryptopals;
use cryptopals::byte_array::xor;
use cryptopals::frequency;
use cryptopals::hex;
use std::iter;
fn main() {
 let secret =
 hex::to_bytes("1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736");
 println!("{:?}", crack_xor(&secret));
}
fn crack_xor(cipher: &[u8]) -> Vec<String> {
 let alphabet = 0..255u8; /* ascii/utf-8 range */
 alphabet
 .into_iter()
 .filter_map(|c| {
 let key = iter::repeat(c).take(cipher.len()).collect::<Vec<u8>>();
 let decrypted = xor(&cipher, &key);
 match String::from_utf8(decrypted) {
 Ok(s) => Some(s),
 Err(_) => None,
 }
 }).filter(|s| frequency::english(s))
 .collect::<Vec<String>>()
}
#[cfg(test)]
mod tests {
 use super::*;
 #[test]
 fn analysis_matches_bacon_message() {
 let secret =
 hex::to_bytes("1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736");
 let actual = crack_xor(&secret);
 assert_eq!(vec!["Cooking MC's like a pound of bacon"], actual);
 }
}