Algorithms written in high-level languages (e.g. C) will look very obvious when you are looking at the source code. However, the compiler can convert them into rather mysterious patterns at assembly level. To improve our reverse-engineering skills, we need to learn about those patterns so that we can identify them quickly. This blog post will list some examples, based on what I encountered while solving a CTF challenge today.
Signed Divisions Between Integers
Take this code for example:
#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;
}
Compile it, fire up your shiny iaito or radare2, and look at the assembly. We do not need to care about main(), so we can go straight to sym.div, where we can see something like this:
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
We do not see an idiv instruction here. Instead, we can see an imul instruction at 0x00001156, followed by a shr instruction and a sar instruction. After that, the result is in the edx register.
But what happens if we use a different number? Let us try that. Compile this:
#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;
}
And we will get a similar disassembly:
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
What happens if we use a negative number? Replace 6 with -7, and we will get something similar:
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
What happens if we do not use a constant? Compile this:
#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;
}
After that, we finally get something different:
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
An x86_64 CPU does support division, but it is expensive. Therefore, if the divisor is already given as a constant, the compiler will perform that optimisation for us at compile time. It will compute a magic multiplier from the divisor and convert the division into a combination of multiplication and bitwise shifts. There is a paper explaining this algorithm further.
However, if the constant is only known at runtime, that optimisation will not help, so the compiler will use the division instruction directly.
Modulo Operations
Now let us compile this:
#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;
}
We will get this disassembly for 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
The instructions from 0x00001150 to 0x00001161 implement division using the magic multiplier explained above. Then it gets a copy of the dividend in ecx and arithmetic-shifts it right by 31 bits. If the dividend is non-negative, ecx will be 0; otherwise, it will be -1.
This is used to compute a bias from the dividend, because division always truncates towards zero. We use the quotient to compute the modulo: for positive numbers, the modulo = dividend - divisor * quotient; for negative numbers, the modulo = dividend - divisor * (quotient + 1).
Bubble Sort
Finally, let us compile this:
#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;
}
This time, look at the graph of sym.bubble generated by iaito:
We can see that a counter is set at 0x00001144. Inside the 0x00001209 block, there is a comparison. If the counter has not reached the threshold, execution proceeds. At 0x00001150, another counter is set. Inside the 0x0000115c block, the comparison between two neighbouring numbers takes place. If the first one is larger, a swap is performed inside the 0x0000118c block.
Conclusion
These are just several examples of the patterns we may see during reverse engineering. As we do more and more reverse-engineering work, we will gain more and more experience, and we will be able to identify more patterns in the disassembly quickly.