Hello,
I have some runnable pseudocode outlining a faster tree verification algorithm.
Before I create patches I'd like to see if there is any guidance on making the
changes as unobtrusive as possible. If the radical change in algorithm is
acceptable I can work on adding the changes.
Instead of composing any kind of structured data out of the portage tree my
algorithm just lists all files and then optionally batches them out to threads.
There is a noticeable speedup by eliding the tree traversal operations which
can be seen when running the algorithm with a single thread and comparing it to
the current algorithm in gemato (which should still be discussed here?).
Some simple tests like counting all objects traversed and verified returns the
same(ish). Once it is put into portage it could be tested in detail.
There is also my partial attempt at removing the brittle interface to GnuPG
(it's not as if the current code is badly designed, just that parsing the
output of GnuPG directly is likely not the best idea).
Needs gemato, dnspython, and requests. Slightly better than random code because
I took inspiration from the existing gemato classes.
```python (veriftree.py)
#!/usr/bin/env python3
import os, sys, zlib, hashlib, tempfile, shutil, timeit
import subprocess
from typing import List
from pprint import pprint
from gemato.manifest import (
ManifestFile,
ManifestFileEntry,
)
from wkd import (
check_domain_signature,
hash_localpart,
build_web_key_uri,
stream_to_file
)
from fetchmedia import (
OpenPGPEnvironment,
setup_verification_environment
)
# 0. Top level directory (repository) contains Manifest, a PGP signature of
# blake2b and sha512 hashes of Manifest.files.gz.
# 1. Manifest.files contains hashes of each category Manifest.gz.
# 2. The category Manifest contains hashes of each package Manifest.
# 3. The package Manifest contains hashes of each package file.
# Must be aware of PMS, e.g. aux tag specifies a file in files/.
# 0. Check signature of repo Manifest.
# 1. Merge items in Manifest.files, each category Manifest, and each package
# Manifest into one big list. The path must be made absolute.
# 2. Distribute items to threads.
# To check operation compare directory tree to files appearing in all
# ManifestRecords.
class ManifestTree(object):
__slots__ = ['_directory', '_manifest_list', '_manifest_records',
'_manifest_results']
def __init__(self, directory: str):
self._directory = directory
# Tuples of (base_path, full_path).
self._manifest_list = []
self._manifest_records = []
self._manifest_results = []
def build_manifest_list(self):
for path, dirs, files in os.walk(self._directory):
#if 'glsa' in path or 'news' in path:
#if 'metadata' in path:
# continue # Skip the metadata directory for now.
# It contains a repository. Current algo barfs on Manifest
# containing only sig.
if 'Manifest.files.gz' in files:
self._manifest_list += [(path, path + '/Manifest.files.gz')]
if 'Manifest.gz' in files:
self._manifest_list += [(path, path + '/Manifest.gz')]
if path == self._directory:
continue # Skip the repo manifest. Order matters, fix
eventually.
if 'Manifest' in files:
self._manifest_list += [(path, path + '/Manifest')]
def parse_manifests(self):
td = tempfile.TemporaryDirectory(dir='./')
for manifest in self._manifest_list:
def inner():
if manifest[1].endswith('.gz'):
name = 'Manifest.files' # Need to also handle Manifest.gz.
path = '{0}/{1}'.format(td.name, name)
subprocess.run(['sh', '-c', 'gunzip -c {0} > {1}'
.format(manifest[1], path)])
for line in open(path):
mr = ManifestRecord(line)
mr.make_absolute(manifest[0])
self._manifest_records += [mr]
else:
for line in open(manifest[1]):
if line.startswith('-'):
return # Skip the signed manifest.
mr = ManifestRecord(line)
mr.make_absolute(manifest[0])
self._manifest_records += [mr]
inner()
def verify_manifests(self):
for record in self._manifest_records:
self._manifest_results += [record.verify()]
class ManifestRecord(object):
__slots__ = ['_tag', '_abs_path', '_path', '_size', '_hashes']
def __init__(self, line: str=None):
self._tag = None
self._abs_path = None
self._path = None
self._size = None
self._hashes = []
if line:
self.from_string(line)
def from_string(self, line: str) -> None:
parts = line.split()
if len(parts) == 2:
self._tag = 'ignore'
return
self._tag = parts[0]
self._path = parts[1]
self._size = parts[2]
self._hashes = parts[3:]
def make_absolute(self, abs_path: str) -> None:
self._abs_path = abs_path
try:
pass
#if 'md5-cache' in abs_path:
# print(abs_path + '/' + self._path)
except TypeError as exc:
return
def verify(self) -> bool:
if self._tag == 'ignore':
return None
# Where is best place to do this? Before?
if self._tag.lower() == 'aux':
self._path = self._abs_path + '/files/' + self._path
elif self._abs_path:
self._path = self._abs_path + '/' + self._path
# Distfiles will not be present.
if self._tag.lower() == 'dist':
return None
if not os.path.exists(self._path):
return False
fd = open(self._path, 'rb')
sha512 = hashlib.sha512()
blake2b = hashlib.blake2b()
while True:
d = fd.read(8192)
if not d:
break
sha512.update(d)
blake2b.update(d)
rsha512 = sha512.hexdigest()
rblake2b = blake2b.hexdigest()
if rblake2b != self._hashes[1]:
return False
if rsha512 != self._hashes[3]:
return False
return True
def __repr__(self) -> str:
#return repr(self._hashes)
return '\t'.join([self._tag, self._size, self._path])
def main() -> int:
# Step 0: verify the repo manifest.
#publishers = ['infrastruct...@gentoo.org']
#ev = setup_verification_environment(publishers)
#mf = ManifestFile()
#mf.load(open('/var/db/repos/gentoo/Manifest'),
# verify_openpgp=True, openpgp_env=ev)
#pprint(mf)
#pprint(mf.openpgp_signed)
#pprint(mf.openpgp_signature)
# Step 1: merge manifests.
#mt = ManifestTree('/var/db/repos/gentoo')
#mt.build_manifest_list()
#mt.parse_manifests()
#mt.verify_manifests()
glsa = ManifestTree('/var/db/repos/gentoo')
glsa.build_manifest_list()
glsa.parse_manifests()
start = timeit.default_timer()
glsa.verify_manifests()
end = timeit.default_timer()
pprint(end - start)
# Handled by checking for None.
#no_ignore = filter(lambda x: x._tag != 'ignore', glsa_manifest_results)
#pprint(glsa._manifest_results)
real_files = [x for x in filter(lambda x: x is not None,
glsa._manifest_results)]
#pprint(real_files)
pprint(len(glsa._manifest_results))
pprint(len(real_files))
all_files = []
for path, dirs, files in os.walk('/var/db/repos/gentoo'):
pass
return 0
if __name__ == '__main__':
sys.exit(main())
```
```python (wkd.py, likely unneeded but I didn't want to redo these files yet)
#!/usr/bin/env python3
import sys, hashlib
import dns
from dns import (
name, query, dnssec,
message, resolver, rdatatype
)
import shutil, requests
def check_domain_signature(domain: str) -> bool:
response = dns.resolver.query(domain, dns.rdatatype.NS)
nsname = response.rrset[0]
response = dns.resolver.query(str(nsname), dns.rdatatype.A)
nsaddr = response.rrset[0].to_text()
# DNSKEY
request = dns.message.make_query(domain,
dns.rdatatype.DNSKEY, want_dnssec=True)
response = dns.query.udp(request, nsaddr)
if response.rcode() != 0:
raise Exception('Unable to request dnskey.')
answer = response.answer
if len(answer) != 2:
raise Exception('Malformed answer to dnskey query.')
name = dns.name.from_text(domain)
try:
dns.dnssec.validate(answer[0], answer[1], {name: answer[0]})
except dns.dnssec.ValidationFailure as exc:
# Validation failed. The raise causes python to abort with status 1.
#raise exc
return False
except AttributeError as exc:
# Validation may have failed; DNSKEY missing signer attribute. dig may
report
# domain as valid.
#
# TODO: Additional state where subdomain of valid domain may fail with
3 nested
# KeyErrors. Avoid temptation to wildcard catch. Safer to put in
process?
#raise exc
return False
else:
return True
def hash_localpart(incoming: bytes) -> str:
'''Z-base32 the localpart of an e-mail address
https://tools.ietf.org/html/draft-koch-openpgp-webkey-service-08#section-3.1
describes why this is needed.
See https://tools.ietf.org/html/rfc6189#section-5.1.6 for a
description of the z-base32 scheme.
'''
zb32 = "ybndrfg8ejkmcpqxot1uwisza345h769"
b = hashlib.sha1(incoming).digest()
ret = ""
assert(len(b) * 8 == 160)
for i in range(0, 160, 5):
byte = i // 8
offset = i - byte * 8
# offset | bits remaining in k+1 | right-shift k+1
# 3 | 0 | x
# 4 | 1 | 7
# 5 | 2 | 6
# 6 | 3 | 5
# 7 | 4 | 4
if offset < 4:
n = (b[byte] >> (3 - offset))
else:
n = (b[byte] << (offset - 3)) + (b[byte + 1] >> (11 - offset))
ret += zb32[n & 0b11111]
return ret
def build_web_key_uri(address: str) -> str:
local, remote = address.split('@')
local = hash_localpart(local.encode('utf-8'))
return 'https://' + remote + '/.well-known/openpgpkey/hu/' + \
local
def stream_to_file(uri: str, fname: str) -> None:
with requests.get(uri, verify=True, stream=True) as r:
from pprint import pprint
pprint(r.headers)
with open(fname, 'wb') as f:
shutil.copyfileobj(r.raw, f)
```
