Btukfyl

Imagine you are reverse engineering a software. This software uses a library, which is obfuscated and encrypted. The library contains a function, lets call it secret_function. This function is a pure function (i.e. it doesn't have any side effect and when called with the same arguments it returns always the same output).

Assuming i can call secret_function how may times i want, with whichever arguments i want, but i can't peek at the implementation, is it possible to build an equivalent function in another language (python for example), only analyzing the input and output values?

This is an example implementation of secret_function:

int secret_function(int a, int b) {

    if (a == 234) {

        return b*2 - a;

    }

    return a*b;

}

A way to archive this i thought of is to call the function with every possible argument, (in the example 2^32 * 2^32, assuming a 32 bit int) and store all of them, to return them based on the arguments, like a giant lookup table. But this doesn't seem very efficient, if at all possible.

UPDATE:
You can assume that the function is working with fixed size arguments. So no strings or variable length arrays.

Your problem seems to be related to what Sibyl aim at doing (https://github.com/cea-sec/Sibyl).
It tries based on the side effects of the function (return value, memory writes, ...) to identify a known function.
Of course, you will need a kind of database to "learn" the function !

If you have all the possible input and all the expected outputs, and they're not indistinguishable from encrypted/compressed data, you can find more efficient storage mechanisms than just having a large lookup table. Even a simple genetic algorithm can very quickly get you to "use a * b, unless a == 234" (I've actually made a solver specifically for this kind of problem, though in a more general mathematical formula case). In the end, it's a rather ordinary optimization problem, where you're balancing off the storage space, computation and preparation time needed to give the correct result. More complicated algorithms can take longer to solve, which is one of the reasons why encryption works - those algorithms are specifically designed to make it extremely labor intensive to go from a set of known inputs and outputs to the private key used for the encryption.

But in any case, to have certainty, you must try all possible inputs. That's easy enough (though certainly laborious) for a couple integers, but quickly gets untenable for something like a string.

Unless you try all the input possibilities, as you suggested, you can only get an approximation of the function. This is basically one of the basic problems in the machine learning field, so I would look that way instead of trying to generate a lookup table for 2^32 * 2^32 values.

You should obviously be careful that you won't have 100% guarantee that the function is equivalent and also remember that in particular fields how the output is computed is as important as the output itself. Take encryption functions: having the same outputs but exposing informations (due to memory leaks, power usage spikes and so on) for side channel attacks means that the "equivalent" function is in fact far worse than the original (to the point it might not be a suitable replacement).