A:link { TEXT-DECORATION: underline } A:visited { TEXT-DECORATION: underline } A:active { COLOR: red; TEXT-DECORATION: underline } A:hover { COLOR: #8080ff; TEXT-DECORATION: underline }

In questo tutorial faremo un po' di matematica, e in particolare ci dedicheremo ad alcune tecniche per invertire le operazioni matematiche e logiche più comuni. 

Maths reversing
!shtam s'teL
Written by Spider

add eax, ebx

Di fronte ad una semplice istruzione come questa, possono nascondersi implicazioni matematiche tutt'altro che banali. Non è infatti così scontato che dopo questa operazione avremo in eax la somma tra eax ed ebx. Se infatti il risultato è troppo grosso per entrare in 32 bits, non avremo certo il risultato desiderato. Bisogna quindi introdurre il concetto di modulo per dare un senso matematico esatto all'operazione appena effettuata.
Ovviamente se siamo sicuri che il risultato sia sufficientemente piccolo tutte queste disquisizioni sono inutili, ma la loro conoscenza può rivelarsi fondamentale in alcune occasioni. 

- La calcolatrice scientifica di windows;
- Un cervello più o meno sano ;-)

 

Prerequisiti:

- conoscenza dell'architettura dei processori Intel e in particolare della numerazione binaria;
- conoscenza delle istruzioni matematiche e logiche in linguaggio assembly;
- capacità di risoluzione di equazioni di primo e secondo grado;
- conoscenza dei prodotti notevoli.

Si consiglia una ricerca in rete riguardo alle aritmetiche modulari.

Iniziamo con una spiegazione basilare del concetto di modulo e di aritmetica modulare.

L'operatore modulo (mod)

L'aritmetica modulare (detta anche aritmetica circolare o aritmetica finita) differisce dall'aritmetica ordinaria in quanto opera su un set limitato di numeri. E' detta aritmetica circolare in quanto dopo l'ultimo numero si ritorna di nuovo al primo... Si può pensare in proposito ad un orologio: se esso segna le ore 11 e lasciamo scorrere 4 ore, non avremo le ore 15 ma la lancetta punterà il numero 3.
L'aritmetica circolare di modulo m opera con m numeri che vanno da 0 a m-1. Quindi lavorando in modulo 5 avremo i seguenti numeri:

0, 1, 2, 3, 4.

L'operatore modulo (mod) restituisce il resto di una divisione, senza preoccuparsi del risultato della divisione. Dati a e b interi, diciamo che:

a / b = q + r

Dove q è il quoziente e r il resto della divisione. Abbiamo quindi che:

a mod b = r

Le operazioni in una aritmetica modulare sono abbastanza semplici. Tutte le operazioni matematiche semplici possono essere eseguite facilmente, ma dopo aver eseguito l'operazione bisogna dividere per m e prelevare il resto... qualche esempio varrà più di mille parole:

(5 + 8) mod 4 = 13 mod 4 = 1
(8 - 5) mod 6 = 3 mod 6 = 3
(5*7) mod 12 = 35 mod 12 = 11
5² mod 7 = 25 mod 7 = 4

E così via.

Viene spesso utilizzata anche la seguente notazione:

a = b (mod n)

Il mod n messo tra parentesi indica che l'operatore di modulo si applica a TUTTA l'espressione. L'uguaglianza appena vista è dunque equivalente a 

a mod n = b mod n

Dati:

a / b = q + r

e:

a mod b = r

possiamo definire alcune proprietà importanti:

1. r < b
2. se a < b, allora a mod b = a;
3. (a + b) mod n = ((a mod n) + (b mod n)) mod n
4. (a * b) mod n = ((a mod n) * (b mod n)) mod n

In una aritmetica circolare continuano comunque a valere le normali regole e proprietà delle 4 operazioni nell'aritmetica ordinaria.

Il perché di queste poche righe sull'operatore mod è molto semplice: nel processore non si lavora nell'aritmetica ordinaria, ma in una aritmetica circolare. In caso di overflow, infatti, il risultato non sarà più consistente nell'aritmetica ordinaria, e dovremo tener conto di trovarci in un'aritmetica modulare. Il modulo dipende dal numero di bit che utilizziamo per rappresentare ogni numero. Se ad esempio lavoriamo con numeri a 32 bit, ci troveremo in un'aritmetica di modulo 2³², ovvero 4294967296... un numero molto grande, ed è per questo che di solito si possiamo ignorare di operare in una aritmetica circolare. Per fare un esempio, se il risultato di un'operazione a 32 bit è 2³² + n (con n < 2³²) il processore ricomincerà da capo e il risultato effettivo sarà semplicemente n (infatti (2³² + n) mod 2³² = n).

