Prevent space bombs

[rossberg]

The Candid serialisation format has two singleton types whose encoding size is zero: null and reserved. That means that an array of arbitrary size over these types (or a super-type like opt t) can be represented in constant space in the serialisation format, but may blow up arbitrarily on the receiver side, creating the risk of DoS attacks.

The space savings from this representation (as opposed to a single byte) are probably not significant for practical use cases, because there normally is little value in passing data of singleton types in the first place.

We should hence change the representation. The challenge is how to do that in a sufficiently backwards-compatible manner.

[nomeata]

I'm not sure how much of a problem this is? Presumably a canister has to do sanity checking of all input from untrusted sources anyways, e.g. after decoding check that arrays are not too large. So this Candid space bomb will either exhaust the instruction limit for this message, or be caught then. In neither case, the huge list will actually hit persistent storage.

It might have been worth starting differently, but we knew about this, didn't we? So not sure if it's worth doing breaking changes for this now.

[nomeata]

Also, out of curiosity, how do interop protocols that support compression on the transport layer deal with this? Most compression algorithms allow for such space bombs?

[chenyan-dfinity]

Yeah, I wonder if it's worth fixing. We always do subtype checking before decoding. Unless the receiver expects a vec null/reserved type, sending such a vector will be rejected immediately.

Suppose null now takes one byte, then the maximal vector we can send is 2M (message size limit). Maybe in the spec, we can say the number of null/reserved values in a message should be less than 2M?

[rossberg]

Unless the receiver expects a vec null/reserved type, sending such a vector will be rejected immediately.

Not quite – as @nomeata reminded me earlier in private conversation, you can send a vec null to a canister expecting a vec opt t, due to subtyping.

[chenyan-dfinity]

@rossberg @nomeata With the extensible variant change, users can now send opt vec null to a function that expects opt nat. I wonder what's the best non-breaking change we can make to the spec?

One idea is to limit the size of vec null/vec reserved on the wire. vec opt empty is isomorphic to vec null, but it's not zero sized, so it's not a problem.

[nomeata]

But in that case, the vec null wouldn't be decoded to a huge value, would it? The subtype check would run first, and just return null?

The code that then skips over the vec null value would naively stupidly count down the size of that vector; presumably that can be optimized, as so:

https://github.com/dfinity/motoko/blob/7d413846d8ab050fdab2b27678daf24b92fb17a9/rts/motoko-rts/src/idl.rs#L307-L310

[chenyan-dfinity]

With the variant spec change, we only check subtyping for reference types. So for decoding opt nat, we will have to decode a huge vector.

[nomeata]

I have to page it all back in, sorry. So what's happening is that it tries to decide the vec null as an int, but this fails (dynamically), and due to the special rules for opt this becomes null?

In that case the (implementation) question would be whether the decoder fails before actually materializing the vector. I think the Motoko decoder would. More naive ones (like the Haskell one) probably don't.

I don't see much room for wire format changes (e.g. don't allow zero sized values in vectors); wouldn't that break existing clients? Or is that breakage acceptable?

[nomeata]

We should add a test excercising this to the test suite, to incentives fixes :-)

I think in the Haskell code I'll add a special form “Vector of constant value” (Replicated :: Natural -> Value -> Value). When decoding, I can recognize a zero size element and decode efficiently to that form, and then later the coercion code can take it from there. So no large architectural changed needed. Maybe the same approach works for rust.

[crusso]

It looks like the code for skipping a vec does the right thing in Motoko: if decoding the first element makes no progress through the buffer, just return.

unsafe fn skip_any_vec(buf: *mut Buf, typtbl: *mut *mut u8, t: i32, count: u32) {
    if count == 0 {
        return;
    }
    let ptr_before = (*buf).ptr;
    skip_any(buf, typtbl, t, 0);
    let ptr_after = (*buf).ptr;
    if ptr_after == ptr_before {
        // this looks like a vec null bomb, or equivalent, where skip_any
        // makes no progress. No point in calling it over and over again.
        // (This is easier to detect this way than by analyzing the type table,
        // where we’d have to chase single-field-records.)
        return;
    }
    for _ in 1..count {
        skip_any(buf, typtbl, t, 0);
    }
}

Not sure I understand what the Motoko deserializer is doing in this case. Perhaps @nomeata can confirm it is ok.

[nomeata]

I think the Motoko deserializer is indeed ok. We should add test that blow up for implementations that aren't ok to the official test suite.