OverTheWire - Krypton - All Levels

Introduction

Krypton is a wargame offered by OverTheWire. The aim of Kyrpton is to give you hands-on experience with cryptography and cryptanalysis, starting with legacy cyphers and moving onto more modern ones.

NOTE: This write-up does contain spoilers for each of the levels, so if you want to try it out for yourself, be warned.

Level 0 -> 1

Link To Level 0

Getting the Password

The initial password is encoded (not encrypted) with Base64. It can be decoded with the command line fairly easily:

echo S1JZUFRPTklTR1JFQVQ= | base64 -d
# KRYPTONISGREAT

Level 1 -> 2

Link To Level 1

Initial Access

sshpass -p KRYPTONISGREAT ssh krypton.labs.overthewire.org -p 2231 -l krypton1

A Little Bit Of Theory

The README hints that the password for the next level has been encoded using a substitution cipher known as ROT13. This is based on the Caesar cipher, where every character is shifted by a certain number of places through the alphabet. In the case of ROT13, this is 13 places;for example, A becomes N, B becomes O, etc. The process of taking the plaintext and turning it into ciphertext can be applied to the ciphertext to get the original plaintext.

If you want to read some more on this, check out this Wikipedia Article.

Finding The Next Password

The file is located in /krypton/krypton1 and is named krypton2. Viewing the contents shows us the encoded message of YRIRY GJB CNFFJBEQ EBGGRA. We could copy and paste this into an online tool, but seeing as we're already on the command line, let's use it.

The tr tool can be used to translate text in multiple ways. In this case, we can reverse the cypher using the following command:

cat krypton2 | tr "[:alpha:]" "N-ZA-Mn-za-m"

The [:alpha:] in the command is a built-in array, which simply corresponds to A-Za-z

With the password in hand, let's move on.

Level 2 -> 3

Link To Level 2

Initial Access

sshpass -p <level 2 password> ssh krypton.labs.overthewire.org -p 2231 -l krypton2

A Little Bit Of Theory

The password for this level has been encoded using the Ceasar Cipher. This is a cypher that shifts the characters by a set value known as the key. For example, if the value of the key is 4, then all the letters would be shifted by 4 places: A becomes E, B becomes F, and so on. The shifting can be either positive or negative, but to reverse the encoding, the opposite action needs to be applied.

Finding The Next Password

To get started, we'll follow the steps in the README to create ourselves a temporary directory.

mktemp -d
# /tmp/tmp.WrDJiHZeW9

cd /tmp/tmp.WrDJiHZeW9
ln -s /krypton/krypton2/keyfile.dat
chmod 777 .

We know the encrypted password is OMQEMDUEQMEK, but we don't know the key (stored in keyfile.dat) to be able to reverse the encryption. So, how can work out the key in order to progress to the next level?

It's pretty simple, we encrypt some data that we have control of:

echo AAA > test
/krypton/krypton2/encrypt test
cat ciphertext 
# MMM

From the control, we have shifted AAA to MMM. This translates to a shift of 12. So we can use the tr command to translate the original ciphertext back to its plaintext equivilent. The amount we'll need to shift it by is 26 - 12 = 14, meaning our tr command will need O-ZA-No-za-n to be plugged into it.

cat krypton3 | tr "[:alpha:]" "O-ZA-No-za-n"

Level 3 -> 4

Link To Level 3

Initial Access

sshpass -p <level 3 password> ssh krypton.labs.overthewire.org -p 2231 -l krypton3

A Little Bit Of Theory

This level requires you to look at analysing intercepted texts for the number of times each letter appears. This approach is known as Frequency Analysis where certain characters of the alphabet will appear more frequently than others. For example, the letter E is more likely to appear in most texts, so if you encounter some ciphertext where a character appears more frequently than others, it's likely to have been substituted for an E.

Finding The Next Password

We've been given three files that have been intercepted, but no key. The only hints we're given from the get-go are that the plaintexts are in English and were all produced by the same key.

There are also a couple of hint files in the same directory, one of which mentions performing some frequency analysis as some letters are more frequent than others. So, let's look at how many times each letter appears in the intercepted texts:

cat found* | tr  -d " " | sed 's/./&\n/g' | sort | uniq -ic | sort -nr

