Cryptographic crumpling: The encryption 'middle ground' for government surveillance

For governments worldwide, encryption is a thorn in the side in the quest for surveillance, cracking suspected criminal phones, and monitoring communication.

Officials are applying pressure on technology firms and app developers which provide end-to-end encryption services provide a way for police forces to break encryption.

However, the moment you provide a backdoor into such services, you are creating a weak point that not only law enforcement and governments can use -- assuming that tunneling into a handset and monitoring is even within legal bounds -- but threat actors, and undermining the security of encryption as a whole.

As the mass surveillance and data collection activities of the US National Security Agency hit the headlines, faith in governments and their ability to restrain such spying to genuine cases of criminality began to weaken.

Now, the use of encryption and secure communication channels is ever-more popular, technology firms are resisting efforts to implant deliberate weaknesses in encryption protocols, and neither side wants to budge.

What can be done? From the outset, something has got to give.

However, researchers from Boston University believe they may have come up with a solution.

On Monday, the team said they have developed a new encryption technique which will give authorities some access, but without providing unlimited access in practice, to communication.

In other words, a middle ground -- a way to break encryption to placate law enforcement, but not to the extent that mass surveillance on the general public is possible.

Mayank Varia, Research Associate Professor at Boston University and cryptography expert, has developed the new technique, known as cryptographic "crumpling."

In a paper documenting the research, lead author Varia says that the new cryptography methods could be used for "exceptional access" to encrypted data for government purposes while keeping user privacy at large at a reasonable level.

"Our approach places most of the responsibility for achieving exceptional access on the government, rather than on the users or developers of cryptographic tools," the paper notes. "As a result, our constructions are very simple and lightweight, and they can be easily retrofitted onto existing applications and protocols."

The crumpling techniques use two approaches -- the first being a Diffie-Hellman key exchange over modular arithmetic groups which leads to an "extremely expensive" puzzle which must be solved to break the protocol, and the second a "hash-based proof of work to impose a linear cost on the adversary for each message" to recover.

Crumpling requires strong, modern cryptography as a precondition as it allows per-message encryption keys and detailed management. The system requires this infrastructure so a small number of messages can be targeted without full-scale exposure.

The team says that this condition will also only permit "passive" decryption attempts, rather than man-in-the-middle (MiTM) attacks.

By introducing cryptographic puzzles into the generation of per-message cryptographic keys, the keys will be possible to decrypt but will require vast resources to do so. In addition, each puzzle will be chosen independently for each key, which means "the government must expend effort to solve each one."

"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 and the safety of its human users," the paper notes. "We design a portion of our puzzles to match Bitcoin's proof of work computation so that we can predict their real-world marginal cost with reasonable confidence."

To prevent unauthorized attempts to break encryption an "abrasion puzzle" serves as a gatekeeper which is more expensive to solve than individual key puzzles. While this would not necessarily deter state-sponsored threat actors, it may at least deter individual cyberattackers as the cost would not be worth the result.

The new technique would allow governments to recover the plaintext for targeted messages, however, it would also be prohibitively expensive.

A key length of 70 bits, for example -- with today's hardware -- would cost millions and force government agencies to choose their targets carefully and the expense would potentially prevent misuse.

The research team estimates that the government could recover less than 70 keys per year with a budget of close to $70 million dollars upfront -- one million dollars per message and the full amount set out in the US' expanded federal budget to break encryption.

However, there could also be additional costs of $1,000 to $1 million per message, and these kind of figures are difficult to conceal, especially as one message from a suspected criminal in a conversation without contextual data is unlikely to ever be enough to secure conviction.

The research team says that crumpling can be adapted for use in common encryption services including PGP, Signal, as well as full-disk and file-based encryption.

"We view this work as a catalyst that can inspire both the research community and the public at large to explore this space further," the researchers say. "Whether such a system will ever be (or should ever be) adopted depends less on technology and more on questions for society to answer collectively: whether to entrust the government with the power of targeted access and whether to accept the limitations on law enforcement possible with only targeted access."

The research was funded by the National Science Foundation.