Divisions, modulos et tri à bulles en x86_64
2026-07-08T17:46:33+08:00
Les algorithmes écrits dans des langages de haut niveau (par exemple C) paraissent très évidents lorsque l’on regarde le code स्रोत. Cependant, le compilateur peut les convertir en motifs assez mystérieux au niveau de l’assembleur. Pour améliorer nos compétences en rétro-ingénierie, nous devons apprendre ces motifs afin de pouvoir les identifier rapidement. Cet article de blog présentera quelques exemples, tirés de ce que j’ai rencontré en résolvant un défi de CTF aujourd’hui.
Divisions signées entre entiers
Prenons ce code par exemple :
#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;
}
Compilez-le, lancez votre magnifique iaito ou radare2, et regardez l’assembleur. Nous n’avons pas besoin de nous occuper de main(), donc nous pouvons aller directement à sym.div, où nous pouvons voir quelque chose comme ceci :
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
Nous ne voyons pas d’instruction idiv ici. En revanche, nous pouvons voir une instruction imul à 0x00001156, suivie d’une instruction shr et d’une instruction sar. Après cela, le résultat se trouve dans le registre edx.
Mais que se passe-t-il si nous utilisons un autre nombre ? Essayons cela. Compilez ceci :
#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;
}
Et nous obtiendrons un désassemblage similaire :
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
Que se passe-t-il si nous utilisons un nombre négatif ? Remplacez 6 par -7, et nous obtiendrons quelque chose de similaire :
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
Et que se passe-t-il si nous n’utilisons pas de constante ? Compilez ceci :
#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;
}
Après cela, nous obtiendrons enfin quelque chose de différent :
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
Un processeur x86_64 supporte bien la division, mais celle-ci est coûteuse. Donc, si le diviseur est déjà donné comme constante, le compilateur effectuera cette optimisation pour nous à la compilation. Il calculera un multiplicateur magique à partir du diviseur et convertira la division en une combinaison de multiplication et de décalages binaires. Il existe un article expliquant cet algorithme plus en détail.
Cependant, si la constante n’est connue qu’au moment de l’exécution, cette optimisation ne sera pas utile ; le compilateur utilisera donc directement l’instruction de division.
Opérations de modulo
Maintenant, compilons ceci :
#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;
}
Nous obtiendrons ce désassemblage pour mymod() :
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
Les instructions de 0x00001150 à 0x00001161 effectuent une division à l’aide du multiplicateur magique expliqué ci-dessus. Ensuite, il obtient une copie du dividende dans ecx et la décale arithmétiquement vers la droite de 31 bits. Si le dividende est non négatif, ecx vaudra 0 ; sinon, il vaudra -1.
Cela sert à calculer un biais à partir du dividende, car la division tronque toujours vers zéro. Nous utilisons le quotient pour calculer le modulo : pour les nombres positifs, modulo = dividende - diviseur * quotient ; pour les nombres négatifs, modulo = dividende - diviseur * (quotient + 1).
Tri à bulles
Enfin, compilons ceci :
#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;
}
Cette fois, regardons le graphe de sym.bubble généré par iaito :
Nous pouvons voir qu’un compteur est réglé à 0x00001144. Dans le bloc 0x00001209, il y a une comparaison. Si le compteur n’a pas atteint le seuil, l’exécution se poursuit. À 0x00001150, un autre compteur est réglé. Dans le bloc 0x0000115c, une comparaison entre deux nombres voisins a lieu. Si le premier est plus grand, un échange est effectué dans le bloc 0x0000118c.
Conclusion
Ce ne sont que quelques exemples des motifs que nous pouvons rencontrer lors d’une rétro-ingénierie. À mesure que nous faisons de plus en plus de travaux de rétro-ingénierie, nous acquérons de plus en plus d’expérience, et nous serons capables d’identifier rapidement davantage de motifs dans le désassemblage.
