pwnthem0le

Home Blog About GitHub

pwnthem0le is a Turin-based, hacking students group born out of CyberChallenge 2018. Read more about us!

16 September 2018

Jordan & Tunisia National CTF 2018 - Transposed Writeup

by mr96

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 , 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:

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:

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

tags: crypto  classic-crypto  permutations