Re: Proposal: drop QPACK encoder stream framing

Roberto Peon <fenix@fb.com> Tue, 12 June 2018 23:36 UTC

Return-Path: <prvs=9701d1302d=fenix@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 B0336130EF3 for <quic@ietfa.amsl.com>; Tue, 12 Jun 2018 16:36:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.72
X-Spam-Level:
X-Spam-Status: No, score=-2.72 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, T_DKIMWL_WL_HIGH=-0.01, T_DKIMWL_WL_MED=-0.01, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=fb.com header.b=A+SxYSXS; dkim=pass (1024-bit key) header.d=fb.onmicrosoft.com header.b=WPpbKI19
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 rRqbcsPQWqwu for <quic@ietfa.amsl.com>; Tue, 12 Jun 2018 16:36:09 -0700 (PDT)
Received: from mx0a-00082601.pphosted.com (mx0b-00082601.pphosted.com [67.231.153.30]) (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 ADFD5129619 for <quic@ietf.org>; Tue, 12 Jun 2018 16:36:09 -0700 (PDT)
Received: from pps.filterd (m0001303.ppops.net [127.0.0.1]) by m0001303.ppops.net (8.16.0.22/8.16.0.22) with SMTP id w5CNWHJO017837; Tue, 12 Jun 2018 16:36:07 -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 : content-id : content-transfer-encoding : mime-version; s=facebook; bh=7OMzgV+2/qRxY0K0HU8QhYIidy6gSAlqeCubPWS0y54=; b=A+SxYSXSofkCAwe8dYmOU1sZPdZJDMZGYQI1OSsTOzr7kQPOxWVDs1k0wwTFIZNsNC4E AJaAfIybtghCCsQup/7vTu3M8vEZiRqRE9CYppzo5tp4WG3fRC+NSuAcjdEi9ae9gMZf XqkUkWFOZd+Isd4D+cV55kvS8YwK9o8yvq8=
Received: from maileast.thefacebook.com ([199.201.65.23]) by m0001303.ppops.net with ESMTP id 2jjp73g90a-1 (version=TLSv1 cipher=ECDHE-RSA-AES256-SHA bits=256 verify=NOT); Tue, 12 Jun 2018 16:36:07 -0700
Received: from NAM05-DM3-obe.outbound.protection.outlook.com (192.168.183.28) by o365-in.thefacebook.com (192.168.177.25) with Microsoft SMTP Server (TLS) id 14.3.361.1; Tue, 12 Jun 2018 19:36:06 -0400
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=7OMzgV+2/qRxY0K0HU8QhYIidy6gSAlqeCubPWS0y54=; b=WPpbKI19lUkND16Fli/C7FZYdBJqAT2gCrp+iP+Y7/4EbwYEiDI6z2dcL3D1gkC4t0XGNAlAYSLecF6BacLrZUHATZXX7QtIj7Yhb4IrmUfnGjjCZPnymCjjq1vzrQak0Y05tquTEcN+b/jpSw+eEhn7FDbS4HpaWi+4SiYQQ0o=
Received: from BYAPR15MB2312.namprd15.prod.outlook.com (52.135.197.146) by BYAPR15MB2264.namprd15.prod.outlook.com (52.135.197.19) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.863.15; Tue, 12 Jun 2018 23:36:04 +0000
Received: from BYAPR15MB2312.namprd15.prod.outlook.com ([fe80::949a:9cbd:277c:96e0]) by BYAPR15MB2312.namprd15.prod.outlook.com ([fe80::949a:9cbd:277c:96e0%4]) with mapi id 15.20.0841.019; Tue, 12 Jun 2018 23:36:04 +0000
From: Roberto Peon <fenix@fb.com>
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/nHnJassB3eSU02Rr8SQ8wAp5KRWJZAAgAAStYCAAJ9EgIAAD04AgAAcpYCAAYnyAIAETJaA
Date: Tue, 12 Jun 2018 23:36:04 +0000
Message-ID: <535018A7-3DC1-448B-9A94-43B30211F10F@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>
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:
user-agent: Microsoft-MacOutlook/10.d.1.180523
x-originating-ip: [2620:10d:c090:200::7:88c]
x-ms-publictraffictype: Email
x-microsoft-exchange-diagnostics: 1; BYAPR15MB2264; 7:PRp2gAw5L6U17gdPXOuJwmZlOV81wntuCqX1/tCrl53AW1qD/f7WNeBA6BgCjZehnv62z9D3iX9s+v6A5GjEjqdzScqd40h8dwj4+zgT1/BY39igrvu1F/0zyu+t1XfsftQasn2WOM43Y2JT6PHojUjRZaft20ae1ELVyg7lNd1N16k50oTHXFki4MrBgIOFeGhXujsbE2DHetp2LCGxM43+3n2ybZquwDAJWzgLURep7jHtXxcOPMpkBLoZQkqC; 20:0s4IP++AaGEqmuEYw1WwTc8XHNexGDBSUs3vei3auS9mJEYkpd/nHDkMrsbuq5R1bJ/wMpQmy8EftwBKKVewriyRGS94VUwQbV16q1Z02xEk4tz/5+gfSa7jXHcW6HuSlRoa56w6LLj3VwKYrJhWlRgAJz8kpLG7UmqqD21dN2k=
x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR;
x-forefront-antispam-report: SFV:SKI; SCL:-1; SFV:NSPM; SFS:(10019020)(39860400002)(346002)(376002)(396003)(366004)(39380400002)(189003)(199004)(33656002)(81166006)(6506007)(99286004)(106356001)(59450400001)(8936002)(76176011)(6116002)(6246003)(6436002)(5250100002)(345774005)(11346002)(2616005)(316002)(446003)(6486002)(476003)(105586002)(25786009)(486006)(53936002)(6512007)(68736007)(229853002)(36756003)(39060400002)(58126008)(54906003)(110136005)(8676002)(2900100001)(4326008)(3660700001)(93886005)(3280700002)(46003)(97736004)(478600001)(81156014)(82746002)(5660300001)(86362001)(2906002)(7736002)(14454004)(6636002)(186003)(83716003)(102836004)(305945005)(42262002); DIR:OUT; SFP:1102; SCL:1; SRVR:BYAPR15MB2264; H:BYAPR15MB2312.namprd15.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1;
X-MS-Office365-Filtering-Correlation-Id: 996d37a4-115b-4464-4403-08d5d0bd43a1
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(7020095)(4652020)(5600026)(711017)(4534165)(4627221)(201703031133081)(201702281549075)(2017052603328)(7153060)(7193020); SRVR:BYAPR15MB2264;
x-ms-traffictypediagnostic: BYAPR15MB2264:
x-microsoft-antispam-prvs: <BYAPR15MB226416C10FC8BD82ECCDC1A2CD7F0@BYAPR15MB2264.namprd15.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(85827821059158)(67672495146484);
x-ms-exchange-senderadcheck: 1
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(3002001)(3231254)(11241501184)(944501410)(52105095)(10201501046)(93006095)(93001095)(149027)(150027)(6041310)(20161123564045)(20161123558120)(20161123560045)(20161123562045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(6072148)(201708071742011)(7699016); SRVR:BYAPR15MB2264; BCL:0; PCL:0; RULEID:; SRVR:BYAPR15MB2264;
x-forefront-prvs: 07013D7479
received-spf: None (protection.outlook.com: fb.com does not designate permitted sender hosts)
x-microsoft-antispam-message-info: t9Oy5fseTcCNv4njswu79OKUQsNnBsGrO6TfiBf+z6SBGGD7bUgiV8JdrK2NIWEUaips+DeAIKLB4m000rSa7yKz8uG0ZPMctJ8UdB+/SDQu1Ehayrtm/sgY8E1BXDs0TFSvGHpgoJwoREQsl/8VDMkz+7WsrlIRPb6SFgWX1uS/Bq8qeKhrkaK7Tn64UBFm
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="utf-8"
Content-ID: <E2EEACC26763A543BB8BF2BF836F3F17@namprd15.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: 996d37a4-115b-4464-4403-08d5d0bd43a1
X-MS-Exchange-CrossTenant-originalarrivaltime: 12 Jun 2018 23:36:04.3020 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 8ae927fe-1255-47a7-a2af-5f3a069daaa2
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BYAPR15MB2264
X-OriginatorOrg: fb.com
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2018-06-12_14:, , signatures=0
X-Proofpoint-Spam-Reason: safe
X-FB-Internal: Safe
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/hD-6Slug-bUcU8HWRO3bzMORs4g>
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: Tue, 12 Jun 2018 23:36:14 -0000

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" <quic-bounces@ietf.org on behalf of kazuhooku@gmail.com> wrote:

    2018-06-09 8:26 GMT+09:00 Alan Frindell <afrind@fb.com>om>:
    >     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