Shapeshifter | Romain Bertin

Publié sur W3Challs puis retiré, Shapeshifter est un petit PE32 x86. Il lit une entrée et n’affiche son message qu’en cas de succès.

Objectif : retrouver une entrée valide, sans source ni indication sur le format attendu. On part du point d’entrée.

Le binaire

$ r2 -2 -q shapeshifter.exe
[0x00402000]> aaa
[0x00402000]> iI
arch     x86
baddr    0x400000
binsz    3128
bintype  pe
bits     32
class    PE32
os       windows
subsys   Windows CUI

C’est un PE32 x86 de 3 128 octets. Voici ses sections :

[0x00402000]> iS
nth paddr        size vaddr        vsize perm name
0   0x00000400  0x344 0x00401000  0x1000 -rw- data
1   0x00000800  0x13d 0x00402000  0x1000 -rw- text
2   0x00000a00   0x6e 0x00403000  0x1000 sr-- imports
3   0x00000c00   0x38 0x00404000  0x1000 sr-- relocs

La section text ne contient que 0x13d octets. Les imports sont tout aussi courts :

[0x00402000]> ii
msvcrt.dll  exit
msvcrt.dll  _write
msvcrt.dll  _read

Pas de fichier externe, pas de crypto, pas de chargement dynamique. Toute la validation tient dans cette routine.

Lecture de l’entrée

Les premières instructions lisent dix octets depuis l’entrée standard vers le buffer 0x40133a.

[0x00402000]> pd 18
0x00402000  push 0xa
0x00402002  push 0x40133a
0x00402007  push 0
0x00402009  call dword [sym.imp.msvcrt.dll__read]

La boucle suivante traite chaque caractère :

[0x00402000]> pd 12 @ 0x402014
0x00402014  movzx eax, byte [ecx + 0x40133a]
0x0040201b  sub eax, 0x41
0x0040201e  cmp eax, 0
0x00402021  jl 0x402135
0x00402027  cmp eax, 0x10
0x0040202a  jg 0x402135
0x00402030  mov byte [ecx + 0x40133a], al

La soustraction de 'A' convertit la lettre en entier :

A = 0, B = 1, ..., Q = 16

Le premier check accepte dix caractères entre A et Q. La même conversion servira pour décoder le message final :

def normalize(password):
    return [ord(char) - ord("A") for char in password]

Calcul de l’index

Après dix itérations, le programme charge deux accumulateurs 32 bits depuis la section data :

[0x00402000]> pd 12 @ 0x40203e
0x0040203e  mov esi, dword [0x401000]
0x00402044  mov edi, dword [0x401004]
0x0040204a  xor eax, eax
0x0040204c  xor edx, edx
0x0040204e  mov ecx, edx
0x00402050  shl ecx, 4
0x00402053  movzx eax, byte [edx + 0x40133a]
0x0040205a  add ecx, eax
0x0040205c  mov eax, dword [ecx*4 + 0x401010]
0x00402063  shr eax, 7

Les valeurs sont lues directement dans la section data :

[0x00402000]> pxw 8 @ 0x401000
0x00401000  0x61cf5a1e 0x00e7933b

ESI vaut 0x61cf5a1e, EDI vaut 0x00e7933b.

L’index combine la position et la valeur normalisée :

index = position * 16 + value

Le stride vaut 16, mais l’alphabet compte 17 valeurs. Q à une position partage donc son index avec A à la position suivante.

La dernière position pose problème. Q passe le premier check, mais produit l’index 160, hors des tables. Le DWORD est lu au début de la table suivante, puis le sélecteur dans la clé finale. Le décodage finit sur une adresse d’écriture invalide. Le domaine utilisable est donc :

positions 0 à 8 : A à Q
position 9      : A à P

Un Q final passe le check des caractères, mais pas le chemin de succès.

Calcul d’une contribution

Le DWORD associé à l’index vient de 0x401010, puis subit un décalage de sept bits. Une seconde table fournit un octet :

