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

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 

30 

31from sigstore._utils import HexStr 

32from sigstore.errors import VerificationError 

33 

34if typing.TYPE_CHECKING: 

35 from sigstore.models import LogEntry 

36 

37 

38_LEAF_HASH_PREFIX = 0 

39_NODE_HASH_PREFIX = 1 

40 

41 

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

43 """ 

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

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

46 |size-1| diverge. 

47 

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

49 determines the correct length of the inclusion proof. 

50 """ 

51 

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

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

54 return inner, border 

55 

56 

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

58 """ 

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

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

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

62 """ 

63 

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

65 h = bytes.fromhex(hashes[i]) 

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

67 seed = _hash_children(seed, h) 

68 else: 

69 seed = _hash_children(h, seed) 

70 return seed 

71 

72 

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

74 """ 

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

76 contains only left-side subtree hashes. 

77 """ 

78 

79 for h in hashes: 

80 seed = _hash_children(bytes.fromhex(h), seed) 

81 return seed 

82 

83 

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

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

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

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

88 

89 

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

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

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

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

94 

95 

96def verify_merkle_inclusion(entry: LogEntry) -> None: 

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

98 inclusion_proof = entry.inclusion_proof 

99 

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

101 inner, border = _decomp_inclusion_proof( 

102 inclusion_proof.log_index, inclusion_proof.tree_size 

103 ) 

104 

105 # Check against the number of hashes. 

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

107 raise VerificationError( 

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

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

110 ) 

111 

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

113 # ourselves. 

114 leaf_hash: bytes = _hash_leaf(base64.b64decode(entry.body)) 

115 

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

117 # calculated hash to match the root hash. 

118 intermediate_result: bytes = _chain_inner( 

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

120 ) 

121 

122 calc_hash: HexStr = HexStr( 

123 _chain_border_right(intermediate_result, inclusion_proof.hashes[inner:]).hex() 

124 ) 

125 

126 if calc_hash != inclusion_proof.root_hash: 

127 raise VerificationError( 

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

129 f"{calc_hash}" 

130 )