Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/sigstore/_internal/merkle.py: 34%

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 hashlib 

27import struct 

28import typing 

29 

30from sigstore.errors import VerificationError 

31 

32if typing.TYPE_CHECKING: 

33 from sigstore.models import TransparencyLogEntry 

34 

35 

36_LEAF_HASH_PREFIX = 0 

37_NODE_HASH_PREFIX = 1 

38 

39 

40def _decomp_inclusion_proof(index: int, size: int) -> tuple[int, int]: 

41 """ 

42 Breaks down inclusion proof for a leaf at the specified |index| in a tree of the specified 

43 |size| into 2 components. The splitting point between them is where paths to leaves |index| and 

44 |size-1| diverge. 

45 

46 Returns lengths of the bottom and upper proof parts correspondingly. The sum of the two 

47 determines the correct length of the inclusion proof. 

48 """ 

49 

50 inner = (index ^ (size - 1)).bit_length() 

51 border = bin(index >> inner).count("1") 

52 return inner, border 

53 

54 

55def _chain_inner(seed: bytes, hashes: list[bytes], log_index: int) -> bytes: 

56 """ 

57 Computes a subtree hash for a node on or below the tree's right border. Assumes |proof| hashes 

58 are ordered from lower levels to upper, and |seed| is the initial subtree/leaf hash on the path 

59 located at the specified |index| on its level. 

60 """ 

61 

62 for i in range(len(hashes)): 

63 h = hashes[i] 

64 if (log_index >> i) & 1 == 0: 

65 seed = _hash_children(seed, h) 

66 else: 

67 seed = _hash_children(h, seed) 

68 return seed 

69 

70 

71def _chain_border_right(seed: bytes, hashes: list[bytes]) -> bytes: 

72 """ 

73 Chains proof hashes along tree borders. This differs from inner chaining because |proof| 

74 contains only left-side subtree hashes. 

75 """ 

76 

77 for h in hashes: 

78 seed = _hash_children(h, seed) 

79 return seed 

80 

81 

82def _hash_children(lhs: bytes, rhs: bytes) -> bytes: 

83 pattern = f"B{len(lhs)}s{len(rhs)}s" 

84 data = struct.pack(pattern, _NODE_HASH_PREFIX, lhs, rhs) 

85 return hashlib.sha256(data).digest() 

86 

87 

88def _hash_leaf(leaf: bytes) -> bytes: 

89 pattern = f"B{len(leaf)}s" 

90 data = struct.pack(pattern, _LEAF_HASH_PREFIX, leaf) 

91 return hashlib.sha256(data).digest() 

92 

93 

94def verify_merkle_inclusion(entry: TransparencyLogEntry) -> None: 

95 """Verify the Merkle Inclusion Proof for a given Rekor entry.""" 

96 inclusion_proof = entry._inner.inclusion_proof 

97 

98 # Figure out which subset of hashes corresponds to the inner and border nodes. 

99 inner, border = _decomp_inclusion_proof( 

100 inclusion_proof.log_index, inclusion_proof.tree_size 

101 ) 

102 

103 # Check against the number of hashes. 

104 if len(inclusion_proof.hashes) != (inner + border): 

105 raise VerificationError( 

106 f"inclusion proof has wrong size: expected {inner + border}, got " 

107 f"{len(inclusion_proof.hashes)}" 

108 ) 

109 

110 # The new entry's hash isn't included in the inclusion proof so we should calculate this 

111 # ourselves. 

112 leaf_hash: bytes = _hash_leaf(entry._inner.canonicalized_body) 

113 

114 # Now chain the hashes belonging to the inner and border portions. We should expect the 

115 # calculated hash to match the root hash. 

116 intermediate_result: bytes = _chain_inner( 

117 leaf_hash, inclusion_proof.hashes[:inner], inclusion_proof.log_index 

118 ) 

119 

120 calc_hash = _chain_border_right(intermediate_result, inclusion_proof.hashes[inner:]) 

121 

122 if calc_hash != inclusion_proof.root_hash: 

123 raise VerificationError( 

124 f"inclusion proof contains invalid root hash: expected {inclusion_proof}, calculated " 

125 f"{calc_hash.hex()}" 

126 )