Add support for importing wotsap db

You can now download and import latest.wot, but be warned that the path
finding algorithm needs some serious optimization before it can easily
go through so many records. It's possible, but it takes a few minutes
on a fast system.

Signed-off-by: Konstantin Ryabitsev <konstantin@linuxfoundation.org>

6 files changed, 142 insertions, 26 deletions

diff --git a/.gitignore b/.gitignore
index e0d12f3..ac7aa2f 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,7 +1,7 @@
 .idea
-graph.*
-siginfo.db
-ownertrust.txt
+*.db
+*.png
+*.wot
 keyring.kbx
 keyring.gpg
 *.pyc
diff --git a/examples/torvalds-to-jeyu.png b/examples/torvalds-to-jeyu.png
index 00acd02..41d978a 100644
--- a/examples/torvalds-to-jeyu.png
+++ b/examples/torvalds-to-jeyu.png
diff --git a/graph-paths.py b/graph-paths.py
index fb5966c..2863f90 100755
--- a/graph-paths.py
+++ b/graph-paths.py
@@ -50,13 +50,17 @@ def get_key_paths(c, t_p_rowid, b_p_rowid, maxdepth=5, maxpaths=5):
         sys.exit(1)
 
     logger.info('Found %s keys signed by top key' % len(sigs))
+    lookedat = 0
 
     paths = []
     ignorekeys = [item for sublist in sigs for item in sublist]
     for (s_p_rowid,) in sigs:
-        path = wotmate.get_shortest_path(c, s_p_rowid, b_p_rowid, 0, maxdepth-1, [], ignorekeys)
+        lookedat += 1
+        logger.info('Trying "%s" (%s/%s)' %
+                    (wotmate.get_uiddata_by_pubrow(c, s_p_rowid), lookedat, len(sigs)))
+        path = wotmate.get_shortest_path(c, s_p_rowid, b_p_rowid, 0, maxdepth-1, ignorekeys)
         if path:
-            logger.info('Found a path with %s members' % len(path))
+            logger.info('\- found a path with %s members' % len(path))
             paths.append([t_p_rowid] + path)
             ignorekeys += path
 
diff --git a/graph-to-full.py b/graph-to-full.py
index d33be65..b2958ab 100755
--- a/graph-to-full.py
+++ b/graph-to-full.py
@@ -39,14 +39,21 @@ def get_key_paths(c, b_p_rowid, maxdepth=5):
 
     paths = []
     ignorekeys = [item for sublist in f_p_rowids for item in sublist]
+    lookedat = 0
 
     logger.info('Found %s fully trusted keys in the db' % len(f_p_rowids))
     for (f_p_rowid,) in f_p_rowids:
-        path = wotmate.get_shortest_path(c, f_p_rowid, b_p_rowid, 0, maxdepth-1, [], ignorekeys)
+        lookedat += 1
+        logger.info('Trying "%s" (%s/%s)' %
+                    (wotmate.get_uiddata_by_pubrow(c, f_p_rowid), lookedat, len(f_p_rowids)))
+
+        path = wotmate.get_shortest_path(c, f_p_rowid, b_p_rowid, 0, maxdepth-1, ignorekeys)
 
         if path:
-            logger.info('Found a path with %s members' % len(path))
+            logger.info('\- found a path with %s members' % len(path))
             paths.append(path)
+            # we want to find maximum paths, so we unset _seenkeys
+            wotmate._seenkeys = []
             ignorekeys += path
 
     if not paths:
@@ -116,4 +123,4 @@ if __name__ == '__main__':
     chunks = cmdargs.out.split('.')
     outformat = chunks[-1]
     graph.write(cmdargs.out, format=outformat)
-    logger.info('Wrote %s' % cmdargs.out)
\ No newline at end of file
+    logger.info('Wrote %s' % cmdargs.out)
diff --git a/make-sqlitedb.py b/make-sqlitedb.py
index 197671e..9263bbd 100755
--- a/make-sqlitedb.py
+++ b/make-sqlitedb.py
@@ -21,11 +21,12 @@ from __future__ import (absolute_import,
                         unicode_literals)
 
 import os
+import sys
 import sqlite3
 import wotmate
 
 
-def populate_all_pubkeys(c, use_weak):
+def keyring_populate_all_pubkeys(c, use_weak):
     logger.info('Loading all valid pubkeys')
     keyid_rowid_map = {}
     for line in wotmate.gpg_run_command(['--list-public-keys'], ['pub:']):
