OverTheWire: Krypton

Level 0 → Level 1 🔗

Welcome to Krypton! The first level is easy. The following string encodes the password using Base64:

S1JZUFRPTklTR1JFQVQ=

Solution

This is fairly straightforward.

$ echo 'S1JZUFRPTklTR1JFQVQ=' | base64 -d

Answer: KRYPTONISGREAT

Level 1 → Level 2 🔗

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!

Solution

The password is encoded with a simple Caesar cipher, with a rotational shift of 13 (ROT13)
We can use the built-in unix utility tr to decode the string

$ cat krypton2 | tr 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 'NOPQRSTUVWXYZABCDEFGHIJKLM'
LEVEL TWO PASSWORD ROTTEN

Answer: ROTTEN

Level 2 → Level 3 🔗

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.

One shot can solve it!

Solution

We know we are dealing with Caesar cipher, and we have an encryption utility at our disposal. In order to determine the shift used, we can simply encrypt the whole alphabet and analyze the final transformation

$ echo ABCDEFGHIJKLMNOPQRSTUVWXYZ > plaintext
$ /krypton/krypton2/encrypt plaintext
$ cat ciphertext
MNOPQRSTUVWXYZABCDEFGHIJKL

The A maps to M, B maps to N and so on. This means it has a shift of 12 (ROT12)

To decrypt the final string, we need to apply the exact opposite procedure, since unlike ROT13, ROT12 is not symmetrical.

$ cat /krypton/krypton2/krypton3 | tr 'MNOPQRSTUVWXYZABCDEFGHIJKL' 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

Answer: CAESARISEASY

Level 3 → Level 4 🔗

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)

You know the following important details:

The message plaintexts are in English (very important) - They were produced from the same key (even better!)

Solution

Using this site, I did a quick single-letter frequency analysis on the text.

We can clearly see that the most frequent letter is S (12.1%). In English language, the most frequent letter is E, statistically. Therefore, we can say with high confidence that S maps to E.

Replacing all occurences of S to e

$ cat found1 | tr 'S' 'e'
CGZNL YJBEN QYDLQ ZQeUQ NZCYD eNQVU BFGBK GQUQZ QeUQN UZCYD eNJDe UDCXJ ZCYDe...

In the following step, I am going to make a bit of a calculated guess. Given that the context of the encrypted text probably has something to do with cryptography, caesar cipher, etc, I am going to assume that there is a word ‘CRYPTOGRAPHY’ somewhere in the text. If this assumption were true, then we will have already cracked a lot of letters, and the text will start to make sense.

The word CRYPTOGRAPHY contains three repeating characters which we will use to help construct our search pattern. Repeating characters are R, Y, and P, occuring twice at a very specific positions. This pattern can be captured by the following regex

$ cat found{1..3} | tr -d ' ' | egrep '.(.)(.)(.)...\1.\3.\2' -o
ZNLYJBENQYDL
EDJSSGJDZSGJ

Two strings are found. We can immediately discard the second result, as our word doesn’t contain any two consecutive letters.

Let’s try the new mapping, ZNLYJBEQD → CRYPTOGAH

$ cat found1 | tr 'SZNLYJBEQD' 'ecryptogah'
CGcry ptogr aphya caeUa rcCph eraVU oFGoK GaUac aeUar UcCph erthe ...

The text is slowly starting to make sense. Now we have enough information to guess the other letters. For example, the first two letters, ‘CG’, most likely map to ‘IN’, which results in phrase ‘IN CRYPTOGRAPHY’

$ cat found1 | tr 'SZNLYJBEQDCG' 'ecryptogahin'
incry ptogr aphya caeUa rciph eraVU oFnoK naUac aeUar Uciph erthe ...

From here on, it is just a matter of detecting word boundaries and similarly filling in the missing pieces. The final translation alphabet then becomes SZNLYJBEQDCGUXTVWFKHMAOI → ecryptogahinsfmldkwqubxv

Decrypting the file krypton4 reveals the password

$ cat krypton4 | tr 'SZNLYJBEQDCGUXTVWFKHMAOI' 'ecryptogahinsfmldkwqubxv'
welld oneth eleve lfour passw ordis brute

Answer: BRUTE

Level 4 → Level 5 🔗

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!

For this exercise, the key length is 6. The password to level five is in the usual place, encrypted with the 6 letter key.

Have fun!

Solution

Firstly, let’s inspect the intercepted messages, see if we can get any clues out of it

$ cat found1
YYICS JIZIB AGYYX RIEWV IXAFN JOOVQ QVHDL CRKLB SSLYX RIQYI IOXQT ...

