This is a very good question.

Public-key certificates have the purpose to authenticate an assertion, namely that you are communicating with the entity that you intend to communicate with. Specifically, guarding against a Man-in-the-Middle attack (MitM) is done by authenticating the key material that is used.

Your issue is the following. Say A and B want to establish a secure channel using their public keys $K^\mathsf{pub}_A$ and $K^\mathsf{pub}_B$. If they haven't yet established a secure key exchange, a plain exchange is prone to a MitM. So you utilize a trusted entity (CA in PKI, KDC in Kerberos) that vouches for authenticity of the exchanged public keys by way of certificates (see below). Asymmetric crypto has the great advantage that a certificate, once issued, can be reused many times for many communication peers. Compare that to the symmetric case where you cannot reuse Kerberos tickets - that's one of the reasons why certificates have a much longer life time than Kerberos tickets. The only problem that remains is how to establish a secure channel between A and CA and B and CA. **This cannot happen ad-hoc in a trustworthy way**, which is the central point of your question.

So it seems that by utilizing a CA you have just moved the problem around without any progress (even worse, you introduced a new critical dependency), but there is one important difference: You need to establish a secure channel only with one _trust anchor_ - which makes the problem feasible in the first place.

You need to take a special route to establish trust between you and a trust anchor. This can be by meeting in person or other suitable out-of-band mechanisms. In Windows Active Directory environments this is you being authenticated on a computer joined to a domain using your credentials. The trick here is to design the process such that it scales well. However, there are still many leaps of faith to make:

In principle, a public-key certificate works like any other kind of certificate, including the ones in the real world.

1. If some authority A asserts some property $\mathsf{Property}(X)$ for some $X$
2. If A publishes the assertion in a kind-of unforgeable way
3. If some entity Y trusts A

then Y has virtually no choice but to believe that $\mathsf{Property}(X)$ is true.

For public-keys in a X.509-style PKI that means, A is a CA, $\mathsf{Property}(X)$ is a claim along the lines of "the key $K^\mathsf{pub}_X$ herein belongs to entity $X$" and the unforgeable way is via secure digital signatures with adequate key-lengths (for simplicity, I assume that all relevant algorithms are implemented flawlessly...).

Moreover, each of the following conditions are crucial:

4. Y needs to have a genuine copy of CA's public key.
5. CA must be trustworthy, which means, they know what they do and they are not corrupt or being corrupted themselves.
6. All devices involved are trustworthy (i.e. not infested by trojans, backdoors and such)

Each of those is quite tricky and hard to achieve - if at all.

### Acquiring a public key in a trustworthy way

I think this is the issue that gave rise to the question. Since anyone can create arbitrary key pairs and from this, create arbitrary certificates, the trick is to distinguish between the wheat and the chaff, i.e. to tell genuine and fake root certificates apart. This can be done by secure channels, but for that you need some kind of trustworthy "seed". For instance, if you consider how the Web Of Trust works, particular the legendary PGP key signing parties, all involved attendees meet in person and mutually check photo IDs (another brand of certificate...). However, that does not scale.

On the other hand, if you consider how root certificates are distributed in web browsers and operating systems, you find that you depend on the software vendors. Now, once upon a time there was the vision of a global PKI with one ultimately trusted root, where a copy of the public key or digital fingerprints thereof would be virtually everywhere posted (e.g. in printed publications). Of course, there was/is no agreement conceivable on who that could be, and thus this position remains vacant. Well, not quite, the software vendors silently filled that vacancy, and this seems to be accepted on the ground that there is nothing better in sight for the moment, and somehow, this seems to work (but see below).

Closed organizations like enterprises and government bodies are a special class of cases - whenever you enter the organization, you get your PC, your accounts, and alongside you get your key pair and the public key of the organization root CA (more precisely, this is typically stored in the Windows Active Directory, where the AD architecture with its protocols like Kerberos provide the secure channel).

### CA trustworthiness

Running a root CA properly is not easy, especially since they are very attractive attack targets. You need detailed procedures, background checks of the staff, regular training, suitable rooms, etc. etc. etc. And yes, there are audits by the browser forum and possibly other bodies, but the famous glitches of Commodo and DigiNotar show how hard it is to run a CA properly.

The humorous [application of "Honest Ahmad" for a root certificate][1] sheds some light on the weaknesses of the whole construction.

### Device trustworthiness

This is another property that is hard to achieve. General-purpose hardware with general-purpose OSes allow you to install any software that you want - and coincidentally, any software that you don't want, including malware. The average textbook describes an encryption process (say) as _Alice encrypts message M with her key K_ or something like that. But who is Alice? If that refers to a person, then the statement is to be read as _Alice instructs her computer to ..._ . Given the Trojan malware that we saw in the past (particularly Trojans for "alternative" online banking) it is easy to conceive that the computer does something quite different than intended or expected while pretending otherwise.

### Now what?

To be honest, nobody knows. Bruce Schneier and others have written a lot about that. But as far as I know (I am not closely watching, though) the whole construction was never thoroughly contested in the courts. Until then it holds what I said earlier: The existing architecture somehow works, despite the many leaps of faith you have to make, and alternatives that are _widely_ accepted are not in sight.


  [1]: https://bugzilla.mozilla.org/show_bug.cgi?id=647959