Jordan & Tunisia National CTF 2018 - Transposed Writeup

crypto
, ,

The challenge give us a zip file, with an encrypted string L{NTP#AGLCSF.#OAR4A#STOL11__}PYCCTO1N#RS.S and the encryption python code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import random

W = 7
perm = range(W)
random.shuffle(perm)

msg = open("flag.txt").read().strip()
while len(msg) % (2*W):
    msg += "."

for i in xrange(100):
    msg = msg[1:] + msg[:1]
    msg = msg[0::2] + msg[1::2]
    msg = msg[1:] + msg[:1]
    res = ""
    for j in xrange(0, len(msg), W):
        for k in xrange(W):
            res += msg[j:j+W][perm[k]]
    msg = res
print msg

Code Analysis

The challenge name give us an hint: we have to decrypt a transposition cipher. Basically the code selects a random permutation of , puts some padding at the end of the string to get a length multiple of and then encrypts the string. The encryption procedure works as follows:

  • Swaps the first and the last element of the string
  • Puts the characters with even index in the first half of the string and the ones with odd index in the second part (e.g. ABCDEFGH --> ACEGBDFH)
  • Swaps again the first and the last element
  • Split the string in blocks of characters and apply the selected permutation to each one
  • Iterate this process times

Attack

This entire process can be seen as a permutation itself (basically because we are working in the permutation group generated by the set and we are composing permutations). So, recalling that for every permutation there exist an integer such that (a sort of fixed point), and that this is at most the cardinality of the cyclic subgroup generated by , we can see that iterating this process with the right 7 elements permutation will give us the correct plaintext.
Fortunately, we have only permutations to test, and looking for the word FLAG in the result gives what we needed:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import random
import itertools

msg2 = "L{NTP#AGLCSF.#OAR4A#STOL11__}PYCCTO1N#RS.S"
for perm in itertools.permutations(range(7)):
    msg = msg2
    for i in xrange(100):
        msg = msg[1:] + msg[:1]
        msg = msg[0::2] + msg[1::2]
        msg = msg[1:] + msg[:1]
        res = ""
        for j in xrange(0, len(msg), 7):
            for k in xrange(7):
                res += msg[j:j+7][perm[k]]
        msg = res
        if "FLAG" in msg:
            print(msg)

Flag: FLAG{##CL4SS1CAL_CRYPTO_TRANSPOS1T1ON##}