The outputs I'm getting are only 2x the length of the input strings so any kind of brute force programme would be fine. Thanks.
6
-
1$\begingroup$ That's not possible in general, by an argument similar to that for this question: we can make a counterexample where sucess would be a break of a cryptographic primitive that is trusted secure. For affine functions (including linear, CRCs..) see this answer. Software recommendation is not really on-topic $\endgroup$– fgrieu ♦May 4, 2020 at 12:11
-
$\begingroup$ Maybe in some specific cases, you can use machine learning. It wouldn't give you a specific function per se but would give you an approximation. $\endgroup$– QuestionEverythingMay 4, 2020 at 12:39
-
$\begingroup$ @HasanIqbal True, but I guess you would have to train it somehow. That might that you have to have a set of input strings, algorithms and output strings put into the neural network. Or do you think you can train it using just a large set of inputs and outputs? $\endgroup$– Maarten Bodewes ♦May 4, 2020 at 14:54
-
$\begingroup$ @MaartenBodewes Although I'm no expert in ML, I think that's the essence of training. Give it a set of input and corresponding output, ML algorithms would basically try to 'fit the curve' as best as it can. $\endgroup$– QuestionEverythingMay 4, 2020 at 15:44
-
$\begingroup$ It is fascinating because, as described in the comments above, there is an impossibility in general to reveal functions, and, at the same time, it is also impossible in general to hide a program that realizes a computable function: the known program obfuscation problem (boazbarak.org/Papers/obfuscate.pdf.) $\endgroup$– Crypto LearnerMay 5, 2020 at 1:29
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
Recovering an arbitrary function $f:M \rightarrow N$ from samples $x_i, f(x_i)$ is clearly impossible without additional information unless the given $x_i$ cover $M$ or unless $N$ is of size one, since an arbitrary continuation can be chosen on the remaining inputs. By the same token, it is trivial to find some function that reproduces the input-output behaviour of $f$ (for instance one may just pick a function that takes inputs outside the given values to some constant output in the codomain of the function).
Finding the simplest or most efficient function that reproduces some given input-output behaviour is believed to be difficult in general, even when a full description of the target function is given to the adversary and even when domain and codomain are fairly small. For instance, the paper Partitions in the S-Box of Streebog and Kuznyechik by Leo Perrin basically showed a surprisingly efficient way to implement the S-box of the Russian encryption algorithm Kuznyechik (and the Russian hash function Streebog) as well as the techniques used to obtain this representation and won the best paper award at FSE 2019. The S-box in question is a function that takes an 8-bit value to another 8-bit value and is completely public. Hence, even for functions that small, recovering an efficient function representation from the value table will not be easy in the general case.
$\begingroup$
$\endgroup$
As it was mentioned in the comments, you could try to use machine learning. The open-source software WEKA might help you to get started.
One possibility is to use the PART classifier to generate a decision list for each output bit (as a function of the input bits). Another possibility is to use the JRip classifier to generate a ruleset.
Obviously, many input bits require a large dataset and usually generate a large decision list or ruleset.
