(OTS) Zstd Bomb Blob

[l-monninger]

Summary

A malicious user may post a zstd bomb (a small compressed blob which decompresses to a huge buffer) as a blob on the movement Celestia namespace. Even though blob data is checked to be signed, zstd decompression happens before the signature checks. This is done with the zstd::decode_all(blob.data) function, which has no limits on the decompressed size of the blob. Even with Celestia’s 2 MB blob size limit, we were able to produce a PoC that uses approximately 100 GB of RAM on decompression.

[l-monninger]

@khokho

[mzabaluev]

Should we impose some constant size limit on IR blobs, or should it be a chain parameter?

[l-monninger]

Should we impose some constant size limit on IR blobs, or should it be a chain parameter?

Yes, but we also want to change the order of operations s.t. we are checking signatures on compressed blobs. That way we know honest signers are involved or not.

Even with a supposed limit on IR blobs, we can still get bombed. But, later on, we can perhaps entertaining slashing signers that bomb.

Ideally, we would also want to just have a way to catch bombing behavior and ignore said blob. For example, I think you can use maxWindowSize() in zstd to accomplish this, i.e., set the max decompressable size, but not sure.

[l-monninger]

@khokho, can you share over your bomb s.t. we can write tests against it.

[khokho]

@l-monninger Here's the PoC:

fn zstd_bomb() {
    // MAGIC + header with max window size
    let mut b: Vec<u8> = vec![0x28, 0xb5, 0x2f, 0xfd, 0x0, 0x7f];
    let n_blocks = 0x530000;
    for _ in 0..n_blocks {
        // RLE block encoding 0xff byte repeated 0x8000 times
        b.extend(&[0x02, 0x00, 0x10, 0xff]);
    }
    // Block to finish the data
    b.extend(&[0x01, 0x00, 0x00]);
    // Check that we fit in celestia limits
    assert!(b.len() < 0x1_500_000);
    // decode the bomb
    // uses up at lest 100GB on my machine after which it crashes
    let res = zstd::decode_all(b.as_slice()).unwrap();
    dbg!(res.len());
}

[mzabaluev]

To me it boils down to two approaches:

1. Change the format so that the compression layer does not get applied to the signature, and use the signature to sign/verify the compressed payload. Keep relying on Celestia's innate limit to limit the size of compressed blobs.
2. Impose a limit on the size of decoded blobs and pass it to the zstd decoder.

[l-monninger]

@mzabaluev Yeah, that's what I would say.

[mzabaluev]

We have the maximum block size parameter in memseq configuration, but it's in the number of transactions.

1. Is this enough information to derive the upper bound on the size of an uncompressed blob?
2. This parameter governs the blobs that the node creates. Can we also apply it to blobs received from DA?

[l-monninger]

We have the maximum block size parameter in memseq configuration, but it's in the number of transactions.

1. Is this enough information to derive the upper bound on the size of an uncompressed blob?
2. This parameter governs the blobs that the node creates. Can we also apply it to blobs received from DA?

We could assume some like Celestia bytes $\times$ (Compression Ratio + $\mu$) is reasonable. I would suggest $\mu$ should be 1--allowing for a particularly well compressed blobs to make it through.

Yes, we should be able to apply it with blobs received via maxWindowSize().

[mzabaluev]

We could assume some like Celestia bytes × Compression Ratio + μ is reasonable.

I assume this really means Celestia_Bytes × (Compression_Ratio + μ)
The compression ratio is for a reference corpus, the real transaction blobs might have a different entropy, as they contain lots of uncompressible data like address hashes.

[mzabaluev]

By plugging zstd decompressing reader directly into the bcs decoder in streaming fashion, we can limit the allocation requirements to the 2 GB limit enforced internally by bcs. No changes in format are required.

[mzabaluev]

the 2 GB limit

This has to be multiplied by the number of byte array fields in the data structure, so it's 4 x 2 GiB. Combined with other memory use, this is pushing on operating budgets. So while the streaming fix defends against worst attacks, a proper solution would need the format change.

[mzabaluev]

byte array fields

As we're realizing perhaps too late, three of these fields have no reason to be variable-length byte arrays, unless we want to designate the format of signature, signer, and id fields by their length, which would be a bad practice. So perhaps we should change the intermediate blob format and deal with upgrading.

[l-monninger]

Currently, we still have the ability to change the DA on all of our networks, so I would just make this change.

[mzabaluev]

After discussion with @l-monninger, the data blob size limit of 2 GiB, while manageable on most machines that are expected to run a DA light node, still allows submitting blobs that would cause intolerable latency when decompressed and decoded.
So we'll need a configurable container size limit in the bcs decoder.

[khokho]

Hello, I checked out the bug fix and it looks good. I also reviewed the BCS changes, and it’s great that they’re optional and shouldn’t affect existing code.