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

"Soni L." <> Wed, 30 October 2019 09:46 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 0EE851208DC for <>; Wed, 30 Oct 2019 02:46:15 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.75
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: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 6RdVDIjNJpa3 for <>; Wed, 30 Oct 2019 02:46:13 -0700 (PDT)
Received: from ( [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 (Postfix) with ESMTPS id 62D7A1200E0 for <>; Wed, 30 Oct 2019 02:46:13 -0700 (PDT)
Received: from lists by with local (Exim 4.89) (envelope-from <>) id 1iPkVl-00076C-8B for; Wed, 30 Oct 2019 09:43:29 +0000
Resent-Date: Wed, 30 Oct 2019 09:43:29 +0000
Resent-Message-Id: <>
Received: from ([2603:400a:ffff:804:801e:34:0:4f]) by with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.89) (envelope-from <>) id 1iPkVj-00075R-37 for; Wed, 30 Oct 2019 09:43:27 +0000
Received: from ([2607:f8b0:4864:20::a43]) by with esmtps (TLS1.3:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.92) (envelope-from <>) id 1iPkVh-000502-FC for; Wed, 30 Oct 2019 09:43:26 +0000
Received: by with SMTP id k19so322212vke.10 for <>; Wed, 30 Oct 2019 02:43:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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;; 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 with ESMTPSA id 3sm540464uaj.16.2019. for <> (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 30 Oct 2019 02:43:22 -0700 (PDT)
Sender: "Soni L." <>
References: <> <> <>
From: "Soni L." <>
Message-ID: <>
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: <>
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;;
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: 1iPkVh-000502-FC be2b650c976c5895b1679348521316c9
Subject: Re: New I-D: Security Considerations Regarding Compression Dictionaries
Archived-At: <>
X-Mailing-List: <> archive/latest/37080
Precedence: list
List-Id: <>
List-Help: <>
List-Post: <>
List-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]
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? (or, 
perhaps, this? )

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