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.

Attacks/Breaches

3/19/2018
06:49 PM
Connect Directly
Twitter
LinkedIn
RSS
E-Mail
50%
50%

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
Comments
Newest First  |  Oldest First  |  Threaded View
ANON1242483132375
100%
0%
ANON1242483132375,
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. 
When It Comes To Security Tools, More Isn't More
Lamont Orange, Chief Information Security Officer at Netskope,  1/11/2021
US Capitol Attack a Wake-up Call for the Integration of Physical & IT Security
Seth Rosenblatt, Contributing Writer,  1/11/2021
Register for Dark Reading Newsletters
White Papers
Video
Cartoon
Current Issue
2020: The Year in Security
Download this Tech Digest for a look at the biggest security stories that - so far - have shaped a very strange and stressful year.
Flash Poll
Assessing Cybersecurity Risk in Today's Enterprises
Assessing Cybersecurity Risk in Today's Enterprises
COVID-19 has created a new IT paradigm in the enterprise -- and a new level of cybersecurity risk. This report offers a look at how enterprises are assessing and managing cyber-risk under the new normal.
Twitter Feed
Dark Reading - Bug Report
Bug Report
Enterprise Vulnerabilities
From DHS/US-CERT's National Vulnerability Database
CVE-2021-22166
PUBLISHED: 2021-01-15
An attacker could cause a Prometheus denial of service in GitLab 13.7+ by sending an HTTP request with a malformed method
CVE-2021-22167
PUBLISHED: 2021-01-15
An issue has been discovered in GitLab affecting all versions starting from 12.1. Incorrect headers in specific project page allows attacker to have a temporary read access to the private repository
CVE-2021-22168
PUBLISHED: 2021-01-15
A regular expression denial of service issue has been discovered in NuGet API affecting all versions of GitLab starting from version 12.8.
CVE-2021-22171
PUBLISHED: 2021-01-15
Insufficient validation of authentication parameters in GitLab Pages for GitLab 11.5+ allows an attacker to steal a victim's API token if they click on a maliciously crafted link
CVE-2020-26414
PUBLISHED: 2021-01-15
An issue has been discovered in GitLab affecting all versions starting from 12.4. The regex used for package names is written in a way that makes execution time have quadratic growth based on the length of the malicious input string.