背景
攻击是如何发生的?
contracts/CrossChain.sol
中, MerkleProof.validateMerkleProof
函数被调用functionhandlePackage(bytes calldatapayload, bytes calldataproof, uint64 height, uint64 packageSequence, uint8 channelId) onlyInitonlyRelayer sequenceInOrder(packageSequence, channelId) blockSynced(height) channelSupported(channelId) external {
// -- snip --
require(
MerkleProof.validateMerkleProof(
ILightClient(LIGHT_CLIENT_ADDR).getAppHash(height),
STORE_NAME,
generateKey(packageSequence, channelId),
payloadLocal,
proofLocal
),
"invalid merkle proof"
);
// -- snip --
}
contracts/MerkleProof.sol
中,函数function validateMerkleProof
首先将上述步骤 1 中的所有入参组装成十六进制字节码,并通过staticcall
调用 bnb-chain 的 0x65 预编译合约。functionvalidateMerkleProof(bytes32 appHash, string memorystoreName, bytes memorykey, bytes memoryvalue, bytes memoryproof) internal view returns (bool) {
if (appHash == bytes32(0)) {
return false;
}
// | storeName | key length | key | value length | value | appHash | proof |
// | 32 bytes | 32 bytes | | 32 bytes | | 32 bytes ||
bytes memory input = new bytes(128+key.length+value.length+proof.length);
// -- snip --
uint256[1] memory result;
/* solium-disable-next-line */
assembly {
if iszero(staticcall(not(0), 0x65, input, length, result, 0x20)) {}
}
return result[0] == 0x01;
}
}
func (c *iavlMerkleProofValidate) Run(input []byte)
被调用, 步骤 2 的入参被解析并写入变量kvmp
。随后, kvmp.Validate()
被调用。// input: // | payload length | payload |
// | 32 bytes | |
func (c *iavlMerkleProofValidate) Run(input []byte) (result []byte, err error) {
defer func() {
if r := recover(); r != nil {
err = fmt.Errorf("internal error: %v\n", r)
}
}()
// -- snip --
kvmp, err := lightclient.DecodeKeyValueMerkleProof(input[precompileContractInputMetaDataLength:])
if err != nil {
return nil, err
}
valid := kvmp.Validate()
if !valid {
return nil, fmt.Errorf("invalid merkle proof")
}
result = make([]byte, merkleProofValidateResultLength)
binary.BigEndian.PutUint64(result[merkleProofValidateResultLength-uint64TypeLength:], 0x01)
return result, nil
}
kvmp
数据结构定义如下:
kvmp := &KeyValueMerkleProof{
Key: key,
Value: value,
StoreName: storeName,
AppHash: appHash,
Proof: &merkleProof,
}
github.com/bnb-chain/bsc/core/vm/lightclient/types.go
文件中, 函数 func (kvmp *KeyValueMerkleProof) Validate()
被调用,后续相应调用流程如下首先,跳转到 err := prt.VerifyValue(kvmp.Proof, kvmp.AppHash, kp.String(), kvmp.Value)
.
再跳转到 prt.Verify(proof, root, keypath, [][]byte{value})
随后跳转到 poz.Verify(root, keypath, args)
最后跳转到 args, err = op.Run(args)
func (kvmp*KeyValueMerkleProof) Validate() bool { prt := DefaultProofRuntime()
//-- snip --
err := prt.VerifyValue(kvmp.Proof, kvmp.AppHash, kp.String(), kvmp.Value)
return err == nil
}
func (prt *ProofRuntime) VerifyValue(proof *tmcrypto.ProofOps, root []byte, keypath string, value []byte) (err error) {
return prt.Verify(proof, root, keypath, [][]byte{value})
}
func (prt *ProofRuntime) Verify(proof *tmcrypto.ProofOps, root []byte, keypath string, args [][]byte) (err error) {
poz, err := prt.DecodeProof(proof)
if err != nil {
return fmt.Errorf("decoding proof: %w", err)
}
return poz.Verify(root, keypath, args)
}
func (poz ProofOperators) Verify(root []byte, keypath string, args [][]byte) (err error) {
// -- snip --
for i, op := range poz {
// -- snip --
args, err = op.Run(args)
if err != nil {
return
}
}
if !bytes.Equal(root, args[0]) {
return cmn.NewError("Calculated root hash is invalid: expected %+v but got %+v", root, args[0])
}
// -- snip --
return nil
}
opz
是由函数 poz, err := prt.DecodeProof(proof)
解码proof
所得,具体解析结果如下:注意。这些 "操作 "指定了计算 IAVL 树的 Merkle 根的方法,并由 func DefaultProofRuntime() (prt *merkle.ProofRuntime)
ingithub.com/bnb-chain/bsc/core/vm/lightclient/multistoreproof.go
指定
func (op IAVLValueOp) Run
func (opIAVLValueOp) Run(args [][]byte) ([][]byte, error) { if len(args) != 1 {
return nil, cmn.NewError("Value size is not 1")
}
value := args[0]
// Compute the root hash and assume it is valid.
// The caller checks the ultimate root later.
root := op.Proof.ComputeRootHash()
err := op.Proof.Verify(root)
if err != nil {
return nil, cmn.ErrorWrap(err, "computing root hash")
}
// XXX What is the encoding for keys?
// We should decode the key depending on whether it's a string or hex,
// maybe based on quotes and 0x prefix?
err = op.Proof.VerifyItem([]byte(op.key), value)
if err != nil {
return nil, cmn.ErrorWrap(err, "verifying value")
}
return [][]byte{root}, nil
}
MerkleProof.validateMerkleProof
的验证 ,上述代码需要满足两点要求func (op IAVLValueOp) Run
返回的 return [][]byte{root}, nil
结果需与步骤 4 函数 func (poz ProofOperators) Verify
中的 args[0]
参数匹配,即 !bytes.Equal(root, args[0])
。err := op.Proof.Verify(root)
与 err = op.Proof.VerifyItem([]byte(op.key), value)
的返回错误必须为 nil op.Proof.ComputeRootHash()
in func (op IAVLValueOp) Run
计算所得的root
是不可伪造的。因此,我们进一步深入函数 op.Proof.ComputeRootHash()
进行细节追踪:首先跳转至 func (proof *RangeProof) ComputeRootHash()
再跳转至 func (proof *RangeProof) _computeRootHash()
随后调用函数_computeRootHash()
中的闭包 func(path PathToLeaf, rightmost bool)
最后调用到闭包中的hash = (pathWithLeaf{Path: path, Leaf: nleaf,}).computeRootHash()
func (proof *RangeProof) ComputeRootHash() []byte {
if proof == nil {
return nil
}
rootHash, _ := proof.computeRootHash()
return rootHash
}
func (proof *RangeProof) _computeRootHash() (rootHash []byte, treeEnd bool, err error) {
if len(proof.Leaves) == 0 {
return nil, false, cmn.ErrorWrap(ErrInvalidProof, "no leaves")
}
if len(proof.InnerNodes)+1 != len(proof.Leaves) {
return nil, false, cmn.ErrorWrap(ErrInvalidProof, "InnerNodes vs Leaves length mismatch, leaves should be 1 more.")
}
// Start from the left path and prove each leaf.
// shared across recursive calls
var leaves = proof.Leaves
var innersq = proof.InnerNodes
var COMPUTEHASH func(path PathToLeaf, rightmost bool) (hash []byte, treeEnd bool, done bool, err error)
// rightmost: is the root a rightmost child of the tree?
// treeEnd: true iff the last leaf is the last item of the tree.
// Returns the (possibly intermediate, possibly root) hash.
COMPUTEHASH = func(path PathToLeaf, rightmost bool) (hash []byte, treeEnd bool, done bool, err error) {
// Pop next leaf.
nleaf, rleaves := leaves[0], leaves[1:]
leaves = rleaves
// Compute hash.
hash = (pathWithLeaf{
Path: path,
Leaf: nleaf,
}).computeRootHash()
// -- snip --
// We're not done yet (leaves left over). No error, not done either.
// Technically if rightmost, we know there's an error "left over leaves
// -- malformed proof", but we return that at the top level, below.
return hash, false, false, nil
}
// Verify!
path := proof.LeftPath
rootHash, treeEnd, done, err := COMPUTEHASH(path, true)
if err != nil {
return nil, treeEnd, cmn.ErrorWrap(err, "root COMPUTEHASH call")
} else if !done {
return nil, treeEnd, cmn.ErrorWrap(ErrInvalidProof, "left over leaves -- malformed proof")
}
// Ok!
return rootHash, treeEnd, nil
}
func (pwl pathWithLeaf) computeRootHash()
中我们可以发现,步骤 6 中所述 root
仅与 IAVL 树的最左侧叶子节点及其路径级联的哈希相关。
// `computeRootHash` computes the root hash with leaf node.
// Does not verify the root hash.
func (pwl pathWithLeaf) computeRootHash() []byte {
leafHash := pwl.Leaf.Hash()
return pwl.Path.computeRootHash(leafHash)
}
RangeProof
定义中的对应关系如下type RangeProof struct { // You don't need the right path because // it can be derived from what we have. LeftPath PathToLeaf `json:"left_path"` InnerNodes []PathToLeaf `json:"inner_nodes"` Leaves []proofLeafNode `json:"leaves"` // memoize rootVerified bool rootHash []byte // valid iff rootVerified is true treeEnd bool // valid iff rootVerified is true }
github.com/tendermint/iavl@v0.12.0/proof_path.go
相关文件中,发现了中间节点哈希级联运算函数的漏洞。值得一提,尽管在 BSC 中调用的版本是 v0.12.0,我们发现在该库的最新版本实现中仍然存在相应问题。无需担心的是,相关问题已经有热心开发者通过issue#579反馈给 tendermint 的相关开发团队。
func (pin proofInnerNode) Hash(childHash []byte) []byte {
hasher := tmhash.New()
buf := new(bytes.Buffer)
// -- snip --
// Where the bug is located
if len(pin.Left) == 0 {
if err == nil {
err = amino.EncodeByteSlice(buf, childHash)
}
if err == nil {
err = amino.EncodeByteSlice(buf, pin.Right)
}
} else {
if err == nil {
err = amino.EncodeByteSlice(buf, pin.Left)
}
if err == nil {
err = amino.EncodeByteSlice(buf, childHash)
}
}
// -- snip --
hasher.Write(buf.Bytes())
return hasher.Sum(nil)
}
func (pin proofInnerNode) Hash(childHash []byte)
中,目标中间节点的左孩子 len(pin.Left)
长度不为 0,根据代码逻辑,理应进入到else
分支。在else
分支中,我们发现其计算仅涵盖了pin.Left
与childHash
,而 pin.Right
并未纳入哈希计算中。因此,尽管一个恶意的节点被插入到 IAVL 树的证明中,其 IAVL 树的根哈希校验依旧可以通过,最终导致了此次攻击的发生。其他潜在攻击
github.com/cosmos/iavl
,使用该库的项目包括 cosmos 生态的核心组件 cosmos-sdk , IBC 等. 因此理论上使用 cosmos-sdk 构建的的项目、与 cosmos 跨链的项目都有可能受到影响,下文我们将分析是否有实际的攻击可能性。ics23
规定了可使用的向量证明,其中就包括了 iavl 树的证明。因此我们需要调查 github.com/cosmos/iavl
的错误实现是否引入 ics23
的实现中。ics23
实现为ics-23-go 和 [confio/ics23](https://github.com/confio/ics23/blob/a4daeb4c24ce1be827829c0841446abc690c4f11/go/proof.go#L122。这里的实现没有使用 iavl 库,因此没有收到影响。github.com/cosmos/iavl
库做验证的项目依旧可能存在被攻击的风险(即使已经升级 SDK)。小心!THE END
【免责声明】市场有风险,投资需谨慎。本文不构成投资建议,用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资,责任自负。