Breaking the Web of Trust
With all the discussion about SHA-1 weaknesses and generation of new OpenPGP keys going on there's some concern about how the web of trust will be affected. I'm particularly interested in the impact on Debian; while it's possible to add new keys and keep the old ones around that hasn't worked so well for us with the migration away from PGPv3 keys. We still have 125 v3 keys left, many of them for users who also have a v4 key but haven't asked for the v3 key to be removed or responded to my email prodding them about it. I don't want to repeat that.
So if we're looking at key replacement we need to have some idea about where our Web of Trust currently stands, and what effect various changes might have on it. I managed to find the keyrings Debian shipped all the way back to slink and ran the keyanalyze and cwot stats against them. I then took the current keyring, pull in all the updates for the keys in it (so that any signatures from newly generated keys would be included) and ran the stats again. Finally I took details of 12 key migrations (mostly from Debian Planet but also a couple of others I knew about) and calculated what the effect of removing each key would be. These stats are cumulative and I replaced the most well connected (by centrality) keys first.
The results are below.
- Total is the total number of keys in the keyring
- SCS is the largest Strongly Connected Subset
- Reachable is the largest reachable subset
- MSD is the Mean Shortest Distance
- Centrality is the average centrality for the reachable subset
- update-foo indicates that foo's key was replaced with a newer one
| Total | SCS | Reachable | MSD | Centrality | |||
|---|---|---|---|---|---|---|---|
| 1999-02-06 (slink) | 228 | 36 | (15.78%) | 50 | (21.92%) | 2.9022 | |
| 2000-01-03 (potato) | 375 | 104 | (27.73%) | 180 | (48.00%) | 4.3382 | |
| 2001-09-22 (woody) | 948 | 538 | (56.75%) | 704 | (74.26%) | 4.7320 | 2008.6249 |
| 2005-05-28 (sarge/etch) | 1106 | 883 | (79.83%) | 969 | (87.61%) | 3.3485 | 2074.6604 |
| 2007-12-04 | 1191 | 1001 | (84.04%) | 1062 | (89.16%) | 3.1103 | 2113.3747 |
| 2009-01-18 (lenny) | 1126 | 947 | (84.10%) | 1010 | (89.69%) | 3.0489 | 1941.2594 |
| 2009-04-04 (squeeze/sid) | 1121 | 946 | (84.38%) | 1008 | (89.91%) | 3.0466 | 1936.9761 |
| 2009-05-06 (current) | 1067 | 894 | (83.78%) | 958 | (89.78%) | 2.9670 | 1759.4363 |
| Total | SCS | Reachable | MSD | Centrality | |||
| base | 1067 | 904 | (84.72%) | 959 | (89.87%) | 2.9640 | 1776.4389 |
| update-93sam | 1067 | 902 | (84.53%) | 958 | (89.78%) | 2.9734 | 1780.9874 |
| update-joerg | 1067 | 900 | (84.34%) | 958 | (89.78%) | 2.9776 | 1780.7578 |
| update-aurel32 | 1067 | 898 | (84.16%) | 957 | (89.69%) | 2.9803 | 1779.2497 |
| update-noodles | 1067 | 896 | (83.97%) | 956 | (89.59%) | 2.9831 | 1777.8326 |
| update-jaldhar | 1067 | 896 | (83.97%) | 955 | (89.50%) | 2.9855 | 1779.9193 |
| update-srivasta | 1067 | 896 | (83.97%) | 955 | (89.50%) | 2.9904 | 1784.3382 |
| update-ana | 1067 | 895 | (83.88%) | 954 | (89.40%) | 2.9926 | 1784.3102 |
| update-nobse | 1067 | 893 | (83.69%) | 953 | (89.31%) | 2.9947 | 1782.2392 |
| update-neilm | 1067 | 892 | (83.59%) | 951 | (89.12%) | 2.9974 | 1782.6098 |
| update-reg | 1067 | 891 | (83.50%) | 950 | (89.03%) | 2.9977 | 1780.8515 |
| update-rmayorga | 1067 | 890 | (83.41%) | 949 | (88.94%) | 2.9984 | 1779.4910 |
| update-evgeni | 1067 | 889 | (83.31%) | 948 | (88.84%) | 2.9974 | 1776.6445 |
This is actually more hopeful than I thought. There's an obvious weakening as a result of the migrations, but the MSD stays under 3 and the centrality stays fairly constant too. The reachable/SCS counts do decrease, but at this point it looks fairly linear rather than an instant partition. Of course the more keys that are removed the more likely this is to drop off suddenly. Counteracting that DebConf9 is coming up which will provide a good opportunity for normally geographically disperse groups to cross sign, reinforcing the WoT for these new keys.
Either way I at least have a better handle on the current state of play, which gives me something to work with when thinking about how to proceed. For now, bed.