There is a fundamental rule here: in order to create a secure channel through an untrusted network, both ends of the channel must both possess some prior information that has been pre-shared through a trusted mechanism. The function of a Certificate Authority is to provide this shared trust without the two communicating entities needing any prior knowledge of each other in particular.
First, consider how you might set up a secure channel between two people exchanging messages over a long wire. If the two people know nothing about each other, they have no way to prove that the person on the other end is who they say they are, and no way to prove that a message sent from one end was not tampered with before it got to the other end. Since they share no common information, they cannot encrypt their messages either. This is a fundamental problem that cannot be bypassed.
If the two people communicating met in person, beforehand, they could share some secret information that allows them to verify the authenticity of messages, e.g. by agreeing upon a password and using that to generate encryption and authenticity keys. This is called a "pre-shared key", or PSK for short.
If the two people can't meet in person, they might establish a PSK using an existing channel that they both trust. For example, they could talk to each other on the phone if the types of attackers they're worried about aren't able to tap phones. This is known as an out-of-band (OOB) channel.
Certificate Authorities effectively act as a trusted out-of-band channel, but instead of using them to share keys directly (which doesn't scale and is problematic from a security perspective) they instead use the CA as a root of trust that provides each user with enough trusted information to build secure channels with each other, without needing a PSK or having to share any actual messages with the CA. In this way, CAs are effectively proxies for trust - if Alice trusts the CA, and the CA has validated Bob's identity, then Alice can trust that she is communicating with Bob.
If you think about a client connecting to a server over the internet, there are a ton of routers along the way that are untrusted. The server knows nothing about the client beforehand, and the client knows nothing about the server other than its name. However, the client has a trusted set of CA certificates installed on their system, and the server's certificate is signed by one of those CAs. As such, the client can trust that they are communicating with the real server, and not someone else. In practice, the "trust" is implemented and enforced using cryptography.
In your example, both clients could communicate securely by using a trusted CA, assuming that the CA performs their job properly and does not incorrectly issue a certificate to the wrong person.
Here's an example:
- Alice and Bob both generate an asymmetric (public/private) key pair, and a certificate signing request (CSR).
- They send the CSR to the CA, along with proof of identity. The CA verifies that the name on the CSR matches the name on the proof of identity, and issues a certificate to each of them. This certificate is signed using the CA's private key, and contains the user's name and public key.
- Alice and Bob both register their certificates with the server.
- Alice tells the server that she would like to talk to Bob. The server sends over Bob's certificate. Alice can look at the certificate and verify it against the CA's trusted certificate. If the name on the certificate says "Bob", and the signature is valid, she knows that this is an authentic copy of Bob's certificate.
- Alice encrypts a message using Bob's public key, from the certificate. (In practice a hybrid cryptosystem is used, but that's an implementation detail.) She signs the encrypted message with her private key. She asks the server to send it to Bob.
- The server sends the message to Bob, and says "this came from Alice".
- Bob asks the server for Alice's certificate, and the server sends it.
- Bob looks at the certificate, checks that the name on it says "Alice", and verifies its authenticity using the trusted CA certificate. If it is properly signed, he knows that this is a legitimate copy of Alice's certificate.
- Bob uses the public key from Alice's certificate to validate the signature on the message that was delivered from Alice. If it matches, he knows that the message was not tampered with.
- Bob now uses his private key to decrypt the message from Alice. He now has the message.
The server at no point has access to the plaintext message. If the server sends its own certificate instead of the real one for Alice or Bob, the user can see that the name on the certificate either does not match the name of the person they were expecting to talk to, or that the certificate was not properly signed by the CA. If the server attempts to modify the message in transit, it cannot falsify the signature, because it does not have access to the user's private key.
This does not completely protect the channel from attack, though. The server can still substitute previous legitimate messages into the conversation, using a replay attack. Since the previous messages are properly signed, and the server is not modifying the message itself - just substituting the message for a different one - this allows the server to change the meaning of the conversation without changing the content of the individual messages. Consider this chat:
Bob: How much did your car repairs cost?
Alice: $1300
Bob: Damn, that's a lot.
Alice: Yeah :(
[conversation continues]
Bob: Hey, the contractor is asking for more money than I expected, how much are we supposed to be paying them?
Alice: Huh? We already paid them in full.
Since all messages are legitimately signed, the server can take any previous message and substitute it in place, as long as it is going from and to the same people, in the same direction:
Bob: How much did your car repairs cost?
Alice: $1300
Bob: Damn, that's a lot.
Alice: Yeah :(
[conversation continues]
Bob: Hey, the contractor is asking for more money than I expected, how much are we supposed to be paying them?
Alice: $1300
The server has not forged any signatures, but it has changed the meaning of the conversation.
This can be resolved in a number of ways, such as by the client including a random message ID at the start of every new conversation, then incrementing that ID after each message. This ID is inside the encrypted message itself, which is signed by the user's certificate, so the server cannot see the ID or tamper with it. If the server tries to replay a message out of order, the client can detect that this happened:
[350785249] Bob: How much did your car repairs cost?
[540582471] Alice: $1300
[350785250] Bob: Damn, that's a lot.
[540582472] Alice: Yeah :(
[350785251] Bob: Hey, the contractor is asking for more money than I expected, how much are we supposed to be paying them?
[540582471] Alice: $1300
Notice how the message IDs for Bob go in order: 350785249, 350785250, 350785251. But, for Alice, the message IDs go: 540582471, 540582472, 540582471. This allows Bob to detect that Alice's previous message was replayed.
This also protects against omission, i.e. the server removing a message from the conversation by choosing not to deliver it. When the next message comes along, the message IDs will not be in sequence because a message was not delivered.
In practice this is usually implemented in a more secure way than just ID numbers, but this illustrates the point more clearly than a full technical description of replay protection.
The security of this system hinges on both users trusting the CA to only issue certificates to legitimate users who have been properly identified. The mutual trust in the CA is what allows them to create a secure channel.
An alternative is for the users to pre-share their certificates or public keys through a trusted out-of-band system. This is how email encryption works, for the most part. Users may publish their public keys on social media, on a USB stick through the mail, via email in an encrypted ZIP archive with a password shared over the phone, or even directly in person, depending on what level of security they require. All that changes here is the mechanism of establishing prior trust.