Signed e unsigned

Entriamo adesso dentro la mente matematica del processore...

Le operazioni matematiche eseguite dal processore si suddividono in due categorie: signed e unsigned. Nelle operazioni unsigned i calcoli vengono effettuati senza segno. Ciò significa che non esistono numeri negativi, e l'intervallo di numeri che possiamo utilizzare va da 0 a 2ⁿ-1, dove n è il numero di bit su cui lavoriamo. Per cui se lavoriamo a 16 bit possiamo lavorare con numeri da 0 a 65535. Nelle operazioni signed invece il bit più significativo indica il segno dell'operazione, e in questo caso possiamo lavorare con numeri da -(2^n-1) a 2^n-1 - 1 (ovvero a 16 bit da -32768 a 32767).

Quando eseguiamo un'istruzione matematica in assembly dobbiamo sempre tenere presente se tale operazione sia signed o unsigned.

Add e Sub

Su queste due istruzioni c'è poco da dire. Esse lavorano sia in signed che in unsigned, nel senso che forniscono un risultato valido per entrambi i tipi di operazione. Sta perciò a noi interpretare correttamente il risultato.
L'unica cosa importante da tenere presente è la dimensione del registro di destinazione, perché da essa dipende il modulo dell'aritmetica in cui si lavora. Perciò se scriviamo add al,bl dobbiamo tenere presente di lavorare in modulo 2⁸ = 256.
Notiamo che ciò non influisce sulle normali regole di addizione e sottrazione neppure in caso di overflow: se ad esempio a + b = c, allora c - b = a.

Per fare un esempio, lavorando a 8 bit unsigned (ovvero in modulo 256), 

234 + 127 = 105 (mod 256),
e 105 - 127 = 234 (mod 256).

A 8 bit signed, invece,

-113 - 58 = 85, 
e 85 - (-58) = -113

Possiamo osservare che nel caso di operazioni signed le cose si fanno un po' più complesse: mentre per le unsigned abbiamo un'aritmetica circolare con i numeri 0,1,2,...255,0,1..., per le operazioni signed i numeri in circolo sono -128,-127...0,1...127,-128,-127... Sarebbe in questo caso impreciso affermare di lavorare in una aritmetica modulare nel senso stretto della parola: l'elemento più piccolo qui non è 0 ma -128, e si ha quindi una sfasatura di -128 sull'aritmetica di modulo 256. Anche qui possiamo solitamente ignorare la faccenda... Adesso però possiamo eseguire i calcoli dell'ultimo esempio consci di ciò che stiamo facendo :). Otteniamo un risultato equivalente aggiungendo 256 a tutti i numeri negativi e effettuando i calcoli come unsigned:

(-113+256) + (-58+256) = 341 
341 mod 256 = 85

Per effettuare la conversione di un numero negativo da signed a unsigned è sufficiente aggiungere 256 (ovviamente solo se si lavora a 8 bit); viceversa, per convertire in signed un numero unsigned maggiore di 127 bisogna sottrarre 256.

Equazioni logico-aritmetiche

Veniamo alla parte più interessante del tutorial. Con il termine di equazioni logico-aritmetiche intendo delle equazioni in cui oltre ad operazioni aritmetiche compaiono anche operazioni logiche. Ad esempio:

NOT(x XOR 64) + x = 134

Ovviamente non possiamo bruteforcare, per almeno due buoni motivi: il primo è che non è l'obiettivo di questo tutorial; il secondo è che il bruteforcing diventa improponibile per numeri grandi o quando serve una velocità di risoluzione particolarmente elevata.

In generale, vedremo come sia possibile trasformare le equazioni di questo tipo in equazioni semplici, che non utilizzano operatori logici.

Cominciamo con il caso più semplice: l'operatore NOT.

Operatore NOT

Tra gli operatori logici, il più semplice da invertire è sicuramente l'operatore NOT. Un'equazione contenente l'operatore NOT può essere ridotta ad un'equazione algebrica semplice. Bisogna tuttavia fare la distinzione tra signed ed unsigned. Lavorando in signed, possiamo dire che:

NOT(a) = -a-1

Per cui ad esempio:

NOT(x) = 5
-x-1 = 5
x = -6

