Encryption With A Back Door Is NOT Encryption

There’s been an increasing call in recent weeks and months for encryption to have government ‘backdoors’ put into them. This is a bad idea. No really, it’s an incredibly bad idea. Even if we took the assumption that it is a push that’s made with only the purest of intentions, and the government universal key is kept 100% safe and secure and never leaked or misused, it’s still a really, unbelievably, stupid idea.

I gave a talk on this back in September 2019 at Dragon Con on this topic, you can watch it here.

If you don’t want to watch that, or want it in specifics, then here’s why:

Caution, there may be some maths here, but it’s not really hard maths, nothing beyond what you should have done at school aged 14 anyway. Where possible things have been kept simple for ease of understanding.

In December 2018 Australia passed a law called the Telecommunications and Other Legislation Amendment (Assistance and Access) Act 2018. Amongst other things, it mandated including backdoors into technology, mainly to overcome encryption, so as to ‘aid law enforcement’ by handing over data when requested. 

In July 2019, US Attorney General Bill Barr upped that by “asking” tech companies to provide access to encrypted messages, and if they don’t, he may look into forcing it sayingObviously, the Department would like to engage with the private sector in exploring solutions that will provide lawful access. While we remain open to a cooperative approach, the time to achieve that may be limited.

Most recently (March 4 2020), the Director of the FBI has also been pushing weakened encryption.

Here’s the thing though — any backdoor put into encryption makes it no longer encryption. 

There are many ways to encrypt, from the simplest Caeser Cypher (where you shift the letters along the alphabet, the most common being ROT13) to SHA256 or RC5–4096 used where security is essential. And they all have one thing in common, and that’s one decryption key to get the right answer.

When you add a second key, you halve the effectiveness of the cypher. With a Caeser its no longer 1 right and 25 wrong, it’s 2 right and 24 wrong, and so it’s 1/13 and not 1/26.

Sure, with a Caeser cipher, that’s not a big deal, you can manually check them in a few moments anyway. but others have far bigger key-spaces (that’s possible number of keys) like RC5–64, which has 18,446,744,073,709,552,000 possible keys (that’s 2 to the power of 64, or 2⁶⁴ — hence the term 64-bit key)

in 1998, the distributed.net project group did a brute force attack on RC5-64. After almost 57 months, at an average rate of 102 billion keys every second, they found a key that decrypted it, after going through 82.7% of all the keys. At that point (2002) they switched to RC5-72 and have been crunching it since, at an average rate of 555 billion keys per second (an actual rate of 1,500 billion/second) but have only covered 6.3% (because there’s 4,722,366,482,869,645,213,696 keys, 256 times larger, or 2⁸ — which is the difference between 2⁶⁴ and 2⁷², or another way, 4,722 billion billion).

These aren’t even the complex encryption in use most of the time, but simpler, outdated ones now mainly used to make a point..

 More complex keys take more time to work obviously, which is why governments want backdoors. Sure you can use supercomputers, but who wants to spend 6 very expensive months on a limited resource each time, especially for an unknown payout? So backdoors are the only way to realistically do it.

Lets simplify things a bit, and go to a 50 year old board game called ‘Mastermind’. It’s one most people are familiar with, where one person selects 4 balls/pegs of different colours and hides them in an order. Then the other person has 10 attempts to guess the sequence, being given pegs that tell only if the code has the right colour in the right place, or the right colour but in the wrong place (but not which one it is). Here’s a video explanation

As with all things, we can transpose this into either letters or numbers (each colour given its own) so the sequence “Green Red, Yellow, Blue” could be 1354 or CABE or whatever you assign each colour to be. So, a fun game? Yes, for a logical battle.

Now, how fun would this game be if it was scored by a computer, and that the sequence “Green Blue White Yellow” would always be recognized as a winning guess — in effect a backdoor to the game. Well, there’d be no point in playing, would there? In effect, the game no longer is a game, because there’s nothing to guess, and no point keeping the code hidden. At least while people know it’s the backdoor code, so as long as it’s just single player games against a computer, and it doesn’t show the code, people may assume the backdoor code was the real code. it’s only when it works every time that people will suspect. Unless someone spills the beans anyway.

You can do the same thing with locks. Keys are just piece of metal with bits cut into them. And yes, again you can represent those keys as codes in letters or numbers. Assign each possible depth a letter or number, and so a key with 5 positions (generally called ‘pins’ in most locks) each with 10 depths would have 10⁵ combinations (10x10x10x10x10) which could be represented by 00000 to 99999 (this is a simplified ‘for example’). Yes, physical keys are just like the game of Mastermind above.

