反转涉及模算术的函数

Question

我正在尝试对函数进行逆向工程以获取输入。假设我们知道输出 (x)。是否有可能获得输入（z）？函数代码如下

uint myfunc (uint z){
    var uint_1 = 1372797859u;
    var uint_2 = 1114478491u;
    ulong a = (ulong)z;
    uint x  = 1u;
    for (int i = 0; i < 32; i += 1)
    {
        if ((uint_2 & 1u) != 0u)
        {
            x  = (uint)((ulong)x  * a % (ulong)uint_1);
        }
        a = a * a % (ulong)uint_1;
        uint_2 >>= 1;
    }
    return x ;
}

假设我们知道这个函数抛给我们的输出 (x) 的值，比如 35500。

考虑x = (uint)((ulong)x * a % (ulong)uint_1); 很明显，左侧的 x 大于右侧的，因为我们从 uint x = 1u; 开始如果我们有类似 x = a % (ulong)uint_1; 的东西，我们可以通过暴力检查 a 的值（从 a 开始，从 1 开始，然后以 1 递增）。代码很复杂，我不知道是否可以对这个函数进行逆向工程。

Answer 1

您可以直接使用 SMT 求解器，或通过符号执行引擎根据其输出查找函数输入。

例如，您可以用 C 重写您的函数并使用 KLEE 找到答案：

#include <klee/klee.h>

uint myfunc (uint z) {
  ...
}

int main(int argc, char* argv[]) {
  int input, output;
  input = klee_int("input");
  output = myfunc(input);
  klee_assert(output == 35500);
  return 0;
}

使用 clang 编译此代码以发出 LLVM IR：

clang -c -emit-llvm -o main.bc main.c

然后运行KLEE就可以了

klee main.bc

然后使用ktest-tool分析结果。

Answer 2

不仅可以获得输入 z，您还可以使用您的函数 myfunc 稍作改动即可获得它：只需更改

var uint_2 = 1114478491u;

到

var uint_2 = 42451u;

详细说明：

函数 myfunc 正在使用固定指数执行 mod 平方幂运算。具体来说，就是计算 z^1114478491 mod 1372797859.

还有，1372797859 = 25057 * 54787，两个因数都是质数。这可能被认为是带有玩具大小参数的 RSA cryptosystem 的实例。我们可以将 myfunc 视为执行 RSA 加密 ^*，因此将 1114478491 视为加密指数。因此，使用维基百科页面中概述的过程，我们可以计算出解密指数，结果为 42451。由于 myfunc 只是一个 mod 元求幂函数，只需将 1114478491u 更改为 42451u，我们就有了decrypt 函数是逆函数。

^{*RSA中存在加密和解密指数，但哪个角色分配给哪个指数是任意的。但是在实际实现中，加密指数通常很小，实际上几乎都是65537，这么小的指数只能起到加密指数的作用，否则系统很容易被攻破。}

反转涉及模算术的函数

Reversing a function involving a modulus arithmetics

math

reverse-engineering

modulus