HTB: Cyber Apocalypse 22 — How the columns have turned Writeup

Cyber Apocalypse 2022 Banner

Crypto: How the columns have turned writeup

Challenge description and lore

When unzipping the downloaded challenge we are presented with two .txt files, and one core source.py script:

dialog.txt:

Miyuki says:
Klaus it's your time to sign!
All we have is the last key of this wierd encryption scheme.
Please do your magic, we need to gather more information if we want to defeat Draeger.
The key is: 729513912306026

encrypted_messages.txt:

VEOAOTNRDCEEIFHIVHMVOETYDEDTESTHTCHLSRPDAIYAATOSTEGIIIOCIPYLTNOTLRTRNLEEUNBEOSFNANDHTUFTEETREEEEOEDHNRNYA
AAVPDESEETURAFFDUCEDAEECNEMOROCEANHPTTGROITCYSSSETTSKTTRLRIUAVSONOISECNJISAFAATAPATWORIRCETYUIPUEEHHAIHOG
NABPSVKELHRIALDVEHLORCNNOERUNGTAEEEHEHDORLIEEAOTITUTEAUEARTEFISESGTAYAGBTHCEOTWLSNTWECESHHBEIOYPNCOLICCAF
NIRYHFTOSSNPECMPNWSHFSNUTCAGOOAOTGOITRAEREPEEPWLHIPTAPEOOHPNSKTSAATETTPSIUIUOORSLEOAITEDFNDUHSNHENSESNADR
NUTFAUPNKROEOGNONSRSUWFAFDDSAAEDAIFAYNEGYSGIMMYTAANSUOEMROTRROUIIOODLOIRERVTAMNITAHIDNHRENIFTCTNLYLOTFINE

The ciphertext consits of five blocks of 105-long strings. In order to understand how the strings have been encrypted, we must first look at the source code of the python script.

The first point-of-interest is the PRNG class, which has some interesting parameters at first glance. Upon further inspection, we can see that its role matches more the one of a decoy, as the object’s constructor is called only once, and its next() function always produces the same key.

When looking at the main() function we also notice that the key found in the dialog.txt file is the initial key passed to the core encryption function, namely twistedColumnarEncrypt().

def twistedColumnarEncrypt(pt, key):
    derived_key = deriveKey(key)
    width = len(key)
    blocks = [pt[i:i + width] for i in range(0, len(pt), width)]
    blocks = transpose(blocks)
    ct = [blocks[derived_key.index(i + 1)][::-1] for i in range(width)]
    ct = flatten(ct)
    return ct

Let us go through this function step by step. Firstly, we take our known key and mess with it. The specifics of how we mess with it are not important, as we can just use the same function on the key provided to us in the text file:

deriveKey(str(729513912306026)) 
-> [13, 5, 14, 10, 3, 8, 15, 4, 6, 9, 1, 11, 2, 7, 12]

We now have an array of the values 1–15 as the key. Moving further down the encryption function, we first define width, which is the length of our array, so fifteen. We then split the “plaintext” (which we don’t have yet) into blocks of 15. As there is no padding function, this means our plaintext has to be a multiple of 15, otherwise the function fails. We then run our array of 15-byte strings through the transpose function:

def transpose(array):
    return [row for row in map(list, zip(*array))]

While it admittedly looks confusing, all this function does is iterate through the blocks and concatenate the first character of each into an array, then the second character, and so forth. To illustrate this, I created a 2D array of 15-byte words (A-O). After running transpose, you can see that all A’s are concatenated together, as well as the B’s, C’s, etc. More importantly, they are concatenated in order.

blocks = ['ABCDEFGHIJKLMNO', 'ABCDEFGHIJKLMNO', 'ABCDEFGHIJKLMNO', 'ABCDEFGHIJKLMNO', 'ABCDEFGHIJKLMNO', 'ABCDEFGHIJKLMNO', 'ABCDEFGHIJKLMNO']
transpose(blocks)
-> [['A', 'A', 'A', 'A', 'A', 'A', 'A'], ['B', 'B', 'B', 'B', 'B', 'B', 'B'], ['C', 'C', 'C', 'C', 'C', 'C', 'C'], ['D', 'D', 'D', 'D', 'D', 'D', 'D'], ['E', 'E', 'E', 'E', 'E', 'E', 'E'], ['F', 'F', 'F', 'F', 'F', 'F', 'F'], ['G', 'G', 'G', 'G', 'G', 'G', 'G'], ['H', 'H', 'H', 'H', 'H', 'H', 'H'], ['I', 'I', 'I', 'I', 'I', 'I', 'I'], ['J', 'J', 'J', 'J', 'J', 'J', 'J'], ['K', 'K', 'K', 'K', 'K', 'K', 'K'], ['L', 'L', 'L', 'L', 'L', 'L', 'L'], ['M', 'M', 'M', 'M', 'M', 'M', 'M'], ['N', 'N', 'N', 'N', 'N', 'N', 'N'], ['O', 'O', 'O', 'O', 'O', 'O', 'O']]

With that in mind, the last part of the encryption function is running a list comprehension on the newly transposed blocks. It uses a simple algorithm to scramble the blocks, and invert their contents. More on that later.

The final flatten() function is just there to concatenate characters into strings. If we run it on the above 2D array returned by transpose(blocks), we get:

