A New Design for Cryptography’s Black Box

DVDP_ObfuscatedCode_613x343.gif

A two-year-old cryptographic breakthrough has proven difficult to put into practice. But new advances show how near-perfect computer security might be surprisingly close at hand.

In July 2013 a pair of studies set the cryptography world on fire. They were posted within days of one another to an online archive where researchers share their work, and together they described a powerful new method for hiding the secrets inside software programs.
The method was called “indistinguishability obfuscation,” or IO. The authors touted it as a “central hub” for all of cryptography — a unified basis upon which to reconstruct familiar cryptographic tools like public keys and selectively secure signatures. The papers also took a first stab at demonstrating what IO might look like mathematically.
The research produced a flurry of interest at the time, but in the two years since the announcement, computer science researchers have encountered a number of practical challenges that stand in the way of using IO. For one thing, IO is extraordinarily slow. Obfuscating a program adds delays that would be measured not in minutes or hours, but in lifetimes. In addition, the method is not nearly as mathematically secure as it needs to be.
But in the past few months, a number of studies have provided some of the most important advances since the 2013 announcement. Some researchers now think we could get a working system in a decade, or maybe even sooner than that. “As of right now it seems like there are no big limitations,” said Amit Sahai, a computer scientist at the University of California, Los Angeles, who was a co-author on both of the papers. “IO is powerful and can do almost anything we’ve ever wanted to do.” And if IO can be constructed in terms of certain simple mathematical assumptions, researchers believe that even a quantum computer couldn’t break it.
A Mountain of Small Steps
Indistinguishability obfuscation begins by positing two programs that compute the exact same outputs by different methods — for example, the equivalent functions f(x) = x(a + b) and f(x) = ax + bx. For any set of three inputs — a, b and x — each program produces the same result as the other, but arrives at that result by a different path. IO says that given two equivalent programs, it should be possible to encrypt them so that users cannot tell which version they have, no matter how much they poke around.
The 2013 papers convinced many people that IO has the power to dramatically broaden the scope of cryptography. But the studies didn’t specify how to make the idea practical. Researchers have two primary challenges: First, to speed up the process. And second, to ensure that IO is secure.
IO would be comically impractical to use today. Any encryption scheme is going to slow down a program at least a little. In the case of IO, the mountain of equations needed to achieve indistinguishability slows things down a lot.
“It probably takes hundreds of years to obfuscate and run a program,” said Vinod Vaikuntanathan, a cryptographer at the Massachusetts Institute of Technology who has been heavily involved in IO research. “When it becomes that ridiculous you stop caring about the exact numbers.”
One general strategy taken by computer scientists to speed up running times has been to reduce obfuscating one large program to obfuscating connected smaller programs. As computer scientists envision it, obfuscating a program would require two steps. Improvements in either step could increase efficiency overall.
The first step is the harder one. Current IO methods begin with a so-called “bootstrapping” program that is small enough to obfuscate. This program interacts with the large “target” program. The bootstrapping program acts like a secure bubble around the target program’s inputs and outputs — it obfuscates anything that comes in and out of it, effectively obfuscating the target program as a whole.
Yet no one has figured out how to efficiently obfuscate even the small bootstrapping program. It’s like trying to find the “first chink in the armor,” Sahai said. “The bootstrapping program is where we’re really stuck.”
Researchers have made more progress on the second step. Once the bootstrapping program is in place, the challenge is to obfuscate longer and more varied kinds of computations. At the annual Symposium on Theory of Computing (STOC) in Portland, Ore., in June, three teams of researchers presented work that demonstrated how to go from obfuscating any single circuit — which researchers already knew how to do in theory — to obfuscating a general-purpose computer (or Turing Machine, in the eyes of theoretical computer scientists).
It’s a big leap. In order to obfuscate a circuit, researchers need to know the size of the input and every step in the computation ahead of time. Computers, by contrast, are set up to read arbitrarily long inputs, making additional computations as more data come into view. The work presented at STOC showed how to use a technique called punctured programming to obfuscate these longer, open-ended calculations as a series of discrete, connected, circuit-size steps.
“The main technical achievement applies IO for circuits to the local steps of a computation and ties things together so you are protecting the computation globally,” said Allison Bishop, a computer scientist at Columbia University who co-authored one of the papers presented at STOC.
Mathematically Proven Security
Making IO more efficient would address a practical problem. Establishing that it’s highly secure would solve a fundamental one.
When Sahai and Brent Waters, a computer scientist at the University of Texas, Austin, described a way to use IO in 2013, it was largely a matter of belief that this style of obfuscation would protect the secrets inside a program. Their initial work was kind of like tying a very complicated-looking knot — it might appear very tough to undo, but without really understanding the structure of the knot, it’s hard to be sure there isn’t some simple way of unwinding it.
“At that point there was just a construction, it wasn’t even clear how to argue security,” Vaikuntanathan said. “There was no clue how to go about it.”
The situation has improved since then. Any good cryptography scheme rests on a mathematical foundation that defines the problems the intruder would have to solve in order to break the code. RSA encryption, for example, uses the product of two large prime numbers. To start reading your emails, an intruder would have to work backward from that product and identify the two primes that were multiplied to produce it — a task that’s understood to be impossible given the limits of current computing power.
The mathematical assumptions underlying a cryptography scheme need to be hard. They should also be simple, long-tested, and well-understood, so that cryptographers can be confident that a problem is as difficult as it looks.
“It has to be a mathematical problem we can understand. Otherwise experience has taught us that it’s likely to get broken,” Sahai said.
In 2013 there were no practical security assumptions behind IO. A year later, in April 2014, Waters, Bishop and Craig Gentry, a research scientist at the IBM Thomas J. Watson Research Center in Yorktown Heights, N.Y., released a pair of papers boiling the problem of IO down to a set of simple assumptions related to a type of mathematical object called multi-linear maps. (Sahai was a co-author on one of the papers.) “We said if the attacker breaks [IO] in any way, he must be solving one of these problems,” Bishop said.
Yet multi linear maps were only introduced into cryptography in 2013. Experts haven’t had time to rigorously assess how reliable they are. “Right now, if these multi linear-map candidates got broken, you wouldn’t shock the world,” Waters said.
Currently, computer scientists are trying to figure out how to replace multi linear maps with a better-understood mathematical obstacle. The best hope seems to be “learning with errors” (LWE), a problem in machine learning. LWE and multi linear maps share a common mathematical ancestry in a field called lattice-based cryptography, which is why one seems like a good candidate to replace the other. However, no one has figured out how to make the leap.
“It’s like looking across a cliff. It’s so close, it looks like I can jump across it, but that really isn’t the case,” Vaikuntanathan said.
The Security Rush
Despite the challenges facing IO as a field, experts express confidence that an IO-based security scheme is coming. Sahai points out that the lag time in cryptography from idea to implementation has been as high as 30 years. Given the pace of progress that’s been set in the last two years, he thinks IO could be ready much sooner than that. “We’re hoping to shorten it to 10-15 years,” he said.
The major milestone to watch for is the establishment of a simpler mathematical basis for IO security. The most prominent figures in the field think the circumstances are right for IO adoption to move quickly. Bishop said she “wouldn’t bet against” a simple set of hard security assumptions developing in less than a decade. Vaikuntanathan is even more bullish. “I would even go so far as to say a couple years.”
Perfecting the Art of Sensible Nonsense In a watershed moment for cryptography, computer scientists have proposed a solution to a fundamental problem called “program obfuscation.”
Classical Computing Embraces Quantum Ideas Computer scientists are finding that “thinking quantumly” can lead to new insights into long-standing classical problems.
The optimism owes in part to all the resources that have flowed into IO research over the last two years. Sahai now serves as the director of the Center for Encrypted Functionalities at UCLA. The center, which is devoted to obfuscation research, was founded in 2014 and is funded by a $5 million grant from the National Science Foundation, with Waters and Bishop as co-principal investigators. Also last fall, the Defense Advanced Research Projects Agency (DARPA) announced the creation of SafeWare, a research program that supports the creation of “highly efficient and widely applicable program obfuscation methods with mathematically proven security properties.”
The rush to develop IO speaks to its power but also to the cat-and-mouse game intrinsic to cryptography. At the same time that researchers are developing new security strategies, others are hard at work on quantum computers. If and when they arrive, their computing speed will lay waste to most existing cryptographic schemes. Except — perhaps — for IO.
Quanta: http://bit.ly/1KQa7Sg

 