Ovviamente NOT(5) = -6, quindi in questo caso sarebbe bastato eseguire il not di 5 per ottenere il risultato voluto. In casi più complessi, tuttavia, è necessario trasformare in equazione algebrica:

NOT(x - 5) + 2x = 24
-x + 5 - 1 + 2x = 24
x = 24-4 = 20

Con un semplicissimo passaggio matematico la soluzione diventa semplicissima.

In unsigned, le cose sono un po' diverse:

NOT(a) = n - a

Dove n è si calcola come 2^m-1, indicando con m il numero di bit a cui si lavora. Ad esempio, lavorando a 32 bit:

NOT(x²) + 5x = 4294967245
4294967295 - x² + 5x = 4294967245
-x² + 5x = -50
x² - 5x - 50 = 0

x = (5 ± SQR(25 + 200))/2 = (5 ± 15)/2

Da cui segue x = 10 o x = -5, che sono le due soluzioni dell'equazione. Notare che, sebbene lavoriamo in unsigned, la soluzione x = -5 è valida, dato che -5 convertito in unsigned è uguale a 4294967291, che è una soluzione esatta. Il perché di tutto ciò è molto semplice, e risiede nel fatto che lavoriamo in una aritmetica modulare.
Sappiamo infatti che -x in unsigned è uguale a 2³² - x. Ricordandoci di lavorare in modulo 2³² diciamo che

(2³²-x)² mod 2³² = (2³²-x)(2³²-x) mod 2³² = (2⁶⁴ - 2³²x - 2³²x + x²) mod 2³² =
= (2⁶⁴ mod 2³²) - (2 * 2³²x mod 2³²) + (x² mod 2³²) = 0 - 0 + (x² mod 2³²) = x²


Operatore XOR

Con l'operatore NOT le cose erano davvero banali... Con lo XOR si comincia a fare sul serio :)

Consideriamo la seguente equazione:

(x XOR 5) + x = 101

In un'equazione di questo tipo, per trovare le soluzioni valide è necessario scomporre il secondo operando dello xor in potenze di 2, ovvero convertirlo in numero binario:

(5)₁₀ = (101)₂

Dobbiamo tenere presente una cosa: eseguire lo xor tra un numero e una potenza di 2, è equivalente a sottrarre se il bit corrispondente è settato; ad aggiungere se il bit è azzerato. Ad esempio x XOR 1 incrementa x se è pari, lo decrementa se è dispari. Ciò ci suggerisce un approccio per attaccare lo xor, come nella seguente equazione:

(x XOR 4) + x = 73

/ x + 4 + x = 150
\ x - 4 + x = 150

/ 2x = 146
\ 2x = 154

/ x = 73
\ x = 77

Da cui ricaviamo che i due possibili valori di x sono 73 e 77.

Torniamo all'equazione vista poco fa:

(x XOR 5) + x = 101

In questo caso l'incognita viene xorata con un numero che non è una potenza di 2; tuttavia osserviamo che 5 è pari alla somma di 1 + 4, entrambe potenze di 2. Le varie combinazioni di somme e differenze tra 1 e 4 forniscono 4 possibili risultati:

4+1 = 5
4-1 = 3
1-4 = -3
-1-5 = -5

Per cui stavolta trasformiamo l'equazione iniziale in 4 equazioni che forniranno 4 possibili risultati:

/x + 5 + x = 101
|x + 3 + x = 101
|x - 3 + x = 101
\x - 5 + x = 101

/2x = 96
|2x = 98
|2x = 104
\2x = 106

/x = 48
|x = 49
|x = 52
\x = 53

Ed ecco le 4 soluzioni dell'equazione, ottenute senza neppure l'ombra di bruteforcing :)

In generale, se in un'equazione di questo tipo il secondo operando dello xor contiene n bit settati ad 1, allora il numero di possibili soluzioni sarà dato semplicemente da 2ⁿ.

Abbiamo la seguente equazione:

x * (x XOR 268435455) = 536869722

268435455 vale in binario 000000001111111111111111111111111111, che significherebbe 2²⁸ equazioni risolutive (per giunta di secondo grado, che fornirebbero 2 soluzioni ciascuna). In realtà, le soluzioni sono soltanto 2. Infatti possiamo considerare soltanto le equazioni intere (ovviamente solo se non viene usata la FPU per svolgere i calcoli). Con un bruteforcer troviamo le due soluzioni:

34, 268435421

Si possono tuttavia fare delle considerazioni: se n è una soluzione, lo è anche n XOR 268435455. Pertanto il numero di soluzioni è sicuramente pari. Un buon modo per ridurre il campo di ricerca delle soluzioni può a volte essere la scomposizione in fattori primi di 536869722:

