Re: Proposal: drop QPACK encoder stream framing

Kazuho Oku <> Sat, 09 June 2018 22:56 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 0114A130FB8 for <>; Sat, 9 Jun 2018 15:56:57 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.099
X-Spam-Status: No, score=-0.099 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id nXYMO50CBAWH for <>; Sat, 9 Jun 2018 15:56:55 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:400e:c00::232]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id C835C130F24 for <>; Sat, 9 Jun 2018 15:56:55 -0700 (PDT)
Received: by with SMTP id b74-v6so8348840pfl.5 for <>; Sat, 09 Jun 2018 15:56:55 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=i0LIx8BaWs2rBLtjD1kp71rwdo/EcoIO+ACW4TPsYqQ=; b=P0HNC8SHn2Y5uyYi0/6JcwJ1NbOdR6DSE0trgrNcDumwFuowXCxZ/nrp6ZWGSndpWQ KMQyzAd3oVTVLYR06PHUv4adLMlApL73wV0iee6/jOSwJE/05/RAaAxUzjD/1mEgKrEN tRB2h1HhovWLIHR1+aUapmhCfZq6i7+9RkZj7hajdqPxn9Fr9RIudl5i7T4HFPBF7hQH VMgIwxHgSPLxJLT8t+R7O4eWSvZhv1OZV43rZSbz3CXzOiVq7TdZT1nrYf+ZNACweqig j7KkE0F72jfixqlZIOCsQDANN+R9Ad0mY7vrMddRPydThPbsGBwvB2ieDlRg0rZhW1Lm wirQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=i0LIx8BaWs2rBLtjD1kp71rwdo/EcoIO+ACW4TPsYqQ=; b=WCi8mEbytgBFiKdF+GdGRlq9nVse9C1PnFH1P2R1tw/QgtKzfNa2wkXWaJ2HOMF7wI GDr9yllj+ew7us9bDT63kJvIb6znm6EiAM2C+Sj9iEWXeoYOGuJ4Ie0c/lyUOdsA+7sQ L3l45iqpcWTJZW2iXYrrcTTS/YAYG2kpZzD9VjDgjbI40LLyrbB5GHuN8MKsC0+qRmzo acnhvu3yIh9jjv6QytSPadDJo8AkKSIwit0RmjCo4pl4YKBeI8dXuvzZWXZ4FZ7p+l/O +NENp2IHUUCTM5y1yWluSOQmaZz8DgJW8iQqwPK2jX+x6ZZ34XR2DOfU7KsUlLff2D7V gKcw==
X-Gm-Message-State: APt69E1C/VGs3S4Onm/k7m+zKdmWNYlsrT0QKSAFbtxsdjNoCwD8nlCx eftUi05+2hSlx8ziVK0ey7MFQtPDjqOkq9wHUu8=
X-Google-Smtp-Source: ADUXVKLtH29y4tkfcXv8t0H7XQccEPhcWKTq7E94C5E5lkh1nsJ3hXppYXP2BT+pAA3ATXqTK9LiR0+xDKGVuUz2NRY=
X-Received: by 2002:a63:ba02:: with SMTP id k2-v6mr9936630pgf.179.1528585015247; Sat, 09 Jun 2018 15:56:55 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a17:90a:1181:0:0:0:0 with HTTP; Sat, 9 Jun 2018 15:56:54 -0700 (PDT)
In-Reply-To: <>
References: <20180607151112.GA28823@ubuntu-dmitri> <> <> <> <> <>
From: Kazuho Oku <>
Date: Sun, 10 Jun 2018 01:56:54 +0300
Message-ID: <>
Subject: Re: Proposal: drop QPACK encoder stream framing
To: Alan Frindell <>
Cc: Martin Thomson <>, QUIC WG <>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <>
X-Mailman-Version: 2.1.26
Precedence: list
List-Id: Main mailing list of the IETF QUIC working group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sat, 09 Jun 2018 22:56:57 -0000

2018-06-09 8:26 GMT+09:00 Alan Frindell <>:
>     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