Boost _ Firedancer v0.1 34272 - [Blockchain_DLT - Medium] Remote memory corruption in Shred tile
Remote memory corruption in Shred tile
Submitted on Wed Aug 07 2024 22:54:16 GMT-0400 (Atlantic Standard Time) by @Swift77057 for Boost | Firedancer v0.1
Report ID: #34272
Report type: Blockchain/DLT
Report severity: Medium
Target: https://github.com/firedancer-io/firedancer/tree/e60d9a6206efaceac65a5a2c3a9e387a79d1d096
Impacts:
Key compromise/exfiltration exploit chain
Liveness issues that cause Firedancer v0.1 validators to crash or be unavailable
Remote Code Execution (RCE)
Description
Remote memory corruption in Shred tile
Overview
A memory corruption vulnerability exists in the Shred tile of Frankendancer and Firedancer. The vulnerability is a critical out-of-bounds write on the end of a heap allocation with fully attacker-controlled data and can be triggered by a UDP packet received from a fully remote attacker.
Root Cause
The root cause is that the calculated footprint for fd_bmtree is too small to contain Merkle trees of high depth. In particular, the footprint for fd_bmtree_commit is calculated as follows:
Going deeper, the fd_bmtree objects are allocated jointly by fd_fec_resolver_new() as follows:
The parameter INCLUSION_PROOF_LAYERS is defined to 10 which means that each fd_bmtree has the following layout:
one
fd_bmtree_commit_theader1023
fd_bmtree_node_tnodes16
ulongbitmap containing valid bits for each node
Now that we understand the layout of fd_bmtree, let's analyze how it's being used by fd_fec_resolver_add_shred() which is the function that processes incoming shreds from the P2P UDP network. The fd_bmtree objects are initialized lazily upon the first received packet (when the ctx lookup fails), and they are allocated from a linked list allocator ("freelist"). Here is that location:
After the fd_bmtree has been initialized and associated to a context, incoming shreds use fd_bmtree_commitp_insert_with_proof() to insert additional proof entries into the tree. Here is where the vulnerability lies. The fd_bmtree_commitp_insert_with_proof() takes two parameters: tree_depth (now called proof_depth) and shred_idx. The tree depth is calculated according to:
Tracing deeper, the tree_depth is the lowest 4 bits of the shred->variant parameter that is attacker-controlled. As given by 4 bits it can take any value between 0 and 15. However the fd_bmtree was only allocated to hold 1023 nodes. In the first for-loop inside fd_bmtree_commitp_insert_with_proof() we find the following snippet:
The iterator layer will iterate through range of values [0..proof_depth). The calculation of sibling_idx is somewhat complicated, but to quicky illustrate the point it has a contributing term of (2UL<<layer) which maximally comes out to (2 << 15) == 65536 in the final iteration. This is much greater than the 1023 entries the fd_bmtree was designed to handle. This for loop will access state->inclusion_proofs out-of-bounds... but these access are only reads and does not yet lead to memory corruption. The HAS() macro also goes out-of-bounds at this point by the way.
After that, there's another for loop. I will spare the details here as they are not interesting... Unlike other loops in this function, this loop actually checks the index against inclusion_proof_sz and will eventually break due to that condition. Because of this condition, it will not go out-of-bounds.
Finally there are two for loops which copies the proofs into the tree. Here they are...
The last loop causes an out-of-bounds write at point [a] where the memcpy() copies the i:th proof to state->inclusion_proofs[ sibling_idx ].hash. Once again, sibling_idx is too large because of the contributing term (2UL<<i) which is maximally (2<<15), whereas the inclusion_proofs array only holds 1023 entries.
The heap and freelist can be groomed in various ways by sending network packets.
Impact
The impact is a critical remotely triggered memory corruption in the Shred tile, which can lead to remote code execution in the Shred tile. The out-of-bounds data is fully controlled by the remote attacker, while the offset can be partially influenced but has constaints. The predictable memory layout as a result of the combined heap allocation helps make memory layout easier and more reliable, and an exploit developer might be able to use that to their advantage.
The P2P UDP packets have an Ed25519 signature, but the corruption is triggered prior to signature verification so the corruption is within reach even by attackers that don't have a high stake in the network and a correct signature is not required to exploit the vulnerability.
Proof of concept
Proof-of-concept
We have tested and confirmed the vulnerability at Git commit hash as specified in the Bounty program: e60d9a6206efaceac65a5a2c3a9e387a79d1d096
Attached to this report is a proof-of-concept Python script which constructs the necessary UDP payloads to trigger the vulnerability:
It crashes with the following register output:
As can be seen above in the register dump, r15 has been completely controlled as a result of the memory corruption (0x4141414141414141).
To make the proof-of-concept more concise, the following diff was applied to Frankendancer. Note that none of the changes are required to trigger the vulnerability, they are just there to feng shui the bmtree freelist to get it to a state where it can clearly showcase the vulnerability:
Last updated
Was this helpful?