RE: Proposal: drop QPACK encoder stream framing

Mike Bishop <mbishop@evequefou.be> Sun, 10 June 2018 23:16 UTC

Return-Path: <mbishop@evequefou.be>
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 5005C130F25 for <quic@ietfa.amsl.com>; Sun, 10 Jun 2018 16:16:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, 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=evequefou.onmicrosoft.com
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 NWkXwAypYIwZ for <quic@ietfa.amsl.com>; Sun, 10 Jun 2018 16:16:05 -0700 (PDT)
Received: from NAM04-SN1-obe.outbound.protection.outlook.com (mail-eopbgr700111.outbound.protection.outlook.com [40.107.70.111]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BEC49130EDE for <quic@ietf.org>; Sun, 10 Jun 2018 16:16:04 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=evequefou.onmicrosoft.com; s=selector1-evequefou-be; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Y6DQbI7O55Bx2BE8ouMkh5kbj9apuYeSba1jGzI18nA=; b=IJPTpcvgi4tyRXrFPYMSHz15tTKZV1RNShOaseyj8rV+OCLPqdtSvv3pcT9eWm75ux43VcAwSYAepDUuCLZaGCigjwD5xxv8HRXjNDF1ZsojiP7KbUVJpq5SC2Cw+DJavb14f6nLJkM3orAIYoKSoBygRjDDRf+LC3e1eMQs5HQ=
Received: from BYAPR08MB3944.namprd08.prod.outlook.com (52.135.194.30) by BYAPR08MB4150.namprd08.prod.outlook.com (52.135.196.33) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.841.17; Sun, 10 Jun 2018 23:15:59 +0000
Received: from BYAPR08MB3944.namprd08.prod.outlook.com ([fe80::6093:5ef9:46a3:ca1f]) by BYAPR08MB3944.namprd08.prod.outlook.com ([fe80::6093:5ef9:46a3:ca1f%4]) with mapi id 15.20.0841.019; Sun, 10 Jun 2018 23:15:59 +0000
From: Mike Bishop <mbishop@evequefou.be>
To: Kazuho Oku <kazuhooku@gmail.com>, Alan Frindell <afrind@fb.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/nHe+1l0+zihD0qpT4Ov4UtYwaRWJZAAgAAStYCAAJ9EgIAAD04AgAAcpYCAAYnyAIABlE8Q
Date: Sun, 10 Jun 2018 23:15:59 +0000
Message-ID: <BYAPR08MB3944795B91F2EEF1E0A08543DA790@BYAPR08MB3944.namprd08.prod.outlook.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>
In-Reply-To: <CANatvzyHXnDCKPfpgf7-gZzDODRJ85Xz-diZ3ioBB-O=F2fvpg@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [2601:600:8080:5a28:8d18:eaf1:e372:5b55]
x-ms-publictraffictype: Email
x-microsoft-exchange-diagnostics: 1; BYAPR08MB4150; 7:bfg91XZch+8oeuwhjrdEM4WPAfeG2kMOj8Qwwaq67SH8crEDciIQZhdIX5du5tbyI8U1ttkJAM96Ajn9mF3yKL4soVgLmi6rKxfiyifrOdBRbgg1EAxY7VlJrEwLVFp8/VGhFiHLfsUA3XXCkOAT29m4IsRPme614m7xmAoxBE5T/w8UVbWaJggeNk46Cz11aP+oxYX3rlLlioZS7qsOgCPWfu/hshrqMqacu9LJn0QsZ8hIX+Ju1i1SFxU8zDxi
x-ms-exchange-antispam-srfa-diagnostics: SOS;
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(7020095)(4652020)(7021125)(5600026)(4534165)(7022125)(4603075)(4627221)(201702281549075)(7048125)(7024125)(7027125)(7028125)(7023125)(2017052603328)(7153060)(7193020); SRVR:BYAPR08MB4150;
x-ms-traffictypediagnostic: BYAPR08MB4150:
authentication-results: spf=none (sender IP is ) smtp.mailfrom=mbishop@evequefou.be;
x-microsoft-antispam-prvs: <BYAPR08MB415052E3794221C9059EB1CADA790@BYAPR08MB4150.namprd08.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(28532068793085)(85827821059158)(67672495146484)(21748063052155);
x-ms-exchange-senderadcheck: 1
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(6040522)(2401047)(5005006)(8121501046)(3231254)(944501410)(52105095)(3002001)(93006095)(93001095)(10201501046)(149027)(150027)(6041310)(20161123558120)(20161123564045)(20161123562045)(2016111802025)(20161123560045)(6043046)(6072148)(201708071742011)(7699016); SRVR:BYAPR08MB4150; BCL:0; PCL:0; RULEID:; SRVR:BYAPR08MB4150;
x-forefront-prvs: 0699FCD394
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(376002)(396003)(366004)(39830400003)(346002)(39380400002)(13464003)(199004)(189003)(97736004)(6246003)(6306002)(54896002)(46003)(68736007)(5660300001)(478600001)(5250100002)(105586002)(790700001)(74316002)(86362001)(25786009)(6116002)(236005)(93886005)(106356001)(55016002)(2900100001)(9686003)(7696005)(4326008)(59450400001)(39060400002)(7736002)(110136005)(53546011)(3660700001)(33656002)(99286004)(81156014)(81166006)(486006)(476003)(3280700002)(8936002)(102836004)(561944003)(2906002)(6506007)(8676002)(54906003)(316002)(345774005)(74482002)(14454004)(186003)(53936002)(229853002)(446003)(11346002)(6436002)(76176011); DIR:OUT; SFP:1102; SCL:1; SRVR:BYAPR08MB4150; H:BYAPR08MB3944.namprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:0; MX:1;
received-spf: None (protection.outlook.com: evequefou.be does not designate permitted sender hosts)
x-microsoft-antispam-message-info: iacVP6TZsV06Eyku6/gKmoxtoS6CDKni2NxaoH1vCzKY2kIs+Q4tAhgiL56BOcBMQdGB+IyWGaLRuplcerg/HQRFBkmSKCGfjv4Hvk0SqEqLy7Dg1BMt3Lh59BLoXpZ4M/QMdEt9B5FqPH/tZt09yB4WrbvrM5a/XykT0zZqBNzBEE+ex8qEGrb6Xo+f4xRS
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: multipart/alternative; boundary="_000_BYAPR08MB3944795B91F2EEF1E0A08543DA790BYAPR08MB3944namp_"
MIME-Version: 1.0
X-MS-Office365-Filtering-Correlation-Id: 6750487f-6062-4778-e425-08d5cf2820d9
X-OriginatorOrg: evequefou.be
X-MS-Exchange-CrossTenant-Network-Message-Id: 6750487f-6062-4778-e425-08d5cf2820d9
X-MS-Exchange-CrossTenant-originalarrivaltime: 10 Jun 2018 23:15:59.8674 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 41eaf50b-882d-47eb-8c4c-0b5b76a9da8f
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BYAPR08MB4150
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/n5OeqQjJiabBwsdRfkyxMTa8Pg4>
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: Sun, 10 Jun 2018 23:16:09 -0000

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