Re: Proposal: drop QPACK encoder stream framing

[Roberto Peon <[e-mail]>]

Were I to put lengths somewhere, it'd be on another stream, which consisted solely of fixed/constant-sized metadata about the headers.
-=R

On 6/9/18, 3:57 PM, "QUIC on behalf of Kazuho Oku" <[e-mail] on behalf of [e-mail]> wrote:

    2018-06-09 8:26 GMT+09:00 Alan Frindell <[e-mail]>:
    >     Because I think reparsing is the best strategy here, let me argue that
    >     the worst case is not O(N^2).
    >
    >     Of course, in theory it is O(N^2), because there is no upper bound for
    >     the integer representation. But the reality is that implementations
    >     are required to have an upper bound. I'd assume that they would
    >     typically only permit values that fit in a 32-bit (u)int (16-bit is
    >     another option for some).
    >
    > The O(N^2) work I was thinking of was something like this:
    >
    > The encoder sends a very long Huffman encoded header name followed by a long value, but they send the value one byte at a time.  If the decoder naively reparses the entire Insert instruction every time a byte arrives, it will end up Huffman decoding the header name on every new byte of the value.  The name can be skipped over to re-parse the value length, and verify if the full value is present.  However, even skipping over it may be a linear operation in a zero-copy implementation that maintains a linked list of data buffers.
    
    Thank you for the clarification. That sounds like an interesting
    attack vector that we need to be aware of.
    
    OTOH, I am not sure if we need to consider the possibility of
    streaming Huffman decoding in this discussion, considering the fact
    that the compressed strings remain length-prefixed.
    
    Even if we remove the framing of the QCACK instructions,
    implementations will continue to have the freedom to buffer a complete
    Huffman-encoded string (the length of the string being identified by
    the length octets.
    
    > -Alan
    >
    >
    
    
    
    -- 
    Kazuho Oku