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

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. 
Mobile Banking Malware Up 50% in First Half of 2019
Kelly Sheridan, Staff Editor, Dark Reading,  1/17/2020
Exploits Released for As-Yet Unpatched Critical Citrix Flaw
Jai Vijayan, Contributing Writer,  1/13/2020
Microsoft to Officially End Support for Windows 7, Server 2008
Kelly Sheridan, Staff Editor, Dark Reading,  1/13/2020
Register for Dark Reading Newsletters
White Papers
Cartoon Contest
Write a Caption, Win a Starbucks Card! Click Here
Latest Comment: This comment is waiting for review by our moderators.
Current Issue
The Year in Security: 2019
This Tech Digest provides a wrap up and overview of the year's top cybersecurity news stories. It was a year of new twists on old threats, with fears of another WannaCry-type worm and of a possible botnet army of Wi-Fi routers. But 2019 also underscored the risk of firmware and trusted security tools harboring dangerous holes that cybercriminals and nation-state hackers could readily abuse. Read more.
Flash Poll
[Just Released] How Enterprises are Attacking the Cybersecurity Problem
[Just Released] How Enterprises are Attacking the Cybersecurity Problem
Organizations have invested in a sweeping array of security technologies to address challenges associated with the growing number of cybersecurity attacks. However, the complexity involved in managing these technologies is emerging as a major problem. Read this report to find out what your peers biggest security challenges are and the technologies they are using to address them.
Twitter Feed
Dark Reading - Bug Report
Bug Report
Enterprise Vulnerabilities
From DHS/US-CERT's National Vulnerability Database
PUBLISHED: 2020-01-18
Westermo MRD-315 1.7.3 and 1.7.4 devices have an information disclosure vulnerability that allows an authenticated remote attacker to retrieve the source code of different functions of the web application via requests that lack certain mandatory parameters. This affects ifaces-diag.asp, system.asp, ...
PUBLISHED: 2020-01-18
A memory usage vulnerability exists in Trend Micro Password Manager 3.8 that could allow an attacker with access and permissions to the victim's memory processes to extract sensitive information.
PUBLISHED: 2020-01-18
A RootCA vulnerability found in Trend Micro Password Manager for Windows and macOS exists where the localhost.key of RootCA.crt might be improperly accessed by an unauthorized party and could be used to create malicious self-signed SSL certificates, allowing an attacker to misdirect a user to phishi...
PUBLISHED: 2020-01-18
An arbitrary code execution vulnerability exists in the Trend Micro Security 2019 (v15) consumer family of products which could allow an attacker to gain elevated privileges and tamper with protected services by disabling or otherwise preventing them to start. An attacker must already have administr...
PUBLISHED: 2020-01-18
A Persistent Arbitrary Code Execution vulnerability exists in the Trend Micro Security 2020 (v160 and 2019 (v15) consumer familiy of products which could potentially allow an attacker the ability to create a malicious program to escalate privileges and attain persistence on a vulnerable system.