Randomness is a source of power. From the coin toss that decides which team gets the ball to the random keys that secure online interactions, randomness lets us make choices that are fair and impossible to predict.
But in many computing applications, suitable randomness can be hard to generate. So instead, programmers often rely on things called hash functions, which swirl data around and extract some small portion in a way that looks random. For decades, many computer scientists have presumed that for practical purposes, the outputs of good hash functions are generally indistinguishable from genuine randomness — an assumption they call the random oracle model.
“It’s hard to find today a cryptographic application… whose security analysis does not use this methodology,” said Ran Canetti of Boston University.
Now, a new paper has shaken that bedrock assumption. It demonstrates a method for tricking a commercially available proof system into certifying false statements, even though the system is demonstrably secure if you accept the random oracle model. Proof systems related to this one are essential for the blockchains that record cryptocurrency transactions, where they are used to certify computations performed by outside servers.
There’s “a lot of money relying on this stuff,” said Eylon Yogev of Bar-Ilan University in Israel. For blockchain proof protocols, “there’s a huge motivation for attackers to break the security of the system.”
In the new paper — by Dmitry Khovratovich of the Ethereum Foundation, Ron Rothblum of the zero-knowledge proof technology company Succinct and the Technion in Haifa, Israel, and Lev Soukhanov of the blockchain-focused start-up [[alloc] init] — the researchers are able to prove lies no matter which hash function is used to generate the “randomness” the proof system relies upon.
When Yogev heard about the team’s result, he said, “I had the feeling that someone is pulling the carpet from under my feet.” He and others have been working to patch up these vulnerabilities. But “it’s far from being a solved issue,” he said.
More broadly, the new result is forcing a reckoning about the random oracle model. “This is a time to rethink,” Canetti said.
A Mathematical Blender
A host of different computing applications — from cryptocurrencies to cloud computing — involve convincing a bunch of strangers on the internet that you’ve performed a computation correctly. The new paper shows how to hijack a fundamental technique that enables people to certify such computations. The technique, called the Fiat-Shamir transformation, is useful not just in blockchains and cloud computing but also in many other cryptographic applications, such as the key exchanges that safeguard web transactions and encrypt text messages. It’s so ubiquitous that it has become a verb, as in “Let’s Fiat-Shamir this.”
... continue reading