A Very Brief History of Cryptography

The inventions of language, writing, and secrets led to the inevitable invention of cryptography, and its nemesis cryptanalysis.

Magic

Language is magic: It allows us to transfer thoughts from brain to brain. Writing is another kind of magic. It lets us transfer thoughts from brain to brain, even if the brains are far away from each other, or do not even exist at the same time! It does this by freezing the language in time, in a format that endures far better than brains do. It is really quite impressive, for a species that only recently came down from the trees, and is still pondering whether it would have been smarter to stay up there.

Secrecy

Sometimes you want to be selective about whose brains you transfer your thoughts to. With spoken language, you would e.g. make sure Thag is not around when you suggest to Grok that you will both have Thag’s pet mammoth for dinner (while hoping Grok is hungry enough to agree to this prospect, and not, say, pass your thought on to Thag’s brain).

With writing, the challenge is more complex. You may trust that your dear nephew Lucius will not open your letter, but deliver it to the garrison commander in Lutetia as promised. Though can you trust that he won’t be intercepted by those Gauls and have the writing forcibly and vigorously taken from him? Once the letter is out of your hands, the recipients are out of your control. We need a way to write things that only some people can read.

Cryptography

The art of cryptography is surprisingly old. It’s been used to protect trade secrets 3500 years ago. Julius Caesar used an easily explained form of encryption 2000 years ago: He replaced every letter with the one that comes 3 places after it in the alphabet, so that LEGION is written as OHJLRQ. The trick had been explained to the recipient in advance, and with that knowledge they could easily decrypt what looked like gibberish to anyone else. This is a simple form of substitution cipher. These days you can find it in books for children, though back then it was a military secret.

The encryption key you need to unlock the Caesar cipher is “3 places after”. We’ve shifted the alphabet 3 places. Another simple cipher is to reverse the alphabet, this is used in the Bible. Yet another is to choose a string of text for our key, and use that as the start of our reordered alphabet, filling in the remaining letters in order. If our key is “IBEXA”, then our alphabet is “IBEXACDFGHJKLMNOPQRSTUVWYZ”. Using the Ibexa key we can decrypt “Btgkxgmd lalnqibka awoaqgamear. Cirsaq. Sndasfaq.” to “Building memorable experiences. Faster. Together.” You can play with such ciphers here, for example.

Cryptanalysis

Just as predator and prey influence each other’s evolution, so does cryptography and cryptanalysis. Once you know how to encrypt something you don’t want others to know, you start thinking about ways to decrypt things that others don’t want you to know. It’s not obvious how to get from “sndasfaq” to “together” if you don’t have the key and you only have that one word, but if you have several sentences worth of such gibberish, there are ways of figuring it out.

We humans are pretty good at pattern recognition. Language is full of patterns, and while the simplest substitution ciphers replace all the letters, they leave the patterns intact. In typical English, the most common letter is E, then T, then A. You might count all the letters in the encrypted text, and find that the most common ones are G, Y, and O. Try to replace them with E, T, A, and see if the gibberish makes a little more sense now. And so on.

This frequency analysis can be time consuming, but Caesar’s cipher doesn’t stand a chance against it. In the 800s, the Arab thinker Abu Yūsuf Yaʻqūb ibn ʼIsḥāq aṣ-Ṣabbāḥ al-Kindī wrote a book on such methods. Al-Kindi may have been the first methodical cryptanalyst. He was also a classical polymath, working on philosophy, Islamic theology, logic, ethics, mathematics, physics, chemistry, psychology, pharmacology, medicine, metaphysics, cosmology, astrology, and music theory, and that’s not even all of it.

Computers change everything

Still, Al-Kindi was only human. With the help of computers, such simple ciphers can be cracked in the blink of an eye, and these days they offer no security at all. To do better we must hide the recognisable patterns, for a start. And time is essential. Any cipher can be cracked if you have infinite time. A good cipher takes a long time to crack when you don’t have the key, yet is quick when you have it. But computers keep getting faster, so we have to make our encryption stronger and stronger to keep up. It’s a never-ending battle.

The problem is similar with hashing, hashes must be made more and more computationally expensive (take a long time) to crack. PHP’s password_hash(), which we use in eZ Platform, is designed to change over time as new hashing algorithms become available. And then we’re back in the Middle East long ago, because “algorithm” comes from the name of Muhammad ibn Musa al-Khwarizmi, born a few years before Al-Kindi.

اَلْعَرَبِيَّةُ, हिन्दी, Ελληνικά, 漢語, ?

In closing, here’s a little trick: Have you ever wanted to register at some website, and discovered that they have a password limitation like “passwords must be 8-10 letters long”? That’s too short to be safe these days, too easy for a computer to crack. So apart from not registering, what can you do? It’s not just about length, but also complexity. Mixing numbers and symbols into your password makes it more complex. But we can do even better.

If we’re lucky and all UTF-8 characters are allowed, we can insert random letters from nearly any language, including emoji, not just the Latin alphabet. With maximum 10 characters and over a million UTF-8 code points to choose from, we can make some 2.89 x 10^60 different passwords. That’s a lot. It’s comparable to a 34 characters long password made only of a-z, A-Z, and 0-9. You may find it difficult to type "9둾ֶ"ዽ풘⏱۲ͼ 搖", but that’s what password managers are for. You’re using one, aren’t you?

An exercise left for the reader: Generate a cryptographically secure random UTF-8 string, x characters long.

Please remember our guidelines for safely reporting security issues in eZ Systems products, and do the same for other vendors. Until next time, stay safe!