How to implement a Web of Trust, or something similar?

Alice get a public and a private key from the RSA guy.

Bob need to send to Alice a nuclear secret code (or his babysiter's phone number).

Bob ask for Alice's public key on the server, but the evil Eve intercept the request and send her key instead.

How to avoid those situations?

Someone from StackExchange on Crypto told me:

Linking identity to public keys is out of scope for pure crypto. Cryptography can't know who you mean with "Alice". Exchange it in RL, have somebody else you already trust tell you(either web of trust or CA),...

Well, how do I implement that (in PHP/MySQL) ? Can someone explain to me how to implement this or how this is working so I can implement it?

Thank you

  • If you do a quick search of SE you will find dozens of references to the web of trust 'problem'. You may find luck starting there.
    – grauwulf
    Commented Jan 24, 2013 at 18:47
  • 1
    From a programmatic Point of view, nodes that link to nodes that link to nodes, and creating a summary view (inner join) of this data may limit your performance. This is a tricky problem to solve. ... I'm also working on the same thing Commented Jan 24, 2013 at 22:50
  • Yeah I'll try to work on something to avoid the performance hit. If you came up with anything, tell me ;) Commented Jan 25, 2013 at 2:46

2 Answers 2


The basic idea of the web of trust, as used in PGP to send messages, is peer validation:

Alice knows Bob, Bob knows Cindy, but Alice does not know Cindy. Cindy wants to send Alice something privately, but first needs to be "introduced" to Alice.

Cindy begins by first asking Alice for her public-key certificate. Alice sends it; it's public information, so she can broadcast it to the world. Included on this one certificate would be a number of digital signatures, each from a person Alice knows, including Bob, who is vouching for the accuracy of this certificate. Each signature is unique to the combination of the certificate and the signer, and the creation of a signature requires a private key known only to that signer. Once created, anyone who knows the public key matching the signer's private key can use that key to verify that the signature matches both the message and the signer (or that it doesn't).

As such, the evil Eve cannot hope to alter the message in such a way that the signature(s) would still match, nor can she change the signatures themselves, without having compromised the private keys of all signers. The worst she can do, given that someone else already knows and is vouching for Alice's identity, is corrupt the certificate causing Cindy to reject it, preventing the intended communication.

Alternately, Cindy could ask all her friends if they know Alice, and any that do, including Bob, can each forward Cindy a copy of Alice's certificate with only their signature on it. This reduces the number of signatures that have to be included on a single certificate to provide a good chance for Cindy to recognize one; since Cindy's asking her own friends, who would only respond if they did indeed know Alice, Cindy only receives signatures from people she knows and ostensibly trusts. But, it could cause a flood of data to be sent to Cindy if Cindy and Alice have a lot of mutual friends.

In either case, Cindy scans these signatures for signers that she knows. She find's Bob's name, validates his signature of this certificate, and now knows that Bob thinks this is the real certificate for the real Alice. Cindy now has the choice to trust Bob implicitly, and so trust Alice's certificate herself on his word alone, or to partially trust Bob, and look for other people she knows who have signed Alice's certificate. If she finds enough people she partially trusts, or at least one person she implicitly trusts, she can trust Alice's certificate by extension. This is known as the "trusted introduction" and is central to the web of trust.

Once Cindy decides to trust the certificate, she uses its public key to encrypt the key to a symmetrically encrypted message that has also been signed by Cindy with her own certificate. She then sends it to Alice. Alice doesn't know Cindy, and so repeats a similar process that Cindy did to obtain, validate and decide to trust Cindy's public-key certificate (which she does, because Bob has signed Cindy's certificate and Alice trusts Bob implicitly). She uses her own private key to decrypt the message key, then uses the message key to decrypt the message, and finally uses Cindy's public key to validate the message's signature.

Now, that's with three people who are already partially "entangled" in the web and so can trust each other based on peer recommendation. For two people with no mutual trusted friends, such as when a web is just starting or when a new person who's never used PGP before tries to join, this automatic peer recommendation simply won't work; there are no peer recommendations to speak of (there may not even be peers). To spin the first few threads of this web properly, the people wishing to form it must exchange certificate files with each other inside an environment that is inherently trusted (known as a "key signing party"). Otherwise the evil Eve can intercept the certificates being exchanged, replace them with forged certificates, and she becomes a "man in the middle".

The oldest, simplest way to avoid this is simply to meet in person and physically exchange certificate files with each other. Other possibilities, such as secure drop-boxes, exist, but all Eve needs is one second of unrestricted, undetected access to the physical storage of the key to screw it all up.

  • Amazing KeithS! Thanks for this unbelievable detailed answer. Now I understand perfectly the Web of Trust, thanks to you ;) And thanks for your time too! Commented Jan 25, 2013 at 2:45

This is a classic problem which a web of trust is designed to help with. If a web of trust is being done well, the public key should be presented to get a signature from another member of the web and a fingerprint of the public key should be shared in an out of band channel (as well as identity verification should be done out of band). For some web of trusts, this involves actually meeting in person with the individual being authenticated.

This makes it far more difficult to compromise a channel, but even if an attacker manages to compromise one particular channel, that only gets them one signature. The other aspect of a good web of trust is that it should be possible to get multiple signatures attesting to your identity. Even if one or two users end up signing the wrong public key, it would be very difficult (unless a systematic problem is found) to get signatures for the fake public key from multiple other parties in the web of trust.

The attacker could make a bunch of entities to sign their own keys, but since those signers wouldn't be any more trusted than the bogus cert, it wouldn't increase there trust unless the attacker was able to get their bogus certs trusted by signers that you trust.

As far as the logistics of setting up a web of trust, you have a few options. If you want to go for a semi-centrally managed one, you can personally validate the authenticity of some people and then grant them the ability to sign off on people in a central database. For a more P2P / non-centralized version, you simply have to have each client keep track of a list of trust levels associated with public keys they know. Each user's certificate would be signed by each person that approves them and then the client can calculate trust by looking at the public keys that it trusts which have signed it. The downside there is that the keys could get rather large, so it might require some kind of optimization like having the list of trusted certs published for each client and then having the person who wants to authenticate themselves send only the appropriate chains of trust.

Size would still be pretty big though so a centralized system would generally be easier. The centralized system could be as simple as a PKI repository of certificates. Each certificate is stored centrally and any certificates that have signed another cert can be looked up. The server or the client can then browse through the most up to date chains of trust. (Where as in a p2p system, If A signed B and then C signed A, B would have an outdated certificate for their signer A and if third party D only trusted C, then they wouldn't trust B unless things were centralized.)

  • Thanks AJ Henderson for this valuable information. Do you think it's possible for you to explain the "workflow" so I don't make any stupid mistakes while creating my WoT? The way I think of this is: I have 5 users, each user that trust another have a specific entry in a database with an hash of the trusted user's public key. When a new user register... someone must trust him so he can have his own hash entry in the database. Once that is done. A user receiving a message see if the sender is "trusted" calculated with ratio (# of users trusting sender/total number of users), Am I wrong? Commented Jan 24, 2013 at 22:24
  • 1
    @JeremyDicaire - I'll update my answer with some more details. Commented Jan 25, 2013 at 13:52
  • Thanks AJ for the update ;) I appreciate it,I'm all new to crypto and it's harder than I though but I love that :) Commented Jan 25, 2013 at 14:52
  • @JeremyDicaire - yeah, crypto and the wider field of security (both IT and otherwise) can seem deceptively easy at first, but there are a ton of gotchas and subtle ways for things to go wrong. The big trick is to stick to standard algorithms (because algorithms themselves are insanely complex to make secure) and then know the capabilities of each well enough to know how to string them together to mitigate the risks you care about without becoming overly complex. (Complexity in security is generally bad.) Commented Jan 25, 2013 at 15:41
  • Great, thanks for the advise, I'll remember that :) Commented Jan 25, 2013 at 15:51

You must log in to answer this question.

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