[dns-operations] SHA-1 chosen-prefix collisions

[Viktor Dukhovni]

On Thu, Jan 09, 2020 at 06:02:43PM -0500, Warren Kumari wrote:

> Somehow, even though I read (and re-read) the "chosen-prefix" part of
> "chosen-prefix collision", for some reason when it came to DNSSEC I
> felt that the *attacker* needed to be the one choosing the prefix
> (because of the concatenation of the RRSIG RDATA and the RRSET)
> 
> I started reading Tony Finch's excellent blog post (
> https://www.dns.cam.ac.uk/news/2020-01-09-sha-mbles.html ), all the
> while shaking my head in disagreement...  and then read the "sort
> after the innocuous prefix" phrase and the penny finally dropped.

Apologies for failing repeatedly to explain the issue clearly enough.
For a chosen-prefix collision against hash a function H, the attacker's
task is: given two *arbitrary* message prefixes P and P' to find two
message suffixes S and S' such that: H(P || S) == H( P' || S') (where
'||' means concatenation).

A chosen-prefix attack is a powerful tool, a message with metadata P and
payload S can now have the same digest as a message with completely
different, chosen by the attacker metadata P' and payload S' (though
ultimately the combined message lengths need to be the same).

I should also admit, that I did make a mistake in reporting 20 bytes as
the length of the "blocks" they used to construct the collision
suffixes.  I should have remembered that "compression functions" such as
SHA-1 have a larger internal block size (64 bytes in the case of SHA-1).

So the present attack requires a suffix of ~640 rather than ~200 bytes.
The implications of the longer suffix requirement are not yet clear,
waiting to hear back from the authors of the paper.  Perhaps it is
possible to split the suffix over multiple RRs, or at least over
multiple (sub)strings in a single TXT RR.

The longer suffix could for now rule out misuse of TXT records since
each <character-string> chunk of a TXT record is at most 255 bytes.

Regardless, various other RR types do make it possible to "smuggle"
longer payloads into DNS zones.  And indeed if rdata validation is
missing or sloppy and the attack is authorised to publish any data of
his choice for "his" node (say "kittens.example.net"), he can always ask
the zone operator to publish:

    kittens.example.net. IN TYPE12345 \# 640 ( <1280 hex nibbles> )

This is especially true in the case when the attacker is the registrant
for the entire zone, but the DNS operator uses the same ZSK for multiple
unrelated domains (which is the case for ~220k domains that share their
keys with other customers of the same provider).

If we're not yet all sick of this topic, I'll post any relevant updates
from the authors of the paper.  It seems they were not familiar with
SHA-1 in the context of DNSSEC, but may now take a closer look.

-- 
    Viktor.