Authentication impossible without pre-shared public key

Question

Correct me if I am wrong, digital certificates require the user to have the public key for the certificate in their web browser, right?

Which means it has to be pre-shared.

(Say I am designing a cryptosystem which is an application for encrypted chat that uses TLS. However, I want the cryptosystem to be end-to-end, meaning, the client must directly connect to a server of their choice.

How can I make this cryptosystem's authentication work if I allow my clients to create their own servers for direct end-to-end encryption? In other words, the application does NOT contain a pre-shared public key for the digital certificate.

In this scenario, is my application doomed without a pre-shared public key?

Answer 1

You dont need the public key/certificate to be present in the browser. You just need to devise a method to ensure the public key/certificate which is presented by the peer is valid. In a Web Browser scenario this is typically done by a number of known CAs which sign those certificates. But you can also ask the user to authenticate the certificate by a fingerprint or by registering it at a central directory you trust.

You can also what is called "Trust-on-First-Use" which is basically "install this cert". This has the one-time risk of a person in the middle attack. It is how SSH is used most of the time today.

You do not even need a known/verified certificate but can use instead anonymous key agreement. This has of course the big problem that each time this key exchange is done a person in the middle can spoof the server. TLS has aDH ciphers for this.

And finally you can use TLS based on a shared password as well. It depends if both parties know each other and can actually verify each other out of band or not.

If you do not have a central directory authority the most common method is to use a trust on first use setup with the additional option to manually verify the peers (this is for example also used in Whats App in addition to the weak identity proof with phone number).

Answer 2

Correct me if I am wrong, digital certificates require the user to have the public key for the certificate in their web browser, right?

You are wrong, but in a way you're indirectly right. You're wrong because the browser doesn't need to have a pre-shared public key for the site's certificate. The site will send its certificate along with the response, and that certificate will be signed by a certification authority (CA), whose certificate is attached as well.

This shifts the problem—as long as the CA's signature of the server's certificate checks out, now the browser has to check the authenticity of the CA certificate. Which normally is itself signed by another CA, which shifts the problem one more layer. This is called a chain of certificates.

Your operating system or browser vendor bundles a collection of root certificates, and every certificate chain must end in one of those certificates for your browser to recognize it as authentic. So some pre-shared public keys are necessary as you suspected, but you don't need to arrange pre-shared public keys with the sites that you visit. (Instead you need to trust the certification authorities and your OS or browser vendor, which has its own host of problems.)

How can I make this cryptosystem's authentication work if I allow my clients to create their own servers for direct end-to-end encryption?

You would need to do something along these lines:

1. Create a CA for your application. Either:
   • A standalone one, in which case you'd have to bundle the root certificate with your app. (In that case the private key for this certificate is the keys to the kingdom, and needs to be protected with paranoid zeal.)
   • One certified by a third party your clients will recognize (e.g., the certificate comes bundled in their OS or browser).
2. Have clients privately generate their key pairs and associated certificates, and securely submit the latter for signature by your CA. (This is a potential weak spot—authenticating clients securely is critical here!)
3. Clients can now use their signed certificates to establish authenticated, end-to-end encrypted sessions with their peers.

Some reading to get you started, but you'll want to read more than these two links:

• Public key infrastructure (PKI)
• OpenSSL PKI Tutorial v1.1

Answer 3

In cryptography, you can never truly authenticate a person. When our examples include phrases like "Alice authenticates that the message came from Bob," what is actually meant by that is "Alice authenticates that the message came from someone who knows what Bob knows." Typically the key thing that Bob knows is a private key that uniquely identifies him. However, Alice needs a way to distinguish "someone who knows what Bob knows" from "someone who doesn't know anything." This is typically where certificates or other tools are used.

Cryptography cannot solve this on its own, but it can piggyback on any other authentication schemes that may be in play. One solution for encrypted phone calls is to do a Diffe-Hellman key exchange but before the exchange they share commitments as to which numbers they chose, and then present the key information to both parties. They then are free to do anything they please with this information including verbally relaying it over the link. If there is a man-in-the-middle, the two parties will see different key information, because the man in the middle doesn't know the secret number of both sides until it's too late.

In theory, the man in the middle could then corrupt the channel, substituting the "correct" key information in each direction and developing an illusion of everything being just fine. However, it proves to be very difficult to corrupt the channel in this way for phone calls. Voice communication is simply too instantaneous and too complicated to spoof. Depending on your application, your users may also find a very effective way to communicate this information in a way that is hard to corrupt.