3

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.

  • 4
    I think you already answered the question with your example. The special case (234) can't be detected without evaluating the function with exactly that input. A lookup-table also only works for inputs with a defined range, use strings and you will never be able to create a lookup-table. – FooTheBar Apr 9 at 10:04
6

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 !

5

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.

  • The genetic algorithm you cited sounds interesting, have you got any example of that? Can genetic algorithms still be efficient if the number of possible inputs increases? – Rocco Mancin Apr 9 at 14:41
  • @RoccoMancin The number of inputs isn't really what makes the whole process slower (besides the verification); genetic algorithms will tend to take longer to find the solution as the problem becomes more complex (more branching, more complex operations). But of course, for any algorithm you choose, there will always be the step where you need to check all the possible inputs against all the expected outputs if you need 100% accuracy (and even then, only assuming the same inputs always produce the same output). – Luaan Apr 9 at 16:13
  • I have a simple genetic solver available on GitHub (github.com/Luaancz/SalemOptimizer); it's adapted from a more general solver I made some time ago. This particular one only has one "operation" (called branch; today I'd probably go with "expression" or "node"), but that's only because the problem only really needs one - the same approach can easily be used with multiple operations, though. For a math solver, those would be things like add, multiply etc. – Luaan Apr 9 at 16:19
4

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).

2

This problem essentially describes the field of sequential analysis coupled with curve fitting.

If you are able to make some assumptions about the inputs to the secret function that your model needs to be good for, you can use this to guide your choice of algorithm for generating new values to try as inputs to the function.

If you are able to make some assumptions about the characteristics of the function, you can use this to guide your choice of function to fit to the outputs of the secret function, which will determine how the resulting function behaves when you subject it to inputs you haven't tried yet.

Even the "simple" example given might be interpreted many different ways in these fields. For instance:

  • If you can't assume anything about the function and your model of it must reproduce exactly the correct value, you have no choice but to evaluate all 2^64 possibilities. You don't necessarily have to store them all as you go if you correctly guess a function that can reproduce every value with the right parameters.
  • If you know that there is exactly one value of a that changes the function, and that it is one of two linear functions of a and b depending on this value then you'll need on average 2^31 trials to find the magic a value, significantly shrinking the problem.
  • If you don't require an exact reproduction then you can begin reasoning from a value judgement about what errors are acceptable. For instance, a function which is completely wrong 2^-32 of the time might be perfectly acceptable, so if you know that the special case is no bigger than this you can just pick a few random values (almost certainly not accidentally picking a = 234) and solve the linear equations.
  • You might not reasonably know that the function has linear parts, but know that it's no more complex than some other function. The parameters to this more complex function, when fitted to outputs from the secret function, would produce a function which matches linear behaviour for the values obtained from the function, but wouldn't necessarily be guaranteed to behave linearly for untested values; the possible behaviours of any function you choose to fit must hence endeavour to match the range of behaviours that can be considered plausible under your assumptions.

These are big fields, and there are plenty of options that may be available to you with the benefit of the specifics of your problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.