# Harekaze CTF 2018 - Div N

byFebruary 11, 2018

We are given a c function that does the integer division of the argument by a constant N.

```
long long div(long long x) {
return x / N;
}
```

The constant is set at compile time

```
$ gcc -DN=$N -c -O2 foo.c
```

Given the disassembly of the function we need to recover N

```
$ objdump -d foo.o
foo.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000
:
0: 48 89 f8 mov %rdi,%rax
3: 48 ba 01 0d 1a 82 9a movabs $0x49ea309a821a0d01,%rdx
a: 30 ea 49
d: 48 c1 ff 3f sar $0x3f,%rdi
11: 48 f7 ea imul %rdx
14: 48 c1 fa 30 sar $0x30,%rdx
18: 48 89 d0 mov %rdx,%rax
1b: 48 29 f8 sub %rdi,%rax
1e: c3 retq
$ echo “HarekazeCTF{$N}” > /dev/null
```

I tried at first to run the code in an emulator, but the movabs with a quad word immediate wasn’t supported, so I rewrote the code in python.
In the System V x86_64 calling convenction rdi holds the first argument of a function.

The disassembly is in the AT&T syntax, not the usual Intel syntax (e.g. mov %rdi, %rax means rax = rdi, that is move rdi to rax)

```
def div(rdi):
rax = rdi
rdx = 0x49ea309a821a0d01
rdi = rdi >> 0x3f
rdxrax = rdx * rax
rdx, rax = rdxrax >> 64, rdxrax % (2 ** 64)
rdx = rdx >> 0x30
rax = rdx
rax = rax - rdi
return rax
```

Since this function computes x / N, we have that the smallest x such that x / N = 1 is x = N. Since x / N is a monotone function we can use binary search to efficiently find this x.

```
print(div(2 ** 64 - 1))
h = 2 ** 64 - 1
l = 0
while h - l > 1:
m = (h + l) / 2
if div(m) >= 1:
h = m
else:
l = m
# we have that div(l) < 1 and l is non decreasing after each iteration
# so at the end of the binary search l is the greatest x such that div(x) = 0
# that in turn means that l + 1 is the smallest x such that div(x) = 1
print(l + 1)
print(div(l))
print(div(l + 1))
```