5

Public-key cryptography secures communications provided that you use pre-shared public-keys.

The problem is how to share these public-keys while maintaining authenticity? How can we be sure that while sending the key an active attacker isn't replacing the transmission with their own public-key.

The answers that I find to this problem involve using some kind of authority or using a good cryptographic hash function then manually verify the integrity of the public-key by hashing it at the other end point and comparing the hashes.

However an intelligence agency may have been able to subvert a CA and manually verifying hashes doesn't scale well at all.

Providing that the two end-points themselves are secure, and assuming that everything in the middle isn't (a CA sits in the middle), how can we distribute public keys?

This question is only involving the signal between two end-points, not the integrity of the end-points themselves.

8
  • You just say "a CA" can be subverted are you ruling out ALL solutions that involve a 3rd party (for example a "Web of Trust", or a private CA)? Oct 9, 2013 at 4:40
  • Ideally yes, but if there is a solution that relies on a third party/parties that is considered hard enough to subvert as to be considered impossible then that will be satisfactory but I cannot imagine something that would be able to satisfy that to be honest.
    – Shannen
    Oct 9, 2013 at 4:59
  • A PKI infraestructure with X.509 digital certificates is an option? Oct 9, 2013 at 6:03
  • Requires either a certificate authority (see my point on CAs) or signing your own certificate which still requires the client has a copy of the root certificate (terminology may be off here) which then leads to the problem "how do I distribute the certificate?".
    – Shannen
    Oct 9, 2013 at 7:41
  • @Shannen How do you define authenticity? If you want to bind a nice name to a public key you need to find a way to verify if the owner of the private key is the owner of that name. Oct 9, 2013 at 8:10

2 Answers 2

4

You can't, that is precisely why we have trust networks: PKI and WoT.

A public key alone has no use, you must tie that key to an identity for it to be useful. It is this association between key and identity that these complex trust systems aim to make provable, or at the very least, strong.

In the case of PKI, a list of trusted root certificates is known before any communication begins. This list is installed into your OS, or in the case of some browsers, downloaded within the browser itself. This is one reason it is a good idea to check the integrity of a browser download. In Firefox, for example, you can view the installed root certificates under Preferences -> Advanced -> View Certificates.

4
  • 1
    Thank you. I thought as much. I'll research WoTs. I wanted to try and avoid "authorities".
    – Shannen
    Oct 9, 2013 at 9:28
  • If I want to set up a PGP link with someone I know, I will ask them to send their public key, and then I will call them and read it out over the phone to confirm it is correct. Voices are pretty hard to synthesize in real time :P
    – lynks
    Oct 9, 2013 at 9:51
  • Yeah that's what I would do but the situation I'm asking in the context of is a many-to-many pattern, not small scale and needs to be completely transparent to the user.
    – Shannen
    Oct 9, 2013 at 11:45
  • Could you sneaker net the public key? its not a fast or convenient but then there would be no third party.
    – daniel
    Jun 21, 2017 at 7:33
7

Out of the blue, there are only strangers. Two people who don't know each other beforehand cannot, by themselves, establish a secure communication free of impersonation by third parties, because that's not defined. I cannot make sure that I talk with "Bob" if I have no reference framework for who or what "Bob" may be.

Suppose that Alice wants to talk securely with Bob. She has an a priori notion of "Bob". She does not want to talk to just any Bob, but with a specific Bob. Let's take an example: Alice wants to do business with Acme Ltd., a "well-known" corporation. From the point of view of Alice, there is a large body of evidence that there is such a thing as a corporation known as Acme Ltd, which sells a specific kind of goods and/or services that Alice is interested in. Alice thus wants to talk to an authorized salesman from Acme Ltd. Authorized by whom ? By Acme Ltd, of course. If Acme Ltd. says that Bob is the man to talk with, then Alice wants the public key of Bob, that Bob, the one and unique Bob from Acme Ltd. That Bob is defined as "the Acme Ltd salesman". It is Acme Ltd who asserts Bob's identity. In that case, sending to Alice the public key of Bob becomes naturally Acme's job.

Thus, Alice will receive Bob's public key from Acme Ltd. How does Alice know that what she receives really comes from Acme Ltd, the corporation ? There again, this depends on Alice knowing Acme's public key, bound to Acme's identity as asserted by... whoever is in position to give names to corporations. This usually is a chamber of commerce: the corporation is registered with that chamber, and the chamber is the entity which says "this corporation bears that name". Thus, the chamber of commerce should send to Alice the public key of Acme Ltd. Of course, this sending will use some sort of authentication (e.g. a signature) so that Alice knows that it really talks to the actual chamber of commerce.

