div N===
**Category:** Rev, **Points:** 100, **Solves:** 90
```$ cat foo.clong long div(long long x) {    return x / N;}$ gcc -DN=$N -c -O2 foo.c$ 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```
## Writeup
My first attempt was to use [z3](https://github.com/Z3Prover/z3), but z3 wasunable to find the N. Another approach was to be smart and [try to analyzethe compiler optimization](https://reverseengineering.stackexchange.com/questions/1397/how-can-i-reverse-optimized-integer-division-modulo-by-constant-operations).
But, let's go another way. Notice one thing: `(N-1) / N = 0` and `N / N = 1`.So we can just use simple binary search. How? We know that compiled programis a 64 bit ELF and we are given the machine code encoded in hex. So let's justload it to executable memory and run it:
```c++#include <iostream>
int main() {    char function[] = {"\x48\x89\xf8\x48\xba\x01\x0d\x1a\x82\x9a\x30\xea\x49\x48\xc1\xff\x3f\x48\xf7\xea\x48\xc1\xfa\x30\x48\x89\xd0\x48\x29\xf8\xc3"};    long long (*foo_ptr)(long long) = (long long (*)(long long)) function;
    long long a = 0;    long long b = 0x7FFFFFFFFFFFFFFF;
    while (b - a > 1) {        long long mid = a / 2 + b / 2; // more or less; avoiding overflow        if (foo_ptr(mid) >= 1) {            b = mid;        }        else {            a = mid;        }    }    std::cout << a << "\n" << b << "\n";}```
So, let's compile it and run it:```$ g++ -z execstack -o x x.cpp$ ./x974873638438445974873638438446```Who does say that `-z execstack` is bad? :P And, BTW, you don't want to compilethis code with any optimizations, since we are doing stuff we theoreticallyshouldn't do and compiler assumes that we are reasonable programmers :)
So, finally, the flag is `HarekazeCTF{974873638438446}`.
###### By [mrowqa](https://github.com/Mrowqa) <[email protected]>