« Cybersecurity Is A Competition Issue For Business
Decoding the DNS: A New Arena in Cyber Defence »

CyberSecurity Jobsite
Perimeter 81

Directory of Suppliers

Practice Labs

Practice Labs

Practice Labs is an IT competency hub, where live-lab environments give access to real equipment for hands-on practice of essential cybersecurity skills.

Jooble

Jooble

Jooble is a job search aggregator operating in 71 countries worldwide. We simplify the job search process by displaying active job ads from major job boards and career sites across the internet.

XYPRO Technology

XYPRO Technology

XYPRO is the market leader in HPE Non-Stop Security, Risk Management and Compliance.

IT Governance

IT Governance

IT Governance is a leading global provider of information security solutions. Download our free guide and find out how ISO 27001 can help protect your organisation's information.

Authentic8

Authentic8

Authentic8 transforms how organizations secure and control the use of the web with Silo, its patented cloud browser.

ESG Elektroniksystem- und Logistik-GmbH

ESG Elektroniksystem- und Logistik-GmbH

ESG offer a comprehensive portfolio of cyber and IT services ranging from consulting, solutions and operations to testing, simulation and training.

Parsons

Parsons

Parsons has developed a converged security offering that combines cybersecurity, integrated network solutions, and critical infrastructure protection.

