CODEWITHSUNDEEP
mathreverse-engineeringmodulus
spacemanspiff
spacemanspiff

Reputation: 35

Reversing a function involving a modulus arithmetics

I'm trying to reverse-engineer a function to get the input. Suppose we know the output (x). Is it possible to get the input (z)? The code for the function is as follows

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

Suppose we know the value of the output (x) this function throws at us, say 35500.

Considering x = (uint)((ulong)x * a % (ulong)uint_1); It is obvious that x on left hand side is greater than the one on the right hand side as we start with uint x = 1u; If we had something like x = a % (ulong)uint_1;, we could just check the value of a by brute force (starting a with 1 and incrementing it with 1). The code is complex and I don't know if it is even possible to reverse-engineer this function.

Upvotes: 0

Views: 162

Answers (2)

President James K. Polk
President James K. Polk

Reputation: 42010

Not only is it possible to get the input z, you can use your function myfunc with one little change to get it: simply change

var uint_2 = 1114478491u;

to

var uint_2 = 42451u;

To elaborate:

The function myfunc is performing modular exponentiation with a fixed exponent. Specifically, it is computing z1114478491 mod 1372797859.

Also, 1372797859 = 25057 * 54787, both factors are primes. This may be recognized as an instance of the RSA cryptosystem with toy-sized parameters. We may regard myfunc as performing an RSA encryption* and therefore 1114478491 as the encrypt exponent. Therefore, using the procedure outlined in the Wikipedia page we can compute the decrypt exponent which turns out to be 42451. Since myfunc is just a modular exponentiation function, merely by changing 1114478491u to 42451u we have the decrypt function which is the inverse.

*In RSA an encrypt and decrypt exponent exist, but which role is assigned to which exponent is arbitrary. However, in actual implementations the encrypt exponent is usually small, almost always 65537 in fact, and such a small exponent can only play the role of the encrypt exponent or the system is easily broken.

Upvotes: 3

arrowd
arrowd

Reputation: 34411

You can use SMT solver directly, or via symbolic execution engine to find function inputs based on its outputs.

For instance, you can re-write your function in C and use KLEE to find the answer:

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

Compile this code with clang to emit LLVM IR:

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

Then run KLEE on it

klee main.bc

And then analyze results using ktest-tool.

Upvotes: 1

Related Questions