Re: New I-D: Security Considerations Regarding Compression Dictionaries

"Soni L." <fakedme+http@gmail.com> Wed, 30 October 2019 09:46 UTC

Return-Path: <ietf-http-wg-request+bounce-httpbisa-archive-bis2juki=lists.ie@listhub.w3.org>
X-Original-To: ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com
Delivered-To: ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0EE851208DC for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Wed, 30 Oct 2019 02:46:15 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.75
X-Spam-Level:
X-Spam-Status: No, score=-2.75 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HEADER_FROM_DIFFERENT_DOMAINS=0.25, MAILING_LIST_MULTI=-1, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.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 6RdVDIjNJpa3 for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Wed, 30 Oct 2019 02:46:13 -0700 (PDT)
Received: from frink.w3.org (frink.w3.org [IPv6:2603:400a:ffff:804:801e:34:0:38]) (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 62D7A1200E0 for <httpbisa-archive-bis2Juki@lists.ietf.org>; Wed, 30 Oct 2019 02:46:13 -0700 (PDT)
Received: from lists by frink.w3.org with local (Exim 4.89) (envelope-from <ietf-http-wg-request@listhub.w3.org>) id 1iPkVl-00076C-8B for ietf-http-wg-dist@listhub.w3.org; Wed, 30 Oct 2019 09:43:29 +0000
Resent-Date: Wed, 30 Oct 2019 09:43:29 +0000
Resent-Message-Id: <E1iPkVl-00076C-8B@frink.w3.org>
Received: from mimas.w3.org ([2603:400a:ffff:804:801e:34:0:4f]) by frink.w3.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.89) (envelope-from <fakedme+http@gmail.com>) id 1iPkVj-00075R-37 for ietf-http-wg@listhub.w3.org; Wed, 30 Oct 2019 09:43:27 +0000
Received: from mail-vk1-xa43.google.com ([2607:f8b0:4864:20::a43]) by mimas.w3.org with esmtps (TLS1.3:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.92) (envelope-from <fakedme+http@gmail.com>) id 1iPkVh-000502-FC for ietf-http-wg@w3.org; Wed, 30 Oct 2019 09:43:26 +0000
Received: by mail-vk1-xa43.google.com with SMTP id k19so322212vke.10 for <ietf-http-wg@w3.org>; Wed, 30 Oct 2019 02:43:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=sender:subject:to:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-transfer-encoding:content-language; bh=meuabOFcYjW/sHyHV8DWJeSfmksp7NFfbgQxiR9GGWA=; b=owx9g7C8jDdlI1xmGoa0V1hWmdgYG/K2v5tcZT5VYsZDidMpsP29nHGgjIOYcuvBFp FQSqdS8N+bTs0mTZcSHvtV8mDl1jQm+eaqBOJ9+DUHpchmTIuj9PW2HFf9ohu6vunveg HOi34TVT9JKIJ+8IPWXL1Xst//TIo0ZX1QQWqNb2vTiWaEUeXY+fv7fElG7E0V0hHkrm aO0neDx0CZYtSr/aEnNLtviqrzpv9WgYrYF44nmYI7d++0O5QhYawGiK+LdVw+4r0JCr Ph8ylxoLZIGZwo67qUR9DIRR2Z8ql2rOkqLcoRzq09pRaoAEviD69mIDWBcpXJhu0Y58 0bMg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:subject:to:references:from:message-id :date:user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=meuabOFcYjW/sHyHV8DWJeSfmksp7NFfbgQxiR9GGWA=; b=BXBjj0gG5eKWPTNQ3pAYhz/EL9CWNlpTZQSSS8zSfHOP9xctSsbEkr37MCAJPW9zch UbFGqz9W76lj4Vb/YcBbjxE/Dxk1144X2tdA7KW26WIEQJOYLnWDTPF8cHR6ChFApDmT DqtTGUqgl6SrW22N9oeho9kv4yROCmVH6Exd6YCFiz83v6e1eJGSV4UrhGv0PA9Bw1j3 Dmphw/2tF3wGrSj02sqnjpKXtnCd2Lr9PCiON9xdF/roUA/DpDo4E+keeWTXCTRCtKNv mwCKm3W04M+3wcC6QA5kak6digmVE5emCKWSA34YZ4Qg4as29rdGmHF4+3YVAj5bAiGu NwbQ==
X-Gm-Message-State: APjAAAV8n86yXAkLf2UETiHvDBYi43Dp0XOGaWFpm7y7CG5lfjfnj0rE x7x5WR6byb4pO+oeqtQc1iTOCiV80xE=
X-Google-Smtp-Source: APXvYqxXevDb+5iU/uieieNJLF1q79f96EvOYxyAoGEnJYw/HW9cLaswCAoVOh4HuR1ltpcWsXhnIQ==
X-Received: by 2002:ac5:cb0a:: with SMTP id r10mr478064vkl.76.1572428603874; Wed, 30 Oct 2019 02:43:23 -0700 (PDT)
Received: from ?IPv6:2804:431:d77c:258:2e0:4bff:fe37:ec7? ([2804:431:d77c:258:2e0:4bff:fe37:ec7]) by smtp.googlemail.com with ESMTPSA id 3sm540464uaj.16.2019.10.30.02.43.22 for <ietf-http-wg@w3.org> (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 30 Oct 2019 02:43:22 -0700 (PDT)
Sender: "Soni L." <fakedme@gmail.com>
To: ietf-http-wg@w3.org
References: <20988909-6e4e-ea45-139a-ca403a7433eb@felixhandte.com> <CAN2QdAGX0vtBSuUBS_HYsoTuTmmO=-LX_w9OizG+v6jqFMtLTA@mail.gmail.com> <f99d6b86-72af-a019-ae8b-a5673adfc814@felixhandte.com>
From: "Soni L." <fakedme+http@gmail.com>
Message-ID: <c5e37168-b958-8b13-ab97-f9a7f5352b24@gmail.com>
Date: Wed, 30 Oct 2019 06:43:20 -0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.0
MIME-Version: 1.0
In-Reply-To: <f99d6b86-72af-a019-ae8b-a5673adfc814@felixhandte.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Content-Language: en-US
Received-SPF: pass client-ip=2607:f8b0:4864:20::a43; envelope-from=fakedme+http@gmail.com; helo=mail-vk1-xa43.google.com
X-W3C-Hub-Spam-Status: No, score=-4.1
X-W3C-Hub-Spam-Report: BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, W3C_AA=-1, W3C_WL=-1
X-W3C-Scan-Sig: mimas.w3.org 1iPkVh-000502-FC be2b650c976c5895b1679348521316c9
X-Original-To: ietf-http-wg@w3.org
Subject: Re: New I-D: Security Considerations Regarding Compression Dictionaries
Archived-At: <https://www.w3.org/mid/c5e37168-b958-8b13-ab97-f9a7f5352b24@gmail.com>
Resent-From: ietf-http-wg@w3.org
X-Mailing-List: <ietf-http-wg@w3.org> archive/latest/37080
X-Loop: ietf-http-wg@w3.org
Resent-Sender: ietf-http-wg-request@w3.org
Precedence: list
List-Id: <ietf-http-wg.w3.org>
List-Help: <https://www.w3.org/Mail/>
List-Post: <mailto:ietf-http-wg@w3.org>
List-Unsubscribe: <mailto:ietf-http-wg-request@w3.org?subject=unsubscribe>


On 2019-10-29 11:17 p.m., W. Felix Handte wrote:
> On 10/29/19 7:54 PM, Watson Ladd wrote:
> > I'm not sure I appreciate the distinction of "dictionary-based"
> > compression vs. other compression algorithms you draw in the draft.
> > The BREACH attack didn't look at changes to the Huffman table, which
> > was dominated by good old ETOAIN SHRDLU. Instead it changed the length
> > of matches back into the datastream, and thus the length of the
> > observed output. There isn't a separate dictionary to match substrings
> > in in DEFLATE.
>
> Yeah, "dictionary" is an extremely overloaded term in compression, to
> say nothing of computer science generally. This has produced a great
> deal of confusion. But I haven't come up with a better term for the concept.
>
> What I mean by "dictionary" in this context is mostly a user-supplied
> buffer that the compressor makes LZ77-style matches into. (Though, as
> the document notes, various algorithms expect various kinds of data in
> the dictionaries they accept.) This makes it very much a potential
> vector for exactly that kind of attack. And DEFLATE, at least as
> implemented by zlib, does support dictionaries of this form [0].
>
> > A perfect compression algorithm reveals the Kolmogorov complexity of
> > the input. This is enough (if you can compute Kolmogorov complexity)
> > to reveal the differences between "hunter2 h" and "hunter2 z", and
> > then "hunter2 hu" and "hunter2 ha", etc.
>
> Right, compression as it exists today has real outstanding security
> issues. My goal with the document is to assess whether the use of
> dictionaries introduces additional problems on top of the existing ones.
>
> [0] https://github.com/madler/zlib/blob/master/zlib.h#L611
>
So, what you're saying, is that this wouldn't be an issue if we were 
using public-key-based authentication and session tokens?

Like this? https://soniex2.autistic.space/posts/2019/06/uweb.xhtml (or, 
perhaps, this? https://awoo.space/@SoniEx2/102972533369915352 )

(This also touches on another post I've sent this list, but it's not 
relevant here.)