Ding, ding, seconds out: It’s Law v Math

Ding, ding, seconds out: It’s Law v Math

And so Australia will be pitting its legal systems against the laws of mathematics with a new bill to be put forward in the Spring of 2019.

Augus Taylor, the Minister for Law Enforcement and Cyber Security, recently outlined:

(We want to) implement measures to address the impact of encrypted communications and devices on national security and law enforcement investigations. The bill provides a framework for agencies to work with the private sector so that law enforcement can adapt to the increasingly complex online environment. The bill requires both domestic and foreign companies supplying services to Australia to provide greater assistance to agencies.

And so if you read this statement you wonder where the magical potion is going to come from? Will it be a special maths function that no-one, but law enforcement, will know about, or will it be an evil root kit?

Basically the Australian government wants to create a back door on devices and networks, but not allow others in. If someone knows how to do this, they should publish the method as the “good guy algorithm”.

The focus is likely to be on either breaking encrypted tunnels with a man-in-the-middle attack, or for the service providers to copy the encryption key used with secure communications. But most encryption keys are now generated by either end of the connection and cannot be determined by intermediate devices. With end-to-end encryption only the end nodes will have the key, and these will be unique for each session. Once the communication is finished, there is then no trace of the key used.

In a debate over encryption, the Prime Minister (Malcolm Turnbull) defined that, in his country, that mathematics comes in second place to law.

Within new laws, his government will thus force social media and cloud service providers to hand-over encrypted messages.

When asked how this could be achieved, he said:

“Well the laws of Australia prevail in Australia, I can assure you of that. The laws of mathematics are very commendable, but the only law that applies in Australia is the law of Australia

He then went on to say that cryptographers were the problem, and that we needed them to face up to their responsibilities, and that they just can’t wash their hands of it.

Following the UK?

It is likely that the new proposals in Australia will be developed based on the UK’s Investigatory Powers Act (IPA), and where service providers must decrypt secret communications. But, even in the UK, the powers are not able to magically open up encrypted content, or provide a man-in-the-middle.

While the intentions are there to break encryption, the chances of this happening in a world which is moving towards end-to-end encryption is reducing by the day. Only intentional backdoors in code would give governments the control they require, and thus give exceptional access to data. Industry leaders worry that user trust would crumble if they knew that their secret communications were being spied upon.

The UK, though, has been back peddling over the act since it was released, as it doesn’t quite fit into general nature of GDPR. At the time of the enactment of IPA, there was little support in the UK from industry, but that did not stop Amber Rudd, the previous UK Home Secretary, from defining that encryption was“completely unacceptable”, and that “no-one really wanted end-to-end encryption”.

Few people in the know actually support it …

Last year, as the UK Home Secretary outlined her plans around restrictions on end-to-end encryption, I was called by the BBC about back-doors in cryptography. As it is a subject I know well, and had even presented to a select committee in the House of Commons [here], I said I would be interested in debating the issue. They then they asked if I could put forward the concept of backdoors in encryption, and I said:

I can’t do that!

and they said, “Well, we are really struggling to get someone to put that point, couldn’t you just outline the advantages and how it would be possible?”, and I said, “Well, most people with any technical knowledge knows that it is a bad thing, and to provide an academic point-of-view I would have to be critical of it. In fact if I put forward the concept of backdoors in cryptography, I would have no credibility in my field”, and the conversation finished and they didn’t invite me on. Basically I was there to back-up a politician who was on the show.

Seemingly they had a whole lot of people who were keen to tell the world that backdoors in crypto were a very bad thing, and were struggling to find anyone, outside the political world, who would see any sense in breaking the core of Internet security.

Ding, ding, the contenders

So, let’s have a look at some of the contenders … but before this let’s look at a recently published paper. For this we need to examine the “Keys Under Doormats” paper (here):

It is a paper written by the people who know cryptography best … Rivest, Bruce Schneier, Whitfield Diffie, and the people who built the core methods used on the Internet. I appreciate that politicians increasingly care little for the viewpoint of scientists and engineers when making important decisions, but, hopefully, this paper can create a strong foundation to inform the debate.

The grouping delivered their viewpoint on the last debate around the subject (1997), but 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 the 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 would 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?

Crumple zones

This method was recently defined by researchers and 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 thus 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 expensiveness 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.

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, and 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 by 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.

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 like 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.

Scenarios

Let’s have a look at the scenarios defined in the “Keys Under Doormats” paper.

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.

Unfortunately both methods are at risk of a breach of the escrow keys and from insider threats. The complexity of having different nations states involved would also make it extremely complex for vendors.

Conclusions

Politicians still see their borders as strong and where they can put up barriers for what comes into and leaves their country. Not anymore! The Internet does not respect borders. While breaking encrypted communications is possible, it would open up so many problems, and would probably not fix any of them. Users, in general, don’t want to be spied upon, and need to feel secure.

A breach by an insider within one of the major social media and cloud service companies, would end up being the largest data breach ever … where every single word recorded within communications would be open to the world!

While the risks to our society are great, there is, possibly, an even greater risk to our citizens for their privacy. If you ask Phil Zimmerman (creator of PGP), he thinks that law enforcement agencies have never had it so good and that the step to breaking encryption would just be one step too far. So in a world when I can’t even tell if the person who has just send me an email is that person, if anything, we need to move towards building a completely trusted infrastructure built on cryptography.

For cryptographers washing their hands of the issue … I can’t see that!

So let’s pose a few questions:

• Could a country ban the usage of a given mathematical equation, unless it was registered with them and restrict with a government licence?
• Could it be illegal to use the formula: “C = gˣ Mod N”?
• Could it be illegal to use large prime numbers without registration?