CTF - The Catch 2023 - Cat Code

 Aj na modernej lodi CNS Josef Verich sa prejavil nedostatok IT vývojárov. Vďaka tomu sa dostal vývoj generátora prístupových kódov pre satelitné pripojenie na plecia mačky hlavného dôstojníka. Máme zdroják v Pythone a úlohu dopátrať kód. Dostávame radu, že síce mačky sú veľmi milé, štúdie ale preukázali, že nie sú dobrými vývojármi.

Máme dva súbory používajúce okrem pythonu prevažne mačacie názvy:

• meow.py - knižnica s funkciami meow a meowmeow
• meowmeow.py - hlavný program

Moje začiatočnícke vedomosti jazyka Python sa aspoň rozšíria analýzou tohto kódu, ale bude to otravné pre vás, čo ho ovládate :-)

1. Hlavný program

najskôr zanalyzujem, čo robí meowmeow.py, zas ma prenasledujú tie mačky:

#!/usr/bin/env python
# -*- coding:utf-8 -*-
"""
meow meow meow
"""

from meow import meow, meowmeow

def meoow():
    """
    meoow
    """
    meoword = ''
    while meoword != 'kittens':
        meoword = input('Who rules the world? ')
        if meoword in ['humans', 'dogs']:
            print('MEOW MEOW!')
    print(meowmeow(meow(sum([ord(meow) for meow in meoword]))))

if __name__ == '__main__':
    meoow()

