What if We Told You that Applications Could be Run While Still Encrypted?

You would probably tell us to stop wasting your time. Or that it was simply impossible. Or that this would be the holy grail, but could only exist in sci-fi movies.

But, you would be wrong. A new peer-reviewed white paper written by Amit Sahai, a professor of computer science at UCLA, has created quite a stir this week.
It outlines how to encrypt software, and yet still be able to run that software in its encrypted state. Sahai uses a “multilinear jigsaw puzzle” method that effectively adds a new class of “protectable secret” to data cryptography. Any attempt to RE the software would result in garbage out, and it would take a hundred years to possibly break the puzzle…and by that time, of course, the value of doing so would be trivially small to the attacker in all but the most esoteric scenarios.

The research has been collaborated on and peer-reviewed by some talented people in the space, including Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Brent Waters, and Amit Sahai. That bodes well for the research when it will be announced later this Fall officially. If it proves to pass muster, and if there are pragmatic and robust ways to implement this approach, the impact to data security world wide could be one of biggest advances in application security in decades. It would drastically impact the RE community, and result in much slower discovery of application defects (aka vulnerabilities in our world), and also simplify the delivery of OS patches, etc.

Like any and every crypto implementation, there will be weaknesses, and challenges. And the new approach will also need to stand the test of time, and the scrutiny of the larger community of researchers and hackers alike. At the least, we may have finally discovered one of the “holy grails” of application security. While the impact would be universally massive, some close to home examples of how it could be used would be the ability to send a single message that could be sent to a large group of recipients, yet each recipient would get different information, depending on attributes of that particular recipient. Or, perhaps a university could share the results of different treatment tests with big pharma, without revealing sensitive patient PII from the test group.

For more information about the paper and to get an idea of what will be presented this October, see http://eprint.iacr.org/2013/451 But you might want to grab a redbull before you crack it open… an excerpt from the introduction: “In functional encryption, ciphertexts encrypt inputs x and keys are issued for circuits C. Using the key SK_C to decrypt a ciphertext CT_x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually.”

We’ll keep an ear out for hallway discussions and opinions of the hacking community this week, and update the blog if we hear anything particularly interesting at this early stage of discovery.