How to prevent a man-in-the-middle attack in case of a compromised server?

Question

Imagine that a server is serving public keys of the users to their partners to make encrypted communication possible. However, the server does NOT have access to the private keys..

Anyway - imagine the server is hacked and it sends not the requested public keys:

Alice requests Bob's public key
Server sends Eve's public key

Bob requests Alice's public key
Server sends Eve's public key

Alice sends a message to Bob
Server unpacks message, reads it and repacks it -> sends to Bob...

Bob sends a message to Alice
Server unpacks message, reads it and repacks it -> sends to Alice...

My question is - how to prevent such abuse? How can Alice be sure that she's using Bob's public key and vice versa?

Answer 1

Under the scheme you just proposed, you can't. The key here (no pun intended) is if the method used to verify the validity of the keys is compromised, you lose.

SSL tries to avoid this by creating a signature chain - some (very carefully guarded, and verified by other methods) key signs another key, signs another key, signs Alice's key. By verifying each step in the chain you can (in principle) know that the chain is valid - but if the private key along any step in the chain is compromised, you lose.

PGP (aka GPG) tries to solve the problem in a different, but similar way - keys can be signed by any number of other keys, forming a graph (called the web of trust). You select some keys that you have confirmed valid by, for example, verifying them in person, and mark them as trusted. Then any keys reachable by less than N steps (and/or from M distinct paths from different trusted roots) are also considered valid.

If you're really paranoid, you can, of course, physically hand the key to the other person. Of course, they have to be sure it's not someone disguised as you...

That said, the only truly foolproof way of verifying the validity of a key is generating it yourself... unless your hardware/OS/compiler/brain is compromised too :)

Answer 2

The crucial part missing here is authentication. Alice needs a way to know that she is really using Bobs public key. One way would be to exchange the keys personally but that is not always possible.

That is what the Web of Trust is for. Other parties can sign the public key of a user if they are sure that this key belongs to him. If enough (3) of your other contacts (which you trust) signed the public key of Bob, you can be relatively sure that it is his key.