diff options
author | Magnus Ahltorp <map@kth.se> | 2015-02-19 16:23:25 +0100 |
---|---|---|
committer | Magnus Ahltorp <map@kth.se> | 2015-02-19 16:23:25 +0100 |
commit | 16d405f4d696c3d01785b644678261acb0e9ad3a (patch) | |
tree | 68a427e953c270766b2c4a510d81b7f13abe4222 | |
parent | 6e5730c8d7eecec7314c15419aff1112960398bb (diff) |
Added verification of consistency proofs
-rw-r--r-- | tools/certtools.py | 89 | ||||
-rwxr-xr-x | tools/fetchallcerts.py | 6 |
2 files changed, 95 insertions, 0 deletions
diff --git a/tools/certtools.py b/tools/certtools.py index 31045b9..5b556cf 100644 --- a/tools/certtools.py +++ b/tools/certtools.py @@ -461,3 +461,92 @@ def get_intermediate_hash(store, treesize, level, index): zf.close() assert len(layer0) == lastleaf - firstleaf + 1 return calculated_hash + +def bits(n): + p = 0 + while n > 0: + n >>= 1 + p += 1 + return p + +def merkle_height(n): + if n == 0: + return 1 + return bits(n - 1) + +def node_above((pathp, pathl), levels=1): + return (pathp >> levels, pathl + levels) + +def node_even((pathp, pathl)): + return pathp & 1 == 0 + +def node_odd((pathp, pathl)): + return pathp & 1 == 1 + +def node_lower((path1p, path1l), (path2p, path2l)): + return path1l < path2l + +def node_higher((path1p, path1l), (path2p, path2l)): + return path1l > path2l + +def node_level((path1p, path1l)): + return path1l + +def node_outside((path1p, path1l), (path2p, path2l)): + assert path1l == path2l + return path1p > path2p + +def combine_two_hashes((path1, hash1), (path2, hash2), treesize): + assert not node_higher(path1, path2) + edge_node = (treesize - 1, 0) + + if node_lower(path1, path2): + assert path1 == node_above(edge_node, levels=node_level(path1)) + while node_even(path1): + path1 = node_above(path1) + + assert node_above(path1) == node_above(path2) + assert (node_even(path1) and node_odd(path2)) or (node_odd(path1) and node_even(path2)) + + if node_outside(path2, node_above(edge_node, levels=node_level(path2))): + return (node_above(path1), hash1) + + if node_even(path1): + newhash = internal_hash((hash1, hash2)) + else: + newhash = internal_hash((hash2, hash1)) + + return (node_above(path1), newhash) + +def path_as_string(pos, level, treesize): + height = merkle_height(treesize) + path = "{0:0{width}b}".format(pos, width=height - level) + if height == level: + return "" + return path + +def nodes_for_pos(pos, treesize): + height = merkle_height(treesize) + nodes = [] + level = 0 + while pos > 0 and pos & 1 == 0: + pos >>= 1 + level += 1 + if pos & 1: + nodes.append((pos ^ 1, level)) + #print pos, level + while level < height: + pos_level0 = pos * (2 ** level) + #print pos, level + if pos_level0 < treesize: + nodes.append((pos, level)) + pos >>= 1 + pos ^= 1 + level += 1 + return nodes + +def verify_consistency_proof(consistency_proof, first, second): + chain = zip(nodes_for_pos(first, second), consistency_proof) + (_, hash) = reduce(lambda e1, e2: combine_two_hashes(e1, e2, second), chain) + (_, oldhash) = reduce(lambda e1, e2: combine_two_hashes(e1, e2, first), chain) + return (oldhash, hash) diff --git a/tools/fetchallcerts.py b/tools/fetchallcerts.py index 866bb43..39ffd64 100755 --- a/tools/fetchallcerts.py +++ b/tools/fetchallcerts.py @@ -168,6 +168,12 @@ else: print "calculated root hash", base64.b16encode(calculated_root_hash) +if oldsth and oldsth["tree_size"] > 0 and oldsth["tree_size"] != tree_size: + consistency_proof = [base64.decodestring(entry) for entry in get_consistency_proof(args.baseurl, oldsth["tree_size"], tree_size)] + (old_treehead, new_treehead) = verify_consistency_proof(consistency_proof, oldsth["tree_size"], tree_size) + assert old_treehead == base64.b64decode(oldsth["sha256_root_hash"]) + assert new_treehead == base64.b64decode(sth["sha256_root_hash"]) + if calculated_root_hash != root_hash: print "fetched root hash and calculated root hash different" sys.exit(1) |