Aller au contenu
skifo/ BA26 CTF
Tous les challenges
Reverse Résolu Moyen · 3 000 m

Universal Translator

Une transmission pour une VM à pile façon Forth, à désassembler puis exécuter.

Auteur
Nicolas Philipp
Scripts
3 fichiers

Énoncé (résumé)

Une sonde a intercepté une transmission (transmission.bin) destinée à un vieux « traducteur universel ». Le traducteur a perdu la table qui associe les identifiants numériques aux mots de son dictionnaire. On dispose de 4 programmes d’exemple (samples/sample_0{1..4}.bin) avec la sortie exacte produite à l’époque.

Analyse

Le README décrit une machine Forth :

  • pile de cellules 64 bits, tokens d’un octet lus de gauche à droite ;
  • 0x00–0x07 = DUP, DROP, SWAP, OVER, ROT, NIP, TUCK, EMIT (ordre inconnu) ;
  • 0x10–0x19 = +, -, *, XOR, AND, OR, MAX, MIN, LSHIFT, RSHIFT (ordre inconnu) ;
  • tout autre octet = littéral non signé poussé sur la pile ;
  • une sortie n’est enregistrée que si le programme s’est terminé « sans incident » (donc un underflow de pile invalide une table).

Sorties attendues :

Programme Sortie
sample_01 41 41 0B 20 30
sample_02 29 2A 58 43 58 43
sample_03 18 37 39 39 23
sample_04 3B 33 11 08 3E 10 01 40 08 00 08

Il faut retrouver les deux permutations, puis exécuter la transmission.

Point clé

  1. Séparer le problème. Les samples 1 et 2 n’utilisent que 0x00–0x07. On brute-force 8! = 40 320 permutations, en considérant l’underflow comme un échec. Une seule table convient : 00 ROT, 01 TUCK, 02 OVER, 03 DUP, 04 EMIT, 05 NIP, 06 SWAP, 07 DROP.
  2. Les 10! permutations arithmétiques en non signé donnent 0 solution (brute.c, ~1,5 s). La sémantique supposée est donc fausse quelque part.
  3. La fin de sample_04 contient de petits calculs isolés (lit lit op EMIT) qui fixent six opérations à la main :
    • 08 08 19 → 0x10 : 19 = +
    • 0a 09 17 → 0x01 : 17 = -
    • 08 08 13 → 0x40 : 13 = *
    • 09 0a 14 → 0x08 : 14 = AND
    • 08 08 12 08 10 → 0x08 : 12 = LSHIFT, 10 = RSHIFT (8<<8 = 0x800, puis >>8 = 8 ; l’inverse donnerait 0)
    • 08 09 10 → 0x00 : confirme 10 = RSHIFT
  4. Le piège : MIN et MAX comparent en signé (complément à deux sur 64 bits). Les longues chaînes de sample_03/04 produisent des valeurs négatives via - et *. En testant les 4! ordres restants avec MIN/MAX signés, une seule table reproduit exactement les samples 3 et 4 : 11 XOR, 15 MIN, 16 MAX, 18 OR.

Table finale complète :

Octet Mot Octet Mot
00 ROT 10 RSHIFT
01 TUCK 11 XOR
02 OVER 12 LSHIFT
03 DUP 13 *
04 EMIT 14 AND
05 NIP 15 MIN (signé)
06 SWAP 16 MAX (signé)
07 DROP 17 -
18 OR
19 +

EMIT sort l’octet de poids faible du sommet de la pile.

Exploitation (reproductible)

cd .
python3 -I solve.py              # table des opérations de pile (solution unique)
cc -O2 -o brute brute.c && ./brute   # 10! en non signé : 0 solution (montre le piège)
python3 -I brute2.py | grep True  # variantes signé/non signé, une seule table valide
python3 -I brute2.py | tail -1    # exécute transmission.bin → flag

Sortie :

b'BA26{0n3_st4ck_f0rth_4ll}'

Scripts

  • solve.py : interpréteur et brute-force des 8! opérations de pile (samples 1–2).
  • brute.c : brute-force en C des 10! opérations arithmétiques, en non signé (aucune solution).
  • brute2.py : six opérations fixées à la main, test des 4! restantes avec MIN/MAX signés ou non signés, puis exécution de transmission.bin.
  • files/universal_translator/ : contenu du zip.

Code

import itertools, sys
D='./files/universal_translator/'
S=[open(D+f'samples/sample_0{i}.bin','rb').read() for i in range(1,5)]
T=open(D+'transmission.bin','rb').read()
EXP=[bytes.fromhex(x) for x in ['41410B2030','292A58435843','1837393923','3B3311083E1001400800 08'.replace(' ','')]]
M=(1<<64)-1
STK=['DUP','DROP','SWAP','OVER','ROT','NIP','TUCK','EMIT']
ARI=['+','-','*','XOR','AND','OR','MAX','MIN','LSHIFT','RSHIFT']
class E(Exception):pass
def run(prog,tab,maxout=None):
    s=[];out=[]
    for b in prog:
        w=tab.get(b)
        if w is None: s.append(b); continue
        if w=='DUP':
            if len(s)<1: raise E
            s.append(s[-1])
        elif w=='DROP':
            if len(s)<1: raise E
            s.pop()
        elif w=='SWAP':
            if len(s)<2: raise E
            s[-1],s[-2]=s[-2],s[-1]
        elif w=='OVER':
            if len(s)<2: raise E
            s.append(s[-2])
        elif w=='ROT':
            if len(s)<3: raise E
            s.append(s.pop(-3))
        elif w=='NIP':
            if len(s)<2: raise E
            del s[-2]
        elif w=='TUCK':
            if len(s)<2: raise E
            s.insert(-2,s[-1])
        elif w=='EMIT':
            if len(s)<1: raise E
            out.append(s.pop()&0xff)
        else:
            if len(s)<2: raise E
            b2=s.pop();a=s.pop()
            if w=='+':r=a+b2
            elif w=='-':r=a-b2
            elif w=='*':r=a*b2
            elif w=='XOR':r=a^b2
            elif w=='AND':r=a&b2
            elif w=='OR':r=a|b2
            elif w=='MAX':r=max(a,b2)
            elif w=='MIN':r=min(a,b2)
            elif w=='LSHIFT':r=a<<b2 if b2<64 else 0
            elif w=='RSHIFT':r=a>>b2 if b2<64 else 0
            s.append(r&M)
    return bytes(out)
sols=[]
for p in itertools.permutations(STK):
    tab=dict(zip(range(8),p))
    try:
        if run(S[0],tab)==EXP[0] and run(S[1],tab)==EXP[1]: sols.append(tab)
    except E: pass
print(len(sols)); [print(t) for t in sols]

Aussi en Reverse