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:
FD_FN_CONST ulong
fd_bmtree_commit_footprint( ulong inclusion_proof_layer_cnt ) {
/* A complete binary tree with n layers has (2^n)-1 nodes. We keep 1
extra bmtree_node_t (included in sizeof(fd_bmtree_commit_t)) to
avoid branches when appending commits. */
return fd_ulong_align_up( sizeof(fd_bmtree_commit_t) +
( (1UL<<inclusion_proof_layer_cnt)-1UL )*sizeof(fd_bmtree_node_t) +
(((1UL<<inclusion_proof_layer_cnt)+63UL)/64UL)*sizeof(ulong),
fd_bmtree_commit_align() );
}
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_t header
1023 fd_bmtree_node_t nodes
16 ulong bitmap 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:
if( FD_UNLIKELY( !ctx ) ) {
// redacted for simplicity
void * bmtree_mem = bmtrlist_pop_head( bmtree_free_list );
/* Now we need to derive the root of the Merkle tree and verify the
signature to prevent a DOS attack just by sending lots of invalid
shreds. */
fd_bmtree_commit_t * tree;
tree = fd_bmtree_commit_init( bmtree_mem, FD_SHRED_MERKLE_NODE_SZ, FD_BMTREE_LONG_PREFIX_SZ, INCLUSION_PROOF_LAYERS );
// redacted for simplicity
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.
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:
(gdb) info reg
rax 0x85 133
rbx 0x3 3
rcx 0x38c181190b00 62403745745664
rdx 0x162 354
rsi 0x0 0
rdi 0x454c5f5344455248 4993470898079355464
rbp 0x5ddc001fd1f0 0x5ddc001fd1f0
rsp 0x5ddc001fd0e0 0x5ddc001fd0e0
r8 0x0 0
r9 0x4e7d05b5fe00 86298873691648
r10 0x0 0
r11 0x1d420 119840
r12 0x3f7 1015
r13 0xbe5 3045
r14 0x4e7d05b5fe00 86298873691648
r15 0x4141414141414141 4702111234474983745
rip 0x5a3395b576fe 0x5a3395b576fe <fd_shredder_next_fec_set+414>
eflags 0x10293 [ CF AF SF IF RF ]
cs 0x33 51
ss 0x2b 43
ds 0x0 0
es 0x0 0
fs 0x0 0
--Type <RET> for more, q to quit, c to continue without paging--
gs 0x0 0
(gdb)
(gdb) bt
#0 fd_shredder_next_fec_set (shredder=0x4e7d05b5fe00, result=result@entry=0x4e7d05b83520)
at src/disco/shred/../../ballet/shred/fd_shred.h:256
#1 0x00005a33929189c2 in during_frag (_ctx=0x4e7d00001000, in_idx=<optimized out>, seq=<optimized out>, sig=<optimized out>,
chunk=<optimized out>, sz=<optimized out>, opt_filter=0x5ddc001fd6f4) at src/app/fdctl/run/tiles/fd_shred.c:409
#2 0x00005a3395b71a0c in fd_mux_tile (cnc=0x7e1383c09100, flags=<optimized out>, in_cnt=in_cnt@entry=4,
in_mcache=in_mcache@entry=0x5ddc001fee80, in_fseq=in_fseq@entry=0x5ddc001fea80, mcache=0x38c180001100, out_cnt=1,
_out_fseq=0x5ddc001ff680, burst=4, cr_max=16384, lazy=<optimized out>, rng=0x5ddc001fe5f0, scratch=0x5ddc001fe380,
ctx=0x4e7d00001000, callbacks=0x5ddc001fe5a0) at src/disco/mux/fd_mux.c:645
#3 0x00005a3395b647cb in fd_topo_run_tile (topo=0x5a33972bb3d8 <config+568>, tile=0x5a33973598d8 <config+649016>,
sandbox=<optimized out>, uid=<optimized out>, gid=<optimized out>, allow_fd=<optimized out>, wait=<optimized out>,
debugger=<optimized out>, tile_run=<optimized out>) at src/disco/topo/fd_topo_run.c:171
#4 0x00005a33928f5016 in tile_main (_args=0x7ffe1fc7acc0) at src/app/fdctl/run/run1.c:53
#5 0x000072bc2cb25a04 in ?? ()
#6 0x0000000000000000 in ?? ()
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:
