C中的乘法溢出 [英] Multiplication overflow in C

问题描述

我正在做一些安全 CTF 练习，但遇到了这个问题，我一直在解决这个问题.这是编译好的程序的C源代码:

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;
}

让我困惑的事情:

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

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.

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

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.

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

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

在 gdb 中反汇编 main 给出:

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.

推荐答案

这里没有真正的溢出——它只是做一个乘法 mod 2⁶⁴ 并测试结果是否符合预期.要找出所需的输入，您只需找到因子 0x1064deadbeef4601 的倒数(mod 2⁶⁴)，然后乘以 0xd1038d2e07b42569

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

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

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)

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

当 m 是 2 的幂时，φ(2^k) = 2^k-1，所以你可以用只是 2(k-1) 相乘.

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

这篇关于C中的乘法溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！