Analysis inputs

The measurements below are based on wotsap 0.6 and the wot dump of Januari 27th, 2005. The software came from http://www.lysator.liu.se/~jc/wotsap/download.html; The WoT dump came from http://www.lysator.liu.se/~jc/wotsap/wots/2005-01-27.wot.

The statements below ran on FreeBSD using a bash commandline; there are several variations of sed so you may have to adapt the statements for other versions of the program.

Reproducable Analysis

1. Download the wotsap database to a file:

   lynx -source > wot.2005-01-27.wot       \
           http://www.lysator.liu.se/~jc/wotsap/wots/2005-01-27.wot
   

   (10 sec, 907724 bytes)

2. Turn wotsap database into human-readable trust listing:

   ./wotsap --wot=wot.2005-01-27.wot -p >all.2005-01-27.txt
   

   (10 min, 13826676 bytes in 251279 lines: 25082 keys + 226197 sigs)

3. Remove distinction signature/signer and make key occurrences uniqe:

   sed 's/^  . 0x/0x/' <all.2005-01-27.txt         \
           | sort                                  \
           | uniq >key.2005-01-27.txt
   

   (30 sec, 1300475 bytes in 25082 lines)

4. Remove everything but the personal name; turn it into lowercase:

   sed < key.2005-01-27.txt > nom.2005-01-27.txt           \
           -e 's/^0x[0-9A-Fa-f]* *//'                      \
           -e 's/<[^<>]*>//'                               \
           -e 's/([^()]*)//'                               \
           -e 's/^ *//'                                    \
           -e 's/ *$//'                                    \
           -e 's/  */ /'                                   \
           -e 's/"//'                                      \
           -e 'y/ABCDEFGHIJKLMNOPQRSTUVWXYZ/abcdefghijklmnopqrstuvwxyz/'
   

   (30 sec, 397581 bytes in 25082 lines: matches #keys)

5. Remove doubles and count the results:

   cat nom.2005-01-27.txt | sort | uniq > nuq.2005-01-27.txt
   

   (1 sec, 341689 bytes in 21439 lines)

   Apperantly, there are 21439 unique name strings.

6. Conclusions (part 1)

   The number of keys in the WoT is                     25082
   A rough estimate of the number of unique names is    21439 -
                                                        -----
   The number of keys with a previously found name is    3643 (15%)
   

   This number is much lower than expected. Causes:

   • Wotsap only lists primary UIDs. This means that keys with multiple names are not matched. Even if the other keys are actually the same.
   • No conclusion is drawn from sharing email addresses.
   • Names can often be spelled in a variety of ways, beyond sed! For example, middle names and initials may not stand out. Also, there may be long/official versions versus calling names.

7. Calculations for email addresses:

   sed < key.2005-01-27.txt > eml.2005-01-27.txt           \
           -e 's/^[^<]*</</'                               \
           -e 's/>[^>]*$/>/'                               \
           -e 'y/ABCDEFGHIJKLMNOPQRSTUVWXYZ/abcdefghijklmnopqrstuvwxyz/'
   

   (10 sec, 582412 bytes in 25082 lines)

   cat eml.2005-01-27.txt | sort | uniq > euq.2005-01-27.txt
   

   (2 sec, 554168 bytes in 23791 lines)

   Apperantly, there are 23791 unique email addresses.

8. Conclusions (part 2)

   The number of keys in the WoT is                     25082
   A rough estimate of the number of unique emails is   23791 -
                                                        -----
   The number of keys with a previously found email is   1291 (5%)
   

   This is less than name matches. Well, probably there are many people with one name and multiple email address, so that makes sense to me.

   Worst case, the number of matches can be estimated (assuming that no names overlap in the WoT) at 3643 (15%) and best case it can be that people use either a different name or a different email address but not both, in which case there would be an overlap of 3643 + 1291 = 4934 (20%) UIDs.

   The latter measure (4934, 20%) should be cleaned up, that is those keys that have the same email address as name should be subtracted once because they were counted twice.

9. Correcting for name/email overlap in estimates:

   sed < key.2005-01-27.txt > nml.2005-01-27.txt           \
           -e 's/^0x[0-9A-Fa-f]* *//'                      \
           -e 's/([^()]*)//'                               \
           -e 's/^ *//'                                    \
           -e 's/ *$//'                                    \
           -e 's/  */ /'                                   \
           -e 's/"//'                                      \
           -e 'y/ABCDEFGHIJKLMNOPQRSTUVWXYZ/abcdefghijklmnopqrstuvwxyz/'
   
   # excluded rewrite pattern:
           #  's/<[^<>]*>//'
   

   (10 sec, 962762 bytes in 25082 lines)

   cat nml.2005-01-27.txt | sort | uniq > nmq.2005-01-27.txt
   

   (2 sec, 928268 bytes in 24153 lines)

   Apperantly, there are 24153 unique combinations of email address and name string.

Conclusions

The number of keys in the WoT is                     25082
A rough estimate of the number of unique name&mail   24153 -
                                                     -----
The number of keys with a previously found name&mail   929

That must be subtracted from the previous line of conclusions:

Keys with previously found name and+or email          4934
Keys with previously found name and    email           929 -
                                                     -----
Keys with previously found name     or email          4005 (16%)

So, to summarise:

16% of the keys in the strong set of the PGP WoT can be considered equivalent to another key.

This is under the following assumptions:

• that same name and/or email address implies person equivalence

  • only good enough to continue with this estimate!
  • actual process must include more formal checks
  • consider using a global policy or a trust signature to make equivalence hard
  • equivalence is key owner's interest => it stands a chance
  • making this practical can lower the percentage found

• that nothing could be learnt from additional UIDs

  • bare nonsense, purely dictated by the incoming data set
  • making this practical can heighten the percentage found

• that name equivalence is a literal thing, which it isn't

  • bare nonsense, williams and bills; middle names, soundexes, ...
  • making this practical can heighten the percentage found

• that no keys outside the strong set are equivalent with keys within

  • there may be keys on their way in (new keys, old owners)
  • new paths may come into existence through keys outside the strong set
  • making this practical can heighten the percentage found

Estimating the influence on the MSD

The influence of treating keys as equivalents is that a signature on one key can influence any other key equivalent with it. So, the signatures can be seen as signatures on a set of equivalent keys, not on a single key.

This means that users who replace their old key for a new one and who recollect signatures can still rely on the signatures on their old key, provided that they didn't expire it.

For the web of trust as a whole, it means that less keys can be considered to carry the same number of keys. Without a good idea of the error introduced be the assumption, we are going to assume that the signatures are spread evenly over existing keys.

In the Web of Trust of 2005-01-27 these values applied:

Keys in the strong set:                            25082
Signatures in the strong set:                     226197
Average signatures per key:                            9.018
Average MSD (measured from a graphic)                  6.2

After correcting for the keys equivalent to other keys this can be seen as the following 'corrected' situation:

Equivalent key sets in the strong set:             21077
Signatures in the strong set:                     226197
Average signatures per equivalent key set:            10.731
Average MSD (estimated below):                         5.7

One key can reach as many next-keys as it signs (except the obvious self-sig, which was already excluded from the initial all.2005-01-27.txt file). For the non-equivalent WoT this would mean 9.018 keys, then on to 9.018^i in the i'th iteration. The reach of an average key is 9.018 ^ 6.2 = 834994. This apperantly is the number to cover the 25082 keys in the strong set. Note that this number does indeed look like the reachable set which is by nature a superset of the strong set. I am not sure what that means.

For 21077 keys, that number could be lower, probably linearly (?) so the coverage would become 834994 * 21077 / 25082 = 701665. The assumption of linearity isn't strongly founded in math, but do note that its dimension is a number of nodes, as goes for the size of the strong set.

Note:

The latter assumption is false if the total number is indeed the reachable set -- because that is the same in the new situation. The calculation below would then result in an equivalence-corrected MSD of 5.745 -- under the threshold of the figure reported above.

The average MSD can then be estimated with 10.731 ^ avgMSD = 701665, which leads to MSD = ln (701665) / ln (10.731) = 5.67

Note that this improvement is achievable only under the foregoing assumptions, and that actual benefits may vary. There is also a human factor; people may not always want to state by way of policy or trust signature that their keys are equivalent; although it is to be expected that such individuals will have put different names on their keys as well.

Estimating the influence on the number of independent paths

I haven't got a clue... any thoughts, please forward to me:

pub  1024D/89754606 2002-03-28 Rick van Rein <rick@openfortress.nl>
     Key fingerprint = CD46 B5F2 E876 A5EE 9A85  1735 1411 A9C2 8975 4606

pub  1024D/F5BAD1CD 2001-06-25 Rick van Rein <rick@vanrein.org>
     Key fingerprint = 52CA E7AD D0CF 9EED 0E89  07EB 5558 341A F5BA D1CD

Author

This estimation was performed by Dr.ir. Rick van Rein, employee of OpenFortress Digital signatures in the Netherlands.

General information about OpenFortress:

http://openfortress.nl
info@openfortress.nl