247/CTF - Crypto - An Exclusive Key
Hi all! This is my first blog post ever, I’ll try to write every post self-explanatory and explain every detail involved. This time is about the third challenge of cryptography of the platform 247/CTF.
Challenge description
We’re given an exclusive_key file with the following description:
We XOR encrypted this file, but forgot to save the password. Can you recover the password for us and find the flag?
At first sight, we can’t see any repetition, so it seems there is no clue about what xor key was used for encryption:
$ md5sum exclusive_key
e1078ca347364828a43a40bd55c937f2 exclusive_key
$ xxd exclusive_key | head
00000000: 0e15 730c 1712 2233 2718 5a15 5f5d 5c68 ..s..."3'.Z._]\h
00000010: 050b 405b 5914 065d 5846 400b 4100 090a ..@[Y..]XF@.A...
00000020: 570c 4015 085b 5d0e 1014 5b22 3a21 4641 W.@..[]...[":!FA
00000030: 0756 1041 5658 105f 1b0f 4044 170a 6f0d .V.AVX._..@D..o.
00000040: 5150 5252 5d69 590e 5716 5518 055c 560f QPRR]iY.W.U..\V.
00000050: 4151 437e 7613 2f25 4f00 104e 0c3b 5e16 AQC~v./%O..N.;^.
00000060: 5017 5853 0b7c 0452 5250 4116 4e43 320a P.XS.|.RRPA.NC2.
00000070: 590b 445d 025d 5641 1d40 5e37 3823 4569 Y.D].]VA.@^78#Ei
00000080: 5e4b 5113 5b41 165c 5d0c 5743 5851 0b45 ^KQ.[A.\].WCXQ.E
00000090: 1751 5c55 160e 000d 4627 585d 0b51 5909 .Q\U....F'X].QY.
Solution
If we Google a bit, we encounter an amazing tool to analyze multi-byte xor cipher called xortool able to:
- guess the key length (based on count of equal chars)
- guess the key (base on knowledge of most frequent char)
If we run the tool with default settings, it outputs the following results:
$ xortool exclusive_key
The most probable key lengths:
2: 13.4%
4: 13.7%
8: 13.4%
10: 11.9%
12: 9.4%
16: 9.1%
18: 6.4%
20: 9.4%
24: 6.5%
40: 7.0%
Key-length can be 4*n
Most possible char is needed to guess the key!
Well, better than nothing. We can specify the most possible character with -c option, usually is 0x00 (null-byte) for binary data and 0x20 (whitespace) for text data. If we try either of the two, we obtain a similar result:
$ xortool exclusive_key -c "0x00"
The most probable key lengths:
2: 13.4%
4: 13.7%
8: 13.4%
10: 11.9%
12: 9.4%
16: 9.1%
18: 6.4%
20: 9.4%
24: 6.5%
40: 7.0%
Key-length can be 4*n
1 possible key(s) of length 4:
'\\][_
Found 0 plaintexts with 95%+ valid characters
See files filename-key.csv, filename-char_used-perc_valid.csv
The tool will create the folder xortool_out with three files in this case:
- 0.out: decrypted file with guessed xor key.
- filename-char_used-perc_valid.csv: list of most frequent char used for every file (in case of many) and percentage of valid characters in the decrypted file.
- filename-key.csv: list of key used for every file.
Unfortunately, the resulting file doesn’t seem to have been decrypted right:
$ xxd xortool_out/0.out | head
00000000: 5248 2853 4b4f 796c 7b45 014a 0300 0737 RH(SKOyl{E.J...7
00000010: 5956 1b04 0549 5d02 041b 1b54 1d5d 5255 YV...I]....T.]RU
00000020: 0b51 1b4a 5406 0651 4c49 007d 667c 1d1e .Q.JT..QLI.}f|..
00000030: 5b0b 4b1e 0a05 4b00 4752 1b1b 4b57 3452 [.K...K.GR..KW4R
00000040: 0d0d 090d 0134 0251 0b4b 0e47 5901 0d50 .....4.Q.K.GY..P
00000050: 1d0c 1821 2a4e 747a 135d 4b11 5066 0549 ...!*Ntz.]K.Pf.I
00000060: 0c4a 030c 5721 5f0d 0e0d 1a49 121e 6955 .J..W!_....I..iU
00000070: 0556 1f02 5e00 0d1e 411d 0568 647e 1e36 .V..^...A..hd~.6
00000080: 0216 0a4c 071c 4d03 0151 0c1c 040c 501a ...L..M..Q....P.
00000090: 4b0c 070a 4a53 5b52 1a7a 0302 570c 0256 K...JS[R.z..W..V
So, we can try to bruteforce the key. The tools counts with -b option to brute force all possible most frequent chars, or -o to constraint search to printable chars. If we try to run either of two options, we get a bunch of files with no sense at all. But, if we use -m option to specify a longer key, we obtain a more promising result:
$ xortool exclusive_key -o -m 256
The most probable key lengths:
2: 9.5%
4: 10.2%
8: 11.4%
10: 10.8%
12: 9.1%
16: 9.9%
20: 11.3%
24: 8.5%
30: 7.5%
40: 11.8%
Key-length can be 4*n
100 possible key(s) of length 40:
'gab\x16\x01\x13.67mg4kd77l:ac`a0dl`#c6606gram3ab(
'f`c\x17\x00\x12/76lf5je66m;`ba`1ema"b7717fs`l2`c)
'ec`\x14\x03\x11,45oe6if55n8cabc2fnb!a4424epco1c`*
'dba\x15\x02\x10-54nd7hg44o9b`cb3goc `5535dqbn0ba+
"cef\x12\x05\x17*23ic0o`33h>egde4`hd'g2242cvei7ef,
...
Found 35 plaintexts with 95%+ valid characters
See files filename-key.csv, filename-char_used-perc_valid.csv
35 plaintext! If we carefully examine the 99 resulting files, we can spot an almost decrypted HTML file of Wikipedia’s hacker entry in 14.out file:
$ xxd xortool_out/14.out | head
00000000: 3c21 444f 4354 5950 4520 6874 616c 3e0a <!DOCTYPE htal>.
00000010: 3c64 746d 6c20 636c 6173 363d 2263 6c69 <dtml clas6="cli
00000020: 652b 742d 6e6f 6a73 2220 6c61 6e67 3d22 e+t-nojs" lang="
00000030: 656e 2220 6869 723d 2260 7472 223e 0a3c en" hir="`tr">.<
00000040: 6865 2464 3e0a 3c6d 6531 6120 6368 6172 he$d>.<me1a char
00000050: 7365 743d 2255 5446 2d38 222f 320a 3c74 set="UTF-8"/2.<t
00000060: 6978 6c65 3e48 6163 6b65 3720 2d20 5769 ixle>Hacke7 - Wi
00000070: 6b2c 7065 6469 613c 2f74 6974 6c65 3e0a k,pedia</title>.
00000080: 3c73 6372 6570 743e 6463 6375 6d65 6e74 <scrept>dccument
00000090: 2e64 2a63 756d 656e 7400 6c65 6d65 6e74 .d*cument.lement
And if we examine the key used for that file, we can see that it follows the flag structure 247CTF{XXX}, but it contains some bytes out of the md5 hexstring hash range ([a-f0-9]). As we already know both the cipher and plain text, we can xor them to obtain the right key:
In [1]: with open('Hacker - Wikipedia.html', 'rb') as f:
...: plain = f.read()
...:
In [2]: with open('exclusive_key', 'rb') as f:
...: cipher = f.read()
...:
In [3]: ''.join([chr(p ^ c) for p, c in zip(plain[:40], cipher[:40])])
Out[3]: '247CTF{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}'
And the flag!
Daniel Uroz
PhD Student in Computer Science
My research interests include malware analysis, reverse engineering, network security, and forensics