Over the past several months, I’ve started playing Google’s Ingress, a mobile-phone based video game which is cross between capture the flag and a militant version of foursquare. One of the key features of the game is “decoding” secret messages hidden in documents and media given to the players that can be redeemed for special supplies. This prompted an interest in what I call “puzzle cryptography”: identifying and solving puzzles which incorporate elements of classical cryptography systems. And as regular readers of this blog are aware, once we get interested: Python programs get written…
Puzzle cryptography is based on testing methods and spotting clues vs. a more formal “rigorous” approach to cryptography associated with military and security applications. You’re presented with a snippet of material – generally text or images containing text – and called upon to extract a code from that material. Many snippets would actually be viewed as unsolvable in traditional cryptography: they are too short for statistical techniques and usually designed to defeat letter frequency and word pattern analysis. They are, however, a lot of fun to fiddle around with. The purpose of this article is to walk you through some of the common types of “obfuscation” which can be done to a message using classical cryptography and introduce tools to make the process easier.
Classical pen and paper cryptography involves two key elements: letter substitution and transposition. Letter substitution involves remapping the letters of the alphabet to new cipher alphabet, such that A->Z, B->Y, etc. Transposition involves rearranging the order of the letters in the message in a systematic fashion such that an associate can unscramble them into the correct order later. Most classical cipher systems can be reduced to one or both of these concepts.
Let’s start with letter substitution, since that is the older of the two ideas and generally the focus of the simpler puzzles. The normal alphabet is mapped into a new cipher alphabet, either randomly or with a specific order which the cryptographer must solve. This can be done using a single cipher alphabet for the message (monoalphabetic) or by rotating through multiple cipher alphabets (polyalphabetic). Polyalphabetic ciphers are significantly harder to break since you are using a different alphabet mapping for each character in the message, usually in a cycle that repeats every X characters. Most puzzles use monoalphabetic ciphers; if you think you’re tackling a polyalphabetic cipher (usually a Vigenere cipher), look for additional clues about the key.
Our first monoalphabetic substitution cipher was developed by the Hebrews in 500 B.C. and is simply the alphabet written in reverse order. This is known as the Atbash Cipher or a reverse alphabet (solver here). A is mapped to Z, B is mapped to Y, etc. From a security perspective, this system is trivial to crack once you realize the puzzle is using it since there is only one key.
The Romans developed a slightly more advanced system, the Caesar cipher, which shifts every letter in the alphabet by X positions. This shift is known as the Caesar shift; Julius Caesar used a shift of three (A->D, etc.), his nephew Augustus (this first Roman emperor) used a shift of one. While this expanded the key space to a whopping 26 possibilities, it is trivial to break with a brute force attack (sample solver here). It did, however, work relatively well against Caesar’s enemies – many of whom were effectively illiterate and would dismiss the shifted writing as an arcane code.
A couple of hundred years later, somebody realized that if you scrambled the alphabet into semi-random order, it resulted in a really massive number of potential cipher keys. This gave rise to the simple substitution cipher: aka the mixed alphabet and deranged alphabet. Any letter can be mapped into any other letter in the cipher, requiring you to remember a full 26 letter “key” but providing a huge number of potential solutions that overwhelmed brute force attackers. This cipher alphabet could frequently be generated from a simple pass phrase (“we always meet at dawn”) – for a working example of this, check out our cipher workbench tool). In real world cryptology, these were a fairly strong defense until about 800 AD, when Arab mathematicians figured out how to use letter frequency statistics to break these codes.
If you have a large sample of real text, you can use frequency analysis and shotgun hill climbing optimization to break the code. These automated techniques are less effective for smaller samples and situations where the puzzle author intentionally manipulated the distribution of the letters (for example, limiting the number of E’s & A’s). For most puzzles, you need to use word pattern matching to solve the code. This involves focusing on the more obvious words to break a couple of letters, which you can then use to pry open the rest of the puzzle. Some good examples are: single letter words (usually A or I), two or three letter words (frequently conjunctions or possessive pronouns), or words with apostrophes. For more details on this approach to breaking a puzzle, check out our larger article here and Simon Singh’s frequency analysis table; we’ve also got a cryptogram helper that searches the dictionary for words with the same letter repetition pattern as the ciphertext you’re trying to solve:
The next significant advance in real world cryptography was the development of what were called nomeclatures, sets of words / symbols that replaced common phrases. This helped shorten message lengths and further obfuscated the meaning of the message. For example, one cipher word might refer the king of France, another refer to the Duke of Normandy, and the balance of the message would be spelled out, counfounding the prospective cryptographer. Keep your eyes peeled for repeated phrases, particularly if they occur in conjunction with specific real world events.
This was followed by the development of multi-alphabet ciphers, where the mapping of plaintext->ciphertext letters changes with your position in the message. The most common version of this is the Vigenere cipher, which was developed during the 1500’s and was considered relatively strong until the mid-1800s. This system uses a rotating table of 26 caesar shifted alphabets where the alphabet used changes as you advance through the message based on a key word (that repeats); for an example of this system in action, check here. This repetition was to be the undoing of the cipher; once you find the length of the key (using the index of coincidence) you can break the cipher into parts and attack each part individually using frequency analysis and other tools. This is a relatively hard cipher to attack without the aid of serious computing resources and lots of sample text; if you think you are attacking a Viginere cipher in the puzzle, look very carefully at the puzzle for extra clues that may help you guess the key.
Transposition ciphers were a later innovation. The early versions of the concept were physical: the Greek scytale, a standard diameter rod that a message paper could be wrapped around and written / read. These messages would be very difficult to read if intercepted. Letter based transposition ciphers were first mentioned by cryptographers in the early Middle ages and several systems have become common puzzle elements.
The first of these was the route ciphers, where a message was written to be read in a non-standard fashion. One example of this is the Rail Fence system where the user sets up a series of rows and writes the message as a zig-zag between the upper and lower rows. The rows are then stripped off and sent to the recipient. Other route ciphers involve working in a circle around a text, reading backwards, or in alternating directions. Grilles are a similar concept. For puzzle cryptography, this is an area where you should carefully inspect your material for clues about how the route cipher should function.
Column-row transposition is another common transposition cipher mechanism. In this method, the message is written out into rows, which are then rearranged by column using an order specified in the key. This would scramble the message without disturbing the distribution of the letters, generally defeating frequency analysis (for a working example of this, look here). A variant of this involves performing this operation twice; ciphers of this sort were used as field ciphers during the early-to-mid twentieth century. This is another relatively strong puzzle cipher where you should carefully look for clues about the possible key before brute forcing it…
Transposition ciphers can be attacked via several techniques (beyond key sleuthing and guessing, which are the likely approaches for most puzzle cryptography users). Large blocks of text encrypted using a transposition cipher will often display a letter distribution which is similar to the natural language. Small sections of the cipher can be split off and tested for anagrams – if you solve the underlying anagrams, it will provide you with clues about the potential order of the columns. One other weakpoint is that keys close to the correct key will produce significant chunks of legible plaintext (next to obviously scrambled words); this can be used as the basis for an optimization attack.
One interesting note is the systems above tend to get stronger when combined. For example, a system which combines a simple substitution cipher with a transposition cipher improves the resistance of both sub-systems to cryptanalysis. One common attack on substitution ciphers is to use a statistical optimization algorithm which looks at the distribution of letter sequences and compares them to English. One would expect a nearly-correct decryption to have a relatively high proportion of “ing” and “red” trigrams and a relatively low number of “zwk” and “qpl” trigrams. The column scrambling done by the transposition cipher component will reduce the effectiveness of this attack (since you no longer can see individual trigrams). Similarly, transposition ciphers can be attacked using anagramming: looking a sequences of letters to see what you can spell. The alphabet swapping effect of the substitution cipher makes it far more difficult for an analyst to identify anagrams in the text (since you don’t know the underlying letters).. Thus the two different components of the system serve to protect each other.
To end on an optimistic note, most puzzle ciphers are intended to be solved…so look for clues and just keep tinkering with them until you find a solution!