Další dimenze - Autorské řešení úlohy

Solution #

Máme program.b93. Když trochu pogooglíme, zjistíme, že se jedná o esoterický programovací jazyk Befunge:

Befunge je dvojdimenzionální ezoterický programovací […]. Hlavním cílem bylo vytvořit jazyk, který bude tak obtížný ke kompilaci, jak jen to bude možné.

Vypadá to, že nás čeká pořádná zábava…

Befunge 101 #

Pozn.: Tato sekce je spíše jen informativní, ne nutně důležité pro řešení.

Befunge je 2D programovací jazyk - v programu se pohybujeme jako v hracím poli pomocí “šipek” (<>v^) a v tomto daném směru se pohybujeme, dokud nám směr jiná instrukce nezmění. K dispozici máme zásobník, do kterého lze přidávat hodnoty 0-9 (pomocí příslušných číslic) nebo pomocí uvozovek ("), které začínají a ukončují “string” mód, ve kterém všechny znaky, na které narazíme, vloží svoji hodnotu (ASCII) do zásobníku. Dále zde máme instrukce pro artitmetické operace +-*/, které vezmou 2 horní hodnoty zásobníku, provedou příslušnou operaci a výsledek vloží do zásobníku. Poté jsou zde podmínky _ a |. _ vezme hodnotu ze zásobníku a pokud je hodnota nula, pokračujeme od instrukce doprava, jinak doleva. Obdobně se chová | - vezme hodnotu ze zásobníku a pokud je hodnota rovna nule, změníme směr dolů, jinak pokračujeme nahoru.

To by bylo rychlé shrnutí základních instrukcí Befunge.

Analýza #

Nejlepší způsob, jak začít analýzu, je pokusit se program spusit. Ačkoliv Befunge je navrženo tak, aby bylo extrémně komplikované ho zkompilovat (ale často to není nemožné, viz třeba cfunge), tak interpterace je relativně jednoduchá. Na internetu lze najít několik online interpteterů, které navíc mají často schopnost zobrazit zásobník a i (doslova) program flow. Osobně doporučuji tento, alternativně tento (zde ale je rozbité handlování vstupu, musí se manuálně patchnout, ale na druhou stranu tento je dle mého mnohem přívětivější).

Když program spustíme (jakoukoliv metodou; třeba jsme zjistili, že máme moc času a tak jsme si vytvořili vlastní interpreter), zjistíme, že vypíše prgoram “Vstup (37 znaku): " a pak se opakovaně ptá na vstup (konkrétně 37krát), zadáme třeba 37x “A”.

Následně (pokud máme možnost vizualizace programu), můžeme vidět, že se program vydává do oblasti, kde se opakovaně střídají tyto 2 řádky (liší se jen poslední 2 čísla):

^##>#-##:#1##_  $\93+0g-#^_v
> #^ #-##:#1##_ $\93+1g-#^_v

Program celou tuto sekci projede (oba “sloupce”), vyskočí pryč, vypíše “Spatne!” a skončí. Když ale zkusíme zadat něco, co má formát vlajky (třeba HCKR{AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}), tak zjistíme, že na “poslední” řádce se program rozhodl jinak, něco provedl a vydal se procházet celou tuto sekci znova. Pokud jsme ještě více pozorní, můžeme si všimnout, že ze zásobníku zmizela hodnota }/125.

Na základě tohoto si lze tipnout, že každá tato “řádka” kontroluje jeden znak - to si lze potvrdit i tím, že těchto řádek je příhodně 37 (= délka vstupu).

Vyřešení #

Nyní když máme dobrý tip na to, co se (hodně abstraktně) děje, tak musíme přijít na to, jak se reálně ověřují zadané znaky… Víme, že poslední “řádka” (> #^ #-##:#1##_ $\93+7g-#^_v) kontroluje }, to je dobrý start kde začít.

Jediné rozhodování v tomto kusu kódu jsou 2 instrukce _. Pozorovnáním průběhu vykonávání zjistíme, že se (v tomto) začíná zleva a prvnímu rozhodování (instrukce _) předchází jen : (duplikování zásobníku). Pokud není nula, tak se “vracíme zpět” a jdeme na další řádek… to není moc zajímavý. Pokud ale je nula, tak se pokračuje “dále na řádku” na $\93+7g-#^_v. Zde se nějak manipuluje se zásobníkem (pop a prohození), následně se na zásobník dá 9+3 a 7 a vykoná se instrukce g.

g je “speciální” instrukce a jeden z důvodů, proč je Befunge tak obtížný na kompilaci. g umožňuje přečíst znak programu (který se zrovna vykonává) a načíst na zásobník. Jaký znak se načte, určují dvě hodnoty ze zásobníku, vrchní je vertikální souřadnice, druhá je horizontální (obě se počítají od nuly, tedy 0 znamená první řádka/sloupec). V našem případě je to tedy (vrchní/první) 7 a (spodní/druhá) 12. A naštěstí pro nás na této pozici v programu je znak }, což odpovídá našim nálezům.

Nyní můžeme už nám zbývá jen tyto pozice zjistit (a “vyhodnotit”) pro každý řádek, pokud jsme líný, můžeme si na to napsat i nějaký progámek.

Na konci tohoto procesu dostanem vlajku HCKR{Pr1Ste_s1_Vy2k0uS1m3_3D_Pr0GraM}.

Exploit script #

Skript (tedy “nějaký ten prográměk” z předposledního odstavce minulé sekce), který ze zadaného programu dokáže vlajku vyčíst.

INPUT = "program.b93"

CHARS = r"""
ABCDEabcd
FGHIJefgh
KLMNOijkl
PQRSTmnop
UVWXYqrst
Z0123uvwx
45678yz()
9{}_.[]\/
""".strip().split("\n")

SPLIT_COLUMN = 45
MARK = "$\\"

def resolve_pos(pos_str):
    return CHARS[int(pos_str[3])][int(pos_str[1])-1]

first: list[str] = []
second: list[str] = []

with open(INPUT) as f:
    for line in f:
        a = line[:SPLIT_COLUMN]
        b = line[SPLIT_COLUMN:]
        if MARK in a: first.append(resolve_pos(a.split(MARK)[1]))
        if MARK in b: second.append(resolve_pos(b.split(MARK)[1]))

print("".join(first[::-1]+second[::-1]))