[0x00402000]> pd 14 @ 0x402066
movzx ebx, byte [ecx + 0x401290]
sub ebx, 0x30
cmp ebx, 0xa
jl 0x402078
sub ebx, 0x27

Cette séquence convertit un chiffre hexadécimal ASCII. Le dump des 160 octets confirme le format :

[0x00402000]> ps 160 @ 0x401290
2bda2998d9b0ee197da142a0447f672537598dad8f8805ce708ba8c4f67ce367639bae9ac6b3e1a84cebb7b403297b794015e9ce43edfb0668ddaa973ebc7e87716f6b30598ba30945d84485e61c1027

Le programme remet un buffer temporaire de huit octets à zéro. Les masques 0x1f et les décalages de cinq bits découpent le DWORD en cinq groupes, écrits dans le buffer :

0x00402085  mov dword [0x401008], 0
0x0040208f  mov dword [0x40100c], 0
0x0040209c  and eax, 0x1f
0x0040209f  shl eax, cl
0x004020a1  mov byte [ebx + 0x40100c], al
0x004020a7  shr edx, 5
0x004020da  mov eax, edx
0x004020dc  and eax, 0x1f
0x004020df  shl al, cl
0x004020e1  mov byte [ebx + 0x401008], al
0x004020e8  xor esi, dword [0x401008]
0x004020ee  xor edi, dword [0x40100c]

def contribution(position, value):
    index = position * 16 + value
    packed = int.from_bytes(DUMP[index * 4:index * 4 + 4], "little") >> 7
    selector = int(HASH[index], 16)
    offset = selector >> 2
    shift = (~selector) & 3

    buf = bytearray(8)
    for n in range(5):
        buf[offset + 4 - n] = (packed & 0x1F) << shift
        packed >>= 5

    return int.from_bytes(buf, "little")

Les deux dernières instructions XORent le buffer avec les accumulateurs. Une contribution dépend uniquement de la position et de la valeur, jamais des caractères précédents.

On précalcule les contributions et on réunit les accumulateurs dans une cible 64 bits :

TARGET = 0x00E7933B61CF5A1E
F = [
    [contribution(position, value)
     for value in range(16 if position == 9 else 17)]
    for position in range(10)
]

Le validateur se résume à cette équation :

F(0,c_0) \mathbin{\mathrm{xor}} F(1,c_1) \mathbin{\mathrm{xor}} \cdots \mathbin{\mathrm{xor}} F(9,c_9)=\mathrm{TARGET}

Condition de succès

L’entrée est acceptée seulement si les deux accumulateurs valent zéro :

[0x00402000]> pd 16 @ 0x402100
0x00402100  or esi, edi
0x00402102  test esi, esi
0x00402104  jne 0x402135
0x00402106  xor ecx, ecx
0x00402108  mov al, byte [ecx + 0x40133a]
0x0040210e  xor byte [ecx + 0x401330], al
0x00402114  add byte [ecx + 0x401330], 0x41
0x0040211b  add ecx, 1
0x0040211e  cmp ecx, 0xa
0x00402121  jne 0x402108
0x00402123  push 0xa
0x00402125  push 0x401330
0x0040212a  push 1
0x0040212c  call dword [sym.imp.msvcrt.dll__write]

Le programme transforme ensuite une clé de dix octets stockée à 0x401330 :

[0x00402000]> px 10 @ 0x401330
0x00401330  050a 0717 0704 1207 0615

Le solveur reproduit l’opération :

FINAL_KEY = bytes.fromhex("050a0717070412070615")

def decode(password):
    return "".join(
        chr(ord("A") + (value ^ key))
        for value, key in zip(normalize(password), FINAL_KEY)
    )

L’ajout de 'A' vient bien du binaire.

Meet-in-the-middle

17^9 \times 16 = 1\,897\,406\,023\,952

Brute-forcer les 1 897 406 023 952 candidats n’a aucun intérêt. Les contributions indépendantes et le XOR réversible permettent une coupure 5 + 5 :

