Public Key Decryption; or how we can trust governments with access to our encrypted data
It was not until FBI Director Christopher Wray’s speech last week that I started to realize tech companies do have a responsibility to think about ways to help a government. If they fail, the alternative is a state takes matters into their own hands and bans encryption.
We have a whole bunch of folks at FBI Headquarters devoted to explaining this challenge and working with stakeholders to find a way forward. But we need and want the private sector’s help. We need them to respond to lawfully issued court orders, in a way that is consistent with both the rule of law and strong cybersecurity. We need to have both, and can have both. I recognize this entails varying degrees of innovation by the industry to ensure lawful access is available. But I just don’t buy the claim that it’s impossible.
Let us go on a tour to discover where we are, and the different scenarios I believe the future could bring us. We are going to explore my proposal of an inherently secure ecosystem which I name Public Key Decryption using a demonstration that shows how to allow governments to gain access to private decryption keys when following specific rules such as a fair court order and aligning with general consensus. I believe this is the first time such a protocol is invented and described.
But that’s just dangerous
Up until now, technology companies state they do not wish to provide such sort of encryption, as it will be harmful when it falls into the wrong hands.
The common complaint is that there is no safe way for a government to have access to encrypted communications. The only two flavors that have been brought up are (1) to either share a master key (called key escrow), or (2) to build in some backdoor. For the master key, even a child would know that if it would ever leak, the wrong person immediately would gain access to every message ever send. The same thing for the backdoor; if one would reverse engineer it, it renders all earlier secret communication useless by exposing its content.
In the 1990s, the Electronic Frontier Foundation (EFF) raised a red flag on the US Governments refusal to allow licensing of any secure encryption product for export unless it utilized a key recovery algorithm. They decided to crack this governmental standard to proof it was possible for third parties to read encrypted messages.
The next heard complaint is how even if there were a 100% secure way for a government to access and recover encrypted messages through law, there is no way to guarantee these powers will not be abused in the future. When a country turns into a totalitarian state, those laws that once were set up to protect people by requiring a court order before messages could be decrypted, may be pushed aside and will give the state free hand.
Why we have to try
So what if we could develop a secure encryption model that ensures your messages can only be read by the intended receiver or when there is an independent court order by an independent judge who will test the request not only against current law, but also against international human right laws?
Right now many governments call for weakening encryption for the sole purpose of them being able to still listen in to conversations. For example, how many times have the FBI not been blocked because they could not read data from an iPhone of a well identified and captured or killed attacker, such as those of the 2015 San Bernardino or 2017 Sutherland Springs cases?
There are certainly many scenarios where the majority of the people feel like governmental agencies must have the ability to read encrypted messages or unlock devices. Giving a government these tools in such a way that they can not abuse it, also opens up the way for them to no longer block more enhanced encryption technologies, but to actually push for robuster and better encryption as they themselves also benefit from it.
Countries who now already torn on the privacy of their people and block secure channels like VPN or OpenPGP encrypted email, will more and more limit the use of encryption. At some point, their residents may only use state governed encryption protocols, giving those in power a free hand to dictate what is being said or written by anyone. Tech companies just soft-sawder them, because they fail and refuse to come up with inherently safe solutions that protect the individual but that can also protect the security of the state. Even worst, many tech companies comply and set their products up for censorship.
If there was an encryption scheme that allowed countries to read secret messages when they need to, but at the same time prevents them from reading all the messages, there would be one less reason for them to try and lower the standards of encryption techniques.
Tech companies are wrong
Anybody saying it is technically impossible to create a inherently secure encryption protocol that allows governmental access under certain specific and not negotiable conditions only, is wrong or unaware. However, major tech companies and public persons still claim it is absolutely impossible and avoid the discussion.
“And while the government may argue that its use would be limited to this case, there is no way to guarantee such control.” (Tim Cook, Apple)
“But that’s wholly different than requiring companies to enable hacking of customer devices & data. Could be a troubling precedent.” (Sundar Pichai, Google)
“What will happen is, if everybody goes to their respective corners, and the tech community says ‘either we have strong perfect encryption or else it’s Big Brother and an Orwellian world’, what you’ll find is that after something really bad happens, the politics of this will swing and it will become sloppy and rushed and it will go through Congress in ways that are dangerous and not thought through.” (Barack Obama)
“If we get it right, every other democracy will look to us as a model.” (Satya Nadella, Microsoft)
In fact, let me tell you how it can be done.
And this is how it can be done
Bob needs to send a private message to his doctor Alice. Since Bob does not want anybody else to know about his medical condition, he uses encryption.
Just like right now, both Bob and Alice own a key pair that consists out of a public and a private part. When Bob types up his message, he uses Alice’s public key to apply encryption. He sends over the encrypted message and Alice uses her private key to read it.
Since Bob and Alice are using Public Key Encryption, nobody else can snoop in and read what they are saying.
Now imagine Charlotte exchanging messages to her friend David using the same protocol. Two weeks later, Charlotte steps into a school and pulls her weapon. Luckily her weapon jammed and she was incapable of hurting anybody, but when police raided her house they found all kinds of horrible pictures. It also was pretty clear she had conversations with like-minded, but she refuses to give up her private encryption key making it impossible for the police to see who she has been communicating with.
This is where Public Key Decryption comes in. Any time Alice and Bob, Charlotte or David created their key pair, they would download a nation wide list containing everybody’s (anonymous) public key. So when Bob created his key, he was forced to randomly select 200 public keys from this list and use those with a secret sharing algorithm to encrypt his private key. That way, decryption is only possible when at least 50% of the original used keys are provided. Bob adds his new encrypted private key plus public key to the list.
— With Shamir’s Secret Sharing scheme, any t out of n shares may be used to recover the secret.
Back to Charlotte. After a week of investigations, the police still have no clue who Charlotte was talking to. She however did mention that she was not alone, and there are clues that a new attack will take place soon. The police thinks this is serious and goes to court to get a decryption warrant. This is officially handed to Charlotte, but she refuses to cooperate.
As a final resort, the police reaches out to the public. They publish Charlotte’s public key and the corresponding encrypted private key they got from the list and ask the people to check if any of their public keys was one of the 200 random keys used by Charlotte when creating her key pair.
“The authorities seek your help. The suspect arrested for the recent armed school incursion -Charlotte- claims more attacks are at hand. Police confirms having found evidence A-B-C and believes Charlotte communicated with yet to identify third parties who may plan more attacks. Your immediate assistance is requested to allow decryption of all messages exchanged with suspect.”
Bob receives this notice too. He applies his private key against the published encrypted private key package, and discovers he is one in the group of 200 that can make decryption possible. Before he reaches out to the police however, he studies the case and checks the evidence that the police provided along with the request. Bob looks up media coverage about the event and decides it is for the best that Charlotte’s communication can be read be the police, so he complies and offers his help.
Only hours after the call for help, the police received responses from 130 anonymous individuals who firmly believe there is a solid case for decrypting Charlotte’s private key. They put the bits and pieces together, find out about David’s plans and capture him right before he executed his plans.
But what if they tried to read Bob’s communication?
The good part about Public Key Decryption over a backdoor or the government keeping a secret master key, is that the power of the crowd controls what happens. Although most democracies are based on the fundamental of separation of powers, the constant fear exists that this will ever be overthrown.
Public Key Decryption gives power through carefully controlled conditions guarded by general consensus.
Only when the people whom’s public key was used to encrypt the disputed private key make themselves known out of their own initiative, authorities can apply decryption. This means they will have to be transparant, open, and truthful about their reasoning and motivation if they want the public to cooperate. Since it is not known whose public keys were used for the encryption of the private key, anybody can choose not to participate when they do not fully trust the appeal without having to be afraid for countermeasures.
Follow-up exploration
Below lists some of the things that still have to be explored to make Public Key Decryption a viable alternative to the current alternative (which is: no encryption or no public safety). When all pieces of this puzzle are solved, it will provided a hardened protocol that can mitigate any state driven attack.
- There needs to be a way when someone is adding an encrypted private key on the public listing, it in fact is encrypted using known and valid public keys. If not, the encrypted private key should be blacklisted.
- Governments must be prevented to inject malicious or fake public keys to the public list. If they could, this would reduce the odds that someone that encrypts her private key, would pick a real person’s public key at random.
- It may not be possible knowing an encrypted private key, to know which public keys were used during the encryption process.
- For governments to accept this, they must have a way to detect that encrypted communication is using the Public Key Decryption method. They will most likely block all other kinds of encrypted messages, or investigate their origin.
- Some infrastructure that can be used by governments to ask for people’s input must be set up. This could be as simple as a broadcasted message. Only devices that recognize the key, will show this message to their owner to make the decision if they trust the request and wish to help or not.
All of the above are technical questions that may or may not already be solved by other projects.
This is a call to all of those who are involved with building the systems we all use every day, to stand up and work on those things that will keep not only the individual safe, but also our society. Especially leaders such as the ones quoted in this article as well as many others I would like to ask to actively participate. I invite everybody to enroll with me in this conversation and to build upon this new proposal.
TL;DR
Public Key Decryption offers an algorithm forcing authorities having to reach out to (a group of random, anonymous) people and ask for their consent when they want to read encrypted messages.
- When creating a key pair, private keys must be encrypted using a combination of 200 (or any other number) of randomly selected public keys using a secret sharing method such as Shamir’s Secret Sharing.
- At least 50% (or any other representative amount) of the corresponding private keys is required to decrypt this encrypted private key.
- The public and encrypted private keys are published to a central public listing, but it will not be known who those keys belong to.
- When authorities need to decrypt messages, they have to ask the community to check if their public key was used to encrypt the private key.
- If your public key was used, it is up to you to decide if you want to cooperate or not. You can base your decision on the details shared by the authorities, coverage by the media, or the roll of a dice.
- Like voting, the outcome of the general public’s opinion when authorities call for help will represent the line of thoughts of the population and it will force the authorities to be open and transparant.