Po bežných komentároch (ozn. #) tu je blok medzi troma úvodzovkami, tzv docstrings , náhradné riešenie nepodporovaných viac-riadkových komentárov v Pythone.

from meow import meow, meowmeow  - chce použiť funkcie z tejto knižnice (modulu)

Potom je tu funkcia a na konci je podmienka, ktorá túto funkciu zavolá:

if __name__ == '__main__'  - táto podmienka sa používa na spúšťanie kódu, ak je zdrojový kód zavolaný priamo. Obsah tejto podmienky sa nevykoná, ak sa kód pripája ako modul k inému.

Púšťame teda funkciu meoow() zadefinovanú uprostred tohto kódu. Funkcia najskôr obsahuje kód, ktorý sa pýta odpoveď na otázku kto vládne svetu:

while meoword != 'kittens':

    meoword = input('Who rules the world? ')
    if meoword in ['humans', 'dogs']:
        print('MEOW MEOW!')

Ako vidieť, Python na ohraničenie blokov kódu (v cykle, podmienke, ..) nepoužíva zátvorky, ani slová ako begin/end. Miesto toho je tu povinné odsadenie (4 medzery, tabulátor).

Tento cyklus sa tak stále pýta otázku, kým neodpovieme "kittens". Odpoveď bude uložená v premennej meoword. V prípade odpovedi "humans" alebo "dogs" zamňauká, ale pýta sa ďalej.

Ďalší príkaz je ten, ktorý zoberie slovo "kittens" a mal by nám vrátiť kód (predpokladám), avšak okrem mňaukania zamrzne.

print(meowmeow(meow(sum([ord(meow) for meow in meoword]))))

V kóde sú volané funkcie meow a meowmeow z knižnice meow.py v druhom súbore. Postupným vyhadzovaním som zistil, že zamŕza funkcia meow(). Vnútro ktoré do nej vstupuje, sa vyhodnotí ako číslo 770.

print (sum([ord(meow) for meow in meoword]))

770

Ďalšie pátranie teda pokračuje v kóde knižnice.

2. Knižnica meow.py

Knižnica obsahuje funkciu meow() volanú najprv (a zamŕzajúcu) a potom funkciu meowmeow().

Pozrime sa, čo funkcia meow() robí, prečo zamrzne.

#!/usr/bin/env python
# -*- coding:utf-8 -*-
"""
meow
"""

UNITE = 1
UNITED = 2
meeow = [
  [80, 81],
  [-4, 13],
  [55, 56],
  [133, 134],
  [-8, -7, -5],
  [4, 5],
  [5, 6],
  [6, 7],
  [7, 8],
  [15, -1],
  [11, 12],
  [13, 14],
  [17, 18],
  [18, 19],
  [15, 21],
  [22, 23],
  [26, 27],
  [44, 45],
  [48, 49],
  [31, -29],
  [50, 51],
  [60, 61],
  [72, 73],
  [73, 74],
  [19, 2, 20]]


def meow(kittens_of_the_world):
    """
    meowwwwww meow
    """
    print('meowwww ', end='')
    if kittens_of_the_world < UNITED:
        return kittens_of_the_world
    return meow(kittens_of_the_world - UNITE) + meow(kittens_of_the_world - UNITED)


def meowmeow(meow):
    """
    meow meow meow
    """
    meeoww = ''
    for meoww in meeow:
        print('meowwww ', end='')
        meeoww = f"{meeoww}{chr(int(''.join(str(meow)[m] for m in meoww)))}"
    return meeoww

Keď vyhodíme balast na začiatku, vidíme, že funkcia vyzerá takto:

def meow(vstup):

    if vstup < 2:

        return vstup

    return meow(vstup - 1) + meow(vstup - 2)

Ako vidieť, najspomalujúcejším faktorom je, že volá samú seba 2 krát. Vyzerá to ako akási fork bomba, kód sa tu však nevolá paralelne, ale sekvenčne. Teda po veľkom počte vnorení môže prísť k pretečeniu stacku. V každom prípade to však bude pre takýto veľký "strom" volaní veľmi pomalé riešenie.

Pri volaní funkcie s celými číslami od nuly vracia postupne:  0 1 1 2 3 5 8 13

Ako zisťujem, ide o Fibonacci-ho postupnosť - nasledujúce číslo je súčtom dvoch predchádzajúcich. Na webe sú aj vypočítané hodnoty, ale len prvých 300 a my ideme do 770. Dúfam, že Python také gigantické číslo dokáže spracovať.

Než sa pustím do tvorby vlastného kódu (prvotina.. dám si na čas), pozrime čo robí druhá funkcia.

    vystup = ''
    for meoww in meeow:
        vystup = f"{vystup}{chr(int(''.join(str(vstup)[m] for m in meoww)))}"
    return vystup

for meoww in meeow  - cyklus bežiaci pre každý prvok zo zoznamu (dvojíc a trojíc) v premennej meeow

Premenná meoww je teda postupne napĺňaná [80,81], potom [-4,13] atď., tento zoznam použije vnútri cyklu.

meeoww = f"{meeoww}{chr(int(''.join(str(meow[m] for m in meoww)))}"

Tu je vidieť, ako prvé, že premenná meeoww (vystup), ktorú funkcia vráti sa vyskladáva postupne z ľava do prava (po znakoch) pridávaním za existujúci reťazec funkciou f"". 

f"" je funkcia Pythonu formátujúca reťazce, teda často sa používa s print() funkciou.

chr(int(''.join(str(meow[m] for m in meoww)))

poďme z vnútornej strany - najskôr beží cyklus, kde m sa napĺňa číslami z meoww, teda vnútro z dvojíc a trojíc, toho zoznamu hore. Pre tieto čísla nájde zo vstupu daný znak v poradí, vyskladá do čísla po znakoch (cifrách).

Čiže tabuľka so zoznamom (meeow) dvojíc a trojíc čísel sú postupne indexy cifier (znakov reťazca), ktoré sú vo vstupe. Takto vlastne vyskladáme ascii číslo (int konverzia) a z neho potom znak (chr konverzia) pre funkciu f"". Ideme teda po jednom znaku, podľa tabuľky.

Znamená, že Fibonacciho 770-te číslo v poradí je vstup, z ktorého druhá (vonkajšia meowmeow) funkcia vyskladá z cifier ascii kódy jednotlivých znakov, podľa pevnej tabuľky v kóde.

3. Vlastný výpočet Fibonacciho

Keďže potrebujem vypočítať túto postupnosť pre jediné, vysoké číslo, nemusím funkciu šperkovať ošetrovaním vstupu a napevno nastavím prvé číslice (n1,n2). Sčítam výsledok do premennej, a popresúvam premenné tak, aby sa cyklus mohol zopakovať.

def meow(vstup):
    n1 = 0
    n2 = 1
    vysledok = 0
    
    while vstup > 1:
        vysledok = n1 + n2
        n1 = n2
        n2 = vysledok
        vstup -= 1
    
    return vysledok
    
print(meow(770))

37238998302736542981557591720664221323221262823569669806574084338006722578252257702859727311771517744632859284311258604707327062313057129673010063900204812137985

Výsledok má 161 cifier.

Po spustení s upravenou funkciou meow (fibo) vráti mačací kód do sekundy výsledok:

FLAG{YcbS-IAbQ-KHRE-BTNR}