Monday, February 4, 2013

HackIM CTF 2013: Crypto 300

Many of the crypto challenges were more puzzles than mathematical cryptography. This challenge was no different and is shown below
Bellaso Falls in Love Again 300 pts 

CipherText: Gntgc mey fhhsc mzc ugkt 20 wqnle oy evfwfvkcrc, max fhhsc mzc ugkt mzr sqak od updrxxtlor niegtw jaary - Bppw Jcxlbaki
At first glance, we can pick up on the fact that it appears to be a quote of some sort, and it looks like it operates only on letters (the number 20 doesn't appear to be a word). But I didn't really know where to start after that so I Googled "Bellaso Cryptography" and started reading. The wikipedia page credits Giovan Battista Bellaso with using/creating autokey/vigenere-type ciphers. A brief explanation of Vigenere-Type Ciphers:
Plaintext:this is my plaintext
Key:bobb ob bo bbobbobbo <-- The word bob repeated over the length of the plaintext
Ciphertext:uvjt wt nm qmojohfyh <-- Simply add the alphabet index values to get the output
I was still a little lost about where to go from here so I kept reading Google results until I stumbled across a very interesting article on one of Bellaso's Ciphers here. Apparently, Bellaso release a series of challenges to his readers and the first one did not get solved until just a few years ago, and he did it by finding a series of repeating letters, which helped him get the key length. I decided to try that as well to see if I could find a guess of a key-length. There is quite a glaring one that I couldn't believe I had not seen.
Gntgc mey fhhsc mzc ugkt 20 wqnle oy evfwfvkcrc, max fhhsc mzc ugkt mzr sqak od updrxxtlor niegtw jaary - Bppw Jcxlbaki
The chances of this 12 character string not being the same plaintext letters was very small, so we assume that the key lines up exactly with this string. Since we know that the beginning of the key must line up with the beginning of each "fhhsc" string, the key must evenly divide into the number of letters between the beginning of each of those. There are 32 characters between the beginning of the two strings, so key lengths of 2, 4, 8, 16,and 32 are possible. At this point, I found an online tool that would guess keys based on a vigenere cipher and try to decrypt the cipher text, but you have to give it a key length. I started with a keylength of 4, 8, and finally 16 before I got something promising. With a keylength of 16, the tool guessed a key and plaintext of
Key: NCGPYINUBTTOOUIY 
Tlnre ere eooeo sre heee 20 yiard vf qhlohiiwce, end eooeo sre heee ore yphr ap ahfevrenge thlnfi pscew - Varo Wiwsimwo
I thought that the first 8 letters looked kind of like "There are" so I used another online tool to start refining my key. After I made the key such that the first two words were "There are," I had the below plaintext and key.
Key: NGPPYMNUBTTOOUIY 
Plaintext: There are eooeo sre have 20 yeard vf qhlohience, and eooeo sre have one yphr ap ahferience thlnfi psces - Mark Wiwsimwo
You can see that every 8 characters, we have successfully decrypted the text to make the readable English. We also have a first name of the author, so we are definitely on the right track. Now I looked at the "20 yeard vf" which should probably be "20 years of". After some more fiddling, we lock two more characters of the decryption key.
Key: NGPPYMNUMATOOUIY 
Plaintext: There are thoeo sre have 20 years of qhlohience, and thoeo sre have one year ap ahferience twenfi psces - Mark Willimwo
We have some more plaintext now and look at the word "thoeo" which is probably supposed to be "those". Modified the key and we now have this.
Key: NGPPYMNUMATAYUIY 
Plaintext: There are those sre have 20 years of exlohience, and those sre have one year of ahferience twenty psces - Mark Williamo
At this point I guessed what the rest of the quote was and got the key to spit it out to me.
Key: NGPPYMNUMATAYQSO 
Plaintext: There are those who have 20 years of experience, and those who have one year of experience twenty times - Mark Williams
The answer was the full plaintext.

-- suntzu_II

1 comment:

  1. Key was "nullcongoahackim", if you had used encoding operation, instead of decoding

    ReplyDelete