A visual explanation for this command can be found on ExplainShell. But effectively

1. All of the file are being combined together (cat)
2. All spaces are being removed (tr)
3. All characters are being placed on new lines (sed)
4. The characters are being sorted alphabetically (first sort)
5. The unique characters are being counted (uniq)
6. The characters are sorted based on frequency with most occurances at the top (second sort)

Now that we have the frequency with which the number of characters appears in all three texts, let's see if we can make some substitutions based on the list from Cornell.

cat krypton4 | tr "SQJUBNGCDZVWMYTXKELAFIORHP" "ETAOINSRHDLUCMFYWGPBVKXQJZ"

This will give us the output of WELLU ISEAH ELEKE LYICN MTOOW INURO BNCAE, which doesn't make too much sense, so we'll need to move a few of the translates around until we can get something that more closely resembles the English language. For example, we know the word password is likely to appear, so we can start off by looking for characters where there are two of the same letter next to each other.

After a little bit of trial and error, the password was revealed to us.

cat krypton4 | tr "SQJUBNGCDZVWMYTXKELAFIORHP" "EATSORNIHCLDUPYFWMGBKVXQJZ"

Level 4 -> 5

Link To Level 4

Initial Access

sshpass -p <level 4 password> ssh krypton.labs.overthewire.org -p 2231 -l krypton4

A Little Bit Of Theory

This level looks at the Vigenère cipher. This cipher is similar to the ROT13 and Ceasar Cipher, except instead of using an integer to shift the characters of the plaintext, you're using a keyword to substitute; the keyword can be any number of characters long. If the keyword is shorter than the plaintext, it will be repeated.

An example of which can be seen below:

PLAIN:  HELLO EVERY ONE
KEY:    CHEES ECHEE SEC
CIPHER: JLPPG IXLVC GRG

Finding The Next Password

After reading the README for this level, we know we're working with a key length of 6. Now it's time to attempt to crack the password. To do this, we'll first need to decrypt the text found in the intercepted text files. But where do we start? I personally started by brute-forcing the key using Cyberchef, copying one of the texts, and trying out various letters until I got something that resembled English. I lucked out on attempting FRENCH and managed to get the first three letters. From there on, it was just a case of iterating through the alphabet until I was able to get a full decrypion.

For those who don't want the pain, the dcode site has the ability to guess the key if you know some of the parameters, in this case the key length.

Now that we have the key, we can crack the password for the next level.

Level 5 -> 6

Link To Level 5

Initial Access

sshpass -p <level 5 password> ssh krypton.labs.overthewire.org -p 2231 -l krypton5

A Little Bit Of Theory

It's possible to use frequency analysis on ciphertext to ascertain what the length of the key might be. One of those methods is the Kasiski Test. This makes the assumption that some words may end up being encrypted using the same characters as the key, resulting in groups of similar ciphertext.

Finding The Next Password

Using dcode again, we're able to select the Vigenere Cryptanalysis (Kasiski's Test) option for the tool to try and guess the length of the key. In this case, 3, 6, or 9 were the strongest of the candidates.

With this, we can try out one of the three key lengths to get the key in order to crack the password for the next level.

A quick and easy level... Let's move on.

Level 6 -> 7

Link To Level 6

Initial Access

sshpass -p <level 6 password> ssh krypton.labs.overthewire.org -p 2231 -l krypton6

A Little Bit Of Theory

This level introduces the notion of repeating keys as insecure, as Frequency Analysis can be used to quickly determine the key, and we've been using block ciphers. We're now moving on to the world of stream ciphers which are another type of symmetric cipher.

These ciphers create random keys, which are then used to encrypt one character at a time, typically using an XOR function, combining the output with the keystream. In this level, we're introduced to the notion of Linear-Feedback Shift Registers. These take taps off the binary data and XOR them together to get a result. The result of this function is then pushed onto the end of the binary blob, where the digit on the other end is dropped off. Computerphile has a great video that explains it further here.

Finding The Next Password

We'll start just like we did in level 2 by creating a temporary directory and a soft link to the keyfile.

mktemp -d
# /tmp/tmp.vvaf0FpDvG
cd /tmp/tmp.vvaf0FpDvG
ln -s /krypton/krypton6/keyfile.dat

