Simple Ciphers, and a little SpiderLabs Crypto Contest

Millions have died and millions have been saved because ofcryptography. There is no telling whatthe world would be like today if cryptography never existed. Would the Roman Empire have conquered as much as it didwithout being able to conceal its vitally important messages from the enemy?. Thereis of course no telling how the history ofthe world would be rewritten if one single thing – inthis case, cryptography – was removed. The ability to secretly communicatehas always been an extremely important skill that has changed the tides of war andaffected the stability of governments. This is one of the many reasonscryptography is a fascinating subject to me. It's power, the capacity to conceal meaning, is one of the most importantpowers anyone can have against their enemies.

Unfortunately, you can't jump right into the latest andgreatest crypto without understanding the basics – substitution ciphers. Now, Ibelieve most of the people who read this blog are at least somewhat familiarwith the idea of substitution ciphers (the idea that A=C,B=D, etc), but itdoesn't hurt to have a quick primer. I will talk about the actual cryptanalysisof this type of cipher, so as to build the important foundation of futurecrypto endeavors.

I'll be giving you an introduction to the two ciphers neededto solve the challenge at the end.

SubstitutionCipher

This is one of the most well known types of cryptography inexistence. The most historical is the Caesar cipher. It's the ideathat if you put two alphabets on top of each other and you slide the bottom onea certain number of characters in one direction, you now have a newrepresentation of the top alphabet. Today, its typically known as a rotationalcipher. 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 withsubstitution 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 apseudorandom unique sequence of letters, you can start encrypting things. Technicallythe key size is about 88 bits (26!), which is a very large number ofpossible 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 substitutionciphers if the key is larger than SSL implementations some companies stillhave?

Because, as many men keep being told, key size isn'teverything; it'swhat you DO with it that matters. Key size doesn't save the substitution cipherfrom ridicule. The cipher contains a certain pattern that can be easily pickedout (by hand actually) as long as you know where to look. So the next time youhear someone say something along the lines of "Algorithm A is much safer than Algorithm B because A has 128 bits ofsecurity while algorithm B only has 64", try to quell the increasing rage andcalmly explain the source of their ignorance.

As with most things historical no one truly knows the firstperson to discover that pattern in substitution ciphers, but we do know who wrote the earliest known text on thesubject. 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 theFREQUENCY of those letters is the same as the original text." And with that epiphany, it was discovered that witha sufficiently long text you can reliably map the encryption alphabet to the originalalphabet by using the frequency of the occurrence of the letters. Guess whatthey called that type of analysis? Frequencyanalysis. Awesomely creative name, I know.

Frequency analysis is a great example of "thinking outsidethe box". The idea that the relative patterns/characteristics of the letters inthe plaintext message are carried over to the ciphertext message; allow you torather quickly decrypt the message.

What kinds of patterns/characteristics do I mean? Well, letstake 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 toshow 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 nextto 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. Withthose rules come patterns. If the only thing youchange is the way the alphabet is displayed, you still haven't changed all theother 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 withthe better cryptanalysts were the ones that "won" those little communicationbattles.

TranspositionCiphers:

A transposition cipher is the idea that instead ofrearranging the characters of an alphabet to create some new "secret keyalphabet" you are basically just rearranging the order of the original word,just like anagrams. The different transposition algorithms are basicallydescriptions of different ways to rearrange the message.

Just like substitution ciphers, transposition ciphers arevery simple to visualize. For example, the Route cipher takes the followingmessage "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, theother side simply needs to do the reverse. Personally, transposition ciphersare 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, andpretend to know it all. At least until one of you discovers how to solve it andgets 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 thisalgorithm "The Triforce Cipher." Zelda fans maynow applaud.

I can't tell you how this cipher works exactly because thatwould make it entirely too easy. But I can say a few things about it:

  • It is both a transposition and substitutioncipher at the same time.
  • The name of the cipher is the only hint youshould need.
  • It's simple, I swear.

If no one is able to solve it, I'll release another hintafter a few weeks. But remember, you are racing against everyone else, not onlyto solve the first ever Triforce Cipher, but to get the awesome prizes at theend. The decrypted data will tell you how to claim your prize. The first one toclaim 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 willexplain a few benefits, and the many problems with it. I wish you all good luck;D

Ciphertext:

RISCCELBGYDRJHSKEBSHEGZOQBGSUJUDSKQYQHJSJYQKEAYCDSCQFUDWYSDODY

SCYDZRJDLSHDBLSRXJMCEXSJUDSCEBLEDNEFYLSZEPZNMJCYTYFJESEBSJNHQJJD

YSRBLSTJEMZZSNQBSJUDSMFYQVDHSSSSJUDSYODHJSQHSGRYIRGDSZWNARICQTI

URZCHUAIZRHOSMRAIZOQRIACZRWHABLZASTVSCVSZCQMVSICZVSCIAZVSQVMICVS

ZCVMSICAZVSMCIZRSRZZ

Trustwave reserves the right to review all comments in the discussion below. Please note that for security and other reasons, we may not approve comments containing links.