Crypto crumpling could solve the encryption conundrum
- By Patrick Marshall
- Apr 04, 2018
The battle between the federal government and tech companies over encryption heated up again recently when the Trump administration renewed a push to require companies to provide a “back door” into encrypted devices and applications.
The problem with providing such a back door, according to tech companies, is that it introduces a vulnerability that can be exploited by bad actors or used for widespread surveillance. There's no way to grant access to some without opening access to all, they argue.
Researchers from Boston University and Portland State University, however, may have come up with a way to maximize user security but still give authorities a way to gain "exceptional access" for special circumstances. The team, led by Mayank Varia, research associate professor of computer science at BU, developed an encryption technique that is meant to be “broken,” though at a cost intended to put it out of the reach of cyber criminals.
“Cryptographic crumpling” requires an unauthorized user -- presumably a federal or law enforcement agency -- to solve two cryptographic puzzles before being able to decrypt a message. The first, or “gatekeeper,” puzzle is the most difficult and expensive -- to solve. According to the researchers, solving this puzzle with brute force could cost anywhere from 100 million to several billion dollars.
Once that first puzzle is solved, the unauthorized user will still have to solve a second, per-message hash-based puzzle that costs between $1,000 to $1 million for each decrypted message.
This cryptographic crumpling essentially shifts the responsibility for exceptional access to the authority that wants in, rather than depending on the user, the device or the encryption software to protect the contents.
“Our proposal is more or less that the gatekeeper puzzle is something we would recommend changing relatively infrequently, maybe on the order of once every year or two years,” Varia said. “We want the puzzles to be solvable by only the law enforcement and nation-state organizations today, yet still not solvable by other types of organizations even a few years into the future.”
“Normally, when we build things we want to make it is secure as we possibly can,” said Charles Wright, assistant professor of computer science at Portland State University. “In this work, we are trying to find a sort of middle ground between that approach and governments that want access.”
So what would convince tech companies to adopt crypto crumpling? “I think that's the key question going forward,” Wright said. Tech companies would likely oppose legislation requiring it, he said, because it would “come with a whole host of difficulties and costs, especially because the technology moves so fast.” However, there may be reasons of self-interest why those companies might voluntarily adopt the technology.
“Companies need some way to avert an even riskier type of legal mandate,” Wright said. “They might use this as a way to give the [government] a way to get messages that they require while still giving everyone else reasonable security.”
Patrick Marshall is a freelance technology writer for GCN.