Subject: Re: number games. (really NSEC2 vs dictionary attacks)

From: [email-masked]
Date: Thu, 3 Jun 2004 09:16:44 +0200 (CEST)

Don,

That attack was mentioned in:

> Date: Wed, 19 May 2004 15:40:01 +0200 (CEST)
> From: [email-masked]
> To: [email-masked]
> Subject: Re: Proposal to fix NSEC
>
> <hat EDITOR=off>
>
> You're basically bringing back the NO record, with some added jazz:
> http://josefsson.org/draft-ietf-dnsext-not-existing-rr.txt
>
...
<SNIP>
...
> In case you're trying to solve zone walking: Zone walking is still
> possible, hash by hash. An offline dictionary attack (remember that the
> NSECINFO trick does not work) does the rest. To speed things up, you
> could brute-force labels with length up to 5 or 6 characters.

But this was handwaived by some. The crux of it was that with a
enumeration of the reverse space, cache poking or other attacks the road
to zone-enumeration is shorter, especially if your requirement is to just
get to 70% to 75% of the entire zone.

Roy

On Thu, 3 Jun 2004, Don Stokes wrote:

>
> [email-masked] wrote:
> >200M queries a day may not shake an average TLD, but this exercise assumes
> >just 10 kiddies or spammers are interested in the co.uk zone.
>
> If NSEC2 or something a lot like it is deployed, I don't think this will
> get rid of spammers/scammers/script kiddies doing NSEC2 walks.
>
> If you download the entire NSEC2 chain you can do direct dictionary
> attacks on the zone, without requiring network traffic.
>
> Quick tests suggest that even my baby desktop box can do something like
> 6,000,000 SHA1 hashes per second.  A local outfit here was selling
> second-hand PII/400s for about NZ$40 each -- at that kind of price I can
> get a *lot* of compute power for very little money.
>
> Out of curiosity, I did some experiments today, taking an old copy of a
> TLD zone, and subjecting it to tests for susceptibility to dictionary
> attacks.  (Note that this is the reverse of actually performing the
> attack, and, uh, somewhat faster.)
>
> These tests suggest I could find 50% of names in a zone in the space of
> a few hours, on one box, using a fairly dumb dictionary attack on a
> stored list of hashes.  More sophisticated attacks could get better hit
> rates for more time.  While cranking up the NSECINFO iteration count
> would slow the ratbags down (at the expense of legitimate hash
> calculations), I fear that NSEC2 will not solve the problem of data
> mining via traversal of authenticated denial records. It'll be only a
> matter of time before even script-kiddies are doing NSEC2 traversals and
> launching dictionary attacks on large zones for fun and profit.
>
> -- don
>
> --
> to unsubscribe send a message to [email-masked] with
> the word 'unsubscribe' in a single line as the message text body.
> archive: <http://ops.ietf.org/lists/namedroppers/>
>

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Alex Bligh <[email-masked]>
Date: Thu, 03 Jun 2004 08:27:15 +0100

--On 03 June 2004 17:04 +1200 Don Stokes <[email-masked]> wrote:

>> 200M queries a day may not shake an average TLD, but this exercise
>> assumes just 10 kiddies or spammers are interested in the co.uk zone.
>

I may have missed it, but how do you get from the chain of hashed values
(which you can download, but are uninteresting and ephemeral) to a
list of domain names (assuming SHA-1 is one-way).

Alex

---

From: [email-masked]
Date: Thu, 3 Jun 2004 10:04:12 +0200 (CEST)

On Thu, 3 Jun 2004 [email-masked] wrote:

> On Thu, 3 Jun 2004, Alex Bligh wrote:
>
> It was suggested by Don and me to do a dictionary attack to find a
> collision with a hashed label. It might even be feasible to do a brute
> force on labels with 6 characters, considering 37 possible values for a
> character.
>
> A device capable of performing 6000000 hash functions per second (quoting
> Don) walks a space of 37^6 in about 7 minutes.
>
> local hash functions is a wee bit more efficient then online querying

PS. That's why Ben added an iterations field to NSECINFO to up the cost.

Roy

---

From: Don Stokes <[email-masked]>
Date: Thu, 03 Jun 2004 20:30:50 +1200

>list of domain names (assuming SHA-1 is one-way).

By dictionary attack.  I'm not saying they get the full, complete zone. 
NSEC2 is proof against that.  

What I am saying is that walking an NSEC2 chain is still useful to the
sorts of people we've been denying AXFRs to.  The most obvious, but not
the only, use for the chain is a dictionary attack -- you can easily
get 50-80% of names in a typical TLD zone via a straight dictionary
attack, given a local copy of the complete NSEC2 chain and surprisingly
little money's worth of compute power.

>PS. That's why Ben added an iterations field to NSECINFO to up the cost.

Unfortunately, it ups the cost to everyone else, too.

-- don

---

From: [email-masked]
Date: Thu, 3 Jun 2004 10:02:39 +0200 (CEST)

Roy

---

From: "Scott Rose" <[email-masked]>
Date: Thu, 3 Jun 2004 08:18:03 -0400

> -----Original Message-----
> From: [email-masked]
>

Also take into consideration that a random non-existant response will
contain one or more NSEC2 RRs, and each NSEC2 RRs has 2 hash values of valid
names.  An attacker may get a large portion of the (hashed) namespace by
doing random queries like this without too much effort.  They still need to
do the dictionary attack however.

I also have a question about the salt field in the original spec.  I still
am not sure it is useful.  A determined attacker will just take the salt
value anyway and use that.  Why not just have the hash be the FQDN?  For
example:  Hash(www.example.com).example.com.

Mainly I'm thinking of ways to reduce the need for the NSECINFO RR and move
the remaining fields (hash algo and iterations) into the NSEC2 RR.

Scott