Here’s a key, then made into an outline, then its 7 pits marked with its 7 layers, for a L-R code of 2147416

Now no key will use 0000000 or 9999999 (or indeed any of the other 8 identical number keys, as they’d just be a straight bar) but lets say the key is 2541876. If we have a (theoretically perfect) lock that we can’t pick, but have to make a key for, that’s a lot of combinations. So you’d feel it’s pretty secure, unless someone else has a key that matches yours. However, what if there was also a ‘master key’ to that lock, a skeleton key that will unlock all of those locks no matter what the key is? In other words, A backdoor to the lock.

Such locks do exist. In fact, every single lock with this symbol has a backdoor key. 

TSA’s Travel Sentry logo

This is the Travel Sentry logo, and it appears on locks that you’re permitted to use on luggage in the US (“TSA approved”). What the logo means is that the TSA has a master key to open that lock. If you use one without that logo, they’ll just cut the lock off.

So, the logo means your stuff will be safe, right? The TSA will be the only ones with the key, so no-one but TSA agents can open the lock at will? Kinda, yeah… right up until they didn’t.

It started with a fairly innocent look (or so it felt) at the master keys, in a piece about TSA baggage handling in the Washington Post, which gave people enough answers to work on keys.

Now you can download models of the keys to print at home. That means that most such locks, are no more effective than using a twist-tie to keep the zips together, as this video by the lockpick lawyer shows.

So there we have an example of a backdoor key being leaked, and rendering the lock useless. And it’s the same with software, on a much larger scale.

This backdoor was exposed by a seemingly innocuous photograph, but it wouldn’t have changed the end result if a TSA employee had been paid so that someone could make a copy of his keys. Or if someone had just bought a few locks, and broken them open (more on that method in a few).

The simplest way to bypass encryption (or a lock) is to brute-force it. That is, you try every single combination out there, and eventually, you’ll hit the right one. That’s what distributed.net did. It took them a long time, but that’s because it’s somewhat more complex than most.

And that’s the problem the DOJ, and Australian authorities have. The only way to get to encrypted data is one of two ways

  • Either have the encryption itself be made with two decryption keys, one fixed, or
  • Have the software doing the encryption store the decryption key, and decrypt on an external command

Both have the same issues.

The main one is the same as the locks above — any key that’s common will be found to be common at some point. At that point, the encryption is no more, because everyone can decrypt it, much as the TSA locks aren’t locks, they’re fancy metal zipper-ties.

Now, assuming you keep everything secret about this backdoor key, it’s going to run into one big problem — brute force attacking.

Let me give you an example. My own site is a WordPress site, which means it has an encryption element. That encryption element is in its user control — usernames and passwords. WordPress is popular — W3Techs reports that 35% of all websites are using WordPress (62% of all content-management based sites) because it’s easy and flexible, able to handle all kinds of different setups. I use it for my own personal site (ktetch.co.uk) and it’s also the basis of TorrentFreak.com; most Pirate Parties use a version of it, as do some big companies like BBC America, Godaddy, ArsTechinca or Tech Crunch.

Most WordPress sites use a standard url to log in (it’s actually one of the easiest ways to tell if a site is using wordpress) which is usually in the form sitedomain.com/wp-admin/

This is handy for an easy setup for new people, as guides on “how to use WordPress” can give a standard url for setup. Most people don’t change this (it can be a pain, and you have to remember what you changed it to. Not a huge deal, and can be more of an issue of something breaking during upgrades) and it won’t do much in the way of security to do so anyway, a temporary speedbump at best (and if you’re relying on hiding your login point to boost your security, then you’ve already set up for failure).

What a login will do, is attract bots. A number of methods exist to determine usernames for WordPress sites, which aids in gaining access (it’s hard to guess a password when you don’t even have the username, it’s effectively another password as far as bots go). Once you have that though, you can start hammering the system for the right password. If the user is smart, they’ve put limits on the number of attempts at any one time, but that won’t stop a botnet, just slow it. Eventually they will guess my password (even if ‘eventually’ means some time after the heat-death of the universe), and when they do, they have the key to that particular encryption. Unless there’s two keys, where they have one (which one doesn’t matter, it’s the same result). Said password will then be recorded as a ‘success’, and added to the dictionary to try on other sites. I don’t get much, as I’ve a low number of attempts with a significant cooldown period before they can reattempt, but even so, I get a lot of attempts. Here’s a sample of notifications of failed attempts over a 30 hour window, as I’ve set it up to notify me on failed attempts, and I have thousands of these.

An example list of the attacks on my site. (Date was not cherry-picked, it was just when I started this piece)

In 2016, there were over 75 million websites running WordPress. Assume each only gets attacked as often as I do (lets say 40/day) then in the last 4 years, the number of attempts is easy enough to approximate