@@ -50,7 +51,6 @@ def populate_all_pubkeys(c, use_weak):
         c.execute('INSERT INTO pub VALUES (?,?,?,?,?,?,?)', data)
         keyid_rowid_map[fields[4]] = c.lastrowid
 
-    dbconn.commit()
     logger.info('Loaded %s pubkeys' % len(keyid_rowid_map))
     return keyid_rowid_map
 
@@ -68,7 +68,7 @@ def store_uid(c, pubrowid, fields, is_primary):
     return c.lastrowid
 
 
-def populate_uid_sig_data(c, keyid_rowid_map):
+def keyring_populate_uid_sig_data(c, keyid_rowid_map):
     logger.info('Loading uid and signature data')
     sigquery = 'INSERT INTO sig VALUES (?,?,?,?,?)'
     # we use these to track which is the current pubkey/uid we're looking at
@@ -171,7 +171,95 @@ def populate_uid_sig_data(c, keyid_rowid_map):
         sigcount += len(uidsigs)
 
     logger.info('Loaded %s valid uids and %s valid sigs' % (uidcount, sigcount))
-    dbconn.commit()
+
+
+def wotsap_populate_keys(c, fh, size):
+    logger.info('Converting keys...')
+    readbytes = 0
+    keycount = 0
+    while readbytes < size:
+        key = fh.read(8)
+        readbytes += 8
+        # wotsap doesn't give us useful info about the key, just the ID
+        c.execute('''INSERT INTO pub (keyid) VALUES (?)''', (key.hex().upper(),))
+        keycount += 1
+    logger.info('Imported %s keys' % keycount)
+
+
+def wotsap_populate_names(c, fh, size):
+    logger.info('Converting names...')
+    readbytes = 0
+    p_rowid = 1
+    namecount = 0
+    while readbytes < size:
+        blob = b''
+        while True:
+            char = fh.read(1)
+            readbytes += 1
+            if char == b'\n':
+                break
+            blob += char
+            if readbytes >= size:
+                break
+        uiddata = blob.decode('utf8', 'ignore')
+        c.execute('''INSERT INTO uid (pubrowid, uiddata, is_primary) VALUES (?, ?, 1)''',
+                  (p_rowid, uiddata))
+        p_rowid += 1
+        namecount += 1
+
+    logger.info('Imported %s names' % namecount)
+
+
+def wotsap_populate_sigs(c, fh, size):
+    logger.info('Converting sigs...')
+    import struct
+    readbytes = 0
+    p_rowid = 1
+    totalsigs = 0
+    while readbytes < size:
+        sigcount = struct.unpack('!i', fh.read(4))[0]
+        readbytes += 4
+        cursig = 0
+        while cursig < sigcount:
+            # ignore the leading 4 bits for now, as we don't do
+            # anything with sig types for our purposes
+            _sig = 0x0FFFFFFF & struct.unpack('!i', fh.read(4))[0]
+
+            readbytes += 4
+            # in wotsap uidrow ends up being the same as pubrow
+            c.execute('''INSERT INTO sig (uidrowid, pubrowid) VALUES (?, ?)''',
+                      (p_rowid, _sig+1))
+
+            cursig += 1
+            totalsigs += 1
+
+        p_rowid += 1
+
+    logger.info('Imported %s signature relationships' % totalsigs)
+
+
+def convert_wotsap(c, wotsap):
+    import bz2
+    fh = bz2.open(wotsap)
+    magic = fh.read(8)
+    if magic != b'!<arch>\n':
+        logger.critical('%s does not appear to be in ar archive' % wotsap)
+        sys.exit(1)
+    while True:
+        fileident = fh.read(16).strip()
+        if not fileident:
+            break
+        fh.read(32)
+        size = int(fh.read(10).strip())
+        fh.read(2)
+        if fileident[:4] == b'keys':
+            wotsap_populate_keys(c, fh, size)
+        elif fileident[:4] == b'name':
+            wotsap_populate_names(c, fh, size)
+        elif fileident[:4] == b'sign':
+            wotsap_populate_sigs(c, fh, size)
+        else:
+            fh.read(size)
 
 
 if __name__ == '__main__':
@@ -194,6 +282,8 @@ if __name__ == '__main__':
     ap.add_argument('--gpgbin',
                     default='/usr/bin/gpg2',
                     help='Location of the gpg binary to use')
+    ap.add_argument('--wotsap', default=None,
+                    help='Convert a wotsap archive instead of using keyring')
     ap.add_argument('--gnupghome',
                     help='Set this as gnupghome instead of using the default')
 
