A few months ago I wrote a definitive guide to Cryptographic Key Management. In it I wrote a section: A Brief History - the Need for Encryption Key Management. I wanted to expand upon the Classical Era of cryptography a bit because the story of data security goes back for millennia, and the twists and turns of this story can be felt even today.
Introduction
There has been a competition playing out through the centuries all the way from the highest corridors of power down to the shadiest back alleys. It is a struggle of those with a secret and those who want to uncover it. It is the story of cryptography and cryptanalysis.
As with every competition, each side is constantly trying to outfox the other. Peter Baofu described the competition this way, it is “the never ending cycle of replacing old broken designs” of cryptography and “new cryptanalytic techniques invented to crack the improved schemes.” In fact, “in order to create secure cryptography, you have to design against [all] possible cryptanalysis.” This means that both sides are in a never-ending arms race.
In his book, “The Future of Post-Human Mass Media,” Peter Baofu describes two main types of cryptanalysis: Classical and Modern Cryptanalysis. Let’s take a look at the Classical Period to see how this cat and mouse game has played out through the centuries:
The Classical Cat-and-Mouse Game
Classical Cryptography
One of the earliest forms of “secret writing” is the Substitution Cipher where each letter of the message is systematically replaced by another set of predetermined letters. In it’s most famous form, the Caesar Cipher, used by Julius Caesar himself (1st century, B.C.E):
“each letter in the plaintext is 'shifted' a certain number of places down the alphabet. For example, with a shift of 1, A would be replaced by B, B would become C, and so on.”
Another technique was Steganography, which literally means: “covered writing,” is the art of concealing a message in plain sight. Mehdi Khosrowpour recounts one of the first recorded instances (in the 5th century, B.C.E):
“Demaratus, a Greek who lived in Persia, smuggled a secret message to Sparta under the cover of wax.” It “ was to warn Sparta that Xerxes, the King of Persia, was planning an invasion ... by using his great naval fleet. He knew it would be very difficult to send the message to Sparta without it being intercepted. Hence, he came up with the idea of using a wax tablet to hide the secret message. In order to hide the secret message, he removed all the wax from the tablet, leaving only the wood underneath. He then wrote the secret message into the wood and recovered the tablet with the wax.”
Classical Cryptanalytic Response
While steganography is only hard to crack if you don’t uncover the message; substitution ciphers were meant to remain a secret even if the message fell into enemy hands. It remained a fairly reliable means of securing messages, so long as the cipher was not revealed.
All that changed with the first recorded technique of cryptanalysis: Frequency Analysis. This technique “can be traced back to the 9th-century [C.E.], when the Arabian polymath Abu Yusef Yaqub ibn Ishaq Al-Kindi (also known as ‘Alkindus’ in Europe), proposed in A Manuscript on Deciphering Cryptographic Messages.” It comes from the observation that certain letters appear more often than others in a given language (the letter “E,” for example, occurs most often in English). There also also common letter pairings (like “TH” in English).
So, in the case of the Caesar Cipher where the plaintext message is :
meet me at the theater
If each letter is shifted one letter in alphabet, it becomes:
nffu nf bu uif uifbufs
Frequency analysis would note that the most common letter in the ciphertext is “f” (which would suggest it is an “e”) and only letter pairing is “ui” (which would suggest the “u” is “t” and the “i” is “h”). If we replace these portions of the ciphertext we reveal:
_eet _e _t the the_te_
With these two facts of frequency analysis alone we have more than half the message deciphered. With a few logical leaps we could decipher the remaining the five letters. The simple substitution cipher was rendered useless.
The Classical Cryptography Counterattack
 |
Over the centuries other ciphers were introduced like the Polyalphabetic Substitution Cipher where a repeating, offset key is used to encrypt the plaintext (see picture, courtesy of the Library of Congress). First perfected by Johannes Trithemius in 1518 (although other variants existed beforehand), the person encoding the message would switch alphabets for each letter of the message.
So, “meet me” would now become: “lcbp gy,” a ciphertext that simple frequency analysis could not break since most of the letter and pairing statistics of a given language are not easily recognized.
Although, in time, this type of cryptography was broken by the likes of Charles Babbage using modular arithmetic, the existence of his cryptanalytic techniques remained a military secret for some years.
Final Thoughts
Fascinatingly, it was the use of math to break a cipher that led to our current arms race in data security. The use of math and algorithms to break cryptography means you need longer keys to encrypt the data and prevent a brute force attack; which, in turn, means you need faster computers to break the encryption; which, in turn, means you need longer keys; etc.
Unlike today, however, it took centuries to break a cipher back then. Now, it is just decades. From the Hebern Electric Super Code Cipher Machine in the 1920s, to the Enigma Machine of the 1930s and 40s, to the Data Encryption Standard (DES) of the 1970s and 80s, each seemed invincible until enhanced cryptanalytic techniques or greater computing power toppled it. Our current cryptography is reliable and secure, but quantum computers loom on the near horizon and their non-binary logic could brute force attack our current public key cryptography and make them insecure.
And so the arms race continues. Fortunately, NIST has already forecasted this threat and called for replacements to our current standards, well before it is a crisis.
