0. Introduction

0.0 The Pitch

XORcism is a FOSS command-line tool that breaks "rotating xor" style ciphers. It is written in Rust, with a moderate emphasis on test cases, parallelism, running time and memory efficiency. XORcism takes about 6 seconds on a standard laptop to decrypt a bible that's been encrypted with a 975-byte key, which you're invited to try for yourself (xorcism tora_cipher_975.bin).

Xorcism can operate in two modes:

Simple, non-interactive mode (the default)
Interactive mode that proposes multiple solutions, in decreasing order of likelihood

Xorcism supports both xor and modulo-2^32-addition based encryption. Support for modulo-947 multiplication can easily be added, if that sort of thing ever becomes popular.

Usage

Basic CLI usage is simple and blunt: xorcism <INPUT_FILE> will print the most likely decryption to stdout.

To use xorcism as an external crate in your own project, decide if you trust this repository, and if you do then add the following under [dependencies] in your Cargo.toml:

xorcism = { git = "https://github.com/BenH11235/XORcism.git"}

Then you can do, for example:

extern crate xorcism;

use xorcism::crypto::vigenere::{encrypt,decrypt};
use xorcism::utils::xor;
fn main() {
    let pt = b"HELLOWORLD";
    let key = b"key";
    let ct = encrypt(pt,key,&xor);
    let pt2 = decrypt(&ct,key,&xor);
    println!("{}",String::from_utf8_lossy(&pt2));
}

Note that this project has not yet been updated to support newer Rust editions, so opt out by deleting the appropriate line from your Cargo.toml.

0.1 The Anti-Pitch

XORcism solves a long-solved entry-level cryptographic problem. This is a problem you're introduced to in lecture 3 of crypto 101, and for which you could probably get a serviceable solution by running a Google search for "Vigenère cipher decryptor", clicking "view source" on the first result and making some minor modifications to the Javascript that appears. It contains a long apology about how it doesn't work for many interesting cases, and why the authors could not provide better guarantees on the output.

0.2 The algorithm in a nutshell

The method used is similar to the one used by the first person to ever break this kind of cipher, with some "enhancements" we had to introduce to get the thing to work. The steps are:

Pick maximum key length that still means ciphertext can be decrypted in theory (unicity distance) and won't take more than about 10 seconds for the entire decryption process
Score key lengths using coincidence counting, using a 95% confidence interval score; penalize lengths for having a divisor with a high score
Pick candidate key length $k$. Parition ciphertext into $k$ parts and brute-force each part assuming a single-character key, looking for the most likely candidate plaintext.
Re-assemble the plaintexts into a large plaintext.
If the end user is not satisfied with the result, try again for the next most highly scored key length.
Repeat until out of key length, or user hits ctrl+C in anger.

1. When to expect a decryption failure

This is a list of known ciphertexts that XORcism will fail to decipher.

High-entropy plaintext distributions -- You can't decrypt encrypted line noise, because there's no way to tell apart the legitimate decryption from, well, line noise. The same principle applies to compressed files, and to some degree, to hexadecimal digits and base64 (though those are included in the binary for educational purposes). Try to decrypt anything with -p uniform and see what happens.
Binary data -- as a direct result of the above. We're planning to toy with some approaches to this; it may be more tractable, because binary data tends to have more structure than proper line noise.
Any ciphertext where the key size is over 1000, due to the stop-gap performance mitigations mentioned in section 4.2.1.3.
Tried to run XORcism on some ciphertext, didn't get the result you want? Open an issue.

2. Usage

USAGE:
    xorcism [FLAGS] [OPTIONS] <INPUT_FILE>

FLAGS:
    -h, --help                Prints help information
    -n, --interactive-mode    Turns on interactive mode (suggests solutions and writes to output file)
    -V, --version             Prints version information

OPTIONS:
    -c, --combination-function <COMB_FUNC>    Sets the assumed f where f(key_byte, plain_byte) = cipher_byte [default:
                                              xor]  [possible values: xor, add_mod_256]
    -k, --key-distribution <KEY_DIST>         Sets the assumed distribution of the key characters [default: uniform]
                                              [possible values: shakespeare, base64, hex, uniform]
    -o, --output_file <OUTPUT_FILE>           Sets the output file to write to [default: xorcism.out]
    -p, --plaintext-distribution <PT_DIST>    Sets the assumed distribution of the plaintext characters [default:
                                              shakespeare]  [possible values: shakespeare, base64, hex, uniform]

