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

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. 
Microsoft President: Governments Must Cooperate on Cybersecurity
Kelly Sheridan, Staff Editor, Dark Reading,  11/8/2018
To Click or Not to Click: The Answer Is Easy
Kowsik Guruswamy, Chief Technology Officer at Menlo Security,  11/14/2018
Veterans Find New Roles in Enterprise Cybersecurity
Kelly Sheridan, Staff Editor, Dark Reading,  11/12/2018
Register for Dark Reading Newsletters
White Papers
Video
Cartoon
Current Issue
Flash Poll
Online Malware and Threats: A Profile of Today's Security Posture
Online Malware and Threats: A Profile of Today's Security Posture
This report offers insight on how security professionals plan to invest in cybersecurity, and how they are prioritizing their resources. Find out what your peers have planned today!
Twitter Feed
Dark Reading - Bug Report
Bug Report
Enterprise Vulnerabilities
From DHS/US-CERT's National Vulnerability Database
CVE-2018-19279
PUBLISHED: 2018-11-14
PRIMX ZoneCentral before 6.1.2236 on Windows sometimes leaks the plaintext of NTFS files. On non-SSD devices, this is limited to a 5-second window and file sizes less than 600 bytes. The effect on SSD devices may be greater.
CVE-2018-19280
PUBLISHED: 2018-11-14
Centreon 3.4.x has XSS via the resource name or macro expression of a poller macro.
CVE-2018-19281
PUBLISHED: 2018-11-14
Centreon 3.4.x allows SNMP trap SQL Injection.
CVE-2018-17960
PUBLISHED: 2018-11-14
CKEditor 4.x before 4.11.0 allows user-assisted XSS involving a source-mode paste.
CVE-2018-19278
PUBLISHED: 2018-11-14
Buffer overflow in DNS SRV and NAPTR lookups in Digium Asterisk 15.x before 15.6.2 and 16.x before 16.0.1 allows remote attackers to crash Asterisk via a specially crafted DNS SRV or NAPTR response, because a buffer size is supposed to match an expanded length but actually matches a compressed lengt...