Keys Under The Mat: NOBUS, Key Escrow, or a Crumple Zone?

Keys Under The Mat: NOBUS, Key Escrow, or a Crumple Zone?

Breaking Cryto

Earlier this week, senior administration officials met to debate the usage of end-to-end of encryption. But there’s great tension in the debate, as a mandated back-door could open the Internet up to large scale threats. On one side we have the Department of Justice and the FBI — who want a backdoor — and on the other we have the Commerce and State Departments — who define the risks involved for secrets at every level.

This is part of one of the great debates of the 21st Century on whether we need strong cryptography, or methods which can be by law enforcement. In previous proposals, the only acceptable methods which would allow law enforcement to crack crypto is to implement:

• A NOBUS (‘nobody but us’) backdoor, which will be mathematically possible for government agents to crack the encryption but no-one else.
• Key escrow. This is where a copy of the encryption key is kept in escrow so that it can be used by a government agent.
• Crumble zones. While many governments and law enforcement agencies have called for backdoors in encryption, researchers at Boston University recently defined a backdoor method that would allow governments to decrypt secret communications. It uses a crumple zone method and where it is extremely costly to recover keys. The cost is set so that those with the money to crack on a small scale basis— eg homeland defence — but where it will be too expensive for them to perform mass surveillance.

Crumple zones

The method is likened to crumple zones in cars and where it is possible to create a method which breaks a little bit but does not compromise the security of the entity. Overall it allows for exceptional access when required, and for only for those with the correct access rights. there are two hard puzzles integrated into the encrypted content and for each of the ephemeral keys. The first puzzle — the crumpling puzzle — is used for each ephemeral key and which releases the decrypted message. With the second puzzle — the abrasion puzzle — is more difficult and must to solved in order to get access to the first puzzle.

The ephemeral key is only used for one message and is intentionally weak, and only recoverable using brute-force methods (and which will be expensive to implement). Overall the original key will be taken and then used to create the weaker key. The expensive of the brute force method for the puzzles would mean that it would not be possible to implement large-scale surveillance, but where just certain encrypted messages could be cracked.

Normally a large-scale GPU infrastructure would be required to crack the encrypted messages. For the crumple method, it is likely that it would involve an investment of between $150 million and $2 billion. For key sizes of a strength of 60–70 bits, it would require an investment of between $1,000 up to $1million. Assuming improvements in computing power — such as using Moore’s Law — a current cost of $1 million, becomes $1,000 in 15 years.

Keys Under Doormats

So let’s look at the issues from a technical point-of-view, and see what some of the leading cryptography professionals see as the right way forward. For this we need to examine the “Keys Under Doormats” paper (here):

It is a paper written by the people that know cryptography best … including Rivest, Bruce Schneier, and Whitfield Diffie. I appreciate that politicians often care little for the viewpoint of scientists and engineers when making important decisions, as their desiccation are made on political judgements rather than scientific ones, but, hopefully, this paper can create a strong foundation for the debate to happen.

The grouping delivered their viewpoint on the last debate around the subject (1997), and really things have moved on so much with the Internet since then. It is now a part of our lives in a way that could ever be seen. They take a beautifully crafted approach to the importance of the computer security in an opening statement:

In the wake of the growing economic and social cost of the fundamental in security of today’s Internet environment, any proposals that alter the security dynamics online should be approached with caution.

The word caution is left to the end of the sentence but is the word that perhaps should be underlined several times. To break the current Internet in any way could have a major impact on our lives.

They highlight that flaws in software are often the way that investigators manage to get access to restricted data, but go on to say that any intentional infrastructure for backdoor access would bring many problems in how the system would be governed on a global level. Who would have the overarching rights to define backdoor entry, and what would happen if their keys were breached?

Escrow keys

One method that could be used is for everything that is encrypted, must have a copy of the key which law enforcement would use if they required access to the data — an escrow key. This escrow key is a bit like leaving your key under the doormat — as the paper defines in its title. The classic use case of used is with the Clipper Chip, where anyone who wanted to encrypt would gain a licence from law enforcement, and gain a chip to perform the encryption, and where a copy of the chip was kept in case access was required — Government key escrow.

Eventually, in 1997, the Clipper Chip project (Figure 2) was abandoned as it was too difficult to enforce and would have been costly, and was applied to a narrower set of applications, such as in regulated telecommunications systems. Along with the enforcement issue, there was also great risks of the keys becoming exposed (such as from an insider attack — see Figure 1). The authors of the paper even doubt that social media platforms such as Facebook and Twitter could have even be created within a regulated environment.

