GnuPG Web-of-Trust calculations based on trust-signatures don't add up (T7611)

[Daniel Kahn Gillmor]

Hey folks--

I just wanted to give people a heads-up that GnuPG's web-of-trust
calculations are … surprising to me, to say the least.  In particular,
*adding* a trust signature to a WoT path can apparently *reduce* the
calculated validity of a target userID+certificate.

If anyone is actually relying on Web-of-Trust calculations from GnuPG
for their project, i hope you'll take a look at this issue and weigh in
on whether it meets your expectations or not.

Over on https://dev.gnupg.org/T7611 there is a simple script that
generates an example graph that looks like this:

```
      ⓕ2    ⓕ1
Alice —→ Bob —→ Carol → Dave [marginal]
  ⓕ2 🡖        🡕ⓜ1
         Bill
```

Legend: ⓕx means "trust signature (tsig) with full trust of depth x" and
ⓜy means "tsig with marginal trust of depth y".

With the full graph of tsigs shown here, and with Alice being ultimately
trusted, GnuPG claims that Dave's certificate has marginal validity.

If we remove the tsig from Alice to Bill, then Dave's certificate
increases from marginal to full validity.

```
      ⓕ2    ⓕ1
Alice —→ Bob —→ Carol → Dave [full]
              🡕ⓜ1
         Bill
```

That's right: *removing* an independent tsig causes calculated validty
to *increase*.  And vice versa: *adding* an independent tsig causes
calculated validty to *decrease*.

In that ticket, Werner identified this as desired/intended behavior, and
asked for further conversation to happen on this mailing list, hence
this e-mail message.

To be clear about my understanding:

 - I generally expect WoT calculations to be cumulative or additive in
   some sense.  For example, gpg(1) documents the --marginals-needed
   option as "Number of marginally trusted users to introduce a new key
   signer".  This implies (to me, anyway) that adding a marginally
   trusted certification should be able to *increase* the validity of a
   user ID in an OpenPGP certificate.

 - I find it surprising that the addition of a marginally trusted user
   (without superseding any existing certification) would actually
   *reduce* the amount of confidence in the validity of some
   certificate.

 - The code archaeology in T7611 turns up a (rather old) comment
   suggesting that timestamps of signature creation should make some
   sort of difference.  But in the tests i ran, all signatures and all
   certificates are made within the same second, the finest temporal
   resolution that OpenPGP is capable of recording.  So i'm not sure how
   questions about timestamp are relevant.

I want to also note that it's possible that no one is relying on
Web-of-Trust calculations from GnuPG.  From my perspective:

 - I contributed for years to the Monkeysphere (which validated SSH
   cryptographic keys for SSH servers and users), which basically
   assumed that GnuPG's WoT calculations could be relied on, but i don't
   think anyone in that project (including me) ever tested complex
   graphs.  As far as i know, Monkeysphere was ever only deployed with
   single-hop certification authorities in either direction.  For
   example, the ssh user would privately/internally certify the SSH
   host's OpenPGP certificate.  And the SSH host administrator might
   certify the end-user's OpenPGP certificate, which the SSH host itself
   would rely on.

 - For Debian's keyring-maint (where i act as an advisor), which does
   ask questions about OpenPGP certification connectivity, it really
   only uses single-hop certifications from any of a known set of Debian
   Developer certificates.  Interesting graphs can be drawn about WoT
   connectivity from those structures, but they have no concrete effect
   on how Debian works, and they typically aren't using GnuPG's userid
   validity or trust calculations anyway.

 - For regular e-mail address cryptographic identity management, I've
   only ever seen people using the OpenPGP tooling for management of a
   TOFUish keystore, even when they use GnuPG.  Alternately, people
   using OpenPGP might use an entirely non-WoT scheme like the Autocrypt
   recommendation engine.

It would be pretty cool if the OpenPGP WoT was useful in some contexts,
but none of the above seem to actually use it.  And if there is a system
that uses it where GnuPG is in the mix, I'd live to hear about it!  In
such a case, i hope the folks who depend on that system will not be
surprised by this report.  If you're one of those people, I'd be
particularly interested to learn more about your mental model of the
network of OpenPGP identity certifications that we know as the "web of
trust", so i can understand it better.

All the best,

    --dkg
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 227 bytes
Desc: not available
URL: <https://lists.gnupg.org/pipermail/gnupg-devel/attachments/20250506/cc70f39c/attachment-0001.sig>