@@ -215,7 +305,13 @@ if __name__ == '__main__':
     dbconn = sqlite3.connect(cmdargs.dbfile)
     cursor = dbconn.cursor()
     wotmate.init_sqlite_db(cursor)
-    kr_map = populate_all_pubkeys(cursor, cmdargs.use_weak)
-    populate_uid_sig_data(cursor, kr_map)
+
+    if not cmdargs.wotsap:
+        kr_map = keyring_populate_all_pubkeys(cursor, cmdargs.use_weak)
+        keyring_populate_uid_sig_data(cursor, kr_map)
+    else:
+        convert_wotsap(cursor, cmdargs.wotsap)
+
+    dbconn.commit()
     dbconn.close()
     logger.info('Wrote %s' % cmdargs.dbfile)
diff --git a/wotmate/__init__.py b/wotmate/__init__.py
index 5dbe85d..46507dd 100644
--- a/wotmate/__init__.py
+++ b/wotmate/__init__.py
@@ -47,6 +47,15 @@ logger = logging.getLogger(__name__)
 # convenience caching so we avoid redundant lookups
 _all_signed_by_cache = {}
 _all_sigs_cache = {}
+_all_uiddata_cache = {}
+_seenkeys = []
+
+
+def get_uiddata_by_pubrow(c, p_rowid):
+    if p_rowid not in _all_uiddata_cache:
+        c.execute('SELECT uiddata FROM uid WHERE pubrowid=?', (p_rowid,))
+        _all_uiddata_cache[p_rowid] = c.fetchone()[0]
+    return _all_uiddata_cache[p_rowid]
 
 
 def get_logger(quiet=False):
@@ -210,14 +219,14 @@ def make_graph_node(c, p_rowid, show_trust=False):
         show = ''
 
     if algo in ALGOS.keys():
-        algosize = '%s %s' % (ALGOS[algo], size)
+        keyline = '{%s %s|%s}' % (ALGOS[algo], size, kid)
     else:
-        algosize = 'ALGO? %s' % size
+        keyline = '{%s}' % kid
 
     if show_trust:
-        anode.set('label', '{{%s\n%s|{val: %s|tru: %s}}|{%s|%s}}' % (name, show, val, trust, algosize, kid))
+        anode.set('label', '{{%s\n%s|{val: %s|tru: %s}}|%s}' % (name, show, val, trust, keyline))
     else:
-        anode.set('label', '{%s\n%s|{%s|%s}}' % (name, show, algosize, kid))
+        anode.set('label', '{%s\n%s|%s}' % (name, show, keyline))
     return anode
 
 
@@ -244,7 +253,7 @@ def cull_redundant_paths(paths, maxpaths=None):
     return culled
 
 
-def get_shortest_path(c, t_p_rowid, b_p_rowid, depth, maxdepth, seenkeys, ignorekeys):
+def get_shortest_path(c, t_p_rowid, b_p_rowid, depth, maxdepth, ignorekeys):
     depth += 1
     sigs = get_all_signed_by(c, t_p_rowid)
 
@@ -257,23 +266,23 @@ def get_shortest_path(c, t_p_rowid, b_p_rowid, depth, maxdepth, seenkeys, ignore
         return None
 
     for (s_p_rowid,) in sigs:
-        if (depth, s_p_rowid) in seenkeys:
-            continue
-        if s_p_rowid in ignorekeys:
+        if s_p_rowid in ignorekeys or (depth, s_p_rowid) in _seenkeys:
             continue
 
-        subchain = get_shortest_path(c, s_p_rowid, b_p_rowid, depth, maxdepth, seenkeys, ignorekeys)
+        subchain = get_shortest_path(c, s_p_rowid, b_p_rowid, depth, maxdepth, ignorekeys)
         if subchain:
             if shortest is None or len(shortest) > len(subchain):
                 shortest = subchain
-                seenkeys.append((depth, s_p_rowid))
+                _seenkeys.append((depth, s_p_rowid))
                 # no need to go any deeper than current shortest
                 maxdepth = depth - 1 + len(shortest)
         else:
-            # if we returned with None, then this key is a dead-end at this depth
-            seenkeys.append((depth, s_p_rowid))
+            # if we returned with None, then this key is a dead-end at this and lower depths
+            for _d in range(depth, maxdepth):
+                _seenkeys.append((_d, s_p_rowid))
 
     if shortest is not None:
+        _seenkeys.append((depth, t_p_rowid))
         return [t_p_rowid] + shortest
 
     return None