Alpine Cyber Solutions

Alpine Cyber Solutions

Alpine Cyber is a Managed IT Service Provider focused on cybersecurity and cloud services.

CyPhyCon

CyPhyCon

CyPhyCon is an annual event exploring threats and solutions to cyber attacks on cyber-physical systems such as industrial control systems, Internet of Things and Industrial Internet of Things.

Thridwayv

Thridwayv

Thirdwayv helps your enterprise realize the full potential of loT connectivity. All while neutralizing security threats that can run ruin the customer experience - and your reputation.

Enzoic

Enzoic

Enzoic is an enterprise-focused cybersecurity company committed to preventing account takeover and fraud through compromised credential detection.

Aigner Business Solutions

Aigner Business Solutions

Aigner Business Solutions GmbH is a specialist in IT-Security and Data Protection. Concise and focussed.

Two Six Technologies

Two Six Technologies

Two Six Technologies delivers R&D, innovation, productization and implementation expertise in cyber, data science, mobile, microelectronics and information operations.

R-Tech

R-Tech

R-Tech GmbH manages the digital start-up initiative, whose goal is to build a sustainable start-up culture in the field of digitization throughout the Upper Palatinate district of Bavaria.

Kennedys

Kennedys

Kennedys is a global law firm with expertise in litigation/dispute resolution and advisory services, particularly in the insurance/reinsurance and liability sectors, including cyber risk.

Ministry of Electronics & Information Technology (MeitY)

Ministry of Electronics & Information Technology (MeitY)

The Ministry of Electronics & Information Technology is an executive agency responsible for IT policy, strategy and development of the electronics industry.

EDGE Group

EDGE Group

EDGE is one of the world’s leading advanced technology groups, established to develop agile, bold and disruptive solutions for defence and beyond.

Auriga

Auriga

Auriga create innovative software and have become a benchmark for high quality banking software including cyber security solutions to protect business critical devices.

Zyxel Networks

Zyxel Networks

Zyxel Networks is a leading provider of secure, AI-powered networking solutions for small to medium businesses (SMBs) and the enterprise edge.

S4E (Security for Everyone)

S4E (Security for Everyone)

At S4E.io, our mission is to democratize digital security, making it accessible, simple, and effective for individuals and businesses of all sizes.

Interpres Security

Interpres Security

Interpres Security operationalizes TTP-based threat intelligence and automates continuous exposure monitoring to help CISOs and security practitioners reduce threat exposure.