Figure 1: Government escrow

Figure 2: The Clipper Chip

Exceptional access

The paper has a special focus on “exceptional access”, where keys would have to be stored after have been used. In most cases, such as in a secure tunnel, a session key is used and then is deleted after the tunnel has been created. The storage of used keys would create an extremely complex infrastructure, and again which could be compromised for malicious activities. The storage of the keys would thus be a target for intruders, who could record secure conversations and then gain access to the session key at a later time. The authors highlight the recent problems within the US Government Office of Personnel Management (OPM) as the kind of thing that could happen.

As with the access to a key escrow service, the implementation of a into social media also leaves open the opportunity for it to be abused by malicious agents, such as where Chinese agents backed into Google’s data of surveillance targets.

Spanning the world … who has exceptional access?

The major issue of creating exceptional access relates to the different jurisdictions involved, as malicious agents could simply move their communications to other areas in the World, where exceptional access was not implemented. Along with this, who’s exceptional access would the system use. A software company in the UK would possibly implement exceptional access for UK law enforcement, but if this software was operating in China, would it also have to allow exceptional access for Chinese law enforcement? With many standing for an open access, including the UK and US governments, it would seem a backward step to move to a restricted infrastructure.

Opening every door in the World

Of particular worry to the authors is the insider (or trusted employee) threat, where the keys used either by an escrow system or for third-party encryption, could be breached, and cause large-scale data loss. Their viewpoint is that the complexity of creating an escrow system which would scale across all the different agencies and data infrastructures involved would be well beyond current technology. Fraud and extortion could also result, along with the complexity of the coding involved for software vendors. The authors cite the loss of the RSA/EMC seed keys as an example of how a breach of keys can cause serious data loss issues, and that critical infrastructure could come under attack from malicious external agents. The theft is IP is also a major concern if strong encryption is not used.

Scenario 1: Secure Tunnels and Escrow

The authors present the scenario of law enforcement being able to view encrypted data. Normally, with secure communications, both public and private key are used. The encryption that happens in the secure tunnel is normally achieved with symmetric encryption (such as with AES or 3DES) and the key that will be used for the communication is protected using public key encryption.

With SSL/TLS, the server sends its public key to the client (normally in the form of a digital certificate), and the client creates a new symmetric key and encrypts it with the server’s public key and sends it back. The server then decrypts the encrypted key and reveals the session key to be used. Once this has happened both sides have the same symmetric encryption key (Figure 3).

Figure 3: Normal setup of a secure tunnel

The authors outline an approach where the symmetric key is encrypted a second time with a special escrow public key. Then we now have a single encryption process on the data, but both the server and law enforcement can read the stream.

As we see in Figure 4, the public key from law enforcement is added to encrypt the session key and both are sent back to the server. Then a law enforcement agent can listen to the handshaking information and use their private key (which is secret) to reveal the session key — which can then be kept in escrow (or used to decrypt the communications).

The authors outline that the double encryption of the session key is possible, but there are risks in the loss of the private key, and also in storing the session key, and where all the data that was encrypted by that key would be compromised if lost. Their main issue with this type of system is who would actually control additional encryption. In the US, it may be the FBI, but when happens when you have cross-border communications? They speculate of the communications between the US and China, would both countries have to agree to a single escrow agent?

Figure 4: Double key creation

Scenario 2: Encryption-by-default

Apart from secure tunnels, the other area that worries law enforcement is encryption-by-default, typical on mobile devices. On most systems, the encryption key kept in escrow (typically on a domain server), so it is not too difficult to determine the key. the encryption key is stored in the TPM chip, and can only be revealed with a password or fingerprint. Normally there is a lock-out time, or even a slow-down time when brute-force is applied to the pass-phrase, which make it difficult to crack. In this scenario, again the authors propose that the solution is to provide keys which are either provided by law enforcement or are key in escrow. Again both methods are at risk of a breach of the escrow keys and from insider threats. The complexity of different nations states also would make it extremely complex for vendors.

Conclusions

Make your own mind up, as to whether we improve our existing methods. Personally, I have little time for weakening cryptography. There is no magic wand for only the good people to us. Break it, and you could be breaking it for all.