L=F(0,c_0)\mathbin{\mathrm{xor}}\cdots\mathbin{\mathrm{xor}}F(4,c_4)

R=F(5,c_5)\mathbin{\mathrm{xor}}\cdots\mathbin{\mathrm{xor}}F(9,c_9)

L\mathbin{\mathrm{xor}}R=\mathrm{TARGET}

Comme XOR est son propre inverse :

L=\mathrm{TARGET}\mathbin{\mathrm{xor}}R

On peut alors :

énumérer les cinq premières positions ;
mémoriser chaque signature $L$ ;
énumérer les cinq dernières positions ;
rechercher directement $\mathrm{TARGET}\mathbin{\mathrm{xor}}R$ .

La gauche compte $17^5=1\,419\,857$ combinaisons. La droite en compte $17^4\times16=1\,336\,336$ . Total : 2 756 193 demi-combinaisons, environ 688 000 fois moins que le brute-force complet.

La complexité passe de $O(k^n)$ à $O(k^{n/2})$ , avec un coût mémoire comparable. La coupure 5 + 5 équilibre les deux côtés.

Le solveur

Le solveur utilise trois données extraites du binaire :

DUMP, les 640 octets lus à partir de 0x401010 ;
HASH, les 160 caractères lus à 0x401290 ;
FINAL_KEY, les dix octets lus à 0x401330.

F[position][value] donne directement la contribution 64 bits.

Table de gauche

Pour chaque combinaison des cinq premières positions, on calcule le XOR :

left = {}

for values in product(range(17), repeat=5):
    key = (
        F[0][values[0]] ^ F[1][values[1]] ^ F[2][values[2]]
        ^ F[3][values[3]] ^ F[4][values[4]]
    )

Un tuple pour chaque groupe créerait trop d’objets Python. Les cinq valeurs sont compactées dans un entier en base 17 :

def pack(values):
    result = 0
    for value in values:
        result = result * 17 + value
    return result

def unpack(value):
    result = [0] * 5
    for i in range(4, -1, -1):
        value, result[i] = divmod(value, 17)
    return result

Deux groupes peuvent partager une signature. Écraser l’ancien groupe ferait perdre une solution potentielle. Une liste est créée seulement en cas de collision :

value = pack(values)
old = left.get(key)

if old is None:
    left[key] = value
elif isinstance(old, list):
    old.append(value)
else:
    left[key] = [old, value]

Recherche des correspondances

Les quatre premières positions acceptent 17 valeurs. La dernière reste limitée à 16 :

for values in product(
    range(17), range(17), range(17), range(17), range(16)
):
    right = (
        F[5][values[0]] ^ F[6][values[1]] ^ F[7][values[2]]
        ^ F[8][values[3]] ^ F[9][values[4]]
    )

La recherche dans le dictionnaire tient sur deux lignes :

matches = left.get(TARGET ^ right)
if matches is None:
    continue

Si la signature existe, on reconstruit les dix lettres puis on décode le message :

matches = matches if isinstance(matches, list) else [matches]

for match in matches:
    candidate = unpack(match) + list(values)
    password = "".join(chr(ord("A") + value) for value in candidate)
    yield password, decode(password)

Télécharger le solveur Python complet

Résultats

$ python3 shapeshifter_solver.py
MITM: 2.599s
GCEDCKDBCG -> DIDUFORGET
GCEDCKDOCD -> DIDUFORJEW
Solutions: 2

Deux solutions. La première donne DIDUFORGET, le message attendu. La seconde valide la même équation XOR, probablement une collision non intentionnelle.

Le dictionnaire conserve les collisions côté gauche. Aucun candidat valide ne peut être perdu : chaque moitié gauche est indexée sous $L$ , chaque moitié droite est visitée sous $R$ , et le lookup $\mathrm{TARGET}\mathbin{\mathrm{xor}}R$ retrouve $L$ dès que $L\mathbin{\mathrm{xor}}R=\mathrm{TARGET}$ .

Ce résultat couvre le domaine défini plus haut. Un Q final sort des tables avant le test de succès.