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

From: [email-masked]
Date: Thu, 3 Jun 2004 14:29:45 +0200 (CEST)

On Thu, 3 Jun 2004, Scott Rose wrote:

> > -----Original Message-----
> > From: [email-masked]
> >
> > 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
> >
>
> 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.

The salt value is a protection against pre-hashing. If you could prehash
your dictionary, searching for collisions would be very fast.

Roy

--
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: Greg Hudson <[email-masked]>
Date: Thu, 03 Jun 2004 11:18:05 -0400

> example:  Hash(www.example.com).example.com.

Hm.  I was going to say that the salt forces you to attack each hash
separately, instead of the entire zone.  But on consideration (and
rechecking the draft), it looks like the salt has to be the same for the
whole zone in order for NSEC2 to be useful.

So, if I've procured most of the NSEC2 records for a zone (I can't just
download the chain, as some people theorized; as you noted, I have to
make random queries until I've accumulated most of the records), I can
perform a single walk of my dictionary and test each result for
inclusion within the set of NSEC2 hashes.  That doesn't seem very
expensive at all.

Also, if I want to procure lots of NSEC2 records, since I'm just making
random queries, I don't need to parallelize as much as I do for NSEC
walking (where I have to wait an RTT for each packet).  So in some ways
it's easier than an NSEC walk.  If I can run a script on one machine and
get 50-80% of a 4-million-record zone in one day (NSEC2), I might prefer
that to getting 100% of a 4-million-record zone in ten days, or having
to use ten machines to get them all in one day (NSEC).

I'm a little skeptical that spammers will be all that interested in
domain walks of any sort. 
http://www.cdt.org/speech/spam/030319spamreport.shtml suggests that most
spammers are content to harvest unobfuscated email addresses on the web,
and don't take advantage of easy opportunities to harvest other
readily-available sources of addresses (Usenet, WHOIS).  And even if I
experience zero loss in your domain walk (NSEC), I don't necessarily get
many high-quality addresses out of that.  If I have four million
domains, I'm not going to try thousands of addresses per domain; I'm
going to try a few likely targets like "postmaster" and "webmaster" and
"root" and "abuse".  But even then, probably the vast majority of my
email will wind up not even hitting a spam filter, and the people who do
read those addresses aren't likely spam suckers.

I would be more concerned with underhanded DNS "competitors" who want to
replicate the data in your zone and add their own records.  Lossiness is
a much bigger deal to that category of people, and they have to rescan
frequently to remain "competitive"... but there also aren't as many of
them, so they're unlikely to generate a lot of load.

---

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

On Thu, 3 Jun 2004, Greg Hudson wrote:

> readily-available sources of addresses (Usenet, WHOIS).

Because there is no index.... yet.

Roy

---

From: Ben Laurie <[email-masked]>
Date: Thu, 03 Jun 2004 17:27:34 +0100

> do the dictionary attack however.

Note that my plan was to set the time taken (via iterations) to around 
the network turnaround time for a query (i.e. of the order of milliseconds).

> example:  Hash(www.example.com).example.com.

The salt is to avoid precalculated dictionary attacks - on each walk, 
the attacker must recalculate everything.

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

I forgot to mention this last time around. So, if we move the info into 
NSEC2, it must be the same for the whole zone. Therefore, although the 
signature must be over the complete record, the server only needs to 
store _one_ copy of the redundant data, and insert it when sending the 
NSEC2s. Does this reduce your desire to eliminate NSECINFO data?

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff