- State “DONE” [2009-11-12 Thu 15:24]
- State “STARTED” [2009-11-09 Mon 12:30]
- State “DONE” [2009-11-12 Thu 18:24]
- State “STARTED” [2009-11-11 Wed 12:00]
- State “DONE” [2009-11-12 Thu 11:05]
- State “TODO” [2009-11-12 Thu 11:04]
- State “DONE” [2009-11-12 Thu 11:05]
- State “TODO” [2009-11-12 Thu 11:05]
- State “DONE” [2009-11-12 Thu 18:24]
- State “TODO” [2009-11-12 Thu 11:05]
- State “DONE” [2009-11-13 Fri 11:46]
- State “DONE” [2009-11-25 Wed 16:23]
- State “DONE” [2009-11-19 Thu 10:52]
- State “STARTED” [2009-11-17 Tue 11:21]
- State “TODO” [2009-11-17 Tue 15:00]
- State “DEFERRED” [2009-11-16 Mon 14:27]
- State “DONE” [2009-11-25 Wed 16:24]
Gibt es noch Schlüssel, die MD5 einsetzen und damit signieren? Gibt es halbwegs aktuelle Signaturen auf Basis von MD5?
- State “DONE” [2009-11-25 Wed 16:24]
- State “DONE” [2009-12-03 Thu 11:22]
- State “DONE” [2009-12-03 Thu 16:58]
Anhand des Metagraphen ausrechnen, wie viele Knoten von der MSCC erreicht werden können bzw. wie viele diese erreichen können
Bisher wurden zwei Dumps verwendet: 1. Anfang August, 2. Ende September (?). Beim zweiten ist erwartungsgemäss die MSCC gewachsen (wenige hundert Knoten). Allerdings hat sich die nächstkleinere Komponente eine geringere Grösse als beim 1. dump. Das kann eigentlich nur daran liegen, dass diese Komponente durch das Expiren von Schlüsseln/Signaturen zerfallen sind.
Kann der Graph ohne (wesentlichen) Informationsverlust in einen ungerichteten Graphen umgewandelt werden?
- State “DONE” [2009-12-15 Tue 14:38]
- State “DONE” [2009-11-30 Mon 17:24]
- State “TODO” [2009-11-12 Thu 12:07]
Falls nötig edge betweenness auf Basis von MPI und Vertex betweeness implementieren, auf HPC-BW laufen lassen.
Lässt sich unterscheiden, ob Signaturen aus einem privatem Face-to-face-meeting stammen oder auf einer (grossen) Keysigning-Party entstanden sind? Wie hoch ist der Anteil der Nicht-Keysigning-Signaturen?
Die Unterscheidung, ob eine Community eine soziale Gruppe oder eine Keysigning-Party darstellt, kann anhand der Signaturzeit getroffen werden. Wenn alle (die meisten) Signaturen in einer Community in einem engen Zeitfenster gemacht wurden, ist es höchstwahrscheinlich eine Keysigning-Party.
Mit dem Datenstand vom 05.11.09 sind 408464 von 439355 Signaturen nicht one-way, d.h. die grosse Mehrzahl der Signaturen beruht auf Gegenseitigkeit. Das sind wie erwartet wenige, da Signaturen im normalen Vorgang in beide Richtungen unternommen werden. Damit scheint es vertretbar, den Graphen für die Community-Analyse in einen ungerichteten Graphen umzuwandeln.
Mit 263 (max_size = 10) Knoten wird das Ganze darstellbar (fdp -> spring model, Fruchtermann und Rheingold).
Allerdings:
Eine Reihe von Komponten hat keine ausgehenden/eingehenden Kanten. Solche Knoten entfernen und herausfinden, wie weit die Komponentengrösse dann reduziert werden kann.
Ohne singleton Knoten und n = 224 (max_size = 8) ist der Graph noch zeichenbar. Allgemein scheint fdp die besten bzw. einzig brauchbaren Ergebnisse zu liefern. Die Qualität der Zeichnung ist noch sehr zu verbessern. Dazu könnte die Grösse der Knoten reduziert werden (nur Grösse, Kreis enger gezeichnet). Ausserdem sollte die Anzahl der aggregierten Kanten sichtbar sein, z.B. indem eine “Metakante” unterschiedlich dick gezeichnet wird.
Es sind nicht 408000 Signaturen nicht-one-way wie gestern
behauptet, sondern es ist gerade anders herum. D.h. zu 408000
Signaturen gibt es keine Signatur in umgekehrter Richtung. Demnach
gibt es nur zwischen
Allerdings wird das plausibler, wenn man sich die Gradverteilung anschaut. Die grosse Mehrheit der Knoten hat einen Grad von höchstens 3 (allein 18000 mit 1) und es scheint nicht unwahrscheinlich, dass das eine Signaturenpaar eines Grad-1-Knotens gerade nicht auf Gegenseitigkeit beruht. Das würde bedeuten, dass die ganzen Grad-1/2/3 Knoten nur signiert haben (eher nicht signiert wurden bzw. nicht vom signierten signiert wurden).
Wie sieht die Verteilung der Indegrees aus? Trifft out-degree < 3 und in-degree < 3 häufig zusammen (sehr wahrscheinlich)?
Das Problem bleibt allerdings, dass der Graph nicht so ohne weiteres in einen ungerichteten Graphen umgewandelt werden kann. Es muss jetzt darüber nachgedacht werden:
wie gross der Informationsverlust ist, wenn one-way- und two-way Signaturen unterschiedslos in eine ungerichtete Kante überführt werden
ob es Sinn macht, wie bei Pons et al. angemerkt, iterativ Kanten mit Grad 1 zu entfernen. Tragen diese tatsächlich nichts zur Community-Struktur bei?
Wenn die statistische Auswertung mit den ekeys durchgeführt werden soll, ergibt sich ein Problem: Von allen (validen) Signaturen, die ein issuer auf einem bestimmten Key angebracht hat, wird nur eine (d.h. eine signierte uid) übernommen. Problematisch wird das, wenn der issuer zu unterschiedlichen Zeiten unterschiedliche UIDs signiert hat und sich dabei z.B. der Signaturalgorithmus (unwahrscheinlich weil gleicher Key), die Ablaufzeit (schon wahrscheinlicher unter der Prämisse dass überhaupt Ablaufzeiten auf Signaturen verwendet werden) oder der cert level (nicht unwahrscheinlich insoweit cert level != 0x10 benutzt werden) geändert hat.
Kein einziger Schlüssel im dump 091109 hat ein Ablaufdatum. Das ist entweder ein Fehler im DB-Export oder im SQL-import. Vermutlich das erste.
wotsap beachtet scheinbar keine subkeys, d.h. auch keine Signaturen auf Subkeys. Es scheint daher gerechtfertigt, das genau so zu machen.
Die Statistiken über die zeitliche Entwicklung von Algorithmenbenutzung und Schlüssellänge für RSA/DSA sehen hübsch aus und scheinen auch Sinn zu machen. Z.b. sieht man in jüngster Zeit einen Peak von RSA-keys mit grosser Schlüssellänge, der wahrscheinlich mit dem Bekanntwerden der Probleme mit SHA-1 korreliert.
Das Problem dabei ist, das im Moment nur die Keys betrachtet werden, die im Moment als valide und signiert betrachtet werden. Eigentlich müssten aber für ein Intervall alle Keys betrachtet werden, die in diesem Intervall erstellt wurden, auch wenn sie inzwischen nicht mehr gültig bzw. nicht vernetzt sind.
Es müssten also alle Keys aus der Datenbank extrahiert und in SQL abgelegt werden. Dabei muss für revoked Keys abgespeichert werden, wann der Key revoked wurde. Bei der Abfrage muss dann zusätzlich zu den Intervall-Kriterien beachtet werden, ob der Key vor Intervallende abgelaufen ist oder revoked wurde.
Komponenten benennen (durchnummerien a la metagraph) und dann für jeden key die nummer merken (falls er in einer komponente ist).
dump_graph ist offensichtlich fehlerhaft, weil es Keys liefert, die längst expired sind. Ein Vergleich der MSCC mit wot-all deutet an, dass von den knapp 43000 Keys ca. 4000 expired sind. wotsap liefert aktuell (03.12.09) 42000 Keys mit ca. 420000 Signaturen. Mit grosser Wahrscheinlichkeit waren das vor kurzem aber noch eher ca. 38000 Schlüssel.
Update: Die aktuell bearbeiteten Daten stammen vom 15.11.09. Der wotsap-Datensatz vom 13.11.09 enthält tatsächlich nur ~37000 Keys. Aus den Dateigrössen ist auch ersichtlich, dass die Grösse erheblich schwankt. Der übliche Wert scheint aber eher bei ca. 42000 Keys zu liegen.
Möglichkeit: Noch mal einen neuen Dump ziehen und vergleichen.
Modularity hat anscheinend eine Auflösungsgrenze (resolution limit), die es schwierig oder sogar unmöglich macht, Communities unterhalb einer gewissen Mindestgrösse zu finden. (Siehe Good2009, Leung2009).
Siehe Leung2009, dort auch interessante Aspekte über Modularity, Performance-Vergleich mit Modularity-Methoden.
Die Komponentenstruktur und insbesondere ihre Grössenverteilung müsste mit der Literatur verglichen werden. Insbesondere scheint es in random graphs normal zu sein, dass eine giant component entsteht und der Rest der Komponenten sehr viel kleiner ist (Newman2001).
Die Walktrap-Implementierung aus igraph (aber wahrscheinlich auch der Algorithmus an sich) ist auf der vorhandenen Hardware nicht benutzbar. Der Prozess wächst innerhalb von 20 Minuten auf ~2.4 GB Speicher an.
Der Fastgreedy-Algorithmus in der Igraph-Implementierung liefert auf roadw innerhalb von ca. 10 Minuten ein Ergebnis. Es entstehen 665 Communities. Auffällig ist, dass einige (5-6) sehr grosse (ca 4000-5000 Knoten) dabei sind. Ansonsten gibt es einige (15-20) von mittlerer Grösse (100-500). Die grosse Mehrzahl (fast der gesamte Rest) liegt zwischen 5 und 20 Knoten.
Die jeweiligen Methoden für ungerichtete und gerichtete Graphen können einfach verglichen werden, indem Modularity als Gütemass verwendet wird (Modularity für gerichtete Graphen siehe Arenas2007, Leicht/Newmann2008).
Das funktioniert allerdings auf den ersten Blick nicht zwischen gerichteten und ungerichteten Graphen, weil es sich um unterschiedliche Masse bzw. um eine andere Struktur handelt. Können die Masse trotzdem verglichen werden? Wie machen das die Autoren, die gerichtete Algorithmen vorschlagen?
Werden die hauptsächlich von CA’s eingesetzt? (CA Cert Signing Autority…, PGP directory verification…)
Wie sind die Auswirkungen, wenn MD5-Signaturen entfernt werden? Zerfällt die MSCC in mehrere Teile? Das könnte relevant werden, wenn es effiziente preimage-Angriffe gegen MD5 gibt.
Gleiches könnte man sich auch für die Knoten mit höchstem Grad, Knoten mit höchster Betweeness-Centrality und CA-Knoten (Heise, CACert) anschauen.