Code-Breaking (Cryptanalysis): A Complete History

What Is Cryptanalysis: Complete Explanation

Cryptanalysis is a code breaking science that looks at different ways to decrypt encrypted messages without the secret encryption key.

The word “cryptanalysis” is a sandwich of two ancient Greek terms:

1. “Kryptós,” which means “hidden”
2. “Analýein,” which means “to analyze”

We could generalize even further and say that cryptanalysis is the study of any information system with the goal of uncovering the hidden information in the system. This is done using various mathematical tools to examine the information that is available.

While cryptanalysis focuses on studying methods of encryption in order to find out how they work and defeat them, cryptographers often use cryptanalysts’ research results to improve or replace solved encryption algorithms. Together, cryptanalysis and cryptography make up the science of cryptology.

What Are the Different Types of Cryptanalysis?

Generic Cryptanalysis

The three generic kinds of cryptanalysis are classified according to what information the cryptanalyst has. These include:

1. Ciphertext-only attacks
2. Known-plaintext attacks
3. Chosen-plaintext/ciphertext attacks

Ciphertext-only attacks are used when cryptanalysts only have the encrypted message to work with. These are performed with no information about the encryption algorithm, the plaintext or the cryptographic key.

Known-plaintext attacks can be performed to uncover the encryption key when cryptanalysts have both the ciphertext and its matching plaintext. One of the most common known plaintext attacks is linear cryptanalysis.

Chosen-plaintext and chosen-ciphertext attacks are each other’s opposite. These can be used when cryptanalysts have access to the encryption device itself. They can feed the device various chunks of chosen plaintext and compare these to their corresponding ciphertext or run pieces of ciphertext through the device and compare these to their decrypted plaintext. A common chosen-plaintext attack is differential cryptanalysis.

Brute Force Attacks

One of the first attacks discovered by cryptanalysts was the brute force attack. This method tries to defeat the cryptographic system by trying all possible keys, one after the other. Brute force methods can be used in ciphertext-only attacks or known-plaintext attacks.

Although it’s difficult to design a system invulnerable to brute force attacks, most encryption schemes nowadays are set up to make brute force computationally infeasible.

Symmetric and Asymmetric Algorithms

Besides the above generic attacks, many niche types of cryptanalysis are used to decipher specialized algorithms.

There are two main kinds of encryption ciphers, symmetric algorithms, which use the same key for encryption and decryption, and asymmetric algorithms, which use a shared public key for encryption and a secret private key for decryption. Of the two, symmetric algorithms are more popular because they’re quicker and easier to use.

The two most common attacks used to defeat symmetric ciphers include:

1. Differential cryptanalysis
2. Linear cryptanalysis

Differential cryptanalysis looks at two related pieces of plaintext that have been encrypted using the same key. Cryptanalysts analyze the differences between the texts using mathematical probability distributions to try to decipher the correct key.

Linear cryptanalysis can be used when there are enough corresponding pairs of plaintext and ciphertext available. Cryptanalysts go through these pairs using linear approximation to uncover clues about the key or information about the block cipher itself.

Side-Channel Attacks

Side-channel attacks don’t rely on ciphertext or plaintext at all. Instead of trying to find weakness in the algorithms themselves, side-channel attacks look for weaknesses in the implementation of the algorithms.

Common side-channel attacks include:

• Timing cryptanalysis
• Power cryptanalysis
• Electromagnetic cryptanalysis
• Acoustic cryptanalysis

Timing cryptanalysis looks at how long the system takes to compute certain queries. Power cryptanalysis looks at how much power the system uses for a given query. Electromagnetic cryptanalysis tries to uncover relevant information by studying how much radiation the system emits.

Acoustic cryptanalysis studies the sounds the system produces. There are acoustic cryptanalysis attacks that attempt to reconstruct specific keystrokes by listening to the different sounds made by the keys. It’s also sometimes possible to decipher important clues about the system by measuring the sounds made by its electronic components.

What Are Some Examples of Cryptanalysis (Code Breaking)?

Al-Kindi’s Frequency Analysis

The first example of cryptanalysis that we know about from history came in the 800s from an Arabic polymath named Al-Kindi. Al-Kindi was able to solve simple monoalphabetic substitution algorithms, which just replace one letter of the alphabet with another, using frequency analysis.

