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.
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.
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.
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….
Marcos Dione wrote on 09/19/08 at 7:18 pm :
also daniel hess and mathas rachor are teice in the list.
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…
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 [...]
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 [...]
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…