We have a winner! @TimoHirvonen
Congratulations Timo! His gift will be a TrustwaveSpiderlabs goodie package which includes a Trustwave cinchpack, the latestSpiderlabs tshirt, several stickers, a Throwing Star LAN Tap, and an exclusive Spiderlabs challenge coin.
There were many that came very close, and a few who quitJUST before they would have gotten the answer. I cringed every time I saw ithappen. Timo was gracious enough to write up how he solved the cipher, it'spasted verbatim below:
On Monday I noticedthe blog post with SpiderLabs Crypto Contest hints. I googled Triforce andfound this image: http://en.wikipedia.org/wiki/File:Triforce.svg. I calculated the length of the ciphertext, and it turned out to bedivisible by three (273=3*91). Moreover, 91 equals to 1 + 2 + … + 13 so it ispossible to format the ciphertext into three triangles that have one characteron the first row, two on the second, etc.
I split the ciphertextinto three chunks and formatted each chunk into a triangle. The hints told tolook for uniqueness after thetransposition, and one of the tweets (https://twitter.com/atucom/status/289974039794040834) said "look for the side that is unlike the others". None ofthe sides were unique so I clearly did something wrong. However, I did realizethat the length of the long side (2*13) conveniently equals the size of theEnglish alphabet.
Then I noticed thistweet (https://twitter.com/atucom/status/290289441153626113): "left to right, top to bottom". I kept the top triangle but changedthe bottom two: I put the 92nd letter to top of the bottom left triangle, 93rd to the top of the bottom right triangle, then94th&95th to left, 96th&97thto right, and so forth. This transposition had the uniqueness I was lookingfor: the left side of the large triangle was a permutation of the Englishalphabet (RICLDKGUQAWZXBEFPYHJMONSTV).
It was easy to guessthat the permutation of the alphabet is most likely the key for thesubstitution cipher. So I replaced R with A, I with B, etc. The resultingplaintext was clearly English, I just replaced all occurrences of letter X withspaces to make it more readable.
Over the span of the contest I released several hints. Theyare below:
- Blog Hint #1 It is both atransposition and substitution cipher at the same time.
- Blog Hint #2 The name ofthe cipher is the only hint you should need.
- Blog Hint #3 It's simple,I swear.
- Blog Hint #4 It's called the Triforce Cipher,not Sierpinski's Triangle Cipher.
- Blog Hint #5 I introducedtransposition and substitution in the blog because thats what the cipher uses.More accurately, Transposition THEN substitution.
- Blog Hint #6 Once you solve thetransposition, look for uniqueness.
- Blog not-so-hint #1 I said thecipher was simple, I didnt say it was easy ;)
- Blog Hint #7 There are no spaces inthe answer, just letters.
- Blog Hint #8 Keep an eye on @atucomon twitter, I may release a couple more hints in the near future.
- Twitter Hint #1 Once you transposeit correctly, look for the side that is unlike the others.
- TwitterHint #2 the transposition is inspired by normal English. Left to right,top to bottom.
Using these hints, most people can derive the following:
- You have to perform a transposition operationfirst, and then substitution
- The transposition cipher is somehow a Triforce
- The plaintext only contains letters, no spacesor numbers or fancy stuff.
- A certain "side" of the Triforce is special forsome reason
- You arrange the transposition the same asEnglish
This was the ciphertext I gave in the first blog post:
Using the ciphertext, you write it out into the shape of aTriforce:
So now that we have transposed it properly, one of the sidesis special somehow. Well, if you look at the sides of the Triforce, there isone side that is different than the rest. Can you see it?
How is it different than all of the other sides? It's theonly side with one instance of every letter. No duplicates at all on that side.Why does that matter? Well, if you count how many letters there are, you wouldcount 26 letters. Guess what else has 26 letters? The English Alphabet.
If you paid attention to the explanation of substitution ciphers, you would see that they typically have a 1:1 ratio of letters. Knowing this,you can see how this unique 26 letter string has a high probability of being akey. So then lets lay it out:
If you take that key, you can start translating everythingelse that's not the key (the data), which results in:
Lets make this easier to read:
There you have it. To win, you needed to send me the phrase"LOLWUTCRYPTO" on twitter.
Now lets go into my favorite part, the cryptanalysis…
The Triforce CipherCryptanalysis
This isn't the worst cipher in the world, but it reallyisn't that great. There are several limitations that we shall go into.
Being that the cipher must conform to the shape of aTriforce, this imposes a restriction on the size of data it can contain. TheTriforce is a equilateral triangle, which means all sides must be the samelength, and if one of the sides is the key, than the total data size is limitedby how long your key is. This relationship between how long your key length isto how much data you can store can be calculated using the following equation:
Where S is the data size and n is the key length.
Or this excel formula to make it easier:
This means that if you have a 26 letter key, you can contain247 characters of data, which comes out to a total ciphertext length of 273characters.
So if you decided to write the ciphertext using thehexadecimal character set instead of the English alphabet, you could store 92characters of data.
Using the table above, you can easily figure out how longthe key is based on the total length (you can also just count how manydifferent characters there are, but this is easier)
The Wall Of Secrecy Is Very Short
Another issue with this cipher is the fact that the key todecrypt the ciphertext is easily compromised once it's understood that this isa Triforce Cipher. This essentially places it on the same level of strength asa Caesar cipher. If you know what encryption algorithm you are dealing with,it's game over.
The next Spiderlabs Crypto Contest will be a modified bookcode I'm working on.