I recently stumbled upon overthewire.org cyber challenges, and after completing the 33 challenges of the Bandit series in an evening I returned to complete the Leviathan series, then moved on to the cryptographic challenges in the Krypton series. Levels 1 to 3 are straight forward, and these are my notes for future reference for the remaining levels, 4 to 6...
The Krypton series Cyber Challenge from Over the Wire - krypton4 is stated in the file "README", which can be concatenated to the standard out (screen).
--------------------------------------------------------------------------------
$cat README
You more than likely used frequency analysis and some common sense
to solve that one.
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!
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!
--------------------------------------------------------------------------------
There is also a hint in the file "HINT".
--------------------------------------------------------------------------------
$cat HINT
Frequency analysis will still work, but you need to analyse it
by "keylength". Analysis of cipher text at position 1, 6, 12, etc
should reveal the 1st letter of the key, in this case. Treat this as
6 different mono-alphabetic ciphers...
Persistence and some good guesses are the key!
--------------------------------------------------------------------------------
There are also two files "found1" and "found2" containing ciphertext encoded with the unknown key, which is 6 characters in length.
As the key is made up of 6 characters it will repeat at the 7th character position, and the 13th, and so on.
(The hint mentioning position "1, 6, 12" is obviously inaccurate, whether or not intentionally I know not.)
OK, first I'll look at what is happening to create the cipher, then I will think about reversing the process.
Let's say the key is "ABCDEF", the plaintext is "SOME PLAINTEXT".
The ciphertext would be created as follows:
First we remove any spaces or punctuations in the plaintext:
SOMEPLAINTEXT
Then repeat the key against the plaintext:
SOMEPLAINTEXT
ABCDEFABCDEFA
The key character value is added to the plaintext character value to create the ciphertext character.
Character values are 1 to 26 for characters "A" to "Z"
Making a simple letter 'ruler' makes the process easier to compute visually:
1 2 3 4
1234567890123456789012345678901234567890
ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMN
For the first character of ciphertext this gives:
S + A = 19 + 1 = 20 = T
For the 2nd..
O + B = 15 + 2 = 17 = Q
Doing this for the entire plaintext "SOMEPLAINTEXT" with cipher key "ABCDEF" gives the ciphertext:
TQPIURBKQXJDU
So to solve the problem at hand we have the ciphertext, but need to work out the cipher key, and plaintext.
I know the key length is 6, so I know that the ciphertext character 1, 7, 13, 19,... have all been encrypted using the 1st character of the cipher key.
Ciphertext characters 2, 8, 14, 20,... were encrypted with the 2nd character of the cipher key, and so on.
So I remove the spaces in the ciphertext and fold it into lines 6 characters long.
--------------------------------------------------------------------------------
$cat found1|tr -d ' '|fold -w6 |head -n5
YYICSJ
IZIBAG
YYXRIE
WVIXAF
NJOOVQ
--------------------------------------------------------------------------------
Now the 1st, 7th, 13th, 19th, etc characters are all in the first column. Ciphertext characters 2, 8, 14, 20, .. are all in the 2nd column, and so on.
So I need to slice this into individual columns because every character in the first column was encrypted with the 1st character of the cipher key, 2nd column was made with 2nd character of the cipher key, etc.
I use "cut -c1" to perform the slicing and redirect the output to a file "f1a".
--------------------------------------------------------------------------------
$cat found1|tr -d ' '|fold -w6 |cut -c1 > f1a; head -n5 f1a
Y
I
Y
W
N
--------------------------------------------------------------------------------
I then do the same for the other columns 2 to 6, storing each into files f1b to f1f
--------------------------------------------------------------------------------
$cat found1|tr -d ' '|fold -w6 |cut -c2 > f1b; head -n5 f1b
Y
Z
Y
V
J
--------------------------------------------------------------------------------
Now I have six files "f1a" to "f1f" that I can run a letter frequency analysis against to determine the most frequent characters.
Analysing them for the most frequent characters:
--------------------------------------------------------------------------------
$cat f1a|sort|uniq -c|sort -rn
37 J
24 S
22 Y
20 T
18 F
17 W
16 M
14 I
12 N
11 K
9 X
7 Z
7 B
6 Q
5 L
4 P
3 R
3 H
3 G
3 D
1 A
--------------------------------------------------------------------------------
In the English language, which I know the plaintext is written, the most frequent letter is "E".
So I know the most frequent letter from the frequency analysis of the ciphertext is equivalent to "E" in the plaintext.
This allows me to work out the key shifting letters between the plaintext and the ciphertext.
So from the above 1st column ciphertext frequency analysis, I know "J" in the ciphertext is the most common character and corresponds to "E" in plaintext.
plaintext + key = ciphertext
plaintext = ciphertext - key
E = J - ?
(Using the letter 'ruler' again...)
5 = 10 - ?
5 = 10 - 5
? = 5
E = 5
So to get from the ciphertext to plaintext I need to subtract the key character "E", which is of value 5, from the ciphertext character value.
All of this was ONLY for the first column of the ciphertext, so I repeat this for the other columns.
I end up with a 6 character key, "EQSJDX" or "EQDJDX", because the "S" and "D" have equal weighting from the frequency analysis which gave two possible ciphertext characters corresponding to plaintext "E".
Using the "found2" ciphertext for verification it is easy to work out the final correct key as "EQDJDX".
I appled this key in reverse to the ciphertext of the krypton5 password "HCIKV RJOX" and arrived at the password to the next level, krypton5.
--------------------------------------------------------------------------------
$ssh -p2222 krypton5@krypton.labs.overthewire.org
_ _
| | ___ __ _ _ _ __ | |_ ___ _ __
| |/ / '__| | | | '_ \| __/ _ \| '_ \
| <| | | |_| | |_) | || (_) | | | |
|_|\_\_| \__, | .__/ \__\___/|_| |_|
|___/|_|
a http://www.overthewire.org wargame.
krypton5@krypton.labs.overthewire.org's password:
Welcome to Ubuntu 14.04 LTS (GNU/Linux 4.4.0-92-generic x86_64)
* Documentation: https://help.ubuntu.com/
The programs included with the Ubuntu system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.
Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by
applicable law.
krypton5@krypton:~$ figlet $(whoami)
_ _ ____
| | ___ __ _ _ _ __ | |_ ___ _ __ | ___|
| |/ / '__| | | | '_ \| __/ _ \| '_ \|___ \
| <| | | |_| | |_) | || (_) | | | |___) |
|_|\_\_| \__, | .__/ \__\___/|_| |_|____/
|___/|_|
krypton5@krypton:~$
--------------------------------------------------------------------------------