He realized that the average number of times a given letter appears in an average text would stay the same when you substituted it for a different letter. For example, in an average English text, the most common letter, “e,” tends to make up about 12% of the text. If you analyze one of these letter replacement ciphers and find that the letter “g” makes up around 12% of the text, you can be pretty sure that’s the letter that was substituted for “e.”

Bletchley Park’s Crack Team

Another famous example of cryptanalysis was Bletchley Park, which we’ll talk more about later, where Alan Turing and his team cracked the Enigma code using a combination of frequency analysis, brute force and other attacks.

Brute Force Attack on the DES

In 1998, the U.S. Government adopted an encryption algorithm called the Data Encryption Standard (DES). It remained their official cipher for almost 40 years, until cryptanalysts brought it crashing down.

A team of white hats developed a machine they called “Deep Crack,” which used a brute force attack that could try one million DES keys every microsecond. It only took a few hours to test every possible key and break the DES algorithm wide open.

Their success forced the government to replace the DES with a more robust cipher, the Advanced Encryption Standard (AES). The AES uses keys that contain enough bits to make it computationally unfeasible to brute force in any reasonable time scale with the computers that are currently available.

Code Breaking Games and Puzzles

Mastermind

A quick and simple two-player war of strategy, Mastermind was the original code breaking game and is still a bestseller in the game aisle. Player One, the “Codemaker,” makes a four-bit pattern out of six possible peg colors, and Player Two, the “Codebreaker,” tries to deduce the pattern within 10 tries. Even with the provided feedback from the Codemaker, you’ll still need all your powers of deductive reasoning to figure out the right combination out of the 2,000 possible patterns.

Bletchley Park Brainteasers

For fans of the Bletchley Park story, if you think you could have helped Turing unravel the Enigma machine, try your hand at some of the brain twisters in this paperback. Had they been around today, Turing and team may have used some of these codes, crosswords and complex puzzles to help recruit great minds for the war effort. The enigmas in this book are brain stimulating and surrounded by fascinating stories of cryptanalysis.

The Room Three

If you’d rather go digital, this puzzle game for your smartphone immerses you in a rich world full of mind-bending mental trials. The 360-degree gameplay is based on an addictive storyline full of coded items you can pick up with your touchscreen and solve with your powers of logic.

Bletchley Park: A Codebreaking HQ in WWII

Bletchley Park was a complex established by the British government during World War II to help the war effort via cryptanalysis. This was where Alan Turing, accompanied by the smartest people the British government could find, worked to decode secret messages from the Axis alliance. These included messages encrypted with the German Enigma, Tunny and Fish ciphers as well as a few algorithms spun by the Japanese and Italians.

During the early years of World War II, Bletchley Park held around 200 cryptanalysts. As the war progressed, it bloated to almost 9,000 people. These were both service personnel and civilians recruited via cryptic messages and puzzles in newspaper ads across Britain. Experts believe that the war may have ended two years earlier than it otherwise would have, thanks to the efforts of these cryptanalysts. Bletchley Park saved millions of lives and gave birth to modern computing technology.

Cracking Enigma

Enigma was a class of cypher machines that used a combination of electronic and mechanical processes. It had two main segments, the rotors and the plugboard, which worked together to scramble plaintext messages into doubly-encoded ciphertext. The configurations of both segments were changed once a day at the stroke of midnight. The Wehrmacht (German army) was confident the Enigma machines were uncrackable.

The rotor segment ran each letter in a text through three separate rotors then reflected it back through the rotors a second time. This shuffled the alphabet in a peculiar way that made frequency analysis impossible because multiple instances of any given letter were never substituted with the same letter. The rotors only had around 100,000 total combinations, however, which were few enough to make a brute force attack feasible.

The plugboard segment connected pairs of letters and flipped the individual letters in the pairs both before and after the message passed through the rotor segment. The plugboard could be broken with frequency analysis because letter pairings remained the same, but with around 150 trillion possible combinations, brute forcing it was impractical.

These two segments combined into one machine made all the most common cryptanalysis attacks of the time unworkable.

To crack it, Turing and his team at Bletchley Park built on the work of Polish cryptanalysts who had found a way to disentangle the effects of the two segments. They were able to do this based on the Enigma cipher’s one glaring flaw: Any given letter could be converted to any other letter except itself.

As the war progressed, German intelligence found ways to make the Enigma machines more and more difficult to crack. Turing et al responded by developing rudimentary computers based around transistors, which they called “bombes.” These allowed their cryptanalysts to keep up with the German cryptographers, and modern computing was born.