536869722 = 2 * 3 * 89478287

Se x * (x XOR 268435455) è sufficientemente piccolo da entrare in una dword, possiamo trovare il risultato come fattore o prodotto di fattori di 536869722. In questo caso, tuttavia, questo approccio non è sufficiente e il bruteforcing è obbligatorio.

Operatore AND

Il metodo per invertire equazioni che utilizzano l'operatore AND è simile a quello utilizzato per l'operatore XOR. Dobbiamo tenere presente che l'and con un bit settato ad 1 lascia invariato, mentre l'and con un bit settato a 0 equivale a sottrarre o lasciare invariato (a secondo che il bit sia settato o azzerato). Per cui stavolta il numero di soluzioni è dato da 2^m, dove m è il numero di bit azzerati. Ad esempio:

x + (x AND 0FFFFFFFEh) = 29

/x + x = 29
\x + x-1 = 29

/2x = 29
\2x = 28

/2x = 29
\x = 14

La prima equazione che si viene a creare (2x = 29) non ha soluzioni intere, per cui l'unica soluzione valida è la seconda (x = 14).

x + (x AND 0FFFFFEEEh) = 45

/x + x - 0 = 45
|x + x - 1 = 45
|x + x - 16 = 45
|x + x - 17 = 45
|x + x - 256 = 45
|x + x - 257 = 45
|x + x - 272 = 45
\x + x - 273 = 45

/2x = 45
|2x = 46
|2x = 61
|2x = 62
|2x = 301
|2x = 302
|2x = 317
\2x = 318

Escludendo le equazioni che darebbero un risultato fratto, ci rimane:

/2x = 46
|2x = 62
|2x = 302
\2x = 318

Tra queste 4 equazioni si nasconde la soluzione, che si verifica facilmente essere x = 31.

NOTA: A differenza del procedimento usato per lo xor, solo una o alcune delle equazioni finali danno un risultato valido, mentre con lo xor si perveniva a risultati certamente esatti.

Operatore OR

Si ragiona alla solita maniera: se il bit con cui si effettua l'or con 1 è azzerato, l'operazione equivale ad aggiungere, altrimenti lascia invariato il risultato. Il numero di possibili soluzioni è come al solito 2ⁿ con n uguale al numero di bit messi ad 1.

Esempio:

(x * (x OR 32)) OR 1 = 473

Calcoliamo il numero di possibili soluzioni:

x OR 32 raddoppia il numero di soluzioni (dato che 32 in binario vale 100000, con 2 bit uguali ad 1);
x * (...) rende l'equazione di secondo grado, raddoppiano di fatto le soluzioni;
(..(..)) OR 1 raddoppia di nuovo il numero di soluzioni.

In totale 2*2*2 = 8 possibili soluzioni.
Svolgiamo i calcoli:

/(x * (x + 0)) + 0 = 473
|(x * (x + 0)) + 1 = 473
|(x * (x + 32)) + 0 = 473
\(x * (x + 32)) + 1 = 473

/x² = 473              SQR(473) non è intero... scartiamo!
|x² = 272              SQR(472) non è intero... scartiamo!
|x² + 32x - 473 = 0
\x² + 32x - 472 = 0

/x² + 32x - 473 = 0
\x² + 32x - 472 = 0

/x = (-32 ± SQR(1024 + 1892))/2
\x = (-32 ± SQR(1024 + 1888))/2  SQR(1024 + 1888) non è intero... scartiamo!

x = (-32 ± SQR(1024 + 1892))/2

x = (-32 ± SQR(1024 + 1892))/2


e le due soluzioni sono:

x = (54-32)/2 = 11
x = (-54-32)/2 = -43

La seconda soluzione (-43) vale sia in signed, sia in unsigned: infatti -43 signed corrisponde a 4294967253 unsigned, che in modulo 2³² è soluzione valida.

Con questo è tutto. Il tutorial è breve, ma il mio obiettivo è solo quello di dare uno sguardo generale al concetto di aritmetica modulare, e di gettare le basi per la comprensione delle implicazioni che essa ha sull'inversione di istruzioni matematiche e logiche che si possono talvolta incontrare nel reversing di alcuni algoritmi.

Spider

Saluti a chiunque sia riuscito a leggere fino in fondo :-)

Niente disclaimer oggi... Se la matematica è illegale sono contento di essere un fuorilegge :)

Home