AAAAAAABBBBBBBCCCCCCCDDDDDDDEEEEEEEFFFFFFFGGGGGGGHHHHHHHIIIIIIIJJJJJJJKKKKKKKLLLLLLLMMMMMMMNNNNNNNOOOOOOO

So to summarize, here are the four steps that turn plaintext into ciphertext, and which we subsequently have to reverse:

1. Split message into 15-byte words
2. Transpose blocks
3. Scramble blocks & invert contents
4. Concatenate blocks into String

With all that in mind, let us begin the reversing process. We can pick any of the encrypted lines to test out our decryption. Let’s load it into a variable, and split it into 15-byte blocks using list comprehension:

blocks = [ct[i:i+7] for i in range(0, len(ct), 7)] # ct -> ciphertxt

We now have an array of length 7, with 15-byte blocks, adding up to a total of 105 bytes. The next step to reverse is the third one, namely the scramble.

For this step we create a second, empty, array, to which we will gradually add the different blocks. Contrary to our original array, this one will contain 15 sub-arrays, with blocks of length 7. This is due to the Transposing that was done in step two.

rev_blocks = [[] for i in range(15)] # Empty array 

In order to unscramble the blocks, we have to understand what the below line of code did to our existing plaintext blocks:

def twistedColumnarEncrypt(pt, key):
    ...
ct = [blocks[derived_key.index(i + 1)][::-1] for i in range(width)]
...

Essentially, it takes our existing blocks, and places each one of them in the position assigned by the derived key, reversing its contents by using [::-1]. Remeber, the derived key is an array of scrambled integers from 1–15. The index(x) function then returns where this integer can be found in the array:

derivedKey = [13, 5, 14, 10, 3, 8, 15, 4, 6, 9, 1, 11, 2, 7, 12]
derivedKey.index(1) = 10
derivedKey.index(2) = 12
derivedKey.index(3) = 4
...
derivedKey.index(15) = 6

So, to illustrate a simplified version of this algorithm, we insert the blocks of plaintext into the return value of index in a new array:

['FirstBlock', 'SecondBlock', 'ThirdBlock']
derivedKey.index(1) = 2
derivedKey.index(2) = 0
derivedKey.index(3) = 1
-> [0:'kcolBdnoceS', 1:'kcolBdrihT', 2:'kcolBtsriF']

All we have to do is reverse this simple algorithm, and we will have our (transposed) plaintext. We can then just run the transpose() on the resulting blocks and will have the decrypted plaintext. Here’s the decryption function I came up with to reverse it:

def decrypt(ct, key):
    blocks = [ct[i:i+7] for i in range(0, len(ct), 7)]
    rev_blocks = [[] for i in range(15)]
    
    # Undo scramble
    derived_key = deriveKey(str(key))
    for i in range(15):
        rev_blocks[derived_key.index(i+1)] = blocks[i]
    rev_blocks = [i[::-1] for i in rev_blocks]
    rev_blocks = transpose(rev_blocks)
    return flatten(rev_blocks)

I first split the ciphertext into seven 15-byte blocks;
I then create the second array of 15 sub-arrays;
I derive the key to get the new positions of the blocks;
For every block in the new array (so 15 times) I insert the ciphertext block i into the index yielded by the derived key. This can take a bit to wrap your head around so I suggest you read it again.
Lastly, for every block in the new array, I reverse it, using [::-1], and then transpose the whole array, before returning it as a string by using flatten().

The final program to decrypt all messages is:

# solve.py
import os
from clean import *
def decrypt(ct, key):
    blocks = [ct[i:i+7] for i in range(0, len(ct), 7)]
    rev_blocks = [[] for i in range(15)]
    
    # Undo scramble
    derived_key = deriveKey(str(key))
    for i in range(15):
        rev_blocks[derived_key.index(i+1)] = blocks[i]
    rev_blocks = [i[::-1] for i in rev_blocks]
    rev_blocks = transpose(rev_blocks)
     return flatten(rev_blocks)
if __name__ == "__main__":
    with open("encrypted_messages.txt", "r") as f:
        lines = f.readlines()
     for line in lines:
        print(decrypt(line.strip(), 729513912306026))

Side-note: clean.py is a copy of the original source.py, but without the “with” statement at the start, and without the main function. This was done so I can cleanly import all the existing functions without having to load the textfile into memory each time. I will attach it below to avoid confusion; you can paste it into the same directory as the other files, just make sure to save it as clean.py.

# clean.py
import os
def deriveKey(key):
    derived_key = []
for i, char in enumerate(key):
        previous_letters = key[:i]
        new_number = 1
        for j, previous_char in enumerate(previous_letters):
            if previous_char > char:
                derived_key[j] += 1
            else:
                new_number += 1
        derived_key.append(new_number)
    return derived_key
def transpose(array):
    return [row for row in map(list, zip(*array))]
def flatten(array):
    return "".join([i for sub in array for i in sub])
def twistedColumnarEncrypt(pt, key):
    derived_key = deriveKey(key)
    width = len(key)
    blocks = [pt[i:i + width] for i in range(0, len(pt), width)]
    blocks = transpose(blocks)
    ct = [blocks[derived_key.index(i + 1)][::-1] for i in range(width)]
    ct = flatten(ct)
    return ct
class PRNG:
    def __init__(self, seed):
        self.p = 0x2ea250216d705
        self.a = self.p
        self.b = int.from_bytes(os.urandom(16), 'big')
        self.rn = seed
def next(self):
        self.rn = ((self.a * self.rn) + self.b) % self.p
        return self.rn