(sites) x (attempts) x (days) x (years)
75,000,000 x 40 x 365 x 4
 = 4,380,000,000,000 (4.3 trillion attempts)

The real figure will be much, much higher.

This is where the problem starts. If I’ve chosen a simple password, a word like “Harambe” (because I thought it an uncommon word, and I liked Gorrillas and hated what happened) then it’s probably already in the dictionary, and being tried by the bots. Same with letter-number substitutions or “l33t speak” like H4ramb3 (also common in cases where people are forced to comply with arbitrary rules that don’t help) although more unusual cases will not be in there already.

What if, though, they’ve not got MY password, they’ve got the backdoor? It’s easy enough to test, just use the code on another site. If it works, sure, could be a coincidence, so use it on 5 more. If it still works, it could still be a coincidence (maybe I have a lot of sites, you’ve picked 7 that I used the same password on because I’m a moron and reuse passwords) but you can bet that’s now gone to the top of the list of passwords to try.

Of course, they don’t need to just attack someone else’s site. It’s so much quicker to set up a wordpress site locally, and attack it locally as fast as the software can handle. You have speed, you don’t warn anyone, and since you set the password, you know if the one that works is yours, or the key. For $10k you could buy a dozen or more decent machines, and just like distributed.net did with their key cracking, distribute the load and do a billion attempts in few weeks. 

It’s the exact same problem as befell the TravelSentry locks above. Sure the keys leaked publicly because they posted a photo, and a whitehat (or more probably a grayhat) decided to use it as an example of what not to do, but to assume no-one had the backdoor keys beforehand is absurd. You can buy a 4 pack of combination locks for $13 that have the most popular TSA unlock key (number 7). Crack open the case, examine the lock pins (something any locksmith and most engineers can do) and use that to construct a key to test on them. Et voilà, you have the key, and you’ve now gained access to the backdoor.

So in the end, it didn’t matter how secure the TSA kept their backdoor, people just reverse-engineered a publicly available implementation in private to get the backdoor access they need.

So it seems that no matter how hard you try and keep it ‘secret’, if there’s a backdoor, then it’s going to be found. So backdoored encryption is not really going to be encryption, just like a travelsentry lock is not really a lock.

How would it even be implemented?

While I’ve covered the cryptographic side of things somewhat, there’s another thing to look at — if they were to put in back doors, just how would they do it?

As we’ve already said, there’s two ways the backdoor can be put in, either in the encryption itself, or in the thing(s) doing the encrypting/decrypting. 

If it’s in the encryption itself, that’s going to be hard. That means developing an entirely new encryption that will also have a backdoor in it. For a start that’s not easy. Encryption these days is complex. SHA-3 was decided via a contest run by NIST, which was announced in 2007, closed to entrants at the end of 2008, with the entrants whittled down to 14 in July 2009, and a final round selection of 5 by December 2010, while a final decision was made in October 2012 to pick Keccak, it was eventually made a ‘hashing standard’ in August 2015. So from start to finish it took 9 years to adopt that new standard, and one of the big reasons why is that lots of people were testing it to ensure it’s, well, not going to fail.

Unfortunately, one of the ways it would fail is if there was a backdoor. This sort of thing isn’t doom, you can’t ↑↑↓↓←→←→BA(Start) your way though it like a video game, and bypass the boss battle to get to the end screen.

Multiple entities check, not just NIST (which is a subsidiary of the US Department of Commerce), but universities, and similar agencies in allied countries (Canada, UK, etc), so there’s no chance of sneaking it through, and any attempt to do so would just stick big question marks over the reliability, and no-one will use it unless forced to.

And this leads to another issue. I have this perfectly fine cryptography in use right now. Why should I change to this new one (that I’m not aware of being backdoored)? And then the first time its backdoor is used and known, no-one will use it for anything. Not even the people forced to use it (not as intended anyway, they made encrypt another way first, so the backdoor takes them to where they would have been anyway).

In short, why would anyone give up a secure crytography scheme, for a less secure one, or even one that’s suspected of being less secure? You wouldn’t, and neither would anyone else.

So that means a backdoor in the encryption itself is gone. So what’s left is a backdoor in the encryption/decryption tool. This is the only feasible method at all. In fact, in the last few weeks stories have broken that this exact thing happened with products from the Swiss company Crypto AG.

While details themselves are scant as to how it’s been done, there’s a few possible ways that I can think of that would do it. Let’s get some assumptions down to start with. While obviously, any code system would have a massive phase space (that’s the area of possibilities) of, for example a 1024-bit cypher (2¹⁰²⁴, or 1.797×10³⁰⁸ — 1,797-and 306 zeros after it) we’re going to assume its a 6-decimal cypher (aka 10⁶ or 10x10x10x10x10x10), giving 1,000,000 options (000000 to 999999), just to make it easy.

