[DNSOP] SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1

Tony Finch <dot@dotat.at> Tue, 07 January 2020 14:54 UTC

Return-Path: <dot@dotat.at>
X-Original-To: dnsop@ietfa.amsl.com
Delivered-To: dnsop@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E077D12001A for <dnsop@ietfa.amsl.com>; Tue, 7 Jan 2020 06:54:48 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.199
X-Spam-Level:
X-Spam-Status: No, score=-4.199 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_NONE=0.001] autolearn=ham autolearn_force=no
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 ltokItS8-Bqc for <dnsop@ietfa.amsl.com>; Tue, 7 Jan 2020 06:54:46 -0800 (PST)
Received: from ppsw-43.csi.cam.ac.uk (ppsw-43.csi.cam.ac.uk [131.111.8.143]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6EFFC120052 for <dnsop@ietf.org>; Tue, 7 Jan 2020 06:54:46 -0800 (PST)
X-Cam-AntiVirus: no malware found
X-Cam-ScannerInfo: http://help.uis.cam.ac.uk/email-scanner-virus
Received: from grey.csi.cam.ac.uk ([131.111.57.57]:46502) by ppsw-43.csi.cam.ac.uk (ppsw.cam.ac.uk [131.111.8.139]:25) with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) id 1ioqFo-000TKz-mc (Exim 4.92.3) for dnsop@ietf.org (return-path <dot@dotat.at>); Tue, 07 Jan 2020 14:54:44 +0000
Date: Tue, 7 Jan 2020 14:54:43 +0000
From: Tony Finch <dot@dotat.at>
To: dnsop@ietf.org
Message-ID: <alpine.DEB.2.20.2001071450120.14515@grey.csi.cam.ac.uk>
User-Agent: Alpine 2.20 (DEB 67 2015-01-07)
MIME-Version: 1.0
Content-Type: multipart/mixed; BOUNDARY="1870870841-1595969275-1578408884=:14515"
Archived-At: <https://mailarchive.ietf.org/arch/msg/dnsop/kifYnNTaPxsNoaLiqM7I4Ty_EjE>
Subject: [DNSOP] SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1
X-BeenThere: dnsop@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: IETF DNSOP WG mailing list <dnsop.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/dnsop>, <mailto:dnsop-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/dnsop/>
List-Post: <mailto:dnsop@ietf.org>
List-Help: <mailto:dnsop-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/dnsop>, <mailto:dnsop-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 07 Jan 2020 14:54:49 -0000

The third paragraph of the abstract suggests this is relevant to DNSSEC RSASHA1:

https://eprint.iacr.org/2020/014

> SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and
> Application to the PGP Web of Trust

> Gaëtan Leurent and Thomas Peyrin

> Abstract: The SHA-1 hash function was designed in 1995 and has been
> widely used during two decades. A theoretical collision attack was first
> proposed in 2004 [WYY05], but due to its high complexity it was only
> implemented in practice in 2017, using a large GPU cluster [SBK+17].
> More recently, an almost practical chosen-prefix collision attack
> against SHA-1 has been proposed [LP19]. This more powerful attack allows
> to build colliding messages with two arbitrary prefixes, which is much
> more threatening for real protocols.

> In this paper, we report the first practical implementation of this
> attack, and its impact on real-world security with a PGP/GnuPG
> impersonation attack. We managed to significantly reduce the complexity
> of collisions attack against SHA-1: on an Nvidia GTX 970,
> identical-prefix collisions can now be computed with a complexity of
> 2^61.2 rather than 2^64.7, and chosen-prefix collisions with a complexity
> of 2^63.4 rather than 2^67.1. When renting cheap GPUs, this translates to
> a cost of 11k US$ for a collision, and 45k US$ for a chosen-prefix
> collision, within the means of academic researchers. Our actual attack
> required two months of computations using 900 Nvidia GTX 1060 GPUs (we
> paid 75k US$ because GPU prices were higher, and we wasted some time
> preparing the attack).

> Therefore, the same attacks that have been practical on MD5 since 2009
> are now practical on SHA-1. In particular, chosen-prefix collisions can
> break signature schemes and handshake security in secure channel
> protocols (TLS, SSH). We strongly advise to remove SHA-1 from those type
> of applications as soon as possible. We exemplify our cryptanalysis by
> creating a pair of PGP/GnuPG keys with different identities, but
> colliding SHA-1 certificates. A SHA-1 certification of the first key can
> therefore be transferred to the second key, leading to a forgery. This
> proves that SHA-1 signatures now offers virtually no security in
> practice. The legacy branch of GnuPG still uses SHA-1 by default for
> identity certifications, but after notifying the authors, the modern
> branch now rejects SHA-1 signatures (the issue is tracked as
> CVE-2019-14855).

Tony.
-- 
f.anthony.n.finch  <dot@dotat.at>  http://dotat.at/
The Minch: South veering southwest, then west later, 7 to severe gale 9,
occasionally storm 10 at first. Rough or very rough, but high in far north and
in far south. Rain then squally showers. Moderate or poor, occasionally good.