<- CRYPTO

How The Columns Have Turned

4 minutes to read

We are given a Python code to encrypt the flag (source.py), and we are also given dialog.txt and encrypted_messages.txt:

import os


with open('super_secret_messages.txt', 'r') as f:
    SUPER_SECRET_MESSAGES = [msg.strip() for msg in f.readlines()]


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


def main():
    seed = int.from_bytes(os.urandom(16), 'big')
    rng = PRNG(seed)

    cts = ""

    for message in SUPER_SECRET_MESSAGES:
        key = str(rng.next())
        ct = twistedColumnarEncrypt(message, key)
        cts += ct + "\n"

    with open('encrypted_messages.txt', 'w') as f:
        f.write(cts)

    dialog = "Miyuki says:\n"
    dialog += "Klaus it's your time to sign!\n"
    dialog += "All we have is the last key of this wierd encryption scheme.\n"
    dialog += "Please do your magic, we need to gather more information if we want to defeat Draeger.\n"  
    dialog += f"The key is: {str(key)}\n"

    with open('dialog.txt', 'w') as f:
        f.write(dialog)


if __name__ == '__main__':
    main()

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

ETYDEDTYAATOSTTUFTEETHIVHMVOSFNANDHEGIIIOCESTHTCHDHNRNYALSRPDAIRDCEEIFREEEEOETLRTRNLEEUNBEOIPYLTNOVEOAOTN  
EECNEMOTCYSSSEORIRCETFDUCEDAATAPATWTTSKTTRROCEANHHHAIHOGPTTGROIEETURAFYUIPUEEONOISECNJISAFALRIUAVSAAVPDES
GTNOERUTOIAOTIGRESHHBTSEHLORSRSSNTWINTEAUEENTAEEENOICCAFOSHDORLUFHRIALNGOYPNCEIGTAYAPETHCEOUATEFISTFBPSVK
SNUTCAGPEEPWLHITEDFNDMPNWSHFORSLEOAIPTAPEOOOAOTGOSESNADRITRAEREOSSNPECUHSNHENSAATETTPSIUIUOOHPNSKTNIRYHFT
WFAFDDSGIMMYTADNHRENINONSRSUMNITAHIANSUOEMAAEDAIFLOTFINEAYNEGYSNKROEOGFTCTNLYIIOODLOIRERVTAROTRROUNUTFAUP

The idea here is to reverse the algorithm, let’s review what it does:

  • It generates a seed with a custom Pseudo Random Number Generator (PRNG) and uses the next iteration as the key for the encryption algorithm
  • It derives a new key using a custom function deriveKey
  • Separates the message in blocks of the same width
  • Transposes the blocks (i.e. [[1, 2], [3, 4]] becomes [[1, 3], [2, 4]])
  • Then it takes each element of the derived key to sort the blocks and reverse each block
  • Finally, it flattens the list of blocks to a single list (i.e. [[1, 2], [3, 4]] becomes [1, 2, 3, 4])

Let’s start by analyzing the PRNG implementation:

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

The next function has a bad implementation, since ((self.a * self.rn) + self.b) % self.p equals self.b % self.p, and self.b is a fix value. So, next always returns the same value, and we have this in dialog.txt: 148823505998502.

Now, let’s try to reverse the encryption in 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

Since we know the key, and it is always the same, the derived key will be always the same too. Hence, the width of the blocks is constant, so we can start by separating the ciphertext into blocks:

def twisted_columnar_decrypt(ct, key):
    derived_key = derive_key(key)
    width = len(key)
    length = len(ct) // len(key)

    blocks = [list(ct[i:i + length]) for i in range(0, len(ct), length)]

Notice that length is not width, because of the transposition. The relationship between length and width is: len(ct) = length * width.

Now, we need to assign the plaintext at the index of derived key, the corresponding block reversed. It can be a little confusing, but is just the reverse operation. Finally, transpose and flatten the list of blocks:

def twisted_columnar_decrypt(ct, key):
    derived_key = derive_key(key)
    width = len(key)
    length = len(ct) // len(key)

    blocks = [list(ct[i:i + length]) for i in range(0, len(ct), length)]  

    pt = blocks.copy()

    for i in range(width):
        pt[derived_key.index(i + 1)] = blocks[i][::-1]

    pt = transpose(pt)
    pt = flatten(pt)

    return pt

We only need to read the given files and do the decryption. This is the plain text:

$ python3 solve.py
THELOCATIONOFTHECONVOYDANTEISDETERMINEDTOBEONTHETHIRDPLANETAFTERVINYRYOUCANUSELIGHTSPEEDAFTERTHEDELIVERYS  
THECARGOISSAFEWENEEDTOMOVEFASTCAUSETHERADARSAREPICKINGUPSUSPICIOUSACTIVITYAROUNDTHETRAJECTORYOFTHEPLANETA
BECAREFULSKOLIWHENYOUARRIVEATTHEPALACEOFSCIONSAYTHECODEPHRASETOGETINHTBTHISRNGISNOTSAFEFORGENETINGOUTPUTS
DONTFORGETTOCHANGETHEDARKFUELOFTHESPACESHIPWEDONTWANTANYUNPLEASANTSURPRISESTOHAPPENTHISSERIOUSMISSIONPOPO
IFYOUMESSUPAGAINILLSENDYOUTOTHEANDROIDGRAVEYARDTOSUFFERFROMTHECONSTANTTERMINATIONOFYOURKINDAFINALWARNINGM

$ python3 solve.py | grep -E HTB.+
BECAREFULSKOLIWHENYOUARRIVEATTHEPALACEOFSCIONSAYTHECODEPHRASETOGETINHTBTHISRNGISNOTSAFEFORGENETINGOUTPUTS

So the flag is:

HTB{THISRNGISNOTSAFEFORGENETINGOUTPUTS}

The full script can be found in here: solve.py.