So the simplest way is to constrain the phase space. Imagine if we restrict the first digit to only odd numbers. immediately we’ve cut the key possibilities in half. It’s now 5x10x10x10x10x10, or 500,000.

Let’s make two other changes — the 3rd digit can only be even, and the 5th has to be a multiple of 3 (so 3, 6 or 9). That’s changed things to 5x10x5x10x3x10, which gives 75,000 options.

3 small changes, which no-one would really look at have reduced the available number of keys to just 7.5% of the total. There’s ways to be sneakier too. If we said the 2nd and 6th had to add up to 9, well there’s 10 ways of doing that (09, 18, 27, 36, 45, 54, 63, 72, 81, 90) so the hundred options there just dropped to 10 — we’ve effectively made the key one bit less by always locking one key bit to another. there’s now just 7500 options, down from a million. 

That’s the simplest, and if you had the chance to look at 50 encryption keys put out under those rules you might notice something suspicious, and you might not, as they all look random, but by knowing the rules in place, we’ve got 0.75% of the potential keys being used.

Another way that’s much more complex, is to encode a key indicator into the output. If the machine’s set up to use a method where (as a rough example) the 7th character indicates a certain area of the phase space, and the 17th indicates another area, you’ve again extremely limited the space needed to crunch, and if each one reduces it to a 26th, you’ve reduced it to 1/(26*26) of the space, or 0.14%.2–3 more indicators in it and you’ve basically handed the key in the output, if you know what it means.

This may be feasilble in a closed encryption system like embassy communications equipment, where the cryptographic protocols are kept enclosed as part of the product, but the majority of users use encryption systems that are publically available, and so the problem then becomes one of the encryption tool.

Sure if everyone’s using WhatsApp, then there may be a way to slip these kinds of backdoors into the whatsapp software, but that will last just as long as it takes for someone to notice, or the first externally decrypted message to be revealed. And many systems use open encryption standards, so when I send encrypted/signed emails (and almost all of my emails are cryptographically signed, and I will randomly encrypt them as well when I know the recipient can handle it) I will not always be using the same software as other people. If I’m using GnuPG with Enigmail for Thunderbird, and someone else is using a browser extension (such as Flowcrypt in Chrome or FireGPG in Firefox — I do not vouch for these apps, use at your own risk) or a service like Protonmail, we’re all using the same encryption system, but different encoding machines, which makes machine backdooring hard to do, and harder to keep working, as people migrate between compatible apps.

So unless you’re again mandating a new encryption where you control the encryption engine entirely, then you’re not going to get your backdoor to stay. People will change clients, and don’t like being locked into systems which can be bypassed.

Famously, Blackberry’s had secure messaging with their BBM service, but its use dropped after blackberry’s CEO promised to break that encryption if the US government asked him to, following revelations that other governments, like those in Canada, the UK, and elsewhere had backdoor encryption keys from the local Blackbery Enterprise Servers, which they could use. It’s since shut down, probably because of decreased usage after these revelations. 

Conclusion

So backdooring encryption is something that’s not going to happen, not in the real world. It’s not a case of “Nerds need to Nerd Harder”, its a mathematical impossibility that you get to put a backdoor in encryption and no-one notices.

While you could invent a new cryptographic system, and try to force people to adopt it, people are going to test it. In fact, forcing its adoption is going to actually encourage more people to attack it for weaknesses, which means any backdoors will become obvious.

Requiring the use of specific software tied to a specific encryption isn’t going to work either. That SCREAMS backdoors to people (and lets face it, why else would a government require that) and people will instead keep to the old non-backdoored systems, or make new clients using the same encryption system, but without the backdoors.

It’s part maths, and mostly human nature. 

Any system with a backdoor is fundamentally insecure. Who wants to use an insecure system? Banks don’t, because that makes transactions insecure, and liable to spoofing, or injected transactions, or to quote the epilogue from the film Sneakers (which is all about a backdoor for encryption)

In a surprise announcement,  the Republican National Committee...

... has revealed it is bankrupt.

A spokesman said they had plenty of money in their accounts last week...

... but today they just don't know where the money has gone.

But not everybody's going begging.

Amnesty International, Greenpeace and the United Negro College Fund...

... announced record earnings this week...

... due mostly to large, anonymous donations.

If the (mostly Republican) members of Congress are happy to see this happen, then maybe we can start talking. But you can sure bet that they’re not the kind to accept ‘no more secrets’