Simple Ciphers, and a little SpiderLabs Crypto Contest
Millions have died and millions have been saved because of cryptography. There is no telling what the world would be like today if cryptography never existed. Would the Roman Empire have conquered as much as it did without being able to conceal its vitally important messages from the enemy?. There is of course no telling how the history of the world would be rewritten if one single thing – in this case, cryptography – was removed. The ability to secretly communicate has always been an extremely important skill that has changed the tides of war and affected the stability of governments. This is one of the many reasons cryptography is a fascinating subject to me. It's power, the capacity to conceal meaning, is one of the most important powers anyone can have against their enemies.
Unfortunately, you can't jump right into the latest and greatest crypto without understanding the basics – substitution ciphers. Now, I believe most of the people who read this blog are at least somewhat familiar with the idea of substitution ciphers (the idea that A=C,B=D, etc), but it doesn't hurt to have a quick primer. I will talk about the actual cryptanalysis of this type of cipher, so as to build the important foundation of future crypto endeavors.
I'll be giving you an introduction to the two ciphers needed to solve the challenge at the end.
Substitution Cipher
This is one of the most well known types of cryptography inexistence. The most historical is the Caesar cipher. It's the idea that if you put two alphabets on top of each other and you slide the bottom one a certain number of characters in one direction, you now have a new representation of the top alphabet. Today, its typically known as a rotational cipher. ROT13 is an example.
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ
-Rotate the bottom alphabet 13 characters-
ABCDEFGHIJKLMNOPQRSTUVWXYZ
NOPQRSTUVWXYZABCDEFGHIJKLM
So, if there is an "A" in your message, it is now written as an "N". Simple, right? But with substitution ciphers, you're not limited to only sliding it in one direction; you can assign completely random associations to each letter:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
QYPWURIOENVBCMXZLAHGKSJDFT
So once you've banged your face on the keyboard and gotten apseudo random unique sequence of letters, you can start encrypting things. Technically the key size is about 88 bits (26!), which is a very large number of possible combinations. Due to this fact, people used to think (centuries ago)it was impossible to crack. So what gives? Why don't we still use substitution ciphers if the key is larger than SSL implementations some companies still have?
Because, as many men keep being told, key size isn't everything; it's what you DO with it that matters. Key size doesn't save the substitution cipher from ridicule. The cipher contains a certain pattern that can be easily picked out (by hand actually) as long as you know where to look. So the next time you hear someone say something along the lines of "Algorithm A is much safer than Algorithm B because A has 128 bits of security while algorithm B only has 64", try to quell the increasing rage and calmly explain the source of their ignorance.
As with most things historical no one truly knows the first person to discover that pattern in substitution ciphers, but we do know who wrote the earliest known text on the subject. A scientist in the ninth century with a super long name "Abu YūsufYaʻqūb ibn ʼIsḥāq aṣ-Ṣabbāḥ al-Kindī" realized that "Hey, you're only replacing one letter for another but the FREQUENCY of those letters is the same as the original text." And with that epiphany, it was discovered that with a sufficiently long text you can reliably map the encryption alphabet to the original alphabet by using the frequency of the occurrence of the letters. Guess what they called that type of analysis? Frequency analysis. Awesomely creative name, I know.
Frequency analysis is a great example of "thinking out side the box". The idea that the relative patterns/characteristics of the letters in the plaintext message are carried over to the ciphertext message; allow you to rather quickly decrypt the message.
What kinds of patterns/characteristics do I mean? Well, lets take English for example. The first pattern is that the frequency of letters inEnglish writing tend to follow a trend.
(credit: Wikipedia)
What if the text is too small for that particular pattern to show up? Well then, there are other patterns we can look for:
- How often do words start with a certain letter?
- How often do words end with a certain letter?
- What letters are used in words with 1 character?2? 3? 4?
- How many times does a certain letter appear next to another?
- If you think you have decrypted the word correctly, does it make sense in the rest of the message?
English, like most languages, has lots of rules. With those rules come patterns. If the only thing you change is the way the alphabet is displayed, you still haven't changed all the other patterns of the underlying message.
But that didn't change the fact that for hundreds of years, rulers and rebels alike were still using substitution ciphers. The ones with the better cryptanalysts were the ones that "won" those little communication battles.
Transposition Ciphers:
A transposition cipher is the idea that instead ofrearranging the characters of an alphabet to create some new "secret key alphabet" you are basically just rearranging the order of the original word,just like anagrams. The different transposition algorithms are basically descriptions of different ways to rearrange the message.
Just like substitution ciphers, transposition ciphers are very simple to visualize. For example, the Route cipher takes the following message "The kitten is in position" and rearranges the letters top to bottom, left to right; like so:
TI NI
HTI T
ETSPI
E OO
KNISN
And then you can write it out however you want, for example,straight left to right:
TI NIHTI TETSPI E OOKNISN
Simple to understand right? In order to decrypt it, the other side simply needs to do the reverse. Personally, transposition ciphers are my favorite since they are so easy to do by hand.
THE CHALLENGE
Ah, so now the part where I get to sit back, laugh, and pretend to know it all. At least until one of you discovers how to solve it and gets to claim the prizes.
I have come up with my own crypto algorithm (nothing fancy).As best as I could tell, I have not seen it anywhere else. I am calling this algorithm "The Triforce Cipher." Zelda fans may now applaud.
I can't tell you how this cipher works exactly because that would make it entirely too easy. But I can say a few things about it:
- It is both a transposition and substitution cipher at the same time.
- The name of the cipher is the only hint you should need.
- It's simple, I swear.
If no one is able to solve it, I'll release another hint after a few weeks. But remember, you are racing against everyone else, not only to solve the first ever Triforce Cipher, but to get the awesome prizes at the end. The decrypted data will tell you how to claim your prize. The first one to claim the prize will be celebrated on the twitters. Questions/concerns/lols may be sent to jmocuta@trustwave.com
The next post in this series will congratulate the winner(if there is one). As well as go into the cryptanalysis of this cipher. It will explain a few benefits, and the many problems with it. I wish you all good luck; D
Ciphertext:
RISCCELBGYDRJHSKEBSHEGZOQBGSUJUDSKQYQHJSJYQKEAYCDSCQFUDWYSDODY
SCYDZRJDLSHDBLSRXJMCEXSJUDSCEBLEDNEFYLSZEPZNMJCYTYFJESEBSJNHQJJD
YSRBLSTJEMZZSNQBSJUDSMFYQVDHSSSSJUDSYODHJSQHSGRYIRGDSZWNARICQTI
URZCHUAIZRHOSMRAIZOQRIACZRWHABLZASTVSCVSZCQMVSICZVSCIAZVSQVMICVS
ZCVMSICAZVSMCIZRSRZZ