Dark Reading is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them.Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


06:49 PM
Connect Directly

New Method Proposed for Secure Government Access to Encrypted Data

'Crumple Zones' in crypto mechanisms can make it possible - but astronomically expensive - to access encrypted data, say researchers from Boston University and Portland State University.

Security experts long have maintained that providing any kind of backdoor access to encrypted data as governments everywhere have been demanding is not possible without seriously undermining the overall security provided by encryption mechanisms.

Now a pair of researchers from Boston University and Portland State University has developed a first-of-its kind cryptographic technique that they say provides something of a middle ground.

At its core is the notion of a sort of "crumple zone" in cryptographic mechanisms that make it possible - but extremely expensive - for someone to recover keys for decrypting targeted communications, the two researchers said in a paper to be presented at an IEEE symposium next month.

"The idea is that, like a crumple zone in automotive engineering, in an emergency situation the construction should break a little bit in order to protect the integrity of the system as a whole," said Charles Wright, assistant professor of computer science at Portland State and Mayank Varia, a research scientist at Boston University.

Far from compromising security, the technique works best when used with the strongest encryption mechanisms.

And in contrast to previous work on this topic, such as key escrow, the crumple zone approach places the responsibility for achieving exceptional access to encrypted data solely on those who want that access.

Software developers and other entities will have to do very little to accommodate the new technique, which can be retrofitted quite easily into existing applications and protocols, the two researchers said.

In essence, the idea proposed by Wright and Varia is to embed two moderately hard-to-solve puzzles into each of the so-called ephemeral keys that are used by applications to encrypt messages.

One of the puzzles, which the researchers have dubbed the "crumpling puzzle," is chosen independently for each ephemeral key, and solving the puzzle results in message recovery. The other puzzle, dubbed the "abrasion puzzle," is much harder to solve and serves as a gatekeeper to the crumpling puzzle. Only by solving the second puzzle can someone can get to the first puzzle.

"An ephemeral key is one that only lasts for an instant," says Wright. "It is generated, then it's used to encrypt/decrypt one — or maybe a few — messages message typically using a symmetric cipher like AES, and then it's discarded."

A new key is generated for each message that needs to be encrypted.

With crumpling, each ephemeral key is carefully weakened, thereby making it recoverable, but only through expensive brute-force techniques. The original key that the application would normally use as the encryption key is itself used to generate a weaker "crumpled" key, which is then used to perform the actual encryption.

"In practice, using crumpling by itself would be dangerous because it allows anybody to recover the key for a message, as long as they're willing to pay the price for just that one brute-force search," Wright says.

But by integrating the much more expensive to solve abrasion puzzle into the crumpling algorithm, recovering the crumpled key is only possible for someone that has solved the bigger puzzle. "In a nutshell, crumpling is a way to make each ephemeral key breakable. Abrasion is a way to limit who can break the crumpled keys," Wright says.

According to Wright and Varia, the crumpled zone approach enables targeted access to encrypted data while ensuring that large-scale surveillance is prohibitively expensive—at least for the moment. It does not impose any new burdens on encryption providers, and introduces very little by way of new system complexity. The method also only enables passive breaches of confidentiality, meaning an attacker wouldn't be able to manipulate anything or change any encrypted data.

Importantly, it shifts the entire onus for gaining targeted access directly to the government.

Special Hardware

Any entity that wants access to data encrypted via the crumpling method would need two kinds of specialized processing hardware - amounting in total to probably several thousand devices, Wright says.

First, they would need specialized processors for accelerating the processing of algorithms for solving the big "gatekeeper" puzzle.

"There is some cost for designing and fabricating the hardware, and also for powering the computation itself," Wright says. Based on previous research, Wright says the cost of building out the infrastructure for cracking the gatekeeper puzzle could easily go up to between $150 million to $2 billion.

They would also need special processors for doing the brute-force search to recover each crumpled key. "We purposefully designed the crumpling algorithm so that these processors would be a lot like today's Bitcoin miners," he says. The cost, in terms of power, needed to recover a single key could theoretically be astronomical.

"More realistically, we think useful values are probably in the range from $1K up to $1M, which correspond roughly to effective key lengths of 60-70 bits," Wright notes.

