My particular problem has to do with secure communications over a mesh network (http://en.wikipedia.org/wiki/Mesh_network), in particular man-in-the-middle (MITM) attacks. The difficulty is that mesh networks require intermediary nodes (that is MITM) to properly route messages.

By secure communications I mean that any two nodes in the network can first agree on a key and then use that key to encrypt their communications. I would like to do this from a cold start, nodes have no prior knowledge of each other, and without a central authority or a PKI for certificates.

At first I considered using either the YAK key agreement because the protocol only requires one round. However it still needs a PKI to distribute and authenticate certificates which I would like to avoid.

I know about RADIUS servers (worked with them in the past) but it requires a central server which might not be easy to access from anywhere in the network. If it was not for the centralized server, this would be my solution of choice.

I also know about the notary model, but in a mesh network it can happen that all messages to node A must first be routed through node M. Thus the MITM does not allow to get different views from the same certificate.

Are there any other alternatives to the distribution of certificates ?

If I relax the restrictions a little and accepted that each node trusts some subset of the nodes. Then each node could be given, before connecting to the network, a list of trusted certificates. Nevertheless I would like the subset of trusted nodes to change with time. Are there feasible solutions for this ?


Machine A wants to talk to machine B "securely": it wants to be sure that it talks to the right "machine B". If it can do that, then it can do Diffie-Hellman with B and then use the key with the usual crypto tools. But all of this works or is even defined properly only if there is a way by which "machine B" is, from the point of view of A, distinct from any other machine (e.g. C). Without prior knowledge, "B" is just a name and any other machine can logically claim to be "B".

In other words, you need to have a central point somewhere (not necessarily as a physical system; it could be a central concept) which defines that there is a single machine called B, and pinpoints that machine among all others. With an authentication server (your RADIUS example), the central point is indeed a machine which all others trust, and use. With a PKI, the central point is administrative; it is whatever mechanism is able to give a name to each machine, and prevents two machines from claiming the same name.

Certificates are ways to transfer trust. A certificate binds a name to a public key; from the point of view of A, if a certificate has been signed by D and contains the name E and a public key, and A knows D's public key, and A trusts D for not goofing up, then A verifies the signature on the certificate and thus gains some knowledge on E's public key. The certificate is an assertion from the certificate issuer (D) about the binding between a name (E) and a public key.

There are mostly two ways to do PKI:

The two ways illustrate two faces of a trade-off. The tricky point is what I wrote above about "goofing up". A WoT, initially, looks like a good idea: machine A initially trusts its own key. Then it may know from some out-of-band mechanism (A met D in a bar) the public keys of a few other machines, that it trusts. Then A may know the public keys of other systems (e.g. E) on virtue of their keys being signed by D, and the process extends recursively. This is decentralized and works as long as A can find at least one chain of certificates from itself to its ultimate target B; this process can be helped with public key servers, which are just repositories for certificates. The beauty of the thing is that there is no need for additional protection: a certificate is valid if its signature matches, regardless of how the certificate has been obtained. Public key servers need not be trusted in any way.

The inherent problem with WoT is trust dilution. That A knows D's public key does not mean that A _trusts_ D for correctly binding names with keys. At least A met D "in person" and could have some idea about D's gullibility. But A does not know E at all; A only knows what D says in the certificate that D signs for E. Thus, A knows E's public key, but not E's trustworthiness.

Hierarchical PKI manage the trust business by using specialists: certificates are issued only by authorized entities (the Certification Authorities); there are few of them, and they ultimately respond to a central Root CA which is like God for these things. This is very centralized, and this keeps CA in line and allows trust not to be as diluted as in the case of the WoT.

So this hierarchical/WoT choice highlights the trade-off between trying to do some decentralization (that's the point of mesh networks), and avoiding trust dilution. Choose your poison. The theory of WoT is that you can counter dilution by making the graph superconnected: if A finds dozens of certificate chains which all point to B with the same key, and all these chains go through distinct nodes, then B's alleged key is probably genuine.

At least there are useful mitigations. For instance, memory. A given node can remember the public key of another node. That's how it is done with SSH. The very first connection from A to B still requires something to ensure that A uses the right key from B, but afterwards it can just reuse it.

To a large extent, the notary model, as illustrated by Convergence, is a cross between offloaded memory (the notaries remember public keys and complain loudly when a node appears to change its key too often) and a WoT-like trust (when several notaries assert the same key for a given node, it is probably genuine).

In any case, the naming must occur somewhere. It can be a decentralized "somewhere" as in the WoT (a machine B can be "B" if it convinces enough other machines that its name is "B") or something centralized as the X.509 PKI (the central authority gives a name to each machine and there is no discussing it). But it must happen at some physical or conceptual level. Otherwise the question is ill-defined.

  • A little after posting the question, I realized that it all boils down to tying identities with keys. As you have pointed out. I even looked up ID based encryption, but it still requires a centralized (and highly trusted) server just like RADIUS. – ngoncalves Aug 27 '13 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.