$ cat found2
YYIIA CWVSL PGLVH DSAFD TYYRY YEDRG LYXER BJIEV EPLVX BICNE XRIDT ...

Notice the first word in both files. Both words start with the same three letters.

In English language, statistically, the most frequent three-letter word used at the beginning of sentences is the word THE. Therefore, we can assume with high probability that the mapping YYI → THE is true

At this point, we can work out part of the key, by simply subtracting plaintext from the ciphertext.

C =   YYI
P = - THE
—————————
K =   FRE

The following table might help

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
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

Now that we have a partial key, let’s check the krypton5 file, and try to crack part of the cipher.

$ cat /krypton/krypton4/krypton5
HCIKV RJOX

The ciphertext is 9 characters long, and we know that our key has a length of 6. This means, the key would start to repeat itself after the 6th character. Thus, we can decrypt 6 out of 9 characters, and simply guess the remaining three letters!

C =   HCIKVRJOX
K = - FRE...FRE
———————————————
P =   CLE...EXT

From here, it doesn’t take one much imagination to guess that the password is CLEARTEXT

Additionally, we can apply the reverse process, and use this guessed plaintext to work out the full key. The original key then becomes FREKEY

Answer: CLEARTEXT

Level 5 → Level 6 🔗

FA can break a known key length as well. Let’s try one last polyalphabetic cipher, but this time the key length is unknown.

Enjoy.

Solution

The main idea here would be to try again to find the mapping of the THE word, as it is the most common three-letter word in English.

In order to find the correct mapping of the THE word, we could take the most common trigrams (three-letter words) in the text, and simply try out a few of them to see if we can extract any meaningful key from that.

Here is a script I’ve made to print out 5 most common trigrams

import re
import sys
import collections

ciphertext = ''
for file in sys.argv[1:]:
    with open(file) as f:
        ciphertext += ''.join(f.read().split())

trigrams = re.findall(r'(?=(\w\w\w))', ciphertext)
top_five = collections.Counter(trigrams).most_common(5)

for word, count in top_five:
    print(word, count)

Run it with python3, and pass all three messages as arguments

$ python3 top_trigrams.py found{1..3}
ZAL 15
GNX 13
DLC 13
ARI 12
RSI 12

With a bit of trial and error, I’ve finally tried the word DLC, which when decrypted using the assumed word THE, yielded a key KEY. This looks promising.

C =   DLC
P = - THE
—————————
K =   KEY

As before, we can use this partial key to attempt to crack the part of the ciphertext we are interested in.

$ cat /krypton/krypton5/krypton6
BELOS Z

and decrypting it

C =   BELOSZ
K = - KEY...
————————————
P =   RAN...

Guessing the three remaining characters is trivial. The plaintext is RANDOM, and plugging that string back into equation, we obtain the partial key KEYLEN. The partial key already hints at what the original key should be. Making one more guess, we now get the full key: KEYLENGTH. And indeed, this key can successfully decrypt all intercepted messages.

Answer: RANDOM

Level 6 → Level 7 🔗

The password for level 7 (krypton7) is encrypted with ‘encrypt6’.

Good Luck!

Solution

Using the provided encrypt6 utility, I’ve tried encrypting a bunch of A’s just to see how the ciphertext behaves. (known-plaintext attack)

$ python -c 'print("A" * 40)' > plain
$ /krypton/krypton6/encrypt6 plain cipher
$ cat cipher
EICTDGYIYZKTHNSIRFXYCPFUEOCKRNEICTDGYIYZ

It seems that every ‘A’ in the plaintext gets mapped to a different alphabet character in the ciphertext, depending on the position of ‘A’. This looks very much like the Vigenère cipher.

By encrypting a bunch of A’s, the whole key is essentially revealed. We can also determine the key length, just by observing where the pattern repeats itself.

EICTDGYIYZKTHNSIRFXYCPFUEOCKRNEICTDGYIYZ

The final ciphertext is located inside the krypton7 file.

$ cat /krypton/krypton6/krypton7
PNUKLYLWRQKGKBE

Now, we can apply the Vigenère decode procedure. Essentially, the decrypted string is the result of subtracting the key from the ciphertext, char by char.

ciphertext = 'PNUKLYLWRQKGKBE'
key = 'EICTDGYIYZKTHNSIRFXYCPFUEOCKRN'

for c, k in zip(ciphertext, key):
    p = ord('A') + ((ord(c) - ord(k)) % 26)
    print(chr(p), end='')

print()

Answer: LSFRISNOTRANDOM