April 22, 2015 at 20:20Obfuscation programs
Obfuscation of programs is the breakthrough, hottest area of cryptography today. 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 that generates almost everything that we have in cryptography today. We will figure out what it is.
By giving users access to the installation files of programs, companies will inevitably reveal their professional secrets and best practices, and nothing can stop malicious competitors from shameless copying and theft of 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 fixing, and attack the unfortunate users who did not have time to update on time.
These two situations are connected by one fundamental problem, namely: a program written by a person can be a person and understood, analyzed, disassembled. But what if there would be an algorithm that could beyond recognition be irreversibly redoing the program while maintaining its functionality? So that the program would be completely impossible to understand, but at the same time would it work no worse than the original? Such an algorithm is called “obfuscating” or “obfuscator”.
There are currently no good obfuscators at the disposal of developers, 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, it can be called "security through incomprehensibility." But such obfuscation, with little zeal, is easy to deobfuscate, and therefore this is not an obstacle for good hackers.
But what exactly do we want from an obfuscator? “The inability to understand the program” which he issues sounds quite vague ...
In 2001 [1]For the first time, a formal definition was proposed for the first time: the resulting program issued by the obfuscator should give no more information than just a black box that simulates the input / output behavior of the original program. That is, there should not be any difference between the obfuscated program code and, for example, the web service, which simply returns the result of the program at the given input. Such an algorithm is called “Black Box Obfuscation”. Unfortunately, the same article showed 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 return some secret at their own input [1] , Theorem 3.4. Since then, this line of research has died out, people have become dull and obfuscating programs for 12 years was considered impossible.
In 2013 [2]a breakthrough was made in this area, theorists brought out another definition 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 the obfuscations of these two programs will be indistinguishable from each other. That is, if I have programs P1, P2, such that for any input x, P1 (x) = P2 (x), and O is an obfuscator of indistinguishability, which takes program P as input and returns a new program O (P), it will not be possible to distinguish between O (P1) and O (P2). That is, you cannot say which obfuscation belongs to which initial program, either O (P1) is obfuscation P1, or is it obfuscation P2. (Obfuscator O is a probabilistic algorithm). At first sight, it’s not clear how good such an obfuscator is. The answer to this question, which is discussed in the next two paragraphs, was shocked by the cryptographic community.
In 2007 [3] , the “best” obfuscator was investigated. It was proposed to call the obfuscator “best” if the obfuscated program reports no more information than any other program with the same functionality. And it was shown that the Obfuscator of 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 refine 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 the Obfuscator of Indistinguishability together with one-way functions (One-Way Functions) together give:
That is, in fact, the Obfuscator of Indistinguishability is a primitive that forms almost all cryptography, with the help of which you can build almost everything that we have in cryptography today. Of course, much work is still required before the obfuscator becomes available for widespread 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) possibility 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 best-possible obfuscation.” TCC 2007.
By giving users access to the installation files of programs, companies will inevitably reveal their professional secrets and best practices, and nothing can stop malicious competitors from shameless copying and theft of 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 fixing, and attack the unfortunate users who did not have time to update on time.
These two situations are connected by one fundamental problem, namely: a program written by a person can be a person and understood, analyzed, disassembled. But what if there would be an algorithm that could beyond recognition be irreversibly redoing the program while maintaining its functionality? So that the program would be completely impossible to understand, but at the same time would it work no worse than the original? Such an algorithm is called “obfuscating” or “obfuscator”.There are currently no good obfuscators at the disposal of developers, 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, it can be called "security through incomprehensibility." But such obfuscation, with little zeal, is easy to deobfuscate, and therefore this is not an obstacle for good hackers.
But what exactly do we want from an obfuscator? “The inability to understand the program” which he issues sounds quite vague ...
In 2001 [1]For the first time, a formal definition was proposed for the first time: the resulting program issued by the obfuscator should give no more information than just a black box that simulates the input / output behavior of the original program. That is, there should not be any difference between the obfuscated program code and, for example, the web service, which simply returns the result of the program at the given input. Such an algorithm is called “Black Box Obfuscation”. Unfortunately, the same article showed 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 return some secret at their own input [1] , Theorem 3.4. Since then, this line of research has died out, people have become dull and obfuscating programs for 12 years was considered impossible. In 2013 [2]a breakthrough was made in this area, theorists brought out another definition 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 the obfuscations of these two programs will be indistinguishable from each other. That is, if I have programs P1, P2, such that for any input x, P1 (x) = P2 (x), and O is an obfuscator of indistinguishability, which takes program P as input and returns a new program O (P), it will not be possible to distinguish between O (P1) and O (P2). That is, you cannot say which obfuscation belongs to which initial program, either O (P1) is obfuscation P1, or is it obfuscation P2. (Obfuscator O is a probabilistic algorithm). At first sight, it’s not clear how good such an obfuscator is. The answer to this question, which is discussed in the next two paragraphs, was shocked by the cryptographic community.In 2007 [3] , the “best” obfuscator was investigated. It was proposed to call the obfuscator “best” if the obfuscated program reports no more information than any other program with the same functionality. And it was shown that the Obfuscator of 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 refine 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 the Obfuscator of Indistinguishability together with one-way functions (One-Way Functions) together give:
- public key encryption
- short digital signatures
- non-interactive evidence with zero disclosure (NIZKs - Non-Interactive Zero Knowledge Proofs)
- forgetful transfer (Oblivious Transfer)
- 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 whatever you want)
- together with fully homomorphic encryption, give Functional Encryption
- and many many others
That is, in fact, the Obfuscator of Indistinguishability is a primitive that forms almost all cryptography, with the help of which you can build almost everything that we have in cryptography today. Of course, much work is still required before the obfuscator becomes available for widespread use, but the foundation for this has already been laid.
References
[1] Barak B., Goldreich O., Impagliazzo R., Rudich S., Sahai A., Vadhan S. and Yang K. “On the (im) possibility 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 best-possible obfuscation.” TCC 2007.