Cryptography War: Beating Krypton

Continuing to talk about the Wargames, today I'll briefly go through Krypton, the cryptography episode.

The problems are very straightforward and very similar to those from the last CSAW CTF (see my post here).

Disclaimer: if you haven't played WarGames but you are planing to, PLEASE DON'T READY ANY FURTHER. If you don't try to solve the problems by yourself first, you will be wasting your time.

Level 0: Base64 Transformation

This level starts with:

The following string encodes the password using Base64: S1JZUFRPTklTR1JFQVQ= Use this password to log in to krypton.labs.overthewire.org with username krypton1 using SSH. You can the files for other levels in /krypton/.

Base64 is just a way to represent binary data in ASCII, by translating it into a radix-64. Linux provides a built-in Base64 enconder/decoder tool, so all we need to do is:

$ base64 -d KRYPTON0.txt

Level 1: Classic Caesar Cypher

The second level starts with:

The password for level 2 is in the file ‘krypton2’. It is ‘encrypted’ using a simple rotation. It is also in non standard ciphertext format. When using alpha characters for cipher text it is normal to group the letters into 5 letter clusters, regardless of word boundaries. This helps obfuscate any patterns. This file has kept the plain text word boundaries and carried them to the cipher text. Enjoy!

This is the classic Caesar Cypher (they really love this thing :).

In the Caesar’s cipher, the letters in the plaintext are shifted by a fixed number of elements down the alphabet. For example, if the shift is 3, A becomes D , B becomes E , and so on. Once we run out of letters, we circle back to A.

We can solve this challenge in a few lines using Linux's built-in tr (translate tool):

krypton1@melinda:/krypton/krypton1$ VAR=$(cat krypton2)
krypton1@melinda:/krypton/krypton1$ echo $VAR
YRIRY GJB CNFFJBEQ EBGGRA
krypton1@melinda:/krypton/krypton1$ alias rot13="tr A-Za-z N-ZA-Mn-za-m"
krypton1@melinda:/krypton/krypton1$ echo "$VAR" | rot13

Level 2

The third level starts with:

ROT13 is a simple substitution cipher.

Substitution ciphers are a simple replacement algorithm. In this example of a substitution cipher, we will explore a 'monoalphebetic' cipher. Monoalphebetic means, literally, "one alphabet" and you will see why.

This level contains an old form of cipher called a 'Caesar Cipher'. A Caesar cipher shifts the alphabet by a set number. For example:

plain: a b c d e f g h i j k ... cipher: G H I J K L M N O P Q ...

In this example, the letter 'a' in plaintext is replaced by a 'G' in the ciphertext so, for example, the plaintext 'bad' becomes 'HGJ' in ciphertext.

The password for level 3 is in the file krypton3. It is in 5 letter group ciphertext. It is encrypted with a Caesar Cipher. Without any further information, this cipher text may be difficult to break. You do not have direct access to the key, however you do have access to a program that will encrypt anything you wish to give it using the key. If you think logically, this is completely easy.

First, we make a file filled with the alphabet, so we can test the binary:

$ ln -s /krypton/krypton2/keyfile.dat keyfile.dat
$ echo {A..Z} {a..z} > file
$ cat file
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z

Running the binary:

$ /krypton/krypton2/encrypt file
$ cat ciphertext
MNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKL

We see a ROT14 (since ROT13 starts in N).

As a second way to find the rotation, we could use ltrace:

$ ltrace /krypton/krypton2/encrypt file | less

Which shows things such as:

fgetc(0x602250)                                       = 'A'
toupper('A')                                          = 'A'
isalpha(65, 65, 0x7ffff7dd0d00, -1, 0xffffffff)       = 1024
fputc('M', 0x602490)                                  = 77

Now that we know the rotation number, we can decrypt the password in the same way as we did in the previous level:

krypton2@melinda:/tmp$ alias rot14="tr A-Z O-ZA-N"
krypton2@melinda:/tmp$ echo "$VAR" | rot14

Level 3: Frequency Analysis

This level starts with:

Well done. You've moved past an easy substitution cipher.

Hopefully you just encrypted the alphabet a plaintext to fully expose the key in one swoop.

The main weakness of a simple substitution cipher is repeated use of a simple key. In the previous exercise you were able to introduce arbitrary plaintext to expose the key. In this example, the cipher mechanism is not available to you, the attacker.

