Does public key cryptography provide any security advantages, or even just a different security model, over symmetric cryptography?

Question

Lets say Bob wishes to communicate with Alice.

Alice's public key is useless to Bob unless he can prove that the public key came from Alice. To do this, Bob and Alice can establish a secure channel to exchange Alice's the public key, but this same channel can equally be used to exchange a symmetric pre-shared key, so this is effectively identical.

Alternatively, Bob and Alice can both trust a third party Carol, who will verify Alice's public key as belonging to Alice, and then give that public key to Bob, who trusts Carol.

But this doesn't solve the problem. For both Bob and Alice to communicate with Carol, they need Carol's public key and the ability to prove that it belongs to Carol. To achieve this, they both need a secure channel with Carol, which they could then just use to exchange a symmetric pre-shared key between each other, and communicate that way.

In both cases, they would need to trust Carol to not abuse their trust and eavesdrop on the information. Either by swapping out public keys and intercepting the information, or by just using her knowledge of the PSKs to decrypt it.

There don't seem to be any security advantages here. And the security model itself seems to be identical. Is there something I'm missing here, or are the differences purely in terms of scalability?

Answer 1

You incorrectly assume that a secure channel is needed to obtain a public key. This is not the case. It's sufficient to have a trusted third party bind a public key to a specific identity through a digital signature. This signature can be verified by anybody and prevents the key from being secretly manipulated or swapped out, regardless of how it was transmitted.

For example, in the case of HTTPS, severs present an X.509 certificate which has been signed by a certificate authority. Or in PGP/GPG, you can build a web of trust from people you accept as trustworthy. None of this requires a secure channel.

Even if you omit any third parties and want to communicate directly with a single peer, public key cryptography means that the channel only has to be authenticated, not secret. For example, you could put your public key anywhere on the Internet and let your peer download it. To ensure that the key is correct, you only need to, for example, confirm its hash in a call, personal meeting or whatever. No secret information has to be transmitted.

Answer 2

