c - C中的乘法溢出

Question

我正在做一些安全 CTF 练习，并遇到了这个问题。这是编译后的程序的C源代码:

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

让我困惑的事情:

1. long** 当我关闭 gcc 标志时，主参数将无法编译，因此我无法在计算机上重现问题。这是使用不同的编译器吗？编译后的程序在CTF服务器上运行良好。

2. 在测试相等性之前，程序在乘法期间反复溢出。我尝试使用线性同余方程 (mod 2^64) 和扩展欧几里德算法来查找所需的 x 输入，但这对我不起作用。

有人可以帮我解决这个问题吗？我正在尝试找到 *a[1]，正确的程序参数。

在 gdb 中反汇编 main 给出:

(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

这里没有真正的溢出——它只是执行乘法 mod 2⁶⁴ 并测试结果是否符合预期。要计算出所需的输入，您只需找到因子 0x1064deadbeef4601 的倒数(mod 2⁶⁴)，并将其乘以 0xd1038d2e07b42569

对于 2 的幂模数，通常最容易使用欧拉公式求其倒数:

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

当 m 是 2 的幂时，φ(2^k) = 2^k-1，因此您可以通过以下方式计算: 2(k-1) 相乘。