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

From: Tony Finch <[email-masked]>
Date: Tue, 7 Jan 2020 14:54:43 +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  <[email-masked]>  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.

---

From: Viktor Dukhovni <[email-masked]>
Date: Tue, 7 Jan 2020 11:18:08 -0500

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

> > branch now rejects SHA-1 signatures (the issue is tracked as

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.

---

From: Ólafur Guðmundsson <[email-masked]>
Date: Wed, 8 Jan 2020 08:50:05 -0800

> 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

---

From: Viktor Dukhovni <[email-masked]>
Date: Wed, 8 Jan 2020 12:12:42 -0500

> idea, but may buy more time to migrate in an orderly manner.

A thread today on dns-operations seems to suggest there's some confusion
about which uses of SHA-1 are at near-term risk of compromise, and which
still are still safe.

Executive summary:

    Zones signed with algorithms 5 and 7 SHOULD migrate to algorithms 8
    or (IMHO preferably) 13.  Especially when importing customer data or
    delegating child zones not under your control.

    Perhaps a draft is warranted that strengthens the advice to avoid 5
    and 7 in https://tools.ietf.org/html/rfc8624#section-3.1

Maybe I can shed some light on this, and make some recommendations.

    - There are still no known pre-image or 2nd pre-image attacks on
      SHA-1 where given a digest an attacker could create a different
      message with the same digest.

          Users of SHA-1 in a protocol that requires only pre-image
          resistance should still migrate to a stronger hash function
          (e.g.  SHA2-256), but they're not immediately at risk.

          For example, the use of SHA-1 as a digest type in DS records
          is not presently at risk, this only requires 2nd pre-image
          resistance.  Also the use of SHA-1 in NSEC3 records poses no
          new risk.

    - There are still no known attacks on SHA1-HMAC, indeed even
      HMAC-MD5 (IIRC) remains unbroken.  But neither are recommended
      in new applications.

          Users of SHA-1 in a protocol that employs a strong secret key
          with HMAC for data integrity should still migrate to a stronger
          secret MAC function (e.g.  HMAC-SHA2-256), but they're not
          immediately at risk.

    - Collision attacks, indeed "chosen-prefix" collision attacks on
      SHA-1 are now somewhat practical (at around 2^64 CPU cost).

          This substantially weakens SHA-1 when used for signing hashed
          content, where a long-enough portion of the content
          (especially the tail) is contributed by an outside party.

          The weakness is particularly significant when signatures are
          over "data at rest" (certificates, DS records, ...) rather
          than say TLS handshake messages, where the attack would have
          to be performed in real-time.

          Users of SHA-1 signatures over data that is not entirely
          *controlled by the signer*, should promptly begin moving to
          new signature algorithms that use SHA2-256 or similar.

In the context of DNSSEC what this might mean:

    - TLD and other public suffix zones that sign DS RRsets for
      child zones they don't control should phase out use of
      algorithms 5 and 7.  In the meantime DS record RDATA
      should be validated to have the expected hash value length.

    - Zones that consolidate and sign DNS records for multiple
      customers, without delegating a separate zone for each customer
      are at greater risk, as e.g. the longer free-form RDATA of
      TXT records makes a more attractive target for chosen-prefix
      attacks than DS record hashes.

    - Zones that only sign *their own* data, with no input from
      untrusted outsiders are not immediately at risk from the
      recent attacks, but should nevertheless plan to move away
      from algorithms 5 and 7 (to 8 or 13).

    - Perhaps a SHOULD NOT rather than NOT RECOMMENDED for DNSSEC
      Signing, while for now DNSSEC Validation continues to require
      support for 5 and 7, which are still common:

          https://stats.dnssec-tools.org/#parameter

      even among TLDs[1], with e.g. .ORG signed with algorithm 5.

-- 
    Viktor.

[1]

  -  274 TLDs sign with SHA-1 based signature algorithms 5 or 7
  - 1102 TLDs sign with SHA2 based signature algorithms 8, 10 or 13
  -    1 TLD  (.bg Bulgaria) is "mixed", it has both
              algorithms 5 and 8 in its DNSKEY RRset.

---

From: Viktor Dukhovni <[email-masked]>
Date: Wed, 8 Jan 2020 12:29:16 -0500

> Due to the structure of DNS records this is hard to pull off,

Yes, at present.

> The only RR types that are suspect are the ones that can have 1440 of
> "garbage" at the end

Yes, at present, but the attacks may continue to improve, perhaps
requiring fewer attacker supplied blocks to reach a collision.

> select blocks that include valid DNS record envelopes.

Yes, while the block count to go from a chosen prefix to a collision is
substantially more than 2.

> into a valid record ==> but who cares about TXT abuse

This is not correct, because with chosen-prefix attacks the two messages
that collide need not share the same owner and type (that's the whole
point of chosen-prefix, the initial segment of the second message can be
freely chosen by the attacker).  Therefore the TXT record can have the
same signature as some more important record, perhaps a fake DNSKEY
RRset for the zone apex!

> and is larger than 1440 bits.

But the real DNSKEY RRset is not attacker controlled, whoever creates
the zone's DNSKEY RRs can already subvert the zone content in whatever
way they see fit.  Legitimate signatures of DNSKEYs are not at risk.

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

Yes, on this we can agree, even though the risk is lower for "leaf"
zones that only sign their own content.

-- 
    
    Viktor.