Re: [openpgp] Disabling compression in OpenPGP

Andrey Jivsov <openpgp@brainhub.org> Tue, 18 March 2014 19:10 UTC

Return-Path: <openpgp@brainhub.org>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 00E5B1A0455 for <openpgp@ietfa.amsl.com>; Tue, 18 Mar 2014 12:10:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_PASS=-0.001] autolearn=ham
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 o4OH6BOXSpq1 for <openpgp@ietfa.amsl.com>; Tue, 18 Mar 2014 12:10:06 -0700 (PDT)
Received: from qmta13.emeryville.ca.mail.comcast.net (qmta13.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:44:76:96:27:243]) by ietfa.amsl.com (Postfix) with ESMTP id 984E11A044C for <openpgp@ietf.org>; Tue, 18 Mar 2014 12:10:06 -0700 (PDT)
Received: from omta22.emeryville.ca.mail.comcast.net ([76.96.30.89]) by qmta13.emeryville.ca.mail.comcast.net with comcast id f1dj1n0031vN32cAD79ywb; Tue, 18 Mar 2014 19:09:58 +0000
Received: from [127.0.0.1] ([71.202.164.227]) by omta22.emeryville.ca.mail.comcast.net with comcast id f79t1n00Y4uhcbK8i79vLw; Tue, 18 Mar 2014 19:09:58 +0000
Message-ID: <532899EA.6070006@brainhub.org>
Date: Tue, 18 Mar 2014 12:09:30 -0700
From: Andrey Jivsov <openpgp@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0
MIME-Version: 1.0
To: openpgp@ietf.org
References: <CALR0uiJG6GcngWMUkg6NrP7_4uwf8+QDn6aMF-qonOpRMLdo3w@mail.gmail.com>
In-Reply-To: <CALR0uiJG6GcngWMUkg6NrP7_4uwf8+QDn6aMF-qonOpRMLdo3w@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1395169798; bh=mAOvqeZFOaLfhPdpatxTcr07Ub/3bYVhkuydjmUTfc4=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=gCvdXXLv0tj6TYN378p5/0YIXITyREsMf6ubN6rhnxuLM9uRaEsdnHxKObzExi/TQ rxdOL0eVHzSoPSYM7j9MdQGisLN2WxiSKnPocVCnW5cg1G2GERAU7Dc9OOPOyXjHFM iotl5Ti7mz76icrH2TcxvPdC+hav/hV9WgWng0wOq0lAwgekrWC4R4pyT5zunvn75N AaBnMjMLE3TPZ/sBdGZPqpMjyKFtaNRN3z0JgCvXE9WSCFDNOxy/Z67OTkJaLPr+h0 WJn8PLVfJfhc9w4h60pL/8Bxfwo8VkChX2NYWC76hxV11XjdtxAdqf7V6Zg2Im95h+ c4W1xXsrjUEJQ==
Archived-At: http://mailarchive.ietf.org/arch/msg/openpgp/U2mYovSEZUbB83K-V7hPgZtHhFk
Subject: Re: [openpgp] Disabling compression in OpenPGP
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/openpgp/>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 18 Mar 2014 19:10:08 -0000

On 03/18/2014 09:00 AM, Alfredo Pironti wrote:
>
> I have done some preliminary work on password managers that rely on
> OpenPGP (gpg, in fact) to encrypt the passwords. Unsurprisingly, it
> turns out that compressing the password before encrypting it leaks much
> of the password entropy, making dictionary attacks significantly easier
> to mount. (In my preliminary experiments I used a password dictionary
> containing about 4 million passwords. If the attacker knows the original
> password length and its compressed length, then for some combinations of
> the two the candidate dictionary entries can reduce to as few as some
> hundreds.)

I wonder why the additional piece of information is available, which is 
that both the length of the original password and the length of the 
compressed one is available from a ciphertext that is an encrypted password.

Wouldn't only one of these sizes be provided through the size of the 
ciphertext?

When you build a dictionary with 4 million passwords, you can index it 
by the password length or by password's compressed length. It's true 
that OpenPGP CFB format will leak the size either of the plaintext or of 
the compressed plaintext (so perhaps higher-level padding is the right 
thing to do in cases like these). Narrowing down the choices by the size 
of the password v.s. the size of the compressed password seems 
equivalent regarding the password recovery attack.

I do see that if we can narrow down the choices by two sizes 
simultaneously, this will indeed narrow down the possibilities further. 
However, it's unclear how both sizes are obtained from a single ciphertext.