Suppose there is a program and an OpenPGP signature on a website. A user downloads both signature and a program and needs to check if it is the same program the author meant to publish, not modified by anyone else. We consider the build environment, the developer's computer and the developer itself as trusted.

A user also downloads the key from a keyserver and a foreign keyring (probably over untrusted channel), which he supposes has the keys of the people used for signing developer's key, s.a. debian-keyring. User knows noone he can trust, so he is not connected to the web of trust.

How to trust the whole keyring installed as a net of individuals who verify each others but not to trust any minor group of individuals in the net? Will it help to run PageRank treating a valid signature as a vote for key and trust the keys having highest PageRank?

1 Answer 1


If there is no trust anchor into the Debian keyring (or any other group, but let's stick to the Debian example here), you have no chance of verifying anything.

Faking Whole Networks/Keyrings

It is easily possible to replicate the full Debian keyring with all it's user IDs and signatures issued, it will look totally legitimate while being completely made up. Pagerank will return the exactly same results for both networks. In the end, this is pretty much was evil32 did on the whole OpenPGP strongly connected component to showcase short key ID collision attacks.

Certificate Authority Root Certificates

This is a general problem of certification systems, you always need a trust anchor. For X.509 (as used for TLS and S/MIME), certificate authorities are used whose certificates are declared as trusted in the browsers and operating systems. For OpenPGP, you'll have to go out and find a trust anchor on your own. For the Debian keyring, going to a Debian user meetup or Free Software conference is a good start, you'll meet a whole bunch of people in the keyring there.

Trust on First Use

For the general case and when the keys have already been used for signing stuff you're already using for quite some time, you could also apply "TOFU" (trust on first use): it is unlikely that somebody was able to fake the Debian keyring (or even only some keys of them) in lots of different sources. Have a look at the Linux installation you have -- there is a keyring inside (pretty much all Linux distributions use GnuPG and OpenPGP to verify software in their packet manager). Grab some copies or computer magazines with Linux distributions inside in different stores. Use different internet connections in different places to fetch the keyring. If you always find some of the keys, very likely they actually belong to the Debian keyring (or similar keyrings). This does not verify individuals, but at least it verifies the membership of that key in the keyring to a given degree.

  • Thank you for the answer. I've clarified the question a bit. What'd be changed if we assumed the keyring had been got over a secure channel and that the majority of people whose keys were in the keyring were trustworthy in the sense that their keys were not compromised and they hadn't signed the keys of people whose identity they were not sure has been genuine?
    Sep 6, 2016 at 20:36
  • This is a major change in the question. Anyway: if you consider the keyring trustworthy, about what are you bothering then?
    – Jens Erat
    Sep 7, 2016 at 19:06
  • I don't consider keyring entirely trustworthy. For example debian-keyring is the keyring for debian developers who are added manually. This means that you cannot inject there fake identities (Sybil attack) or clones in large scale without compromising the people maintaining the keyring. But it can be possible to inject there some small amount of identities signed by trustworthy devs and then use them to sign some public key with malicious intent, s.a. impersonation.
    Sep 8, 2016 at 11:17
  • For example there is a dev of popular software John who distributes his soft using his website alongside with sigs and public key. An adversary controlling the channel to John's website creates the key with the same short fingerprint and email and other info and puts it into some keyserver, augments the program with malware, signs it and gives all the kit to users instead of John's. A user wanting to verify the origin of the program gets the key from keyserver (or website) and wants to verify its integrity.
    Sep 8, 2016 at 11:17
  • He cannot, he doesn't know which John is real. He downloads debian-keyring and sees that both keys are signed by the members of keyring. He doesn't know who to trust, he is disconnected from the web of trust. My idea is that real John is more connected to the web than the adversary because it can be problematic to make people to take part in large conspiracy without spreading the word. The question is, can PageRank (ore something else) be used to solve this problem?
    Sep 8, 2016 at 11:17

You must log in to answer this question.

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