[Cyber Apocalypse CTF 2022] How The Columns Have Turned

1. Investigation

>> source.py

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()

언뜻 보니 PRNG 클래스를 이용해 매번 다른 랜덤한 정수를 생성하여 key 로 사용하고 해당 key 로 SUPER_SECRET_MESSAGES 를 문제 제작자 분이 손수 만든 암호화 기법(twistedColumnarEncrypt)을 사용하여 암호화 한 뒤 돌려주는 것 같아 보입니다.

 

>> encrypted_messages.txt

VEOAOTNRDCEEIFHIVHMVOETYDEDTESTHTCHLSRPDAIYAATOSTEGIIIOCIPYLTNOTLRTRNLEEUNBEOSFNANDHTUFTEETREEEEOEDHNRNYA
AAVPDESEETURAFFDUCEDAEECNEMOROCEANHPTTGROITCYSSSETTSKTTRLRIUAVSONOISECNJISAFAATAPATWORIRCETYUIPUEEHHAIHOG
NABPSVKELHRIALDVEHLORCNNOERUNGTAEEEHEHDORLIEEAOTITUTEAUEARTEFISESGTAYAGBTHCEOTWLSNTWECESHHBEIOYPNCOLICCAF
NIRYHFTOSSNPECMPNWSHFSNUTCAGOOAOTGOITRAEREPEEPWLHIPTAPEOOHPNSKTSAATETTPSIUIUOORSLEOAITEDFNDUHSNHENSESNADR
NUTFAUPNKROEOGNONSRSUWFAFDDSAAEDAIFAYNEGYSGIMMYTAANSUOEMROTRROUIIOODLOIRERVTAMNITAHIDNHRENIFTCTNLYLOTFINE

암호문 5개를 확인할 수 있습니다.

 

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

우리가 알고있는 모든 것은 이상한 암호화 기법에서 마지막으로 사용된 key 뿐이라며 Draeger 를 패배시키길 원한다면 마법을 부려서라도 어떻게든 해보라고 합니다.

key : 729513912306026

---

2. Solution

먼저 저는 PRNG 클래스가 어떻게 동작하는지 알아보고자 직접 코드를 떼다가 실행해보았습니다.

언뜻 봤을 때는 매번 랜덤한 정수를 생성하는 것 같아보였는데 똑같은 정수가 출력되는 것을 확인할 수 있었습니다. 이는 매번 seed 를 재생성하는 것이 아니라 고정된 seed 를 사용하고 있기 때문입니다.

 

이로써 dialog.txt 에서 주어진 마지막에 사용된 key 가 마지막에만 사용된 것이 아니라 모든 암호화에 사용됐음을 알 수 있습니다.

 

이 다음은 deriveKey 함수에 의해 새로 생성된 key 를 확인해보겠습니다.

derived_key = [13, 5, 14, 10, 3, 8, 15, 4, 6, 9, 1, 11, 2, 7, 12]

 

이 다음은 transpose 함수가 어떻게 동작하는지 확인해보겠습니다.

pt 에는 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 값을 주었고 이를 key 사이즈(15) 만큼 블록 단위로 나눈 뒤 transpose 함수를 수행하면 다음과 같이 변환된다는 것을 확인할 수 있습니다. (행과 열이 서로 바뀜)

BLOCK 1 : ABCDEFGHIJKLMNO
BLOCK 2 : PQRSTUVWXYZ
----transpose----
BLOCK 1 : AP
BLOCK 2 : BQ
BLOCK 3 : CR
BLOCK 4 : DS
BLOCK 5 : ET
BLOCK 6 : FU
BLOCK 7 : GV
BLOCK 8 : HW
BLOCK 9 : IX
BLOCK10 : JY
BLOCK11 : KZ

 

이 다음은 derived_key 를 이용하여 블록의 위치를 바꾼 뒤 String 형태로 바꿔주는 flatten 함수에 대해 알아보겠습니다.

(블록 사이즈를 맞춰주려고 pt 를 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123' 으로 변경했음)

derived_key = [13, 5, 14, 10, 3, 8, 15, 4, 6, 9, 1, 11, 2, 7, 12] 에서 for 문을 이용해 1 부터 인덱스 값을 찾아 ct 에 해당 block[index] 를 reverse 시킨 것을 저장합니다.

 

예를 들면 derived_key 에서 1 의 인덱스는 10 이므로 10번째 블록인 block[10] = ['K', 'Z'] 를 reverse 시킨 ['Z', 'K'] 를 ct 의 맨 처음에 저장합니다.

 

위와 같은 방식을 반복하여 블록들의 위치를 바꾸고 뒤집은 후 flatten 함수를 이용해 문자열로 바꾼 것이 최종적인 암호문이 됩니다.

ct = 'ZK1MTEWHQBXI2NUFYJSD0L3OPARCVG'

 

이제 위를 모두 반대로 수행하는 코드를 구현하면 됩니다.

 

>> sol.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 twistedColumnarDecrypt(ct, key):
    derived_key = deriveKey(key)
    # [13, 5, 14, 10, 3, 8, 15, 4, 6, 9, 1, 11, 2, 7, 12]

    width = len(key)
    # 15

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

    pt = [blocks[derived_key[i] - 1][::-1] for i in range(width)]
    #print(pt)

    pt = transpose(pt)
    #print(pt)
    
    
    pt = flatten(pt)
    return pt


def main():
    key = '729513912306026'

    with open("encrypted_messages.txt", "rb") as f:
        cts = [msg.strip().decode() for msg in f.readlines()]
    print(cts)
    print('='*64)

    flag = ''
    for ct in cts:
        pt = twistedColumnarDecrypt(ct, key)
        print(pt)
        flag += pt

    print(flag)
    '''
    THELOCATIONOFTHECONVOYDANTEISDETERMINEDTOBEONTHETHIRDPLANETAFTERVINYRYOUCANUSELIGHTSPEEDAFTERTHEDELIVERYS
    THECARGOISSAFEWENEEDTOMOVEFASTCAUSETHERADARSAREPICKINGUPSUSPICIOUSACTIVITYAROUNDTHETRAJECTORYOFTHEPLANETA
    BECAREFULSKOLIWHENYOUARRIVEATTHEPALACEOFSCIONSAYTHECODEPHRASETOGETINHTBTHE*****************************IT
    DONTFORGETTOCHANGETHEDARKFUELOFTHESPACESHIPWEDONTWANTANYUNPLEASANTSURPRISESTOHAPPENTHISSERIOUSMISSIONPOPO
    IFYOUMESSUPAGAINILLSENDYOUTOTHEANDROIDGRAVEYARDTOSUFFERFROMTHECONSTANTTERMINATIONOFYOURKINDAFINALWARNINGM
    '''
    # flag is in the 3rd block.
    # HTBTHE*****************************IT
    # add {} -> HTB{THE*****************************IT}


main()

🚩 FLAG : HTB{THE*****************************IT}