Divisionen, Moduli und Bubble Sort in x86_64
2026-07-08T17:46:33+08:00
Algorithmen, die in Hochsprachen (z. B. C) geschrieben sind, wirken im Quellcode sehr offensichtlich. Der Compiler kann sie jedoch auf Assemblerebene in recht mysteriöse Muster umwandeln. Um unsere Fähigkeiten in der Reverse Engineering zu verbessern, müssen wir diese Muster kennenlernen, damit wir sie schnell erkennen können. Dieser Blogbeitrag listet einige Beispiele auf, die darauf beruhen, was mir heute beim Lösen einer CTF-Aufgabe begegnet ist.
Vorzeichenbehaftete Divisionen zwischen ganzen Zahlen
Nehmen wir diesen Code als Beispiel:
#include <stdio.h>
int div(int a)
{
return a / 42;
}
int main()
{
int a;
scanf("%d", &a);
a = div(a);
printf("%d", a);
return 0;
}
Kompilieren Sie ihn, starten Sie Ihr glänzendes iaito oder radare2, und sehen Sie sich die Assemblersprache an. Wir müssen uns nicht um main() kümmern, also können wir direkt zu sym.div gehen; dort sehen wir etwas in etwa wie Folgendes:
36: div (int64_t arg1);
`- args(rdi) vars(1:sp[0xc..0xc])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov eax, dword [var_4h]
0x00001153 movsxd rdx, eax
0x00001156 imul rdx, rdx, 0x30c30c31
0x0000115d shr rdx, 0x20
0x00001161 sar edx, 3
0x00001164 sar eax, 0x1f
0x00001167 sub edx, eax
0x00001169 mov eax, edx
0x0000116b pop rbp
0x0000116c ret
Wir sehen hier keine idiv-Instruktion. Stattdessen sehen wir an 0x00001156 eine imul-Instruktion, gefolgt von einer shr-Instruktion und einer sar-Instruktion. Danach befindet sich das Ergebnis im Register edx.
Aber was passiert, wenn wir eine andere Zahl verwenden? Versuchen wir es. Kompilieren Sie dies:
#include <stdio.h>
int div(int a)
{
return a / 6;
}
int main()
{
int a;
scanf("%d", &a);
a = div(a);
printf("%d", a);
return 0;
}
Und wir erhalten eine ähnliche Disassemblierung:
33: div (int64_t arg1);
`- args(rdi) vars(1:sp[0xc..0xc])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov eax, dword [var_4h]
0x00001153 movsxd rdx, eax
0x00001156 imul rdx, rdx, 0x2aaaaaab
0x0000115d shr rdx, 0x20
0x00001161 sar eax, 0x1f
0x00001164 sub edx, eax
0x00001166 mov eax, edx
0x00001168 pop rbp
0x00001169 ret
Was passiert, wenn wir eine negative Zahl verwenden? Ersetzen Sie 6 durch -7, und wir erhalten etwas Ähnliches:
36: div (int64_t arg1);
`- args(rdi) vars(1:sp[0xc..0xc])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov eax, dword [var_4h]
0x00001153 movsxd rdx, eax
0x00001156 imul rdx, rdx, 0xffffffff92492493
0x0000115d shr rdx, 0x20
0x00001161 add edx, eax
0x00001163 sar edx, 2
0x00001166 sar eax, 0x1f
0x00001169 sub eax, edx
0x0000116b pop rbp
0x0000116c ret
Und was passiert, wenn wir keine Konstante verwenden? Kompilieren Sie dies:
#include <stdio.h>
int div(int a, int b)
{
return a / b;
}
int main()
{
int a, b;
scanf("%d %d", &a, &b);
a = div(a, b);
printf("%d", a);
return 0;
}
Danach erhalten wir endlich etwas anderes:
19: div (int64_t arg1, signed int64_t arg2);
`- args(rdi, rsi) vars(2:sp[0xc..0x10])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov dword [var_8h], esi ; arg2
0x00001153 mov eax, dword [var_4h]
0x00001156 cdq
0x00001157 idiv dword [var_8h]
0x0000115a pop rbp
0x0000115b ret
Eine x86_64-CPU unterstützt Division durchaus, aber sie ist teuer. Wenn der Divisor also bereits als Konstante gegeben ist, führt der Compiler diese Optimierung für uns zur Compile-Zeit durch. Er berechnet aus dem Divisor einen magischen Multiplikator und wandelt die Division in eine Kombination aus Multiplikation und Bitverschiebungen um. Es gibt eine Arbeit, die diesen Algorithmus genauer erklärt.
Wenn die Konstante jedoch erst zur Laufzeit bekannt ist, hilft diese Optimierung nicht, also verwendet der Compiler direkt die Divisionsanweisung.
Modulo-Operationen
Kompilieren wir nun dies:
#include <stdio.h>
int mymod(int a)
{
return a % 42;
}
int main()
{
int a;
scanf("%d", &a);
a = mymod(a);
printf("%d", a);
return 0;
}
Für mymod() erhalten wir diese Disassemblierung:
45: mymod (int64_t arg1);
`- args(rdi) vars(1:sp[0xc..0xc])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov eax, dword [var_4h]
0x00001153 movsxd rdx, eax
0x00001156 imul rdx, rdx, 0x30c30c31
0x0000115d shr rdx, 0x20
0x00001161 sar edx, 3
0x00001164 mov ecx, eax
0x00001166 sar ecx, 0x1f
0x00001169 sub edx, ecx
0x0000116b imul ecx, edx, 0x2a
0x0000116e sub eax, ecx
0x00001170 mov edx, eax
0x00001172 mov eax, edx
0x00001174 pop rbp
0x00001175 ret
Die Instruktionen von 0x00001150 bis 0x00001161 implementieren eine Division mithilfe des oben erklärten magischen Multiplikators. Danach erhält es eine Kopie des Dividenden in ecx und verschiebt ihn arithmetisch um 31 Bits nach rechts. Wenn der Dividende nicht negativ ist, wird ecx 0 sein; andernfalls ist er -1.
Dies dient dazu, einen Bias aus dem Dividenden zu berechnen, denn die Division schneidet immer zur Null hin ab. Wir verwenden den Quotienten, um den Modulo zu berechnen: Für positive Zahlen gilt Modulo = Dividende - Divisor * Quotient; für negative Zahlen gilt Modulo = Dividende - Divisor * (Quotient + 1).
Bubble Sort
Kompilieren wir nun dies:
#include <stdio.h>
void bubble(int *arr, int n)
{
for (int i1 = 0; i1 < n - 1; i1++)
{
for (int i2 = 0; i1 + i2 < n - 1; i2++)
{
if (arr[i1] > arr[i2])
{
int tmp = arr[i1];
arr[i1] = arr[i2];
arr[i2] = tmp;
}
}
}
}
int main()
{
int a[42];
for (int i1 = 0; i1 < 42; i1++)
a[i1] = 42 - i1;
bubble(a, 42);
for (int i1 = 0; i1 < 42; i1++)
printf("%d", a[i1]);
return 0;
}
Diesmal betrachten wir den von iaito erzeugten Graphen von sym.bubble:
Wir können sehen, dass bei 0x00001144 ein Zähler gesetzt wird. Im Block 0x00001209 gibt es einen Vergleich. Wenn der Zähler den Schwellenwert noch nicht erreicht hat, geht die Ausführung weiter. Bei 0x00001150 wird ein weiterer Zähler gesetzt. Im Block 0x0000115c findet der Vergleich zwischen zwei benachbarten Zahlen statt. Wenn die erste größer ist, wird im Block 0x0000118c ein Austausch vorgenommen.
Fazit
Dies sind nur einige Beispiele für die Muster, die wir beim Reverse Engineering sehen können. Je mehr Reverse-Engineering-Arbeit wir machen, desto mehr Erfahrung gewinnen wir, und desto schneller werden wir in der Lage sein, weitere Muster in der Disassemblierung zu erkennen.
