Re: [openpgp] Fingerprints and their collisions resistance

Andrey Jivsov <openpgp@brainhub.org> Sat, 05 January 2013 00:06 UTC

Return-Path: <openpgp@brainhub.org>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 50AAC21F8B54 for <openpgp@ietfa.amsl.com>; Fri, 4 Jan 2013 16:06:14 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.437
X-Spam-Level:
X-Spam-Status: No, score=-0.437 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FH_RELAY_NODNS=1.451, HELO_MISMATCH_NET=0.611, RDNS_NONE=0.1]
Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id TOZWfKFll5gw for <openpgp@ietfa.amsl.com>; Fri, 4 Jan 2013 16:06:13 -0800 (PST)
Received: from qmta03.emeryville.ca.mail.comcast.net (qmta03.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:32]) by ietfa.amsl.com (Postfix) with ESMTP id 7B33D21F8B4C for <openpgp@ietf.org>; Fri, 4 Jan 2013 16:06:05 -0800 (PST)
Received: from omta17.emeryville.ca.mail.comcast.net ([76.96.30.73]) by qmta03.emeryville.ca.mail.comcast.net with comcast id ju361k0041afHeLA30655K; Sat, 05 Jan 2013 00:06:05 +0000
Received: from [192.168.1.8] ([69.181.162.123]) by omta17.emeryville.ca.mail.comcast.net with comcast id k0631k00N2g33ZR8d064DR; Sat, 05 Jan 2013 00:06:04 +0000
Message-ID: <50E76E6B.1040008@brainhub.org>
Date: Fri, 04 Jan 2013 16:06:03 -0800
From: Andrey Jivsov <openpgp@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:13.0) Gecko/20120605 Thunderbird/13.0
MIME-Version: 1.0
To: Christian Aistleitner <christian@quelltextlich.at>
References: <50E530D6.6020609@brainhub.org> <D3684BB5-FDC6-4834-8FAE-C482A25E3FB0@callas.org> <50E5D6AA.6060200@brainhub.org> <874nixev2u.fsf@vigenere.g10code.de> <50E61486.9010209@brainhub.org> <20130104105328.GA5156@quelltextlich.at> <50E733F4.90400@brainhub.org> <20130104222125.GA26665@quelltextlich.at>
In-Reply-To: <20130104222125.GA26665@quelltextlich.at>
Content-Type: text/plain; charset="UTF-8"; format="flowed"
Content-Transfer-Encoding: 8bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1357344365; bh=+42NZ3gIjwgsFeMD+GcNcteYvXLqZID2h9OQgc8Wfnw=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=NC1B44x60C08svzcjMeHDrnLfeBVMRPPx4c0TWMGeMqAsPDzEEsMKF9zkYe2VJ8FT 6WLwVRv6et4ssa1tGXo8btMtimVHUcliHfCDkkDa5aTJcITZHu5D+ELCklttkEVkhn 2KgaNJcS5OVJVZAgph4kAwuq2L65xcuY574nlLLRLhrH+AbnGtGyxyfcV9IwDoNAiI xZnU33ip5C77iFp4g0OZp9tvLU3sMbbXUjTbRedWKajsX3pGmyH+SwhGX8w+hlRVKQ IMC3xZZlPDSzU0jH9QqESZ18v8WQ1lRUtSla6W1CEfzCmmCN66GjtXbgwm2Uav5NA5 CwTz3boF5pIWA==
Cc: openpgp@ietf.org
Subject: Re: [openpgp] Fingerprints and their collisions resistance
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.12
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: Sat, 05 Jan 2013 00:06:14 -0000

We are talking about the realm of (single) DES security here (i.e. ~ 
DES-X variant) and one will need all the additional bits. The question 
of how much can we actually get beyond DES may not be so important in 
the context of this thread.

Recall that my initial post doesn't claim any immediate attack on SHA-1 
or a specific weakness of OpenPGP. I am looking for a solution that we 
can implement in a few years to move to the full 128 bit security (or 
closer to it). This means that we need to have a method now so that we 
can begin to slowly integrate it.

IMO the upgrade can be done "cheaply", without disruption, so my thought 
is why not do it anyway?

On 01/04/2013 02:21 PM, Christian Aistleitner wrote:
> Hi Andrey,
>
> On Fri, Jan 04, 2013 at 11:56:36AM -0800, Andrey Jivsov wrote:
>> On 01/04/2013 02:53 AM, Christian Aistleitner wrote:
>>> Do you have any data / research underpinning this 51 (Besides
>>> Wikipedia)?
>>>
>>> After all, the cited Wikipedia page links to the retracted variant of
>>> an article :-(
>>>
>>> Otherwise, the best /theoretical/ result that I know of is just
>>> above 60.
>>
>> It looks like this is from the paper "Classification and Generation of
>> Disturbance Vectors for Collision Attacks against SHA-1"
>> published in 2011 in Designs, Codes and Cryptography
>> [...]
>
> I guess you are aware of the fact that in recent variants of the
> article, the 51 is gone and that there is a reason why I wrote
> “retracted variant” in my original mail :-)
>
>> Should we rather say that the _practical_ value is about 60 [...]
>> http://www.schneier.com/blog/archives/2012/10/when_will_we_se.html
>
> Practical has more than just one meaning, just as theoretical :-)
> As the post you reference only says
>
>    If Stevens' attack of $2^{60}$ SHA-1 operations serves as the
>    baseline [...]
>
> and does not say that “Stevens' attack” is practical (or “practical”
> in what sense), I am convinced you have read in Stevens' research to
> underpin your claim. For example you might have come across Stevens'
> 2012 PhD thesis and have read passages as
>
>    [...] and this chosen-prefix collision attack against SHA-1 remains a
>    theoretical attack.
>
> in section 7.7.3 (but that's somewhat out of context), or more
> general statements as
>
>    [...] even though no practical collision attacks against SHA-1 or
>    actual colliding messages are known yet.
>
> from section 8.4.
>
>
> But be things as they may, if you know better than Stevens himself and
> can make his results even more practical, please step up and share
> your work.
>
>
> All the best,
> Christian
>
>
>