However, you have been lucky. You have intercepted more than one message. The password to the next level is found in the file 'krypton4'. You have also found 3 other files. (found1, found2, found3)

This time we have to use frequency analysis to count the number of times each letters appears in our message. The results are compared to the frequency in each we see letters in English. This is enough to break this type of cipher.

For this purpose I wrote the following script:

import string
import sys
import operator

FREQ_ENGLISH = [0.0749, 0.0129, 0.0354, 0.0362, 0.1400, 0.0218, 0.0174, 0.0422, 0.0665, 0.0027, 0.0047, 0.0357,0.0339, 0.0674, 0.0737, 0.0243, 0.0026, 0.0614, 0.0695, 0.0985, 0.0300, 0.0116, 0.0169, 0.0028, 0.0164, 0.0004]

def find_frequency(msg):
    dict_freq = dict([(c, 0) for c in string.lowercase])
    total_letters = 0.0
    for c in msg.lower():
        if 'a'<= c <= 'z':
            dict_freq[c] += 1
            total_letters += 1
    list_freq = sorted(dict_freq.items(), key=operator.itemgetter(1))
    return [(c, freq/total_letters) for (c, freq) in list_freq]

def main(filename):
    with open(filename, 'r') as f:
       cipher = f.readlines()
       cipher = cipher[0].strip()
       flist = find_frequency(cipher)
       elist = dict((k, value) for (k, value) in  zip(string.lowercase, FREQ_ENGLISH))
       elist = sorted(elist.items(), key=operator.itemgetter(1))
       trans, key = '', ''
       for i, f in enumerate(flist):ls
          trans += f[0]
          key += elist[i][0]
          print "CIPHER: %s -> %.5f, ENGLISH: %s -> %.5f" %(f[0], f[1], elist[i][0], elist[i][1])
       print "Key is " + key + " for " + trans

       # print key sorted to translate to a-z
       res = zip(trans, key)
       res.sort()
       trans, key = '', ''
       for letter in res:
          trans += letter[1].upper()
          key += letter[0].upper()
       print "tr  [" + key + "] [" + trans + "]"

if __name__ == "__main__":
  main(str(sys.argv[1]))

Running it gives us the key:

$ cat /krypton/krypton3/found1 > cipher
$ cat /krypton/krypton3/found2 >> cipher
$ cat /krypton/krypton3/found3 >> cipher
$ /krypton/krypton3$ python freq.py cipher
$ alias rotvi='tr ABCDEFGHIJKLMNOPQRSTUVWXYZ BOIHPKNQVTWGURXZAJEYSLDFPU'
$ cat /krypton/krypton3/krypton4 | rotvi

We could also use this online tool to find the frequencies.


Level 4: Vigenere Cipher I

The fifth level starts with:

So far we have worked with simple substitution ciphers. They have also been ‘monoalphabetic’, meaning using a fixed key, and giving a one to one mapping of plaintext (P) to ciphertext (C). Another type of substitution cipher is referred to as ‘polyalphabetic’, where one character of P may map to many, or all, possible ciphertext characters.

An example of a polyalphabetic cipher is called a Vigenère Cipher. It works like this:

If we use the key(K) ‘GOLD’, and P = PROCEED MEETING AS AGREED, then “add” P to K, we get C. When adding, if we exceed 25, then we roll to 0 (modulo 26).

P P R O C E E D M E E T I N G A S A G R E E D\ K G O L D G O L D G O L D G O L D G O L D G O\ becomes:

P 15 17 14 2 4 4 3 12 4 4 19 8 13 6 0 18 0 6 17 4 4 3\ K 6 14 11 3 6 14 11 3 6 14 11 3 6 14 11 3 6 14 11 3 6 14\ C 21 5 25 5 10 18 14 15 10 18 4 11 19 20 11 21 6 20 2 8 10 17\ So, we get a ciphertext of:

VFZFK SOPKS ELTUL VGUCH KR This level is a Vigenère Cipher. You have intercepted two longer, english language messages. You also have a key piece of information. You know the key length!

This is a classical case of Vigenere cipher, which is a variation on the Caesar’s cipher. In this case, one uses multiple shift amounts according to a keyword.

To solve this we use the pygenere library in Python. First we need to find the key:

