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

Ólafur Guðmundsson <olafur@cloudflare.com> Wed, 08 January 2020 16:50 UTC

Return-Path: <olafur@cloudflare.com>
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 113B4120144 for <dnsop@ietfa.amsl.com>; Wed, 8 Jan 2020 08:50:20 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cloudflare.com
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 M0DgKcv9Ac19 for <dnsop@ietfa.amsl.com>; Wed, 8 Jan 2020 08:50:17 -0800 (PST)
Received: from mail-oi1-x244.google.com (mail-oi1-x244.google.com [IPv6:2607:f8b0:4864:20::244]) (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 C73EF12008C for <dnsop@ietf.org>; Wed, 8 Jan 2020 08:50:17 -0800 (PST)
Received: by mail-oi1-x244.google.com with SMTP id p125so3180278oif.10 for <dnsop@ietf.org>; Wed, 08 Jan 2020 08:50:17 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=/kxgPqV1QYdVpckYAizqe03caGZnHV7CTURrwFiOtEE=; b=i0kFuCwDnvZXh6adsZrEP6n9ssCxO99aLDMusmvvqU7pcsMSTqP3sdNt4Gn8Gd+ywh DjgAa4WyChuBDX2uqrI0uBGBNOidMDTnOAMgYQC1ANaylKPvmfXApPfYkQkKEw9zSzXB nTpe2BXDZONfv9oqWKZbHcQ1eg+sR3zRAKSLM=
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; bh=/kxgPqV1QYdVpckYAizqe03caGZnHV7CTURrwFiOtEE=; b=kGci81j+7ogDk9DU+lv46EM/v3u6ERj9IyrTKqcI+r42QPHbdah5rANzQ7xXe/dnRY GDtJi8ZPfygBI8IckjxspMF9BhpRFcYvOethrUpSgVBD5rt6HB3HeMWOM3wh8W4fKMJ8 ge29YujVQ3DTyUVmmDEyymxambMF5JZvO3msu74tG+vl1OgY7QMwdOxygKt1oMXOWjC+ d1ScwS0KSPFUYOg5u8mxViBfqUha7VIcvdFcQN2GcfhPW6lHEH0SqYNeF9y09aNandTO yx3uFrTNzmpiIFeflEgGjwAWtHwSxQCrIVmin8IZJquQ2GI5sFo2GVDuoEl7PNJXi2w4 xlYg==
X-Gm-Message-State: APjAAAXaF+7+E78nXi5Wrlp7W+zAuFQ/cUN4lCYfxPGC/NPRtTJBrvQM QF5fAhNYjeKZ6LOmUTY5rjisk70SvhOtm+iqheCRTjxm+YU=
X-Google-Smtp-Source: APXvYqxc6CqECPvHPgejVySVnxAuEhCo4OrDpkaYA/wr3A5LEZcaf3Rq83M3MA6ra53KUSqce7uFp8EhZycB7yWCC3s=
X-Received: by 2002:aca:48cd:: with SMTP id v196mr3384377oia.102.1578502216793; Wed, 08 Jan 2020 08:50:16 -0800 (PST)
MIME-Version: 1.0
References: <alpine.DEB.2.20.2001071450120.14515@grey.csi.cam.ac.uk> <20200107161808.GG73491@straasha.imrryr.org>
In-Reply-To: <20200107161808.GG73491@straasha.imrryr.org>
From: =?UTF-8?B?w5NsYWZ1ciBHdcOwbXVuZHNzb24=?= <olafur@cloudflare.com>
Date: Wed, 8 Jan 2020 08:50:05 -0800
Message-ID: <CAN6NTqw7WUWKhKKEydWJSDGxrdSe9qe9bqzBYNTJkq92dgFVDQ@mail.gmail.com>
To: dnsop <dnsop@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000e8f06c059ba3afd9"
Archived-At: <https://mailarchive.ietf.org/arch/msg/dnsop/q-JjxOdduXnwRSXMo3n_ijgnt6c>
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: Wed, 08 Jan 2020 16:50:20 -0000

On Tue, Jan 7, 2020, 8:18 AM Viktor Dukhovni <ietf-dane@dukhovni.org> wrote:

> 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.
>
>
Due to the structure of DNS records this is hard to pull off,
the only RR types that are suspect are the ones that can have 1440 of
"garbage" at the end
DS has fixed size so I it can not be used unless someone figures out how
select blocks that include valid DNS record envelopes.
TXT will work if the attacker can encode lengths of the individual strings
into a valid record ==> but who cares about TXT abuse
DNSKEY is with RSA is good candidate for this attack as any DNSKEY RRset
for SHA1 algorithms can be attacked by adding a key that sorts to be last
and is larger than 1440 bits.

Thus anyone that is using RSA algorithm < 8 should think about key or
algorithm rollover

Olafur