Re: Proposal: drop QPACK encoder stream framing

Alan Frindell <afrind@fb.com> Mon, 11 June 2018 15:22 UTC

Return-Path: <prvs=97001cdf07=afrind@fb.com>
X-Original-To: quic@ietfa.amsl.com
Delivered-To: quic@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 30B9F131016 for <quic@ietfa.amsl.com>; Mon, 11 Jun 2018 08:22:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.71
X-Spam-Level:
X-Spam-Status: No, score=-2.71 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, T_DKIMWL_WL_HIGH=-0.01, T_DKIMWL_WL_MED=-0.01, T_KAM_HTML_FONT_INVALID=0.01] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=fb.com header.b=rm/zO51D; dkim=pass (1024-bit key) header.d=fb.onmicrosoft.com header.b=HRzY40Xi
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id LVULEQE1MFMI for <quic@ietfa.amsl.com>; Mon, 11 Jun 2018 08:22:26 -0700 (PDT)
Received: from mx0a-00082601.pphosted.com (mx0a-00082601.pphosted.com [67.231.145.42]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id F1B72130F3A for <quic@ietf.org>; Mon, 11 Jun 2018 08:22:25 -0700 (PDT)
Received: from pps.filterd (m0148461.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.0.22/8.16.0.22) with SMTP id w5BFHp6n002985; Mon, 11 Jun 2018 08:22:21 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : mime-version; s=facebook; bh=/qM+XMdlSUPJKF/32uE9ILHJF2hyCQgM1XmTBgUzbmI=; b=rm/zO51DYQA9slIK8ed7htofVtE81+RGYBuhJU0VU1Md6/WquLsgYTiEuK1cBmekWM5p ZYNc9MZBsGljZPG6nl2bU9PpV1OcsrUJUVlIHtTorHPgNNAbI/nL+1WqFqtH8YRP5KEW X0xH+KRMng0w5wxAbW1SJ9tP4dWC6h36gCs=
Received: from mail.thefacebook.com ([199.201.64.23]) by mx0a-00082601.pphosted.com with ESMTP id 2jhs12gdp1-1 (version=TLSv1 cipher=ECDHE-RSA-AES256-SHA bits=256 verify=NOT); Mon, 11 Jun 2018 08:22:21 -0700
Received: from NAM04-CO1-obe.outbound.protection.outlook.com (192.168.54.28) by o365-in.thefacebook.com (192.168.16.20) with Microsoft SMTP Server (TLS) id 14.3.361.1; Mon, 11 Jun 2018 08:22:20 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.onmicrosoft.com; s=selector1-fb-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=/qM+XMdlSUPJKF/32uE9ILHJF2hyCQgM1XmTBgUzbmI=; b=HRzY40XiFRDJKfv+Ro1FvLMWhO4g3nqUZMrXyn/Oqtnnn5kruZg8b7ykjCcLbVr7lfglWyXJzcNibMl4sZpzEBiyoEJU4IaeJdXbNKt9HkojQBr2z9AGFWlEykzwgXPMGw5k21eGWQb+mZTz0DArCTsaky9an2WFGF3BNuqr7kA=
Received: from MWHPR15MB1181.namprd15.prod.outlook.com (10.175.2.135) by MWHPR15MB1678.namprd15.prod.outlook.com (10.175.141.136) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.841.14; Mon, 11 Jun 2018 15:22:18 +0000
Received: from MWHPR15MB1181.namprd15.prod.outlook.com ([fe80::399c:db50:dfc0:3860]) by MWHPR15MB1181.namprd15.prod.outlook.com ([fe80::399c:db50:dfc0:3860%4]) with mapi id 15.20.0841.019; Mon, 11 Jun 2018 15:22:18 +0000
From: Alan Frindell <afrind@fb.com>
To: Mike Bishop <mbishop@evequefou.be>, Kazuho Oku <kazuhooku@gmail.com>
CC: QUIC WG <quic@ietf.org>, Martin Thomson <martin.thomson@gmail.com>
Subject: Re: Proposal: drop QPACK encoder stream framing
Thread-Topic: Proposal: drop QPACK encoder stream framing
Thread-Index: AQHT/nHqXJJQhdl+r0afCsPvVPdYN6RWJZAAgAAStYCAACnpgIAAhKkA//+nSwCAAf9MAIABl6mAgACYpAA=
Date: Mon, 11 Jun 2018 15:22:18 +0000
Message-ID: <0A25977E-C62A-4035-90C7-63D2D6B874E3@fb.com>
References: <20180607151112.GA28823@ubuntu-dmitri> <CABkgnnXbfkVbq6vCvud100h6wr3+9ir3iO7dD6-qaykOmK3JBQ@mail.gmail.com> <CANatvzzzXF8WCXgDCahTa_7JWZ1c1i-9rU_c8c9QWk5_O5u4Ow@mail.gmail.com> <F04D1BA6-8EC6-43EB-ABEC-34C4B30352AB@fb.com> <CANatvzwr6fSER-tq+xLz_e9rOw+mj5RpdS5eb679Ds_3m=PnoA@mail.gmail.com> <8616263A-31EF-4803-BEEF-1FE3FAEB23DB@fb.com> <CANatvzyHXnDCKPfpgf7-gZzDODRJ85Xz-diZ3ioBB-O=F2fvpg@mail.gmail.com> <BYAPR08MB3944795B91F2EEF1E0A08543DA790@BYAPR08MB3944.namprd08.prod.outlook.com>
In-Reply-To: <BYAPR08MB3944795B91F2EEF1E0A08543DA790@BYAPR08MB3944.namprd08.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/10.c.0.180410
x-originating-ip: [2620:10d:c090:200::7:3ed]
x-ms-publictraffictype: Email
x-microsoft-exchange-diagnostics: 1; MWHPR15MB1678; 7:1Nmsyem2Et7OO5gkRydjtZr7YftVUGhTfi/tLdFDvI+8AnKSlnMw95x6rlnI1CKkXhcL8HKXH7bflM6MW54LGTdAFfGTn07Ry4u025hXTol38EeHSngDTF0JXcFElhBF3FuEstsodhIZL6zooJHtje8IMB5Pw+Cg2yrMiPCSLuPqT0Fj8iTY3xK5nHSLIx0RxsKRzFxhGwIj2WqIlNRUiSEtkm/WJVPRK85ue42/ym5QiKUPV7Zeyn+xZQFPibRV; 20:muOoBrxZcQaunbw7HpH1H5uGT7OXnjPc3tYwTwLhxoP/FQXKKQQdn5N8pwYUpjfP9tLpQF4tnibu0bJT/JOe9H1R+SMKYCiMXgxIZBK15bUAawwnI2vwn1diqUbG1CZdPs1HGC+dRiPz6rGe1tEj2kSljlau0lFsz6NY7cR8P8o=
x-ms-exchange-antispam-srfa-diagnostics: SOS;
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(7020095)(4652020)(5600026)(4534165)(4627221)(201703031133081)(201702281549075)(2017052603328)(7153060)(7193020); SRVR:MWHPR15MB1678;
x-ms-traffictypediagnostic: MWHPR15MB1678:
x-microsoft-antispam-prvs: <MWHPR15MB167875F3F0D84141BBACFE6EA7780@MWHPR15MB1678.namprd15.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(28532068793085)(85827821059158)(67672495146484)(100405760836317)(21748063052155);
x-ms-exchange-senderadcheck: 1
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(10201501046)(93006095)(93001095)(3002001)(3231254)(11241501184)(944501410)(52105095)(149027)(150027)(6041310)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(20161123562045)(20161123558120)(20161123564045)(6072148)(201708071742011)(7699016); SRVR:MWHPR15MB1678; BCL:0; PCL:0; RULEID:; SRVR:MWHPR15MB1678;
x-forefront-prvs: 070092A9D3
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(39380400002)(39860400002)(366004)(376002)(396003)(346002)(189003)(199004)(13464003)(486006)(6116002)(97736004)(8676002)(561944003)(6436002)(81166006)(2900100001)(81156014)(14454004)(7736002)(476003)(4326008)(33656002)(11346002)(229853002)(2616005)(446003)(6486002)(25786009)(6246003)(106356001)(39060400002)(105586002)(36756003)(68736007)(345774005)(53546011)(8936002)(53936002)(236005)(82746002)(83716003)(46003)(478600001)(6506007)(2906002)(5660300001)(102836004)(186003)(86362001)(5250100002)(54906003)(58126008)(3660700001)(76176011)(110136005)(99286004)(3280700002)(59450400001)(316002)(93886005)(6512007)(54896002)(6306002); DIR:OUT; SFP:1102; SCL:1; SRVR:MWHPR15MB1678; H:MWHPR15MB1181.namprd15.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1;
received-spf: None (protection.outlook.com: fb.com does not designate permitted sender hosts)
x-microsoft-antispam-message-info: m8RLcMcP+cHd3J4oq2xJ5Zd6Y1GXQpQnz2hiWzW0rbXo6O0K7F85p1bSeXvK4HhMxrVwACF9PWBRG4lHSz4XuymKJxWfjNxMgFWlNTr4FSegyhlYf/Y+hp0PjStkRx+2qH6eq6+XEn5w26YHluusgn9zpxaM7fy7n44WYqnhRYflH3K4aXlCnBgWKFe+hCza
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: multipart/alternative; boundary="_000_0A25977EC62A403590C763D2D6B874E3fbcom_"
MIME-Version: 1.0
X-MS-Office365-Filtering-Correlation-Id: 8c316efb-8963-4f2d-8dad-08d5cfaf1ef3
X-MS-Exchange-CrossTenant-Network-Message-Id: 8c316efb-8963-4f2d-8dad-08d5cfaf1ef3
X-MS-Exchange-CrossTenant-originalarrivaltime: 11 Jun 2018 15:22:18.6606 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 8ae927fe-1255-47a7-a2af-5f3a069daaa2
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR15MB1678
X-OriginatorOrg: fb.com
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2018-06-11_07:, , signatures=0
X-Proofpoint-Spam-Reason: safe
X-FB-Internal: Safe
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/5PeJCTyEwZErTafuHctOq5kAygQ>
X-BeenThere: quic@ietf.org
X-Mailman-Version: 2.1.26
Precedence: list
List-Id: Main mailing list of the IETF QUIC working group <quic.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic>, <mailto:quic-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic/>
List-Post: <mailto:quic@ietf.org>
List-Help: <mailto:quic-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic>, <mailto:quic-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 11 Jun 2018 15:22:34 -0000

The fact that you now need an algorithm that tells you how to correctly/safely deserialize a single instruction is pretty much the point I was making.  This is more complex than just having a byte on the wire tell you how many bytes are required.  But I feel there’s clear consensus here to discard the length prefix.

-Alan

From: Mike Bishop <mbishop@evequefou.be>
Date: Sunday, June 10, 2018 at 4:16 PM
To: Kazuho Oku <kazuhooku@gmail.com>om>, Alan Frindell <afrind@fb.com>
Cc: QUIC WG <quic@ietf.org>rg>, Martin Thomson <martin.thomson@gmail.com>
Subject: RE: Proposal: drop QPACK encoder stream framing


And they probably should, since they can't sensibly do anything without a full instruction.  So an implementation would need to do the following steps:

  *   Check the first byte; at this point, you either know the string’s exact length, or you know it’s longer than 32 bytes
     *   If longer, wait until you’ve gotten at least 32 more bytes, and you’re guaranteed to have the remainder of the number; find the actual length
     *   Wait until you have the actual length plus one byte
  *   Use the length of the encoded string to locate the first byte of the value length; you either find the full length, or you know it’s at least 128 bytes long
     *   If longer, wait until you’ve gotten at least 128 more bytes; you’re guaranteed to have the actual number in there
     *   Wait until you have the actual length (remainder of the instruction)
  *   Decode the instruction



So you’re potentially waiting for more bytes up to four times per instruction (though the odds that a non-malicious sender would hit all four are low), and a naïve implementation might well re-parse the instruction from the beginning after each wait completes.  Implicit in this is the assumption that a 32 byte long integer will always be unacceptably long, and if after the wait you can’t move to the next field successfully, you’ll fail the instruction.



An implementation can always determine how many bytes it needs to wait for to make progress, without accidentally waiting past the end of the instruction and creating a deadlock if that’s a tail.  I think this example has convinced me that the length prefix is unnecessary.  (It does make me wonder whether it would have made more sense to put both lengths at the beginning of the instruction, followed by the values.)



-----Original Message-----
From: QUIC <quic-bounces@ietf.org> On Behalf Of Kazuho Oku
Sent: Saturday, June 9, 2018 3:57 PM
To: Alan Frindell <afrind@fb.com>
Cc: QUIC WG <quic@ietf.org>rg>; Martin Thomson <martin.thomson@gmail.com>
Subject: Re: Proposal: drop QPACK encoder stream framing



2018-06-09 8:26 GMT+09:00 Alan Frindell <afrind@fb.com<mailto:afrind@fb.com>>:

>     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