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