# Time reverse engineering a “random” algorithm

I was just wondering if there are estimations possible for an algorithm using a fixed number of random binary or arithmetic operation on an input of how many (input, output) pairs are necessary to be probably able to reverse engineer this algorithm. And in addition if having any (input, output) combination, the computation time to reverse engineer with fixed computation power (on a regular von neumann architecture).

The only thing I found so far is something about logical depth and how to compare the complexity of algorithms.

• This question is about math and computational complexity, not about reverse engineering. Please post to math.stackexchange.com instead. – Jason Geffner Jul 17 '14 at 21:48
• Well, first it's certainly NOT about mathematics, more likely related to computer science. And, second, I see a direct link to reverse engineering here... The fact that the complexity of an algorithm is not related to the quality of reversing the program is actually something controversial that should be discussed before being thrown away. – perror Jul 17 '14 at 22:50
• I'm not sure how a question about computational complexity that involves multiple variable inputs could be "certainly NOT about mathematics" :) – Jason Geffner Jul 18 '14 at 14:09

In fact, there has been some works on trying to relate the actual complexity of a program before and after obfuscation and its difficulty to reverse.

The seminal paper about that is a technical report from Collberg et al. from 1997 [1]. It defines a measure of potency to classify the different types of obfuscation and order them in terms of added complexity compared to the original program.

Unfortunately, this way of classifying obfuscation transforms is quite naive. Mainly because the complexity of a program gives an idea of how much operations you need to process it, but has no clue on how much it is difficult to simplify it.

For example, adding a lot of unnecessary variables and extra loops to the program will increase a lot its complexity. Yet, an optimizer with a simple static-analysis of the program may recover the original program.

On the contrary, replacing a sequence of complex instructions by a simple look-up table that will mimic perfectly this sequence of instructions will lower the complexity of the program, but figuring out what is the original sequence of instructions just by looking at the table might be quite hard.

So, except for some very specific cases, the complexity of a program is not a trustworthy way to measure its difficulty to reverse.

In fact, we do not have any complete and objective way of measuring how good is an obfuscation... nor does cryptographers have a way to say that a cryptosystem is safe (but, they have tools that can give them much more confidence than we have in our schemes right now, so we should maybe take a closer look at what they do as our fields are getting more and more intimate in these days... just my personal feeling about that).

[1] A Taxonomy of Obfuscating Transformations by Christian Collberg, Clark Thomborson and Douglas Low. Technical Report #148, University of Auckland, 1997.