pwnthem0le

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)

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

tags: crypto  classic-crypto  permutations