import sys
from pygenere import Vigenere, VigCrack

def get_key(msg):
  # Vigenere Cypher
  key =  VigCrack(msg).crack_codeword()
  dec_msg = VigCrack(msg).crack_message()
  dec_msg =  dec_msg.replace(" ", "")
  return key, dec_msg

if __name__ == '__main__':
  # getting the key
  with open('cipher', 'r') as f:
        msg = f.readlines()
        msg_in = msg[0].strip()
        key, answer = get_key(msg_in)
        print 'Message: ' + msg_in
        print
        print 'Answer: ' + answer
        print '(key: ' + key + ')'

The deciphered text is:

THESOLDIERWITHTHEGREENWHISKERSLEDTHEMTHROUGHTHESTREETSOFTHEEMERALDCITYUNTILTHEYREACHED THEROOMWHERETHEGUARDIANOFTHEGATESLIVEDTHISOFFICERUNLOCKEDTHEIRSPECTACLESTOPUTTHEMBACK INHISGREATBOXANDTHENHEPOLITELYOPENEDTHEGATEFOROURFRIENDSWHICHROADLEADSTOTHEWICKEDWITCHOF THEWESTASKEDDOROTHYTHEREISNOROADANSWEREDTHEGUARDIANOFTHEGATESNOONEEVERWISHESTOGOTHATWAY HOWTHENAREWETOFINDHERINQUIREDTHEGIRLTHATWILLBEEASYREPLIEDTHEMANFORWHENSHEKNOWSYOUAREIN THECOUNTRYOFTHEWINKIESSHEWILLFINDYOUANDMAKEYOUALLHERSLAVESPERHAPSNOTSAIDTHESCARECROWFOR WEMEANTODESTROYHEROHTHATISDIFFERENTSAIDTHEGUARDIANOFTHEGATESNOONEHASEVERDESTROYEDHER BEFORESOINATURALLYTHOUGHTSHEWOULDMAKESLAVESOFYOUASSHEHASOFTHERESTBUTTAKECAREFORSHEIS WICKEDANDFIERCEANDMAYNOTALLOWYOUTODESTROYHERKEEPTOTHEWESTWHERETHESUNSETSANDYOUCANNOT FAILTOFINDHERTHEYTHANKEDHIMANDBADEHIMGOODBYEANDTURNEDTOWARDTHEWESTWALKINGOVERFIELDS OFSOFTGRASSDOTTEDHEREANDTHEREWITHDAISIESANDBUTTERCUPSDOROTHYSTILLWORETHEPRETTYSILKDRESS SHEHADPUTONINTHEPALACEBUTNOWTOHERSURPRISESHEFOUNDITWASNOLONGERGREENBUTPUREWHITETHERIB BONAROUNDTOTOSNECKHADALSOLOSTITSGREENCOLORANDWASASWHITEASDOROTHYSDRESSTHEEMERALDCITYW ASSOONLEFTFARBEHINDASTHEYADVANCEDTHEGROUNDBECAMEROUGHERANDHILLIERFORTHEREWERENOFARMSN ORHOUSESINTHISCOUNTRYOFTHEWESTANDTHEGROUNDWASUNTILLEDINTHEAFTERNOONTHESUNSHONEHOTINTHEI RFACESFORTHEREWERENOTREESTOOFFERTHEMSHADESOTHATBEFORENIGHTDOROTHYANDTOTOANDTHELIONWER ETIREDANDLAYDOWNUPONTHEGRASSANDFELLASLEEPWITHTHEWOODMANANDTHESCARECROWKEEPINGWATCH

Finally, we use the key to decipher the password:

def solve(msg, key):
  dec_msg = Vigenere(msg).decipher(key)
  dec_msg =  dec_msg.replace(" ", "")
  return dec_msg

if __name__ == '__main__':
  # deciphering
  key = 'FREKEY'
  with open('pass', 'r') as f:
  msg = f.readlines()
  answer = solve(msg[0].strip(), key)
  print "The answer is: " + answer

Level 5: Vigenere Cipher II

The sixth level starts with:

Frequency analysis can break a known key length as well. Lets try one last polyalphabetic cipher, but this time the key length is unknown.

This is another example of Vigenere Cipher. Using the same method as before we first get the key and then the password.

Fun, isn't?