We want to send an encrypted message to Alice. We can ask her a public key over the network, encrypt with it a message and send that message back. It is bad, because someone can pretend to be Alice and send their public key. The solution said to be PKI. So, we connect to PKI service (for example Verisign) and get the public key. But how is that different from asking Alice directly? Someone can interfere with our connection and send the certificate of their own. I am obviously missing something...
1) Certificate authorities are just one method of creating pki. Pre distributed certificates by a side channel and Web of trust are others. Your question should be, "How can we trust certificate authorities?"
2) That is not how it works, one only connects to verisign to check if the certificate has been revoked. The certificate comes from the same server as you are connecting to and contains verisigns' digital signature with verisigns' public key distributed with the web browser or operating system (or both). In the root certificate store.
As for being able to trust certificate authorities, well it is a big question, there are rules that each browser manufacturer/operating system has before they allow the public key in the root certificate store. The rules state required audits and rules as to when a root certificate should be removed. DigiNotar was a dutch ca that did have it's root certificate pulled. However often the people checking the CAs do not want to pull the bigger ones without 100% proof as websites that use them will instantly break.
Ultimately we have very few ways other ways to manage it at the scale we currently are, though some have tried to prototype other solutions like convergence.
Let's say for example I have a GPG key I use to sign all my messages and emails.
I want to distribute the public key so people can verify that the messages are actually coming from me. What I can do is place the public key on my website so anybody can go there and get the keyfile. If I serve this connection over HTTP, any attacker can intercept the traffic and replace the keyfile, essentially performing a MITM attack.
So what I can do is serve my website over SSL. I can then direct people to my website and they will be able to download the keyfile. If any attacker intercepts the traffic and performs a MITM attack, the web browser will display a warning informing the user that he is not connected to the right server.
In a PKI, the signatures on digital certificates don't create trust; they transfer it. You trust the information contained in a certificate (a name/public key association) because you verified the signature on the certificate relatively to a Certificate Authority's public key... that you trust. You have to start somewhere, with a public key that you inherently trust, i.e. not one that you just downloaded. That root public key is indeed called a "root CA" or "trust anchor". Your Web browser and/or operating systems comes with a few dozens of "trusted CA". Your computer knows the public keys a priori: they come with the OS code, on the OS installation CD-ROM, or preinstalled on the computer, or downloaded with OS updates (which are signed). You can trust these keys to be genuine about as much as you can trust the OS code for being correct.
As for the other side of trust, i.e. whether you can assume that Verisign is not hostile or too gullible... well, Microsoft took this decision for you. Microsoft and Verisign are bound by a mutual contract, and you are bound with Microsoft by a contract (I am assuming here that you use Windows). If Verisign becomes hostile and signs fake certificates, then your security will be endangered; you could then sue Microsoft for a few bucks, and Microsoft would sue Verisign for some billions of bucks. Betting that Verisign and Microsoft will keep each other in line is not that bad a bet.
We might trust Verisign, goDaddy, or Digicert. But a MITMA might render that trust useless as there are quite a few ways to let the browser and therefore the user believe he is in save waters. It is possible to spoof the certificate chain or spoof a revoked certificate as was demonstrated quite eloquently by Mike Marlinspike at Defcon17 ( http://www.youtube.com/watch?v=ibF36Yyeehw ).
So no, you can't trust VeriSign.
Btw. VeriSign has been hacked in the few years before it was acquired my Symantec.