Obfuscation programs
Obfuscation of programs is a breakthrough, the hottest today, field of cryptography. Over the past two years, over 70 articles on this topic have been written, it provokes heated discussions, creates real races between research groups, and opens a testing ground for scientific research. Moreover, it turns out that obfuscation is a fundamental, forming primitive, which generates practically everything that we have in cryptography today. We will understand what it is.
Giving users access to the installation files of programs, companies inevitably reveal their professional secrets and developments, and nothing stops malicious malicious competitors from shamelessly copying and stealing other people's algorithms. Let's pay attention to another example, these are important updates (patches) that fix errors in operating systems. Almost instantly, the next update is analyzed by hackers, they identify the problem that this update is repairing, and attack unfortunate users who have not had time to update themselves.
These two situations are connected by one fundamental problem, namely: a program written by a person can be understood by a person, analyzed, analyzed. And what if there was an algorithm that could beyond recognition, irreversibly redo the program while maintaining its functionality? So that the program would be completely impossible to understand, but at the same time it would work no worse than the original one? This algorithm is called "obfustsiruyuschiy" or "obfuscator."
Developers currently have no good obfuscators at their disposal, and those obfuscators that are widely used today are very primitive - they can rearrange instructions, replace variable names, insert pieces of code that actually have zero effect and do similar things that In general, can be called "security through incomprehensibility." But such obfuscation with a little zeal is easy to deobfuscate, and therefore it is not a barrier for good hackers.
But what exactly do we want from obfuscator? "The inability to understand the program" which he gives sounds very vague ...
')
In 2001 [1] , a formal definition was proposed for the first time: the resulting program issued by the obfuscator should provide no more information than just a black box that simulates the input / output behavior of the original program. That is, there should be no difference between the obfuscated program code and, for example, a web service that simply returns the result of the program at a given input. This algorithm is called the “Black Box Obfuscation”. Unfortunately, in the same article it was shown that such an obfuscator cannot be built for all programs. Namely, there is a very specific class of programs that cannot be obfuscated: these are programs that, at their own entrance, return some secret [1] , Theorem 3.4 . Since then, this line of research has faded away, people have become despondent, and obfuscation of programs for as long as 12 years was considered impossible.
In 2013 [2] , a breakthrough was made in this area, theorists put another definition to light and proposed a real design for it. This new type of obfuscator is called “Indistinguishability Obfuscation” (“iO”), formally: if there are two different programs, but with absolutely identical functionalities, then obfuscations of these two programs will be indistinguishable from each other. That is, if I have the programs P1, P2, such that for any input x, P1 (x) = P2 (x), and O is the indistinguishability obfuscator that takes the program P as input and returns the new program O (P), it will be impossible to distinguish between O (P1) and O (P2). That is, you cannot say which obfuscation belongs to which original program, either O (P1) is obfuscation of P1, or whether it is obfuscation of P2. (Obfuscator O - probabilistic algorithm). At first glance, it is not clear how good such obfuscator is. The answer to this question, which is described in the following two paragraphs, shook the cryptographic community.
In 2007 [3] , the “best” obfuscator was investigated. It was proposed to call obfuscator "best" if the obfuscated program reports no more information than any other program with the same functionality. And it was shown that Obfuscator Indistinguishability - this is the "best" obfuscator. Thus, the candidate design of the best obfuscator in the world is already in our pocket! And soon it will not be necessary to excel in confusing instructions and renaming variables.
But the story does not end there, to the great surprise of cryptographers around the world, it turned out that Obfuscator Indistinguishability together with one-way functions (One-Way Functions) together give:
That is, in fact, Obfuscator Indistinguishability is a primitive, forming almost all of the cryptography, with which you can build almost everything that we have in cryptography today. Of course, it requires a lot of work before obfuscator becomes available for wide use, but the foundation for this has already been laid.
[1] Barak B., Goldreich O., Impagliazzo R., Rudich S., Sahai A., Vadhan S. and Yang K. “On the (im) option of obfuscating programs.” CRYPTO 2001.
[2] Garg S., Gentry C., Halevi S., Raykova M., Sahai A., and Waters B. “Candidate indistinguishability obfuscation and functional encryption for all circuits.” FOCS 2013. ( pdf )
[3] Goldwasser S., and Guy NR "On the best-possible obfuscation." TCC 2007.
Giving users access to the installation files of programs, companies inevitably reveal their professional secrets and developments, and nothing stops malicious malicious competitors from shamelessly copying and stealing other people's algorithms. Let's pay attention to another example, these are important updates (patches) that fix errors in operating systems. Almost instantly, the next update is analyzed by hackers, they identify the problem that this update is repairing, and attack unfortunate users who have not had time to update themselves.
These two situations are connected by one fundamental problem, namely: a program written by a person can be understood by a person, analyzed, analyzed. And what if there was an algorithm that could beyond recognition, irreversibly redo the program while maintaining its functionality? So that the program would be completely impossible to understand, but at the same time it would work no worse than the original one? This algorithm is called "obfustsiruyuschiy" or "obfuscator."Developers currently have no good obfuscators at their disposal, and those obfuscators that are widely used today are very primitive - they can rearrange instructions, replace variable names, insert pieces of code that actually have zero effect and do similar things that In general, can be called "security through incomprehensibility." But such obfuscation with a little zeal is easy to deobfuscate, and therefore it is not a barrier for good hackers.
But what exactly do we want from obfuscator? "The inability to understand the program" which he gives sounds very vague ...
')
In 2001 [1] , a formal definition was proposed for the first time: the resulting program issued by the obfuscator should provide no more information than just a black box that simulates the input / output behavior of the original program. That is, there should be no difference between the obfuscated program code and, for example, a web service that simply returns the result of the program at a given input. This algorithm is called the “Black Box Obfuscation”. Unfortunately, in the same article it was shown that such an obfuscator cannot be built for all programs. Namely, there is a very specific class of programs that cannot be obfuscated: these are programs that, at their own entrance, return some secret [1] , Theorem 3.4 . Since then, this line of research has faded away, people have become despondent, and obfuscation of programs for as long as 12 years was considered impossible. In 2013 [2] , a breakthrough was made in this area, theorists put another definition to light and proposed a real design for it. This new type of obfuscator is called “Indistinguishability Obfuscation” (“iO”), formally: if there are two different programs, but with absolutely identical functionalities, then obfuscations of these two programs will be indistinguishable from each other. That is, if I have the programs P1, P2, such that for any input x, P1 (x) = P2 (x), and O is the indistinguishability obfuscator that takes the program P as input and returns the new program O (P), it will be impossible to distinguish between O (P1) and O (P2). That is, you cannot say which obfuscation belongs to which original program, either O (P1) is obfuscation of P1, or whether it is obfuscation of P2. (Obfuscator O - probabilistic algorithm). At first glance, it is not clear how good such obfuscator is. The answer to this question, which is described in the following two paragraphs, shook the cryptographic community.In 2007 [3] , the “best” obfuscator was investigated. It was proposed to call obfuscator "best" if the obfuscated program reports no more information than any other program with the same functionality. And it was shown that Obfuscator Indistinguishability - this is the "best" obfuscator. Thus, the candidate design of the best obfuscator in the world is already in our pocket! And soon it will not be necessary to excel in confusing instructions and renaming variables.
But the story does not end there, to the great surprise of cryptographers around the world, it turned out that Obfuscator Indistinguishability together with one-way functions (One-Way Functions) together give:
- public key encryption
- short signatures
- Zero Disclosure Non-Interactive Evidence (NIZKs - Non-Interactive Zero Knowledge Proofs)
- Oblivious Transfer
- confidential calculation protocol (multi-party computation protocols)
- broadcast protocol (Broadcast encryption)
- contested encryption (Deniable encryption) (in this scheme, you can provide a false key to the cipher, which will decrypt all the messages you send to what you want)
- together with fully homomorphic encryption, provide functional encryption (Functional Encryption)
- and many many others
That is, in fact, Obfuscator Indistinguishability is a primitive, forming almost all of the cryptography, with which you can build almost everything that we have in cryptography today. Of course, it requires a lot of work before obfuscator becomes available for wide use, but the foundation for this has already been laid.
Links
[1] Barak B., Goldreich O., Impagliazzo R., Rudich S., Sahai A., Vadhan S. and Yang K. “On the (im) option of obfuscating programs.” CRYPTO 2001.
[2] Garg S., Gentry C., Halevi S., Raykova M., Sahai A., and Waters B. “Candidate indistinguishability obfuscation and functional encryption for all circuits.” FOCS 2013. ( pdf )
[3] Goldwasser S., and Guy NR "On the best-possible obfuscation." TCC 2007.
Source: https://habr.com/ru/post/255871/
All Articles