Harekaze CTF 2018 - Div N

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