In addition to the factors mentioned in other answers, preshared keys force the third party (Carol, in your example) to know exactly which parties are communicating. With public-key certificates, Bob needs to know Carol's public key so that he can verify Alice's certificate, but he doesn't need to tell Carol that he's talking to Alice, specifically. (In fact, in real-world applications, Bob usually got Carol's public key long before even Bob knew that he would someday talk to Alice. The interactions between the three parties are very strongly decoupled.)

Likewise, preshared keys force Carol to know the actual secret key that's being used, and may even force Carol to persist that secret key for some period of time (depending on the exact protocol for setting up this key and distributing it to both Alice and Bob). With public-key certificates, Carol never knows Alice's private key.

You say that

In both cases, they would need to trust Carol to not abuse their trust and eavesdrop on the information.

which is true to a point; but there's a difference between trusting Carol's past and present behavior (that she's only issued trustworthy certificates so far) and trusting her behavior indefinitely into the future (e.g. that her records will never be subpoenaed by police).

Answer 3

Emphasis mine:

Alice's public key is useless to Bob unless he can prove that the public key came from Alice. To do this, Bob and Alice can establish a secure channel to exchange Alice's the public key, but this same channel can equally be used to exchange a symmetric pre-shared key, so this is effectively identical.

A 'secure channel' generally means that it is resistant to eavesdropping. Your example in this context most definitely means they do not need a secure channel to exchange public keys. The whole point of a public key is that it can be transmitted publicly and shared. The New York Times could publish a public key on the front page, and anyone could use it to send information to them securely. The more public, the more comfortable you can be that you are talking to the right person. If a symmetric key becomes public, it can be used to decrypt any captured communications. Public keys are meant to be public. The more public they are, the more sure you can be that you are talking to the right person.

Say I do the following:

1. Sign the email contents and send my public key with every email I send
2. Post my public key to social media: Instagram, TikTok, Facebook, Twitter, Youtube, Github, Reddit, Discord, Twitch
3. Have my public key visble on multiple websites I create and maintain
4. Take out a full page add in the New York Times displaying my public key
5. Send out signed and notorized documents to everyone I've ever met with my public key
6. Get a tattoo of my public key fingerprint on my forehead, which is visible in any photograph of my face, including polaroids kept by my family members and photos and videos published on their own social media.

So now I send you an email with my public key attached and signed with my private key. You can compare the public key or it's fingerprint to what is publicly available using any of the methods above, and use it to verify the owner of the corresponding private key (me) sent the email. You can then reply and encrypt your reply using my public key and only I will be able to decrypt it.

You can also have someone else who's public key you already have and trust (Carol here) 'sign' a message containing the public key and a message saying it belongs to me. As long as you trust Carol and the method by which you obtained her public key (possibly in the distant past), you can add to your trust level the fact that Carol thinks you have the right key for Alice.

Alice's public key is useless to Bob unless he can prove that the public key came from Alice.

I wouldn't say it's useless. It depends on what you mean by 'prove'. Proving in a mathematical sense that the key came from a particular person is impossible because you always have to put your trust somewhere, even if it is meeting them face to face and having it be someone wearing one of those Mission Impossible masks. You can use it to encrypt a message to the sender. Even if it isn't Alice, it prevents anyone else from being able to decrypt it, such as a rogue sysadmin at your or Alice's ISP.

The more encrypted communication that happen between Bob and Alice, the more confident they can be. If Bob and Alice exchange emails for years and always encrypt them for example, then if Bob has the wrong key, Alice will never have gotten a message she was able to decrypt. Since they are public, Bob can also ask Carol for Alice's key's fingerprint to make sure it matches his own. He can also verify directly with Alice that he has the right key in some way that he has the right key (face-to-face meeting, phone, text, etc.) and not worry about the conversation being intercepted affecting the security of the information he encrypts.

Also in your symmetric key example using Carol, Carol now also has the symmetric key and could decrypt your communications with Alice. The nature of a public key is that there can be a web of people that you can use to verify the public key associated with Alice, and all of this can be done in public for other people to see. That in fact increases security because anyone that sees someone trying to pawn off a fake key for Alice will have a lot of people that know the correct key and will bring attention to the fake.

And Carol does not have to be involved in the communications at all between you and Alice using public key cryptography. The exchange of information can be asynchronous and distant in time. Imagine this scenario:

1. Bob goes to high school with Carol, where they exchange public keys in person. They use these over the years to encrypt emails to each other. Bob has Carol sign his public key with her private key to authenticate that it belongs to [email protected]. Bob can provide this signature to anyone that trusts Carol to validate his identity according to Carol.
2. Carol and Bob go off to different colleges. Carol is in a sorority with Alice and they also exchange public keys and communicate using encrypted email. Carol signs Alice's public key with her private key to authenticate that it belongs to [email protected]. Alice can provide this signature to anyone that trusts Carol to validate her identity according to Carol.
3. Five years after college Carol gets married. Bob and Alice meet for the first time at the wedding and exchange email addresses. Carol is busy with her wedding and doesn't know they even met.
4. Alice sends Bob an email from [email protected] with her public key and Carol's signature of it that she obtained 5 years ago in college to verify it is her
5. Bob can check the Carol's signature using the public key he received back in high school, and can verify the public key he received in the recent email does belong to [email protected], at least according to whoever has Carol's private key or had it when the signature was generated.
6. Bob can now send Alice emails encrypted with her public key that only she can decrypt. He should now send her his public key and the signature Carol created for him back in high school. Then Alice can verify Bob's key using the signature and Carol's key she received in college, and encrypt her replies to bob.
7. Anyone can send Alice an encrypted email, but to fake the recipient they would have to collaborate with Carol (or someone else that Alice trusts) to create a signature she will accept.

In this scenario Carol doesn't even have to be aware that Alice and Bob are talking, yet by using her private key to create a signature, anyone else with Carol's public key can use that signature to authenticate that Carol's private key at some time signed that information.

If someone intercepts Alice's email to Bob with her public key, it doesn't affect the security. They can't replace the public key without invalidating Carol's signature. If they try to create a fake signature, Bob won't be fooled because he's had Carol's public key since high school.

Answer 4

The key difference is simple: public-key cryptography eliminates the need for the channel used to communicate the public keys to be secure against eavesdropping.

---

All that Alice and Bob need to do is exchange public keys and verify the authenticity of those keys. Assuming ‘perfect’ public key encryption, you only need two other criteria to be met for subsequent communications using those keys to be secure:

• Messages need to be signed using the sender’s private key and the signatures need to be verified using the corresponding public key. If this is done, then disclosure of the public keys is irrelevant to security, because you cannot spoof messages. If for some reason you don’t need authentication of messages, this can be ignored.
• An active attacker must not be able to modify both the message used to share a public key and the message used to prove it’s authenticity. If this criteria is met, then it becomes impossible for an attacker to effect a MitM attack on the subsequent communications (because the key won’t validate in the first place).

That second criteria seems to be the one that’s tripping you up here. It’s important to understand that it does not require that either or both messages involved in sending a key are secret, just that at least one of them is provably authenticated.

That can be achieved by using a trusted third-party for authentication of at least one of the messages, and this is, in fact, the primary way that most public key crypto systems work, though the way they do it varies a bit. Some use an active intermediate agent to relay the keys like you describe, others use a chain of trust rooted in some specific entity (this is how TLS and other systems based on X.509 work), some use a graph model where keys are signed by multiple other keys, each of which can have a varying degree of trust (PGP works this way in theory, though in practice it often devolves into a chain of trust model instead).

---

Looking at this a different way, all that needs to be conveyed by each participant in a public-key crypto system is:

• Their public key.
• Some proof linking the public key to their identity.

Public keys are, by definition not secret information, so they don’t need to be transmitted over a secure channel. And the proof of identity generally is not secret either as it is implemented in most systems (it’s usually a matter of relaying the key fingerprint through some authenticated secondary channel that an attacker is highly unlikely to be able to compromise).

Because none of the information is secret, encryption is not required at all.

Answer 5

With asymmetric encryption, the private key and public key are interchangeable. You (or your software) simply choose one to designate as private and one as public at their creation. In other words, either can be used to encrypt a message that the other one can decrypt.

In your example, if Bob wants to communicate with Alice then they each send their public keys to each other in the clear. Alice can then write a message and encrypt it with her private key and then again with Bob's public key.

Bob receives the double encrypted message and can decrypt the outer layer with his private key. Because only he can decrypt this layer, it is secure against other people reading it. He then decrypts the embedded encrypted message using Alice's public key. Doing this ensures that only a person with Alice's private key could have encrypted it. Within that message Alice could provide whatever bonafides Bob needs to prove she is the Alice that Bob intends to communicate with. Going forward Bob can be assured that (assuming Alice maintains her private key as private) that any messages he receives that works in this manner came from Alice.

Answer 6

Alice's public key is useless to Bob unless he can prove that the public key came from Alice. To do this, Bob and Alice can establish a secure channel...

Yes, they could establish a secure channel, but that's not the only way. For instance, Bob could ask Alice to encrypt his name using her private key and send it to him. If he's then able to decrypt the message using Alice's public key and read his own name, that would indeed prove that the public key matches Alice's private key.

Such scenario is impossible with symmetric cryptography.