**Tags:** rev

Rating: 0

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

```c

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)

```python

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.

```python

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))

```