Jordan & Tunisia National CTF 2018 - Transposed Writeup

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

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 \({1,2,...,7}\), puts some padding at the end of the string to get a length multiple of \(14\) 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 \(7\) characters and apply the selected permutation to each one
• Iterate this process \(100\) 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 \(A = {1,...,14k}\) and we are composing permutations). So, recalling that for every permutation \(\pi\) there exist an integer \(n\) such that \(\pi^n(x)=x\) (a sort of fixed point), and that this \(n\) is at most the cardinality of the cyclic subgroup generated by \(\pi\), we can see that iterating this process with the right 7 elements permutation will give us the correct plaintext. Fortunately, we have only \(7!=5040\) permutations to test, and looking for the word FLAG in the result gives what we needed:

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##}