To ensure that the costs to recover keys remains high as computation grows cheaper, the security parameters of crumpled keys will need to be updated at regular intervals, he says.

Encrypted messages that are prohibitively expensive to decrypt right now could become a lot less expensive to crack as computing costs get lower.

"Assuming that Moore's Law holds up over time, then the cost to recover a crumpled key should decay by 1/2 about every 18 months or so," he says. So a message that costs $1 million to decrypt today will cost just $1,000 in 15 years.

"If you have information that you need to keep secret for a long time, then you need to use a much stronger key today," Wright says.

For example, by setting the price of cracking the "gatekeeper" puzzle at $2 billion today, in 15 years it should still cost about $2 million. "That's within the range of what a corporation or a smaller government could afford, but it's still a substantial price to pay for access to 15-year-old messages," he notes.  

Wright and Varia have not sought feedback on their proposed cryptographic technique from government or law enforcement agencies as yet. The focus for the moment is on getting feedback from the scientific and tech community.

And it may take several years before the community can design a scheme that is safe for real-world use, Wright says.

"This is partly why we're not recommending that anyone deploy our constructions as-is in the immediate future, unless it's the only way to avoid an even riskier outcome like a total ban on encryption," Wright noted.

Related Content:


Interop ITX 2018

Join Dark Reading LIVE for two cybersecurity summits at Interop ITX. Learn from the industry’s most knowledgeable IT security experts. Check out the security track here.

Jai Vijayan is a seasoned technology reporter with over 20 years of experience in IT trade journalism. He was most recently a Senior Editor at Computerworld, where he covered information security and data privacy issues for the publication. Over the course of his 20-year ... View Full Bio

Recommended Reading:

Comment  | 
Print  | 
More Insights
Newest First  |  Oldest First  |  Threaded View
User Rank: Apprentice
3/20/2018 | 9:26:21 AM
Crumple zones?
What a great concept in concept but unfathomable when there are no sustainable zones between intangible value. 
COVID-19: Latest Security News & Commentary
Dark Reading Staff 7/14/2020
Omdia Research Launches Page on Dark Reading
Tim Wilson, Editor in Chief, Dark Reading 7/9/2020
Register for Dark Reading Newsletters
White Papers
Current Issue
Special Report: Computing's New Normal, a Dark Reading Perspective
This special report examines how IT security organizations have adapted to the "new normal" of computing and what the long-term effects will be. Read it and get a unique set of perspectives on issues ranging from new threats & vulnerabilities as a result of remote working to how enterprise security strategy will be affected long term.
Flash Poll
The Threat from the Internetand What Your Organization Can Do About It
The Threat from the Internetand What Your Organization Can Do About It
This report describes some of the latest attacks and threats emanating from the Internet, as well as advice and tips on how your organization can mitigate those threats before they affect your business. Download it today!
Twitter Feed
Dark Reading - Bug Report
Bug Report
Enterprise Vulnerabilities
From DHS/US-CERT's National Vulnerability Database
PUBLISHED: 2020-07-15
The IRC5 family with UAS service enabled comes by default with credentials that can be found on publicly available manuals. ABB considers this a well documented functionality that helps customer set up however, out of our research, we found multiple production systems running these exact default cre...
PUBLISHED: 2020-07-15
IRC5 exposes an ftp server (port 21). Upon attempting to gain access you are challenged with a request of username and password, however you can input whatever you like. As long as the field isn't empty it will be accepted.
PUBLISHED: 2020-07-15
An issue was discovered in drivers/acpi/acpi_configfs.c in the Linux kernel before 5.7.7. Injection of malicious ACPI tables via configfs could be used by attackers to bypass lockdown and secure boot restrictions, aka CID-75b0cea7bf30.
PUBLISHED: 2020-07-15
In Eclipse OpenJ9 prior to version 0.21 on Power platforms, calling the System.arraycopy method with a length longer than the length of the source or destination array can, in certain specially crafted code patterns, cause the current method to return prematurely with an undefined return value. This...
PUBLISHED: 2020-07-15
An issue was discovered in drivers/firmware/efi/efi.c in the Linux kernel before 5.4. Incorrect access permissions for the efivar_ssdt ACPI variable could be used by attackers to bypass lockdown or secure boot restrictions, aka CID-1957a85b0032.