Now that we're done with that, we can start to bruteforce the algorithm. Let's start by creating a few files with some known data to be encrypted:

printf 'A%.0s' {1..80} > a.test
printf 'B%.0s' {1..80} > b.test
printf 'C%.0s' {1..80} > c.test
printf 'D%.0s' {1..80} > d.test
printf 'E%.0s' {1..80} > e.test
printf 'F%.0s' {1..80} > f.test
printf 'G%.0s' {1..80} > g.test

And now to encrypt:

/krypton/krypton6/encrypt6 a.test a.cipher
/krypton/krypton6/encrypt6 b.test b.cipher
/krypton/krypton6/encrypt6 c.test c.cipher
/krypton/krypton6/encrypt6 d.test d.cipher
/krypton/krypton6/encrypt6 e.test e.cipher
/krypton/krypton6/encrypt6 f.test f.cipher
/krypton/krypton6/encrypt6 g.test g.cipher

Looking at a.cipher, we can get the string EICTDGYIYZKTHNSIRFXYCPFUEOCKRNEICTDGYIYZKTHNSIRFXYCPFUEOCKRNEICTDGYIYZKTHNSIRFXY. Interestingly, there's a pattern that repeats every 30 characters. It makes you wonder if that's the case with the others; let's take a look.

B: FJDUEHZJZALUIOTJSGYZDQGVFPDLSOFJDUEHZJZALUIOTJSGYZDQGVFPDLSOFJDUEHZJZALUIOTJSGYZ

C: GKEVFIAKABMVJPUKTHZAERHWGQEMTPGKEVFIAKABMVJPUKTHZAERHWGQEMTPGKEVFIAKABMVJPUKTHZA

Sure enough, every 30 characters, the pattern repeats. But what's even more interesting is that if you look at the first character of each of the ciphertexts, they're sequential. A is E, B is F, and C is G. This repeats all the way through the string. Now we are able to start piecing together the algorithm used for encrypting the data. Using Python, we can work out the differences between each step. Let's use the 30 characters from the A series.

seq = []

cipher = "EICTDGYIYZKTHNSIRFXYCPFUEOCKRN"
for c in cipher:
    seq.append(ord(c) - ord("A"))

print(seq)
# [4, 8, 2, 19, 3, 6, 24, 8, 24, 25, 10, 19, 7, 13, 18, 8, 17, 5, 23, 24, 2, 15, 5, 20, 4, 14, 2, 10, 17, 13]
# [4, 8, 2, 19, 3, 6, 24, 8, 24, -1, 10, 19, 7, 13, 18, 8, 17, 5, 23, 24, 2, 15, 5, 20, 4, 14, 2, 10, 17, 13]
# [4, 8, 2, 19, 3, 6, -2, 8, -2, -1, 10, 19, 7, 13, 18, 8, 17, 5, 23, -2, 2, 15, 5, 20, 4, 14, 2, 10, 17, 13]

With this sequence, we can apply it to the cipher text to reverse the encryption:

cipher = "EICTDGYIYZKTHNSIRFXYCPFUEOCKRN"
seq = []

for c in cipher:
    seq.append(ord(c) - ord("A"))

krypton = "PNUKLYLWRQKGKBE"

out = []
for i in range(len(krypton)):
    temp = ord(krypton[i]) - seq[i]
    out.append(chr(temp))

print("".join(out))
# LFS8IS4O:8A4D53

Now, there is a little problem with this password in that it doesn't actually work! So it looks like we went wrong somewhere, but where? Let's compare the other encrypted strings with their plaintext counterparts, as well as a few other data points.

As we can see, there's definitely some difference between the different letters. Judging by the values, anything above 12 will need to have 26 subtracted from it to produce the correct character. It's time to update the code and try again.

cipher = "EICTDGYIYZKTHNSIRFXYCPFUEOCKRN"
seq = []

for c in cipher:
    diff = ord(c) - ord("A")
    seq.append(diff if diff < 13 else diff - 26)

krypton = "PNUKLYLWRQKGKBE"

out = []

for k, s in zip(krypton, seq):
    temp = ord(k) - s
    out.append(chr(temp))

print("".join(out))
# <THE CORRECT PASSWORD>

Level 7

And there we have it, the end of Krypton.