Vulnerability Management

DARPA moves forward in quest for zero-knowledge proofs for vulnerability disclosure

Former director of DARPA, Arati Prabhakar, joins others on stage during “What Are They Thinking? Man Meets Machine” at the Vanity Fair New Establishment Summit in San Francisco, California. The research and development arm for the Department of Defense have successfully demonstrated a limited set of use cases for applying zero-knowledge...

There are few relationships in cybersecurity more delicate than the one between a security researcher who discovers a vulnerability in commercial software or hardware and the company they notify.

The company may not care about the flaw or its impact on customers, or it might downplay the severity to avoid payment, fail to prioritize patching or simply go after the researcher with legal threats. The researcher may try to extort the company, or disagree on its potential for harm or simply believe that a timelier public disclosure will incentivize the business to develop a quicker patch to protect end users.

While the cybersecurity community and industry have addressed some of these problems through coordinated vulnerability disclosure policies, there’s still a fair amount of disagreement and mismatched incentives that can lead to mistrust between the two parties. One of the trickier problems is around how to ethically disclose a bug to the broader public and put pressure on an organization without revealing technical information that might allow malicious hackers to exploit it before a patch becomes available.  

Enter DARPA.

The research and development arm for the Department of Defense have successfully demonstrated a limited set of use cases for applying zero-knowledge proofs to the software vulnerability disclosure process. A zero-knowledge proof is a cryptographic protocol that allows one party to create mathematical evidence to demonstrate to another party that they can answer a question without having to show their underlying work. In this case, it would allow a security researcher to prove that the vulnerability can be exploited without having to show a proof of concept exploit that might provide a road map to bad actors.

Josh Baron, program manager for DARPA’s Securing Information for Encrypted Verification and Evaluation program, or SIEVE, told SC Media that such proofs have historically had very limited application. Researchers have known since the 1980s that it is theoretically possible to develop a zero-knowledge proof for nearly any interactive exchange you can think of, but it’s only been recently since the cryptocurrency revolution that a number of more practical methods came into focus.

In fact, Baron credited the cryptocurrency community’s work on developing more efficient zero knowledge proofs, particularly a paper called “Snarks for C,” with helping to inspire DARPA researchers to explore ideas for similar applications in other fields that aren’t necessarily wedded to the blockchain.

“You take a problem in the real world, you formalize it mathematically, you figure out how to transform it into the relevant format…and then you give the zero-knowledge proof,” explained Baron.

This is how it works: Imagine a graph with a number of different points. There are lines between each and each point is assigned a color: red, yellow or green. The question at hand is whether you can conclusively prove to someone that each point is a different color from its adjacent points, without actually showing them the graph.

The answer is yes. It’s possible to translate much of the relevant information about those points, their colors and their relation to each other into numerical values or equations that can be calculated without ever viewing the original graph. This same fundamental model can be expanded and applied to many other situations, usually involving a lot more “points” or relevant variables that interact with each other in predictable ways – like different parts of a software system – in order to emulate the same mathematical certainties.

“I could describe software as a Boolean circuit, the output of that circuit is either zero or one,” said Baron. “Imagine if I have a useful exploit of that system and if so, the output of the circuit is one, otherwise it’s zero. What I’m actually proving is that I have such an input without revealing what that input actually is.”

The real-world problem DARPA was looking to tackle in this case is finding a way for security researchers to alert the public of an ongoing software vulnerability without having to rely on the host organization’s good will or risk tipping off malicious hackers. Last year, DARPA put out a call for outside research proposals and two companies – Galois and Trail of Bits – have already used the framework to create zero knowledge proofs of their own.

Galois was able to develop a proof for a previously disclosed memory safety vulnerability in a Game Boy Advance console. More importantly, they were able to use that proof to convince another party of the vulnerability’s existence in about eight minutes. Trail of Bits developed a novel model based on Boolean circuitry that allows researchers to create a binary imitation of systems at the architectural level – essentially providing a yes/no answer as to whether it’s been exploited or compromised by stack and heap overflows, code injection, format string vulnerabilities and memory bypass flaws.

Right now, these use cases are just scratching the surface, limited to a small handful of basic IT hardware products and software vulnerabilities. There are also questions about how accurate any one particular model may be to its real life counterpart. Developing better models that apply to the vulnerability process more generally will require “orders of magnitude more complexity,” but DARPA believes it’s only a matter of time before they can be adopted much more widely, both in the vulnerability disclosure process and in other areas of research.

The biggest obstacle to more widespread adoption is not in the technical details. It’s figuring out a way to translate the complex mathematical process and jargon behind such proofs in a way that doesn’t require an advanced mathematics degree to understand. After all, it does no good to go through all the work of developing an accurate zero-knowledge proof if the person or organization you’re trying to convince doesn’t know what that is, or why it means they have to believe you. Baron said the most common reaction he gets when describing this project to laypeople is extreme skepticism that it’s even scientifically possible.

“We need to get people to understand what the heck it is we’re doing in the first place,” he said. “They have to see that math proof and be comfortable with that, even once the tech is good there’s going to be a discussion of getting people’s head around what it is we can do.”

Derek B. Johnson

Derek is a senior editor and reporter at SC Media, where he has spent the past three years providing award-winning coverage of cybersecurity news across the public and private sectors. Prior to that, he was a senior reporter covering cybersecurity policy at Federal Computer Week. Derek has a bachelor’s degree in print journalism from Hofstra University in New York and a master’s degree in public policy from George Mason University in Virginia.

Get daily email updates

SC Media's daily must-read of the most current and pressing daily news

By clicking the Subscribe button below, you agree to SC Media Terms and Conditions and Privacy Policy.