Looking for cliques in the GPG signatures graph

September 19th, 2008 by lucas

The strongly connected set of the GPG keys graph contains a bit more than 40000 keys now (yes, that’s a lot of geeks!). I wondered what was the biggest clique (complete subgraph) in that graph, and also of course the biggest clique I was in.

It’s easy to grab the whole web of trust there. Finding the maximum clique in a graph is NP-complete, but there are algorithms that work quite well for small instances (and you don’t need to consider all 40000 keys: to be in a clique of n keys, a key must have at least n-1 signatures, so it’s easy to simplify the graph — if you find a clique with 20 keys, you can remove all keys that have less than 19 signatures).

My first googling result pointed to Ashay Dharwadker’s solver implementation (which also proves P=NP ;). Googling further allowed me to find the solver provided with the DIMACS benchmarks. It’s clearly not the state of the art, but it was enough in my case (allowed to find the result almost immediately).

The biggest clique contains 47 keys. However, it looks like someone had fun, and injected a lot of bogus keys in the keyring. See the clique. So I ignored those keys, and re-ran the solver. And guess what’s the size of the biggest “real” clique? Yes. 42. Here are the winners:

CF3401A9 Elmar Hoffmann 
AF260AB1 Florian Zumbiehl 
454C864C Moritz Lapp 
E6AB2957 Tilman Koschnick 
A0ED982D Christian Brueffer 
5A35FD42 Christoph Ulrich Scholler 
514B3E7C Florian Ernst 
AB0CB8C0 Frank Mohr 
797EBFAB Enrico Zini 
A521F8B5 Manuel Zeise 
57E19B02 Thomas Glanzmann 
3096372C Michael Fladerer 
E63CD6D6 Daniel Hess 
A244C858 Torsten Marek 
82FB4EAD Timo Weingärtner
1EEF26F4 Christoph Ulrich Scholler 
AAE6022E Karlheinz Geyer 
EA2D2C41 Mattia Dongili 
FCC5040F Stephan Beyer 
6B79D401 Giunchedi Filippo 
74B11360 Frank Mohr 
94C09C7F Peter Palfrader
2274C4DA Andreas Priesz 
3B443922 Mathias Rachor 
C54BD798 Helmut Grohne 
9DE1EEB1 Marc Brockschmidt 
41CF0322 Christoph Reeg 
218D18D7 Robert Schiele 
0DCB0431 Daniel Hess 
B84EF12A Mathias Rachor 
FD6A8D9D Andreas Madsack 
67007C30 Bernd Paysan 
9978AF86 Christoph Probst 
BD8B050D Roland Rosenfeld 
E3DB4EA7 Christian Barth 
E263FCD4 Kurt Gramlich 
0E6D09CE Mathias Rachor 
2A623F72 Christoph Probst 
E05C21AF Sebastian Inacker 
5D64F870 Martin Zobel-Helas 
248AEB73 Rene Engelhard 
9C67CD96 Torsten Veller

It’s likely that this happened thanks to a very successful key signing party somewhere in germany (looking at the email addresses). [Update: It was the LinuxTag 2005 KSP.] It might be a nice challenge to beat that clique during next Debconf ;)

And the biggest clique I’m in contains 23 keys. Not too bad.

8 Responses to “Looking for cliques in the GPG signatures graph”

  1. Adalbert Blumenkohl wrote on 09/19/08 at 4:02 pm :

    How about duplicates?
    I find “Frank Mohr”, “Christoph Probst” and “Christoph Ulrich Scholler” each two times in this list. They may have multiple keys, but i doubt they’re all different people. So this clique is 42 keys big, but contain less people.

  2. lucas wrote on 09/19/08 at 4:08 pm :

    Well some people use several keys. Filtering out those duplicates is not going to be easy.

  3. Raw Matter wrote on 09/19/08 at 4:16 pm :

    42…

    Lucas just found the single most interesting fact of this day: the size of the biggest clique in the GPG key graph is … wait for it … fortytwo. Yep, I’m just parroting his finding here, but I’m sure you can see why….

  4. Marcos Dione wrote on 09/19/08 at 7:18 pm :

    also daniel hess and mathas rachor are teice in the list.

  5. Jean-Marc Liotier wrote on 09/20/08 at 1:48 am :

    Nice analysis ! But it is pretty sad to see how disconnected the web of trust is…

  6. Lucas Nussbaum: Looking for cliques in the GPG signatures graph : Dragonfly Networks wrote on 09/20/08 at 8:17 am :

    [...] Planet Debian: Lucas Nussbaum: Looking for cliques in the GPG signatures graph [...]

  7. Adrian von Bidder: 42 : Dragonfly Networks wrote on 09/20/08 at 8:18 am :

    [...] just found the single most interesting fact of this day: the size of the biggest clique in the GPG key graph [...]

  8. lucas wrote on 09/21/08 at 7:17 pm :

    @Jean-Marc: actually, the largest clique doesn’t say anything about how well the strongly connected set is connected…