Multiplication overflow in C

Question

I'm doing some security CTF practice and have this problem which I am stuck on. This is the C source code of the compiled program:

int main(int i, long **a) {
    if(*a[1] * 0x1064deadbeef4601u == 0xd1038d2e07b42569u)
        //exec shell
    return 0;
}

Things confusing me:

1. long** main argument won't compile when I turn off gcc flags so I can't reproduce problem on my computer. Is this a different compiler being used? Compiled program runs fine on CTF server.

2. program repeatedly overflows during multiplication before testing equality. I tried using a linear congruence equation (mod 2^64) and extended euclidian algorithm to find the required x input but this did not work for me.

Can someone help me out with this? I'm trying to find *a[1], the correct program argument.

disassembling main in gdb gives:

(gdb) disas main
Dump of assembler code for function main:
   0x000000000040050c <+0>: push   %rbp
   0x000000000040050d <+1>: mov    %rsp,%rbp
   0x0000000000400510 <+4>: sub    $0x10,%rsp
   0x0000000000400514 <+8>: mov    %edi,-0x4(%rbp)
   0x0000000000400517 <+11>:    mov    %rsi,-0x10(%rbp)
   0x000000000040051b <+15>:    mov    -0x10(%rbp),%rax
   0x000000000040051f <+19>:    add    $0x8,%rax
   0x0000000000400523 <+23>:    mov    (%rax),%rax
   0x0000000000400526 <+26>:    mov    (%rax),%rax
   0x0000000000400529 <+29>:    mov    %rax,%rdx
   0x000000000040052c <+32>:    movabs $0x1064deadbeef4601,%rax
=> 0x0000000000400536 <+42>:    imul   %rax,%rdx
   0x000000000040053a <+46>:    movabs $0xd1038d2e07b42569,%rax
   0x0000000000400544 <+56>:    cmp    %rax,%rdx
   0x0000000000400547 <+59>:    jne    0x400562 <main+86>
   0x0000000000400549 <+61>:    mov    $0x0,%edx
   0x000000000040054e <+66>:    mov    $0x40061c,%esi
   0x0000000000400553 <+71>:    mov    $0x40061f,%edi
   0x0000000000400558 <+76>:    mov    $0x0,%eax
   0x000000000040055d <+81>:    callq  0x4003f0 <execl@plt>
   0x0000000000400562 <+86>:    mov    $0x0,%eax
   0x0000000000400567 <+91>:    leaveq 
   0x0000000000400568 <+92>:    retq   
End of assembler dump.

Answer 1

There's no real overflow here -- it's just doing a multiply mod 2⁶⁴ and testing that the result is what is expected. To figure out the desired input, you just need to find the inverse (mod 2⁶⁴) of the factor 0x1064deadbeef4601, and multiply it by 0xd1038d2e07b42569

For power-of-2 modulus, it's generally easiest to find the inverse using Euler's formula:

x^-1 (mod m) ≡ x^φ(m)-1 (mod m)

when m is a power of two, φ(2^k) = 2^k-1, so you can calculate this with just 2(k-1) multiplies.