locked phone (Wright Studio/Shutterstock.com)

Crypto crumpling could solve the encryption conundrum

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.”

About the Author

Patrick Marshall is a freelance technology writer for GCN.

inside gcn

  • When cybersecurity capabilities are paid for, but untapped

Reader Comments

Mon, Apr 9, 2018

How are the puzzles solved? Security has to be against other states. For example, China has equivalent or at this time faster super computers that would allow them to access encrypted data. It sounds like the idea is good for preventing small criminal groups only.

Thu, Apr 5, 2018 Charles Smith Richmond VA

Tried before in the 1990s - result was the DROWN attacks against websites. About 33% of all secured web sites were vulnerable to the DROWN attack. Dumb idea that has failed before.

Please post your comments here. Comments are moderated, so they may not appear immediately after submitting. We will not post comments that we consider abusive or off-topic.

Please type the letters/numbers you see above

More from 1105 Public Sector Media Group