Encryption back door for law enforcement

[Captrek]

Lately, as criminals and terrorists have used encryption technology to frustrate law enforcement and national security, there has been political discussion of whether encryption technologies should be required to have a back door for law enforcement.

One objection to this proposal is that such a backdoor might be used wrongly. Apple CEO Tim Cook said, "But the reality is if you put a back door in, that back door's for everybody, for good guys and bad guys."

Without addressing the larger political question of whether law enforcement ought to have back door access, I'd like to propose a technical solution to the "bad guys" problem.

The backdoor doesn't open with a single key. It takes 100 keys to unlock, and each key is known only to a small group of people. In order for the bad guys to access encrypted communication through the back door, they need copies of all 100 keys. So long as at least one of the 100 key-holding groups successfully protects its secret key and uses it only when they are supposed to, the bad guys are out of look.

In addition, you retire and replace one key pair every day. (Staggered. Over the course of 100 days, all 100 keys are replaced.) Even if a bad guy manages to get copies of all 100 keys, he would be able to read that day's communications only. The next day's communications would use a new key that would lock him out again.

Would this system be practical? Would it be secure?

 

[Robert Maxwell]

Who is generating the keys?

A composite key architecture is not unheard of, but I am not aware of any that require so many keys.

Of course, you could accomplish this using one very long key and breaking it into 100 smaller parts. Say, 100 segments of 2048 bits. Having pieces of it expire daily implies temporal rotation, which also already exists, but not (as far as I know) a first-factor authentication method (it's mainly used as the second factor in two-factor systems--you use a password and a temporal key).

Nevertheless, how the keys are generated becomes the important question. Short of an open blockchain protocol (like Bitcoin and its derivatives), there is no good way to single-source such a key without unduly empowering an individual--which is exactly the problem you are trying to solve.

 

[Captrek]

Who is generating the keys?

...


Nevertheless, how the keys are generated becomes the important question. Short of an open blockchain protocol (like Bitcoin and its derivatives), there is no good way to single-source such a key without unduly empowering an individual--which is exactly the problem you are trying to solve.

Each of the 100 key-holding groups would be responsible for generating a key pair, distributing the public part, and protecting the private part. That's the only way to ensure that each key is known only to the group that's supposed to know it.

They would do it using rigorously vetted open source tools to ensure there's no funny business with the algorithm.

 

[Nebusj]

Would this system be practical? Would it be secure?

And how does every encrypted communication and data-storage medium get the day's Stasi-access update?

 

[Captrek]

Would this system be practical? Would it be secure?

And how does every encrypted communication and data-storage medium get the day's Stasi-access update?

Are you suggesting the encryption could be compromised by compromising the system used to distribute the public keys? I think the key holders would notice pretty quickly if the keys they generated aren't the ones being distributed.

 

[Robert Maxwell]

OK, I don't know how much background you (or anyone) has with encryption. I will assume little to none and give a little background. I will try to keep it simple.

Basic concepts: in encryption, you have plaintexts, ciphertexts, and keys. Plaintext is the original text--the stuff you want to encrypt (or get back out of an encrypted form). Ciphertext is the encoded/encrypted version of the plaintext. And a key is what you think it is: it's what you apply to the ciphertext to get back the plaintext (or the other way around).

But there is much more to encryption than this. In public key cryptography, you have two kinds of keys: a public key and a private key. The private key is used to turn plaintext into ciphertext; the public key is used to do the reverse. This has the side benefit of telling the decrypter (who has your public key) that you (and only you) generated the plaintext, so it adds a layer of authenticity as well. (This is why it is the centerpiece of secure online communications.)

Now, what you've described with this concept of 100 public/private keypairs that rotate on a schedule is combining two concepts:

* Public key infrastructure (PKI), described above
* Time-based one-time passwords (TOTP)

The difficulty is in applying TOTP to PKI while at the same time having some kind of composite private key (based on the TOTP) to decipher all ciphertexts. Basically, everyone would have to opt into using this system where all keys are derived from this master key generation system. It also makes all communications necessarily ephemeral, since the moment one of the 100 keys expires, anything encrypted with it will no longer be possible to decrypt unless the 100 people get together and decide to. I'm actually trying to think of a situation where this would work for the 100 but somehow not work for anyone else. I'm thinking a long-term system where the master key rotates in pieces over time, and all keys are derived from the same master key (and key generation algorithm) would be very difficult to make complex enough to avoid brute force attacks. The basic concept here is "leakage": anytime ciphertext leaks information about the plaintext (or the key), the chances of someone breaking the underlying system increase. Every key rotation is an opportunity for an attacker. The fact that 100 keys exist makes discovering them an achievable goal. TOTPs are generally based on a single secret key--which someone, somewhere has to generate. In fact, everyone using this encryption system would need to know the secret in order to generate the one-time passwords.

I don't know. I think this combination of moving parts, if it's even practical (and it probably isn't), would be very fragile and thus prone to attack--which is the basic problem with any of these "give the government a backdoor" ideas.

Composite keys are a thing. PKI is a thing. TOTP is a thing. Client keys derived from a master key are a thing. But all of them together? It's novel, and novelty in encryption generally leads to massive holes, because of the mathematical nature of encryption.

Basically, I would not worry so much about the 100 keys (although stealing them is probably not nearly as hard as you think), but that the underlying algorithms would likely be quite vulnerable to a range of attacks due to requiring, essentially, two vectors of reversibility. Everything encrypted this way would likely be prey to related-key attacks.

 

[Captrek]

OK, I understand those basic cryptography concepts. Let me try to explain my proposal more clearly.

Imagine 100 levels of encryption. Content is encrypted (for the backdoor) by applying the day's 100 public in sequence. Key 1 converts PlainText to CypherText1, which Key 2 converts CypherText2, etc., with the CypherText100 finally being stored.

Decrypting is a matter of applying the private keys in reverse order. When a legal order comes to decrypt the data, Key Group 100 uses their private key to decrypt CypherText100 to CypherText99, which they provide to Key Group 99, which then provides the CypherText98 to Key Group 98, etc., until Key Group 1 discovers the original plaintext. (Decrypting old stuff will remain possible as long as the groups maintain the old keys.)

Would this system be vulnerable to attack? If so, how?

 

[Robert Maxwell]

A hundred levels of encryption is computationally impractical. If each key is long enough to be useful (so at least 1024 bits, preferably more if you actually care about security), you're talking about a key that's more like 102,400 bits long, which is... much less than practical.

Encryption time scales quadratically with key length (each doubling of key length quadruples encryption time); decryption scales cubically (doubling key length triples decryption time).

102,400 bits is a bit less than 7 doublings of 1024. That means encryption would take roughly 28 times as long as 1024 bits and decryption would take about 21 times as long. That's a lot of extra overhead just so the government can spy on you.

The other option here is to use shorter keys, but 100 of them. Even here, you wouldn't want more than maybe 4096 bits altogether. This means 100 roughly 40-bit keys.

Layering encryption doesn't generally reduce your security (some people would argue this, but mathematically this is correct) but it doesn't gain you any, either.

From a technical standpoint, "run through this excessive amount of cryptography just so Big Brother can spy on your shit" is unpersuasive, and has historically been unpopular as the Clipper chip can attest.

 

[Robert Maxwell]

Further thought: the key generation algorithm would need to be very, very good, especially when it will be generating so many keys on a predictable basis. If anyone screws up the key generation by making it lack sufficient entropy, the entire scheme is compromised.

 

[CorporalCaptain]

Encryption time scales quadratically with key length (each doubling of key length quadruples encryption time); decryption scales cubically (doubling key length triples decryption time).

I haven't read the whole thread, but this just jumped out at me. I think you mean:

decryption scales cubically (doubling key length multiplies decryption time eightfold)

In other words, three is the exponent of two (not the base).

 

[Robert Maxwell]

Encryption time scales quadratically with key length (each doubling of key length quadruples encryption time); decryption scales cubically (doubling key length triples decryption time).

I haven't read the whole thread, but this just jumped out at me. I think you mean:

decryption scales cubically (doubling key length multiples decryption time eightfold)

In other words, three is the exponent of two (not the base).

Whoops! Yeah, you got it. It's been a long day.

 

[Captrek]

Of course, I'm talking about applying the keys in sequence, so the runtime grows linearly with the number of keys.

 

[CorporalCaptain]

Whoops! Yeah, you got it. It's been a long day.

And I had a spelling boo-boo, myself. Fixed!

 

[Robert Maxwell]

Of course, I'm talking about applying the keys in sequence, so the runtime grows linearly with the number of keys.

Applying 100 keys in sequence is actually slower, because the setup/teardown mechanisms have to be performed 100 times now instead of just once. Such overhead can be substantial.

In practice, in terms of security there is no difference between 1 very long key and 100 short keys that add up to the same key length, except that doing 100 short keys is so much busy work when you could've just used one big one. But one big one (that is, big enough to where dividing it into 100 parts still results in usefully-large keys) is still impractical.

In the course of researching my posts here, I came across Shamir's secret sharing algorithm, which doesn't do quite what you're looking for but is an interesting idea nonetheless. I could see using something like this as a mechanism to obtain a very large master key from which all other private keys are derived, but you can only obtain the master key if enough people put their parts together (doesn't have to be all of them, although you can set it up such that they are all required).

Unfortunately, the complexity of your scheme is what dooms it. The best encryption schemes are conceptually and mathematically straightforward, but high-entropy (random) and non-linear (difficult to represent as linear functions). The more layers of complexity you add, the more fragile you make the overall system. Consider what you are suggesting:

1. A key generation system in which all keys are derived from a master key made of 100 separate keys known to a select number of parties. Already this is a flaw because if the underlying master key can be exposed, the entire system is compromised.
2. A staggered, temporal key expiration system that essentially functions as a set of rolling one-time passwords. Existing authentication tokens of this nature rely on operating within secure environments (such as protected hardware dongle, or enclosed in an application that will only run in a trusted environment). You are suggesting having this run on everyone's computers and available as open source, meaning it will be very easy to find exploits/flaws.
3. Two possible decryption vectors: the typical public key decryption method, and the distributed key decryption method. These aren't that unusual, but combined with the previous two features is rather new.

It can't be overstated just how much excessive complexity weakens encryption systems, and this is pretty complex. The encryption we have that works today works because it's been around a long time and is well understood. The thing about a broken, complex encryption method is that you often can't fix it. It's just broken. If it's mathematically compromised, there is really no way around it. You just have to give up and start over.

I'm still trying to determine how everyone would encrypt their traffic in a way that this composite/distributed key can, if assembled, decrypt, without fundamentally compromising the data.

The related-key attacks may also be insurmountable. If you are only switching out one of the 100 keys per day, what you are doing is giving an attacker a long-term pattern of key changes that is probably algorithmically decipherable.

The reason for this is pretty straightforward: existing encryption only works because private keys are generated in closed environments with high entropy, and kept secret. A key system in which everyone is working off of a temporally rotating key means everyone knows how to generate a private key based on the 100 special keys, which means the algorithm for generating (or really, expanding) the 100 keys is known. You'd better hope it's an amazingly good algorithm, or you just broke encryption for everybody.

Sorry for all the rambling. There is good reason why systems like you describe aren't used, though. People much smarter than us plug away at these problems all day, every day, and they are convinced that encryption systems which allow "exceptional access," virtually regardless of the method used, fundamentally compromise security for insurmountable technical reasons. This doesn't mean it's impossible, but it does mean it is beyond the best cryptographic expertise we currently have.

 

[Marc]

Would this system be practical? Would it be secure?

And how does every encrypted communication and data-storage medium get the day's Stasi-access update?

Are you suggesting the encryption could be compromised by compromising the system used to distribute the public keys? I think the key holders would notice pretty quickly if the keys they generated aren't the ones being distributed.

I can't recall exact cases but I'm pretty sure that what you suggest has indeed happened and it hasn't always been discovered right away.

and even if there isn't total compromise at first, simply knowing about a weakness in a system can be enough.

Doesn't even have to be the complete system - just a component.

Afterall how secure can a security key be if it's used 28,000 times http://www.itworld.com/article/2897...same-rsa-encryption-key-used-28000-times.html

 

[Robert Maxwell]

And how does every encrypted communication and data-storage medium get the day's Stasi-access update?

Are you suggesting the encryption could be compromised by compromising the system used to distribute the public keys? I think the key holders would notice pretty quickly if the keys they generated aren't the ones being distributed.

I can't recall exact cases but I'm pretty sure that what you suggest has indeed happened and it hasn't always been discovered right away.

and even if there isn't total compromise at first, simply knowing about a weakness in a system can be enough.

Doesn't even have to be the complete system - just a component.

Afterall how secure can a security key be if it's used 28,000 times http://www.itworld.com/article/2897...same-rsa-encryption-key-used-28000-times.html

Stuff like this cannot be stressed enough. An encryption system is only as strong as its weakest link. The more links, the more potential you have for weak links (known as "attack surfaces" in cryptographic lingo). This is why complex systems are generally disfavored.

 

[Dryson]

I don't think digital keys should be only the means of encryption, I think a retina scan and finger prints should also be part of the key chain which would add almost 100% encryption.

For example in the 100 key chain code of encryption you would have randomly rotating blocks of data that needed a fingerprint or retina scan in order to access the key function. To make the encryption even more difficult to break any person authorized to be part of the finger print or retina scan that would be on duty could be the person or persons required to become the key itself. If a company had 10 such employees that would give this section of the security feature an additional 120 base keys for a single encryption block. Within this special encryption block you could have regular access keys that would need to be input after the initial finger print or retina scan key to then open up another special encryption block and so far forth.

Unless the employee was kidnapped for their eyes and finger prints I don't think this type of security system would ever be able to be breached because if an employee was kidnapped or even taken to a local hospital for treatment they would have their access to the security network revoked and their name taken off of the security roster as well as their retina and finger print keys deleted from the system.

 

[Robert Maxwell]

I don't think digital keys should be only the means of encryption, I think a retina scan and finger prints should also be part of the key chain which would add almost 100% encryption.

No. This is nonsense. A retinal scan is still going to be reduced to digital data. That is to say, a string of numbers. In other words: exactly what a key is. Retinal patterns also have far less entropy than a good RNG. This also applies to fingerprints. Such biometrics are good for controlling physical access in environments where breaking through to the underlying information source is non-trivial (imagine using such a device to block access to a sensitive room, for instance), and would need failsafes such that any tampering would immediately disable the biometric sensors and deny access.

For example in the 100 key chain code of encryption you would have randomly rotating blocks of data that needed a fingerprint or retina scan in order to access the key function. To make the encryption even more difficult to break any person authorized to be part of the finger print or retina scan that would be on duty could be the person or persons required to become the key itself. If a company had 10 such employees that would give this section of the security feature an additional 120 base keys for a single encryption block. Within this special encryption block you could have regular access keys that would need to be input after the initial finger print or retina scan key to then open up another special encryption block and so far forth.

This is just a slightly novel interpretation of a shared secret mechanism. What you have hit on here is that social engineering winds up being the most effective way to compromise security, which means using human beings as keys is actually much worse than purely technical/mathematical means, as humans are quite easy to manipulate. Turning humans into keys is basically the worst idea outside of some very limited scenarios that aren't that useful for day-to-day life.

Unless the employee was kidnapped for their eyes and finger prints I don't think this type of security system would ever be able to be breached because if an employee was kidnapped or even taken to a local hospital for treatment they would have their access to the security network revoked and their name taken off of the security roster as well as their retina and finger print keys deleted from the system.

I am curious as to how you think such a system is going to protect your emails and online transactions. I mean, what scenario is this designed for? It's certainly not an everyday use case.

 

[Dryson]

No. This is nonsense. A retinal scan is still going to be reduced to digital data. That is to say, a string of numbers. In other words: exactly what a key is. Retinal patterns also have far less entropy than a good RNG. This also applies to fingerprints. Such biometrics are good for controlling physical access in environments where breaking through to the underlying information source is non-trivial (imagine using such a device to block access to a sensitive room, for instance), and would need failsafes such that any tampering would immediately disable the biometric sensors and deny access.

This is just a slightly novel interpretation of a shared secret mechanism. What you have hit on here is that social engineering winds up being the most effective way to compromise security, which means using human beings as keys is actually much worse than purely technical/mathematical means, as humans are quite easy to manipulate. Turning humans into keys is basically the worst idea outside of some very limited scenarios that aren't that useful for day-to-day life.

I am curious as to how you think such a system is going to protect your emails and online transactions. I mean, what scenario is this designed for? It's certainly not an everyday use case.

Its the human element that I am focusing on. Keys are generated and then stored and are easily accessible. Even if those keys are random theirself the best hacker will always be able to break the algorithm because the keys are a constant set of data that can be hacked and can even be mimicked to break into a computer. A random outside variable however is hard to track because the input variable being the retinal scan or finger print scan can be any so defined parameter such as point to point checks on a finger print across the ridge of the finger print that nearly a billion if not more such point to point encryption could place that a hacker would never be able to generate a key for fast enough to beat. For example a finger print is taken and has 10,000 points logged based on different distances between the ridges of the finger print. When the security program runs it's random finger print key access block the program would identify three different points on the finger print to make the initial match. From there the program would determine its secondary key access by randomly choosing various distances to other points from the initial scan to other points on the finger print where the computer would be the only entity that would know the key that it was going to be used to allow access.

Not this would not be used in an everyday scenario. It would be used for when someone tried to get my beer from the fridge.

 

[Robert Maxwell]

I would strongly suggest you read a book or take a course on cryptography because you're rattling a bunch of things off the cuff with no real understanding of what cryptography is and does.