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

Viktor Dukhovni <ietf-dane@dukhovni.org> Tue, 07 January 2020 16:18 UTC

Return-Path: <ietf-dane@dukhovni.org>
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 C2C251207FF for <dnsop@ietfa.amsl.com>; Tue, 7 Jan 2020 08:18:11 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.2
X-Spam-Level:
X-Spam-Status: No, score=-4.2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-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 2lcTMGSHeT2Q for <dnsop@ietfa.amsl.com>; Tue, 7 Jan 2020 08:18:09 -0800 (PST)
Received: from straasha.imrryr.org (straasha.imrryr.org [100.2.39.101]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E0F3812081F for <dnsop@ietf.org>; Tue, 7 Jan 2020 08:18:08 -0800 (PST)
Received: by straasha.imrryr.org (Postfix, from userid 1001) id 170152ADCAB; Tue, 7 Jan 2020 11:18:08 -0500 (EST)
Date: Tue, 7 Jan 2020 11:18:08 -0500
From: Viktor Dukhovni <ietf-dane@dukhovni.org>
To: dnsop@ietf.org
Message-ID: <20200107161808.GG73491@straasha.imrryr.org>
Reply-To: dnsop@ietf.org
References: <alpine.DEB.2.20.2001071450120.14515@grey.csi.cam.ac.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <alpine.DEB.2.20.2001071450120.14515@grey.csi.cam.ac.uk>
User-Agent: Mutt/1.12.2 (2019-09-21)
Archived-At: <https://mailarchive.ietf.org/arch/msg/dnsop/mKyizSZYka7CZSQ7CMejxTMMoyQ>
Subject: Re: [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 16:18:16 -0000

On Tue, Jan 07, 2020 at 02:54:43PM +0000, Tony Finch wrote:

> The third paragraph of the abstract suggests this is relevant to DNSSEC RSASHA1:
> 
> https://eprint.iacr.org/2020/014

[ I've Bcc'd the authors, perhaps they'll follow up with a comment, or
  reply to me off-list with permission to quote or repost. ]

> > 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).

Reading the paper more closely, one finds:

- Section 1.1
  - Record Computation
    - 2nd paragraph:
      ... Our attack uses one partial block for the birthday stage,and 9
      near-collision blocks.

If I'm reading this correctly, the attack requires > 9*160 = 1440 bits
of complete freedom in the tail of the data to be signed.  But with
RSASHA1, when a parent domain signs the DS RRset of a child zone, the

    https://tools.ietf.org/html/rfc4034#section-3.1.8.1

    RR(i) = owner | type | class | TTL | RDATA length | RDATA

elements at the end of the data to be signed have repeating structure in
the owner, type, class and TTL, which likely mean that just the digest
of each "DS" RDATA is fully attacker controlled.  This digest must then
be ~1440 bits long, but that would only be the case if the signer paid
no attention to the (plausible) validity of the DS RRs, since IIRC none
of the registered DS digest types produce hashes this long.

    https://www.iana.org/assignments/ds-rr-types/ds-rr-types.xhtml

If a parent zone does accept arbitrary DS RR payloads in which the hash
value length is not consistent with the purported digest type, then it
may well be exposed to the chosen-prefix attack.  Otherwise, it may be
that checking the hash value to be of the expected length for the digest
type (160, 256 or 384 bits depending on the digest type) is enough to
thwart this specific attack.

This does not mean that staying with algorithm 7 (RSASHA1) is a good
idea, but may buy more time to migrate in an orderly manner.

-- 
    Viktor.