kixelated
commented
6 days ago MoQ's message encoding is similar to QUIC's, but the difference is that QUIC datagrams have a finite size and are not susceptible to a trickle attack.
I've implemented two types of MoQ parsers:
- Async state machine.
- Trial parser.
The async parser is easy in some languages (JavaScript, Go). There could be excessive wake ups if the stream is written one byte at a time but I that's a fundamental QUIC problem (userspace wakeup).
My trial parser (Rust) returns a More(min_bytes_needed) error to help mitigate this attack. You can return the remaining size (ex. string/VarInt) in addition to the minimum size of any remaining fields (usually 1 byte).
You could implement a state machine manually too, but a trial parser will be fine if you don't allocate on the heap.
I'm on the fence if we should length prefix or not. I've implemented both and think streaming is easier in general across multiple languages, but I do think this decoding gotcha is real.
huitema
LPardue
suhasHere
afrind
The MoQ transport messages are encoded as a combination of varints, bit strings, and t-l-v objects. In the absence of a "header length" field, applications have to resort to trial parsing: accumulate some incoming bytes from the stream, try to parse those bytes as a message, and if that fail accumulate more bytes and retry. This may not be a huge problem in normal operation. The peer endpoint will compose a message and typically send those bytes all at once; the QUIC stack will deliver them all at once, but even so there may be cases where the QUIC stack cannot send them in a single STREAM_DATA messages, so the logic for "accumulate and try" has to be present.
Suppose a peer sending its data one byte at a time, because it is either malicious or buggy. The length of the message cannot be computed before all components are parsed: the first byte of each varint defines its length, the length field of bits or bytes strings need to be parsed in full, then number of parameters or versions needs to be known. To obtain the length of a component, all components before it need to be parsed, which means that the number of trial parsing is typically a function of the number of components -- maybe an O(N2) function since the cost of each trial depends on the number of components before it. That number can be very large for messages including parameters, because the number of parameters cannot be known in advance -- the peer could send an arbitrary number of them in an attempt to "greasing". Parsing is a somewhat CPU intensive operation, which implies that trial parsing can be exploited for a mild DOS attack.
Prepend a length field to messages would mitigate trial parsing, but I am not sure that we need to fix this. Having limits on message size would impose a de-facto limit on the processing cost of each message. A malicious attackers could send series of short messages such as "subscribe updates" to trigger the same CPU consumption. In typical QUIC stacks, the main CPU load comes form passing messages through the OS/app boundary in socket calls, and an attacker could DOS the target by sending series of short messages. The next component is the cost of encryption and decryption, compared to which the cost of trial decryption is probably small. We may decide to do nothing, but it would be nice in that case to have a documentation of the reasoning (as in this issue), and maybe a discussion of why the attack does not matter in the security section.
Addressing the "limits" issue (#473) would also somewhat mitigate the problem, as limiting the "number of parameters" appears to be the main way to increase the number of components in messages.