Tornado was a reverse engineering challenge from the Fword CTF. We are given the following Python file:
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#!/usr/bin/python3
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from binascii import hexlify
import random
key = "very_awes0m3_k3y"
flag = "FwordCTF{xxx_xxx}" #REDACTED
assert len(flag) == 62
assert len(key) == 16
def to_blocks(text):
return [text[i*2:(i+1)*2].encode() for i in range(len(text)//2)]
def random_bytes(seed):
random.seed(seed)
return long_to_bytes(random.getrandbits(8*16))
def encrypt_block(block,key):
cipher = AES.new(key.encode(), AES.MODE_ECB)
plain_pad = pad(block, 16)
return hexlify(cipher.encrypt(plain_pad)).decode()
def encrypt(txt, key):
res = ""
blocks = to_blocks(txt)
for block in blocks:
res += encrypt_block(block, key)
return res
def translate(txt,l,r):
return txt[:l]+txt[r:]+txt[l:r]
def shuffle(txt):
seed=random.choice(txt)
random.seed(seed)
for _ in range(45):
l = random.randint(0, 15)
r = random.randint(l+1, 33)
txt = translate(txt, l, r)
return txt
flag = shuffle(flag)
print (encrypt(flag, key))
"""
3ce29d5f8d646d853b5f6677a564aec6bd1c9f0cbfac0af73fb5cfb446e08cfec5a261ec050f6f30d9f1dfd85a9df875168851e1a111a9d9bfdbab238ce4a4eb3b4f8e0db42e0a5af305105834605f90621940e3f801e0e4e0ca401ff451f1983701831243df999cfaf40b4ac50599de5c87cd68857980a037682b4dbfa1d26c949e743f8d77549c5991c8e1f21d891a1ac87166d3074e4859a26954d725ed4f2332a8b326f4634810a24f1908945052bfd0181ff801b1d3a0bc535df622a299a9666de40dfba06a684a4db213f28f3471ba7059bcbdc042fd45c58ae4970f53fb808143eaa9ec6cf35339c58fa12efa18728eb426a2fcb0234d8539c0628c49b416c0963a33e6a0b91e7733b42f29900921626bba03e76b1911d20728254b84f38a2ce12ec5d98a2fa3201522aa17d6972fe7c04f1f64c9fd4623583cc5a91cc471a13d6ab9b0903704727d1eb987fd5d59b5757babb92758e06d2f12fd7e32d66fe9e3b9d11cd93b11beb70c66b57af71787457c78ff152ff4bd63a83ef894c1f01ae476253cbef154701f07cc7e0e16f7eede0c8fa2d5a5dd5624caa5408ca74b4b8c8f847ba570023b481c6ec642dac634c112ae9fec3cbd59e1d2f84f56282cb74a3ac6152c32c671190e2f4c14704ed9bbe74eaafc3ce27849533141e9642c91a7bf846848d7fbfcd839c2ca3b
"""
By filling out the flag variable with some 62 character string, we recieve a 992 character long encrypted string. We see that 992=62*16, so it looks like each 16 characters corresponds to a character of the flag. Moreover, there is a 992 string provided at the bottom of the code, which seems like the encrypted, shuffled version of the flag we need to catch.
Objective
The given string is of the form encrypt(shuffle(flag)), so if we can apply the reverse operations, we should have the flag. This means that we need to write a decrypt and unshuffle function.
AES Decryption with ECB
We see that the string was encrypted with AES.MODE_ECB, which is AES encryption with the Electronic Codebook mode of operation. This encrypts message blocks independently, so being able to decrypt one block would be enough to decrypt all of them.
We split the encrypted flag into 62 blocks of 16, decrypt each block and then concatenate the result. To decrypt each block we need a key. This key was used for the encryption process, and since AES is symmetic, we can use it for the decryption process as well. The following code was used for the splitting and decryption:
1
2
3
4
5
6
7
8
9
10
11
12
13
def decrypt_block(key, block):
cipher = AES.new(key.encode(), AES.MODE_ECB)
inputblk = unhexlify(block)
dec = cipher.decrypt(inputblk)
return dec
def decflag():
ans = ""
target = "3ce...<redacted for brevity>...a3b"
for i in range(32):
piece = (decrypt_block(key,target[i*32:i*32+32])).decode("utf-8")
ans = ans + piece
print("block " + str(i+1) + ": " + ans)
This prints the following string:
1
block 32: aaFho_i_aC2b_abfc8edFw!kolae_ngbom_r__f_9T525eg__ihedd}{pmertt
The above string seems like a shuffled version of the flag since we can identify the FwordCTF{} letters.
Unshuffling the flag
Shuffling a string is based on translating a string several times. Translating a string means dividing a string up into 3 parts according to 2 (left and right) points, and then swapping the middle and right section of the string. Shuffling then translates the output again, but with new left and right points.
If we know the set of left and right points used to shuffle a string, we can unshuffle the string by untranslating it according to the last translation applied. The untranslate function is shown below:
1
2
3
4
5
def translate(txt,l,r):
return txt[:l]+txt[r:]+txt[l:r]
def untranslate(txt,l,r):
return txt[:l]+txt[l-r:]+txt[l:l-r]
The shuffle function geneates the left and right points randomly according to some seed. The seed was based on the actual flag we’re trying to get, so how can we generate the same random numbers?
Finding the seed
We see that for one shuffle iteration, we translate 45 times, which means generating 45 left and right point pairs. The left point is in the range of [0,15] and the right point is in the range of [l+1,33]. Trying to brute force the right combination of 45 pairs of left and right points seems like a bad idea.
If we look at the seed was chosen, we see that random.choice(txt) was used. This means that one character from the correct flag was chosen as the seed. Since we have the shuffled string, it means that one of the characters in the string corresponds to the seed. By looping through each character, the same set of left and right points would be generated at some point, which can then be used to unshuffle the string. This is the final unshuffle function used:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def unshuffle():
for i in range(62):
txt="aaFho_i_aC2b_abfc8edFw!kolae_ngbom_r__f_9T525eg__ihedd}{pmertt"
print("current seed: " + str(flag[i]))
boundsarray = []
random.seed(flag[i])
for j in range(45):
l = random.randint(0, 15)
boundsarray.append(l)
r = random.randint(l+1, 33)
boundsarray.append(r)
for k in range(89,-1,-2):
txt = untranslate(txt, boundsarray[k-1] , boundsarray[k])
print(txt + "\n")
Running unshuffle() and filtering the output gives us the following:
1
2
3
4
5
6
7
8
9
.../fword-ctf-2020# ./run.py | grep CTF -B 2
current seed: h
FwordCTF{peekaboo_i_am_the_flag_!_i_am_the_danger_52592bbfcd8}
--
current seed: h
FwordCTF{peekaboo_i_am_the_flag_!_i_am_the_danger_52592bbfcd8}
We found the flag, and we see that h was used as the seed. Big thanks to @FwordTeam and the author of the challenge! :)