Re: [Cfrg] Internal collisions
Dan Brown <dbrown@certicom.com> Sun, 02 August 2015 03:47 UTC
Return-Path: <dbrown@certicom.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7E6551A8A63 for <cfrg@ietfa.amsl.com>; Sat, 1 Aug 2015 20:47:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level:
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7] 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 zl8QOXk6e0Dw for <cfrg@ietfa.amsl.com>; Sat, 1 Aug 2015 20:47:02 -0700 (PDT)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) by ietfa.amsl.com (Postfix) with ESMTP id 9B57A1A8A62 for <cfrg@irtf.org>; Sat, 1 Aug 2015 20:47:02 -0700 (PDT)
Received: from xct102cnc.rim.net ([10.65.161.202]) by mhs214cnc.rim.net with ESMTP/TLS/AES128-SHA; 01 Aug 2015 23:47:00 -0400
Received: from XCT116CNC.rim.net (10.65.161.216) by XCT102CNC.rim.net (10.65.161.202) with Microsoft SMTP Server (TLS) id 14.3.210.2; Sat, 1 Aug 2015 23:46:59 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT116CNC.rim.net ([::1]) with mapi id 14.03.0210.002; Sat, 1 Aug 2015 23:46:59 -0400
From: Dan Brown <dbrown@certicom.com>
To: "D. J. Bernstein" <djb@cr.yp.to>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Internal collisions
Thread-Index: AQHQy68R+xgpZDff0UGF08OtLC2WBJ316kiQgAI5zgD///BPqQ==
Date: Sun, 02 Aug 2015 03:46:58 +0000
Message-ID: <20150802034656.5333071.17011.5439@certicom.com>
References: <810C31990B57ED40B2062BA10D43FBF5E1DC43@XMB116CNC.rim.net>, <20150802004308.9548.qmail@cr.yp.to>
In-Reply-To: <20150802004308.9548.qmail@cr.yp.to>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/rhqe_kdiX755zXg-oI0HVByAdIQ>
Subject: Re: [Cfrg] Internal collisions
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sun, 02 Aug 2015 03:47:04 -0000
retracting the "oops" as requested Original Message From: D. J. Bernstein Sent: Saturday, August 1, 2015 8:43 PM To: cfrg@irtf.org Subject: Re: [Cfrg] Internal collisions Dan Brown writes: > For consistency, if CFRG views prefixed wide-pipe hashes as a serious > general-purpose PRF construct, thereby obviating the need for HMAC's > extension-resilience, then it is not much of stretch to say that a > wide-pipe hash obviates the need for H(R,M)'s collision-resilience. I have no idea why you call this "consistency"; it doesn't match what the cryptanalytic literature actually says about the security levels of these constructions. As a concrete example, 24 steps are broken in the SHA-384(M,R) construct that you're using. What matters here is that the attacker knows internal collisions. It is far more difficult to break 24 steps of SHA-384(R,M), or 24 steps of SHA-512(R,M). I explained in an earlier message why the randomization is a huge obstruction for state-of-the-art collision-finding techniques. For similar reasons, it is far more difficult to break 24 steps of reduced SHA-512(seed,M) as a PRF, never mind the fact that in this context the attacker doesn't have direct access to the output. > Is that what the reduced-round attacks are indicating: no > difference between SHA-512 and SHA-256? What about for SHA-3? SHA-256 and SHA-512 are broken for essentially the same number of steps, in essentially the same way. For SHA-3, the very different amounts of truncation in SHA3-256 and SHA3-512 produce a gap of 1 or 2 rounds (out of 24), depending on which attack strategy you look at. > Oops, in Watson Ladd's proposal: H(M,R) has no known feasible attacks, > but changing this to H(M) makes it forgeable Please retract this statement. I clearly specified the three possibilities here as the long-message bottlenecks in the existing proposals. The proposals that have H(M) as a bottleneck are of course using R in a subsequent (non-bottleneck) stage of the signing process. You are instead referring to the absurd idea of throwing R away. This is not what any of the proposals do, and bringing it up isn't helpful for the discussion. Also, please retract your false suggestion that the proposals vary in the applicability of Pointcheval--Stern. ---Dan _______________________________________________ Cfrg mailing list Cfrg@irtf.org http://www.irtf.org/mailman/listinfo/cfrg
- [Cfrg] Internal collisions D. J. Bernstein
- Re: [Cfrg] Internal collisions Dan Brown
- Re: [Cfrg] Internal collisions David Jacobson
- Re: [Cfrg] Internal collisions Ilari Liusvaara
- Re: [Cfrg] Internal collisions Dan Brown
- Re: [Cfrg] Internal collisions Paterson, Kenny
- Re: [Cfrg] Internal collisions D. J. Bernstein
- Re: [Cfrg] Internal collisions Dan Brown
- Re: [Cfrg] Internal collisions D. J. Bernstein
- Re: [Cfrg] Internal collisions Dan Brown
- Re: [Cfrg] Internal collisions Bryan Ford
- Re: [Cfrg] Internal collisions D. J. Bernstein