Researchers at UCLA said they’ve developed a game-changing obfuscation mechanism that will put a dent in hackers’ efforts to reverse engineer patches and understand how an underlying piece of software works.
“You write your software in a nice, reasonable, human-understandable way and then feed that software to our system,” UCLA computer science professor Amat Sahai said in a university release. “It will output this mathematically transformed piece of software that would be equivalent in functionality, but when you look at it, you would have no idea what it’s doing.”
Sahai and his fellow researchers, Sanjam Garg, Craig Gentry, Shai Halevi and Mariana Raykova of IBM Research, and Brent Waters of the University of Texas, said this is the first time software obfuscation has been accomplished and could be an important tool in protecting intellectual property, for example. Sahai said that previous obfuscation attempts could be broken in days; this new method would require a hacker to spend hundreds of years to break the cryptography they’ve put in play.
“The real innovation that we have here is a way of transforming software into a kind of mathematical jigsaw puzzle,” Sahai said. “What we’re giving you is just math, just numbers, or a sequence of numbers. But it lives in this mathematical structure so that these individual pieces, these sequences of numbers, can only be combined with other numbers in very specified ways.
“You can inspect everything, you can turn it upside-down, you can look at it from different angles and you still won’t have any idea what it’s doing,” Sahai said. “The only thing you can do with it is put it together the way that it was meant to interlock. If you tried to do anything else — like if you tried to bash this piece and put it in some other way — you’d just end up with garbage.”
The team’s paper, “Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits,” will be presented at the IEEE Symposium on Foundations of Computer Science in October. It also covers functional encryption, a method that encrypts information on the fly and depending on identity characteristics of the recipient, they would be able to decrypt only certain bits of information. Sahai offered the example of a hospital sharing treatment outcomes with a researcher without sharing patient information.
The secret sauce, however, is in the jigsaw puzzle analogy.
In Multilinear Jigsaw Puzzle we view group elements as the puzzle pieces. The intuitive analogy to jigsaw puzzles is that these group elements can only be combined in very structured ways—like jigsaw puzzle pieces, different puzzle pieces either fit together or, if they do not fit, then they cannot be combined in any meaningful way,” the researchers wrote in their paper. “We view a valid multilinear form in these elements as a suggested solution to this jigsaw puzzle: a valid multilinear form suggests ways to interlock the pieces together.”
The paper said that the jigsaw puzzle scheme consists of two algorithms, a Jigsaw generator and verifier. The generator builds system parameters and group elements that are mathematically verified whether they are a correct solution.
By obfuscating software patches, for example, vulnerabilities being repaired would be hidden from an attacker, the paper said, giving IT teams time to test and deploy patches without fear of the patch being reverse engineered in the meantime. The same goes for cases where intellectual property is being shared and that legal protections would not be enough to protect the IP from being reverse engineering new software, for example.
