For the entire day I had the pleasure of trying to break what I will call an *Alternating Substitution Cipher*. Let me explain.

# Cipher Internals

Given our plaintext “example” we will encrypt it using two Simple Substitution Ciphers. One cipher will be applied to the letters in even positions (“xml”) and another cipher applied to the letters in odd positions (“eape”). When determining which cipher to use to encrypt a letter you alternate from the previous cipher used, hence *Alternating Substitution Cipher*.

But how do you break this cipher?

# Breaking Simple Substitution

Breaking a simple substitution cipher is not too difficult, you can use letter frequencies and the dependencies between letters to reverse engineer the key and break the decryption. You can even automate this process, here is a snippet of code from lantern which does that:

# Breaking Alternating Substitution

Automating the breaking of *Alternating Substitution* is difficult but not impossible. The difficulty here is that you are restricted to only letter frequencies, dependencies between letters are broken due to the alternation. Given enough ciphertext and a well tailored frequency distribution to compare against, we can break it. Here is my lantern code to do so:

Yep, 4 lines. We separate the ciphertext into two columns and crack each substitution cipher separately, scored using chi-squared against a custom distribution. Once cracked just combine the plaintexts back together.

## Warning!

`custom_distribution`

can and will hurt you. Since you don’t have the luxury of letter dependencies this distribution must be incredibly accurate. Small variations can significantly affect the accuracy of decryption.

## How did you find the correct distribution?

To be honest I cheated. I ended up solving the cipher by hand then using the plaintext to form the distribution in order to automate the breaking of the cipher.

## Well gee, what if I can’t do that?

That’s where I’m still thinking. I could make lantern provide different distributions to use without a user needing to find and tailor their own. This may help is certain scenarios but obviously not all.

My best solution for this is to implement a two step solution. First is to have code to fiddle with the key found through automation. Since it could have matched on an inaccurate distribution, swapping around letters from the target distribution could move the decryption closer to the correct solution. Secondly, implement a manual decryption terminal session which starts off from the previous automated data. Basically giving you the best head start possible while you fiddle with the keys to crack the cipher.

**Update**:
I wrote an algorithm which breaks it automatically! It’s not 100% accurate though, some manual tweaking is needed at the end. Essentially it’s a 3 dimensional hill climb that scores based on the combination of the individual ciphers. This way we can use letter dependencies to get much more accurate results. I may make it into a module into lantern. We will see how it organically grows over time.

You can see the script to solve this here: https://gist.github.com/CameronLonsdale/d8ea9d199b057125bf9ed95a59802354. This code supports more than just two subsitution ciphers, therefore it breaks the class of encryption known as *Periodic Subsitution Ciphers*.

# Try Yourself

Here’s the cipher in case you want to try! If you use lantern let me know how it goes!