ARGS:
    <INPUT_FILE>    Sets the input file to use

3. Why did you write this?

It seemed like a good way to get better at Rust.
We took note of Halvar Flake's Keynote Talk at SSTIC 2018 where he argues that tools in the RE community are closed-source, closed-binary, unit-test-free, memory-inefficient, throwaway single-threaded python "frameworks" with zero interoperability or separation of concerns, full of "deadline is tomorrow" hacks, written to check a box for a presentation that's full of non-reproducible examples and non-applicable hyperbolic claims. We tried, Halvar.

4. Technical Details

4.1 Overview of the cipher

The modern rotating xor is a form of what's classically known as a "Vigenère cipher", after Blaise de Vigenère, a French cryptographer who did not invent it in the 16th century. The cipher is described by the following formula:

\text{Enc}(k,p)_i = p_i \oplus k_{i\ \mod |k|}

The use of the xor function is a modern artifact; the original version used some oldfangled function called a tabula recta where English letters were treated as the numbers 0 to 25, and encryption was simple addition modulo 26. In truth, one can use any function $f(\text{keychar},\text{plaintextchar})$ with the property that $f(k,f(k,p))=p$, and the principle remains the same.

The Vigenère cipher resisted decryption for hundreds of years, which earned it the Bond villain nickname le chiffre indéchiffrable (the unbreakable cipher). Finally, in 1863, German cryptographer Friedrich Kasiski produced a cryptanalysis for it. The cryptanalysis proceeds as follows:

Figure out the key length $|k|$ using statistical properties of the ciphertext
Partition the ciphertext into $|k|$ parts based on the key character that was used during encryption (so for instance, if the key is 4 characters long, it will be partitioned into 4 parts -- the first with indices 0, 4, 8...; the second with indices 1, 5, 9...; the third with indices 2, 6, 10...; and the fourth with indices 3, 7, 11...).
Cryptanalyze each part separately
Re-assemble the cryptanalyzed parts

Steps 2 and 4 are trivial, and do not involve any analysis; the cryptographic work is done in steps 1 and 3.

4.1.1 "The largest kappa value"? Don't you mean the one closest to the plaintext distribution?

Yes, in theory. The thing is, searching for the highest kappa will always work, AND will sometimes work when doing the theoretical "right thing" would have failed.

For sane input, partitioning with the correct key length will preserve the plaintext kappa, while partitioning with the wrong key length will, very probably, result in a lower value. This is why Kasiski's method works in the first place. So, we can expect a search for the highest kappa to work just as well as a search for the exact kappa, unless we're dealing with adverserial input (which we probably aren't, and this is out of scope, out damned spot, etc etc).

Conversely, however, searching for the "correct kappa" will fail if we're convinced that the plaintext distribution has a higher kappa than it actually does. This can happen very easily, considering that we don't really know where the ciphertext even came from, and the "plaintext distribution" is, by necessity, an educated guess.

For example, the "Shakespeare" distribution used for breaking the pitch example and the "full break test" example has a kappa value of about 0.08, but the actual plaintexts have a kappa value of about 0.06. If we had insisted on an exact match for the kappa value, the decryption would fail. We could use a different distribution with an adjusted kappa value of 0.06, but then the plaintext might, unbeknownst to us, actually have a kappa of 0.04, and we're back where we started.

To sum it up, in this case there are strong theoretical reasons to do the theoretically incorrect thing, as it basically results in a free win. Somewhere a mathematician is crying.

4.2 Details of cryptanalysis

4.2.1 Recovering the key length

Kasiski's original strategy was looking for repeated strings in the ciphertext. He reasoned correctly that if a string repeats in the ciphertext, this is probably a result of the same plaintext bytes being encrypted by the same key bytes, given that the alternative is an unlikely coincidence.

A related, more modern method is guessing a key length $k$ and then examining the statistical properties of the individual partitions. If the key guess is correct, the partitions are expected to have statistical properties that

XORcism

Install / Use

README