Published on: 2017-09-12T11:44:48+00:00
In an email exchange on the bitcoin-dev mailing list, Mark Friedenbach discussed a potential attack on Bitcoin's hash trees. The attack involves creating a script that appears safe but is actually controlled by the attacker. Friedenbach presented two possible scripts and suggested modifying the scheme to use a different initialization vector (IV) for hash tree updates to prevent such attacks. However, another user responded with an example of a MAST branch that requires only a few bytes of collision, indicating that the attack may not be as difficult as initially thought.The email thread also discusses the vulnerability of third-party scripts in general. The attack described involves finding a collision between innocuous and malign scripts using different hash functions. Friedenbach explained the procedure for getting a collision and suggested that multi-party wallet level protocols should require a 'delinearization' step to prove the safety of a construct.In response to Russell O'Connor's query about a security breach in the Bitcoin Improvement Proposal (BIP) tree structure, Friedenbach expressed uncertainty about the possibility of conducting the attack described using the specified tree structure. He believes that breaking SHA256 completely would be necessary to accomplish the attack. O'Connor expressed concern about the lack of distinction between leaf nodes and internal nodes in the design, which could lead to vulnerabilities. He suggested using a different IV for the fast hash of internal nodes to mitigate this risk.Peter Todd agreed with O'Connor's proposal for a fast hash for internal nodes, but cautioned against creating new hash functions using custom IVs. He suggested using bog-standard SHA256 with a fixed first block to allow optimized implementations to start with a fixed midstate. Todd clarified that using custom IVs results in a hash function equivalent to prefixing the data with the padded version of the fixed string and using a regular SHA256 hash.The design of fast Merkle trees does not distinguish between leaf nodes and internal nodes, allowing for validation of paths longer than 32 branches. However, this lack of distinction poses a security risk. O'Connor demonstrated how counterparty could include specially crafted "scripts" masquerading as leaves, allowing them to reveal malicious code at a deeper level. O'Connor suggested using a fixed IV value for the fast hash of internal nodes to address this vulnerability.In a recent email, O'Connor proposed that the fast hash for internal nodes should use a fixed value that is the SHA-256 hash of a fixed string. However, it is noted that new hash functions should generally not be created by using custom IVs. Instead, bog-standard SHA256 should be used with a fixed first block.Overall, the discussions revolve around the potential attack on Bitcoin's hash trees, the vulnerability of third-party scripts, and the need for modifications in the design of fast Merkle trees to prevent attacks and address security risks. The provided links contain additional information and code related to these topics.
Updated on: 2023-08-01T21:50:13.813968+00:00