sigstore._internal.merkle

  1# Copyright 2022 The Sigstore Authors
  2#
  3# Licensed under the Apache License, Version 2.0 (the "License");
  4# you may not use this file except in compliance with the License.
  5# You may obtain a copy of the License at
  6#
  7#      http://www.apache.org/licenses/LICENSE-2.0
  8#
  9# Unless required by applicable law or agreed to in writing, software
 10# distributed under the License is distributed on an "AS IS" BASIS,
 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 12# See the License for the specific language governing permissions and
 13# limitations under the License.
 14
 15"""
 16Utilities for verifying proof-of-inclusion within Rekor's Merkle Tree.
 17
 18This code is based off Google's Trillian Merkle Tree implementation which Cosign uses to validate
 19Rekor entries.
 20
 21The data format for the Merkle tree nodes is described in IETF's RFC 6962.
 22"""
 23
 24from __future__ import annotations
 25
 26import base64
 27import hashlib
 28import struct
 29import typing
 30from typing import List, Tuple
 31
 32from sigstore._utils import HexStr
 33from sigstore.errors import VerificationError
 34
 35if typing.TYPE_CHECKING:
 36    from sigstore.models import LogEntry
 37
 38
 39_LEAF_HASH_PREFIX = 0
 40_NODE_HASH_PREFIX = 1
 41
 42
 43def _decomp_inclusion_proof(index: int, size: int) -> Tuple[int, int]:
 44    """
 45    Breaks down inclusion proof for a leaf at the specified |index| in a tree of the specified
 46    |size| into 2 components. The splitting point between them is where paths to leaves |index| and
 47    |size-1| diverge.
 48
 49    Returns lengths of the bottom and upper proof parts correspondingly. The sum of the two
 50    determines the correct length of the inclusion proof.
 51    """
 52
 53    inner = (index ^ (size - 1)).bit_length()
 54    border = bin(index >> inner).count("1")
 55    return inner, border
 56
 57
 58def _chain_inner(seed: bytes, hashes: List[str], log_index: int) -> bytes:
 59    """
 60    Computes a subtree hash for a node on or below the tree's right border. Assumes |proof| hashes
 61    are ordered from lower levels to upper, and |seed| is the initial subtree/leaf hash on the path
 62    located at the specified |index| on its level.
 63    """
 64
 65    for i in range(len(hashes)):
 66        h = bytes.fromhex(hashes[i])
 67        if (log_index >> i) & 1 == 0:
 68            seed = _hash_children(seed, h)
 69        else:
 70            seed = _hash_children(h, seed)
 71    return seed
 72
 73
 74def _chain_border_right(seed: bytes, hashes: List[str]) -> bytes:
 75    """
 76    Chains proof hashes along tree borders. This differs from inner chaining because |proof|
 77    contains only left-side subtree hashes.
 78    """
 79
 80    for h in hashes:
 81        seed = _hash_children(bytes.fromhex(h), seed)
 82    return seed
 83
 84
 85def _hash_children(lhs: bytes, rhs: bytes) -> bytes:
 86    pattern = f"B{len(lhs)}s{len(rhs)}s"
 87    data = struct.pack(pattern, _NODE_HASH_PREFIX, lhs, rhs)
 88    return hashlib.sha256(data).digest()
 89
 90
 91def _hash_leaf(leaf: bytes) -> bytes:
 92    pattern = f"B{len(leaf)}s"
 93    data = struct.pack(pattern, _LEAF_HASH_PREFIX, leaf)
 94    return hashlib.sha256(data).digest()
 95
 96
 97def verify_merkle_inclusion(entry: LogEntry) -> None:
 98    """Verify the Merkle Inclusion Proof for a given Rekor entry."""
 99    inclusion_proof = entry.inclusion_proof
100
101    # Figure out which subset of hashes corresponds to the inner and border nodes.
102    inner, border = _decomp_inclusion_proof(
103        inclusion_proof.log_index, inclusion_proof.tree_size
104    )
105
106    # Check against the number of hashes.
107    if len(inclusion_proof.hashes) != (inner + border):
108        raise VerificationError(
109            f"inclusion proof has wrong size: expected {inner + border}, got "
110            f"{len(inclusion_proof.hashes)}"
111        )
112
113    # The new entry's hash isn't included in the inclusion proof so we should calculate this
114    # ourselves.
115    leaf_hash: bytes = _hash_leaf(base64.b64decode(entry.body))
116
117    # Now chain the hashes belonging to the inner and border portions. We should expect the
118    # calculated hash to match the root hash.
119    intermediate_result: bytes = _chain_inner(
120        leaf_hash, inclusion_proof.hashes[:inner], inclusion_proof.log_index
121    )
122
123    calc_hash: HexStr = HexStr(
124        _chain_border_right(intermediate_result, inclusion_proof.hashes[inner:]).hex()
125    )
126
127    if calc_hash != inclusion_proof.root_hash:
128        raise VerificationError(
129            f"inclusion proof contains invalid root hash: expected {inclusion_proof}, calculated "
130            f"{calc_hash}"
131        )