So Alice now needs to know the chamber of commerce's public key. Since chamber of commerces tend to be public entities, this gets us to the state or country which contains that chamber of commerce. And so on...

Here I am retracing the classic hierarchical public-key infrastructure model: you get public keys from the entities who are in charge of defining names. There could be some sort of delegation. For instance, if Alice visits Acme's Web site, and the Web site uses HTTPS (i.e. SSL), then that Web server will present a certificate. That certificate is signed by a Certification Authority, which is not operated by the chamber of commerce; instead, it is a private entity who accepted to sign the certificate because Acme's sysadmin presented to the CA some documents, emanating from the chamber of commerce, which demonstrate that the certificate request really comes from Acme Ltd.

With some kind of domains (notoriously the .com, .org... domains), the coupling is looser: a certificate will be issued to a requester as long as he demonstrates that he technically controls the relevant domain. It is assumed that if there was some foul play (e.g. DNS poisoning) then the true Acme Ltd will complain at some point, and certificate revocation will be employed to fix the issue. This is still hierarchical because the chamber of commerce, state... will be invoked during litigation to demonstrate that there is a corporation named Acme Ltd, and the name "Acme" really belongs to Acme Ltd.


The naming, in the legal sense of the term, is intrinsically hierarchical. It is a monopoly of modern states; indeed, it was a cause of conflict in many countries during the last two or three centuries (in older times, names were handled by the "community", usually the local church, not by any central state). However, a decentralized, community-driven naming can still be used.

For instance, suppose that you want to send a private email to Linus Torvalds, creator of the Linux operating system. What notion of identity will you use ? Do you want to talk to "Linus Torvalds", as defined by the Finnish authorities (he is from Finland) ? Or do you want to talk to the famous Linus Torvalds, creator of Linux ? This is a case where the notion of identity is driven by fame, i.e. Linus Torvalds is whoever is designated as Linus Torvalds by a lot of people.

This leads to the Web of Trust. This uses the same concept of certificates as the PKI (a certificate being an object containing a name and a public key, and signed by someone). However, in the WoT, everybody acts as a CA. We don't use "naturally designed" CA. Every single person can simply assert bindings between identities and public keys.

How can a WoT provide any kind of security ? Liars exist. Alice may build a chain from her to Bob:

  • Alice knows Charlie's public key (Charlie is a friend of Alice).
  • Charlie knows Darren's public key, and has issued a certificate for that: the certificate contains Darren's name and Darren's public key, and is signed by Charlie.
  • Darren knows Ernest's public key, and has issued a certificate for him.
  • Ernest knows Bob's public key, and has issued a certificate for him.

Alice thus knows Darren's public key provided that she trusts Charlie for not being a liar (or being very gullible). Charlie is Alice's friend, so Alice may make some good assumptions on Charlie's reliability. Now Alice knows Ernest's public key, provided that Darren is not a liar. So Alice must trust not only that Charlie is not a liar, but also that Charlie is good at judging people and would not have issued a certificate to a liar. Then we get to Bob: for that, Alice must trust that Charlie is not a liar, would not have issued a certificate to a liar, and would not have issued a certificate to someone who would accept to issue a certificate to a liar. This begins to entail a lot of nested assumptions...

The important point is that the WoT relies on community-driven identities: an identity is defined by a lot of people agreeing on it. The WoT is secure not because you build and verify one chain, but many chains which go through distinct people's keys, and they all agree to assert that Bob is Bob. This is the oft-forgotten necessary condition for security -- and, in practice, it does not work well (or at all). You can already consider yourself lucky if you can build one chain from you to your intended recipient.


So there are always "authorities". With a classic hierarchical PKI (as is used, for instance, in X.509 certificates for SSL servers), the list of such authorities can be known and controlled by each user (this is the "trusted root" certificate store in his OS or browser). With a Web of Trust, the authorities are "the people" and security relies on "the people" to be, on average, honest (there can be liars, but most people are not).

Unfortunately, the Web of Trust will yield enough security only at great expense: the graph of certifications must be very redundant, and whenever you are trying to validate the purported public key of someone, you must gather many distinct chains, and verify them all. If you do not do that, then Evil People (insert your favourite three-letter agency here) could easily bootstrap a fake identity by bribing or fooling two or three persons.

So you cannot avoid "authorities", but you can choose your poison. There is, though, a powerful mitigation called memory: if, at some point, you obtained the public key of someone, then you can remember it and use that key thereafter. This is the model of SSH (the .ssh/known_hosts file) and it works well with usual OpenPGP implementations (that's called "your keyring"). It is not perfect, though, because memory-based PKI must still be bootstrapped (to remember a public key, you first have to learn it) and does not work well with key renewal or revocation.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .