Re: [saag] SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1
Phillip Hallam-Baker <phill@hallambaker.com> Tue, 07 January 2020 18:53 UTC
Return-Path: <hallam@gmail.com>
X-Original-To: saag@ietfa.amsl.com
Delivered-To: saag@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id CCB2012010E for <saag@ietfa.amsl.com>; Tue, 7 Jan 2020 10:53:48 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.399
X-Spam-Level:
X-Spam-Status: No, score=-1.399 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.25, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no 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 7UuKZ-H7C-yF for <saag@ietfa.amsl.com>; Tue, 7 Jan 2020 10:53:47 -0800 (PST)
Received: from mail-oi1-f175.google.com (mail-oi1-f175.google.com [209.85.167.175]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E6357120145 for <saag@ietf.org>; Tue, 7 Jan 2020 10:53:46 -0800 (PST)
Received: by mail-oi1-f175.google.com with SMTP id l9so382860oii.5 for <saag@ietf.org>; Tue, 07 Jan 2020 10:53:46 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=3nedsFlXDq4obx1qqSaeL8hzGOzqR5XQlSj5XHtgMVM=; b=Yz4y9o4GjcqZ53RIRfwoaUUpMSEYmuTozN4liPK1boF1yA9mkaLjDvLI4pfdLEsFv6 S9k51jrpF5iHct1ujVA1JjMaromodhNpx2JxMJ/3u8iR9jZWTyZqXQ8LiJ/rKVzywsc/ MjQsVoH6VNwxXs+JaGrs12FSm6A26kJkXR0SvI+UmDXoGBPoCVbdra9tWe71SLi0/6lt 3EU3oo2+4152EwcR1qFw9hfB/nN1JamZfiCOceVlZmYIUnCQ01HLSvnAKdnahovoD9m+ zNy5y7uVLl9jM7ji26r3hsrYxv5Fq7PLUGdhFyvvybfr0DpRPHtFnQ41jKxLTwfnqZmp 5HbQ==
X-Gm-Message-State: APjAAAVnk/9Z3bixy/B0NvitSjVqr5JiFZUUjymqoK5ia95Y8fng+IF/ 8bRR+md4lF4o82ceMfrsaUqqa5GpACv+KBzo9gLOxFYtDL0=
X-Google-Smtp-Source: APXvYqyr7RkKQzdFGgSU1rYbgfrXVPvFyVBBqNuSqEMOMuLhhOI/EYqYRJIAR/OIstbuAlJzigett7I0pr4lVjfZ+ik=
X-Received: by 2002:aca:cdd6:: with SMTP id d205mr686879oig.90.1578423225955; Tue, 07 Jan 2020 10:53:45 -0800 (PST)
MIME-Version: 1.0
References: <A6C5B299-54AE-48E8-98BF-981C85B9D3BE@vigilsec.com>
In-Reply-To: <A6C5B299-54AE-48E8-98BF-981C85B9D3BE@vigilsec.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Tue, 07 Jan 2020 13:53:37 -0500
Message-ID: <CAMm+Lwhx5wpoKXAYbS9V6oUzOJ2FVk_+Y=ZiK2N9Vnp8U0wHyQ@mail.gmail.com>
To: Russ Housley <housley@vigilsec.com>
Cc: IETF SAAG <saag@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000b03d55059b914ba1"
Archived-At: <https://mailarchive.ietf.org/arch/msg/saag/xl4pl78lr0NnD-dRy0dxHLkhns8>
Subject: Re: [saag] SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1
X-BeenThere: saag@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Security Area Advisory Group <saag.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/saag>, <mailto:saag-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/saag/>
List-Post: <mailto:saag@ietf.org>
List-Help: <mailto:saag-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/saag>, <mailto:saag-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 07 Jan 2020 18:53:49 -0000
I was just about to post. As it happens, I was in the middle of making an intro video on digest functions for my free course on crypto. So I guess I will tape it today rather than waiting till Friday (if the heavy equipment laying new gas pipes in the street is quiet enough). The need to move on from SHA-1 was one of the reasons I originally started looking at an improved fingerprint presentation using Base32 encoding that allowed for safe truncation etc. SHA-1 has more than enough bits for many applications, the problem is the algorithm. I would like to move to SHA-2-512/ SHA-3-512 and only 512 bits regardless of the precision required. https://mathmesh.com/Documents/draft-hallambaker-mesh-udf.html On Tue, Jan 7, 2020 at 10:23 AM Russ Housley <housley@vigilsec.com> wrote: > 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). > > _______________________________________________ > saag mailing list > saag@ietf.org > https://www.ietf.org/mailman/listinfo/saag >
- [saag] SHA-1 is a Shambles: First Chosen-Prefix C… Russ Housley
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Phillip Hallam-Baker
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Peter Gutmann
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Phillip Hallam-Baker
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Christian Huitema
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Jeffrey Walton
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Phillip Hallam-Baker
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Andrey Jivsov
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Alan DeKok
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Peter Gutmann
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Black, David
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Watson Ladd
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Peter Gutmann
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Viktor Dukhovni
- Re: [saag] SHA-1 is a Shambles: First Chosen-Pref… Robert Moskowitz