Subject: dictionary attack on nameservers

From: Miek Gieben <[email-masked]>
Date: Wed, 28 Jul 2004 21:05:31 +0200

Hello, 

After seeing much discussion about NSEC2/3 and God knows what, I
deceided to try something completely different. How long would it take
to do a dictionary attack on the .NL zone? And thereby receiving
almost the entire .NL zone without doing an actual AXFR (nor walking
the NSEC chain if NL would do DNSSEC).

I've downloaded 2 dictionary files (apt-get install wdutch
wbritish-large). These are my dictionaries to attack a nameserver. The
dutch and british dictionary contain around 220,000 words. A word
generator could also be written, which would generate sensible (would
be) domain names.

Another small (perl) program walks through theses words. and queries a
NL nameserver. NX domain replies are stored in a seperate file, valid
replies are stored in another.

Thus I've written 2 trivial tools in about half an hour, I downloaded
some dictionaries and I was ready to query a NL server. Total
preparation time: 1 hour.

  [ I only tried the NL dictionary, I'm to impatient to wait a whole day
  to try all my words... So the calculations may be a bit off, but
  general picture should still be correct. ]

Next I fired up the tool and waited. After 46 minutes the whole NL
dictionary was used up. And I had a partial NL zone.

Some numbers:
started: 10:32
finished: 11:18
total running time: 46 minutes

229360 words in 46 minutes,  4986 words/minute.

This yieled 44886 domain names. Which is a succes rate of 19.57%
(estimate) (of the 229360 words)

(there are lies and there is statistics, but 20% of 4986 is about
1000. So you get about 1000 valid domains/minute by doing this).

NL has 1 million domain names, so this gives me only about 5 percent
of the NL zone.  But to put it bluntly: if I wait 20 * 46 minutes (~=
15 hours), I should get almost the whole NL zone.  I haven't look into
this but 80%, maybe 90% sure looks feasible. And the better the
dictionary, the better the results of course. Also the attack is
highly parallel, 2 computers querying 2 different nameserves, would
cut this time in half.

So within a day you can get an AXFR of any zone out there (the bigger
the zone, the more hits you get, the more accurate your "AXFR" will
be). So my question right now is:

Why is so much effort pumped in to a new NSEC solution for DNSSEC when
people can walk DNS zones so easily right now?

Btw, I will be happy to try this out on other TLD's out there :-)

Regards, 
Miek

--
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: [email-masked]
Date: Wed, 28 Jul 2004 20:10:37 +0000

> people can walk DNS zones so easily right now?

	GACK!!!  would you stop telling people how some of 
	us enumerate thier zones when AXFR is blocked and 
	they don't make the zone contents available in other
	ways (ftp for example).  :)

--bill

---

From: Samuel Weiler <[email-masked]>
Date: Wed, 28 Jul 2004 16:23:23 -0400 (EDT)

Good work.  Interesting result.

> 15 hours), I should get almost the whole NL zone.

This logic is bogus.  The density of hits with dictionary words is
probably greater than the density of hits with other namespaces (like
pairs of words).  While 240K names yielded 45K hits, you'll have to
try far more than 5M names to hit all 1M names in the zone.

For example, if you test the set of all dictionary names with 123
concatenated onto them, (ie. mortgage123.nl), you'll test the same
number of names as you did in your experiment so far, but get far, far
fewer hits.  Even so, some of those names exist in the zone, and
absent some a priori method of predicting which ones do, you have to
test them all to find which ones do.

-- Sam

---

From: Miek Gieben <[email-masked]>
Date: Wed, 28 Jul 2004 23:05:47 +0200

[On 28 Jul, @22:23, Samuel wrote in "Re: dictionary attack on names ..."]
> This logic is bogus.  The density of hits with dictionary words is

well, as I said, statistics == lies.

The main point of my post is that I can enumerate (for +/- 90%) a zone
in 24 hours, even if AXFR is blocked. 

[ The people interested in this kind of information certainly don't
mind they can only get 90%. And btw, you really have a hard time
blocking this... ]

So do we want nsec2/3/X to close down the remaining 10% or do we say:
we can live with enumeration in DNSSEC because even in the DNS people
can walk our zone?

grtz Miek

---

From: Doron Shikmoni <[email-masked]>
Date: Thu, 29 Jul 2004 00:05:38 +0300

>15 hours), I should get almost the whole NL zone.
Could you please explain how you infer this?

Thanks,
Doron

---

From: Paul Vixie <[email-masked]>
Date: Wed, 28 Jul 2004 23:02:24 +0000

miek wrote:

> ..., I should get almost the whole NL zone.  I haven't look into this
> but 80%, maybe 90% sure looks feasible. And the better the dictionary,
> the better the results of course. Also the attack is highly parallel,
> 2 computers querying 2 different nameserves, would cut this time in
> half.

actually, if you have bind8 or bind9 and if your operating system has
kernel-visible pthreads, you can parallelize using the "irs" interface.
see "bind8/contrib/manyhosts/" for an example of how altavista used to
postprocess its web logs back in the days before google.  (so, you don't
actually need two computers to parallelize this function.)

> people can walk DNS zones so easily right now?

all i can say is, humans are involved, and humans love complexity, and
humans hate to be told that they're solving the wrong problem.  let's
have a look at the ol' archives, shall we?

     From: Paul Vixie <[email-masked]>
     To: [email-masked]
     Subject: Re: Proposal to fix NSEC 
     Date: Sat, 22 May 2004 16:34:39 +0000

     ...

     What *I* think, since you mentioned it, is that TLD holders who
     fear enumeration think that restricting AXFR is actually preventing
     enumeration, and that if they'd spend a few years in the trenches
     against spammers and data miners they would come to the conclusion
     that "all useful malevolent forms of enumeration are already
     possible and are already being done" and would then conclude that a
     one-decade DNSSEC is better than a two-decade DNSSEC, given that
     all other things are equal.

or, even more succinct:

     From: Paul Vixie <[email-masked]>
     To: [email-masked]
     Subject: Re: Proposal to fix NSEC 
     Date: Sun, 23 May 2004 21:28:02 +0000

     > I am illustrating that Paul cannot enumerate the zone either
     > accurately or completely.

     i never said i could.  what i said was that i could get a complete
     useful enumeration, containing everything a spammer or marketroid
     would need in order to make "the bad use" of whois that ccTLD's
     supposedly don't want made.

yet, interest in NSEC2 (and now NSEC3) persists.  thank you for proving
that useful enumeration does not depend on AXFR or NSEC, but i think that
the proponents of NSEC2 (and now NSEC3) believed my assertions on this
point and will not be swayed by your evidence.  they do not doubt that
"all useful enumerations are already possible", but they live in a world
where they have to be seen "doing something about the problem".  because
of the way IETF works, that probably means "we all have to be seen doing
something about the problem" even though, as first stated, and now proven,
there either is no problem, or the problem doesn't come from NSEC.

> Btw, I will be happy to try this out on other TLD's out there :-)

i suggest that you do them all.  it won't change anything -- we'll still
rush headlong into another decade of incremental complexity in dnssec --
but it will be satisfying to have the true purpose of that complexity
exposed in advance, for all to see.

note-- ISC will begin work on NSEC3 as soon as there's funding/interest
in it.  the views expressed here are personal, and do not reflect isc's
commitment to implement whatever the community decides upon.

paul

---

From: Roy Arends <[email-masked]>
Date: Thu, 29 Jul 2004 09:03:39 +0200 (CEST)

> we can live with enumeration in DNSSEC because even in the DNS people

I have seen no claims that NSEC2/3/X can prevent zone walking or
enumeration. The goal is to make zone walking more expensive.

The lock on my front door does not prevent break-ins. Its goal is to make
break-ins more expensive.

Roy

---

From: Peter Koch <[email-masked]>
Date: Thu, 29 Jul 2004 09:49:33 +0200

> in 24 hours, even if AXFR is blocked. 

thanks for this effort, hard data is a Good Thing.

> mind they can only get 90%. And btw, you really have a hard time

"The people" have different reasons, some of them want a 100% copy and some
of them want near-realtime "diffs". And it's always the last 10% that makes
90% of the price ...

-Peter

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Thu, 29 Jul 2004 10:52:55 +0200

>we can live with enumeration in DNSSEC because even in the DNS people

That is exactly what I think we should do first.  Get the requirements 
on which this comunity wants to base its developments and then make the 
tradeoffs.

See
http://ops.ietf.org/lists/namedroppers/namedroppers.2004/msg01237.html

--Olaf

---

From: Roy Arends <[email-masked]>
Date: Thu, 29 Jul 2004 11:06:11 +0200 (CEST)

> http://ops.ietf.org/lists/namedroppers/namedroppers.2004/msg01237.html

The important thing is to get consensus within the WG on a few points.
Most importantly:

 o  Will current deployment plans for dnssec-bis be hurdled with nsec++.

 o  Will deployment be feasible with dnssec-bis for _large_ tlds.

If either one is a yes, lets drop nsec+.

Roy

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Thu, 29 Jul 2004 11:06:03 +0200

On Wed, Jul 28, 2004 at 09:05:31PM +0200,
 Miek Gieben <[email-masked]> wrote 
 a message of 68 lines which said:

> wbritish-large).

Do note that this attack works well against ccTLD (where almost all
the domain names are in the national(s) language(s) or in english) but
not against gTLD, where domain names are in hundreds of different
languages or are made by companies like Interbrand and do not appear
in any dictionary.

> 15 hours), I should get almost the whole NL zone. 

I am very skeptical about that. The remaining domain names are the
most difficult to guess (Huitema's attack would be better because you
can match on a partial word.)

> this but 80%, maybe 90% sure looks feasible. 

I do not believe it.

> Btw, I will be happy to try this out on other TLD's out there :-)

Do not hesitate to try with ".fr", which is much smaller, and tell us
the percentage you get with the wfrench dictionary in Debian.

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Thu, 29 Jul 2004 12:24:29 +0200

On Wed, Jul 28, 2004 at 11:02:24PM +0000,
 Paul Vixie <[email-masked]> wrote 
 a message of 83 lines which said:

>      i never said i could.  what i said was that i could get a
>      complete useful enumeration, containing everything a spammer or
>      marketroid would need in order to make "the bad use" of whois
>      that ccTLD's supposedly don't want made.

Getting domain names for spamming is one bad use, and one for which
probably 50 % of the zone would be more than enough.

But there are other bad uses (reverse cybersquatting is a good
example, when big corporations try to find domain names looking like
their trademarks in order to harass the holder). And they typically
require more than 50 % of the zone.

---

From: Damien Miller <[email-masked]>
Date: Thu, 29 Jul 2004 22:18:44 +1000

> break-ins more expensive.

This is a false analogy: the people who want to enumerate DNS zones
wouldn't be spending their own money - they have zombies and botnets to
do the work for them.

-d

---

From: Alex Bligh <[email-masked]>
Date: Thu, 29 Jul 2004 13:43:26 +0100

> wouldn't be spending their own money - they have zombies and botnets to

Though TBF that is the case for both dictionary attacks AND nsec
enumerations.

Alex

---

From: Edward Lewis <[email-masked]>
Date: Thu, 29 Jul 2004 09:14:32 -0400

I'm afraid that I think arguing over the feasibility of dictionary 
attacks, "privacy," and the motivation for and threat of DNS data 
mining is not getting us very far.

Thanks to Miek for taking a stab at enumerating the effort to 
dictionary-attack a zone.  But to really make it convincing, I'd like 
to see an attack carried out  and compare the results to the real 
zone.  Only when we hit a high percentage of the names (65%, 80%, 
90%) would I be really interested in the measure of resources needed 
to pull it off.

But I stress that it's a bit of red herring (non-topic).

As far as the issue of zone enumeration, my thoughts fall into this:

1) When DNSSEC originated, zone enumeration was not a threat. 
Because of this, I think DNSSECbis, meeting other goals, is done and 
ready to be published as a doc set.  If operators aren't happy with 
it, they can treat the doc set the same way they treated RFC 2065 and 
RFC 2535.

2) I do think zone enumeration is a nuisance.  I wouldn't rate it a 
threat to DNS, nor would I rate it a desired feature.  I applaud 
anyone's initiative to study the issue and propose a means to 
accomplish all of what DNS and DNSSEC stands for while preventing 
zone enumeration.

I don't blame all network malfeasance (e.g., spam) on zone 
enumeration though.  Zone enumeration just one element.  But still, 
the DNS ought to limit it's network slag.  (Slag is a waste product 
in steel production.  Olafur reminds me now and then that I need to 
avoid obscure words...;))

3) Zone enumeration is not a privacy issue.  Data in the DNS is not 
private, but bulk access to it can be a problem.  The situation is 
like a company on-line phone list.  I can ask for the number of one 
person, but not the organizational structure of the company.  Don't 
think of that as a privacy concern though - thing of it as an abuse 
of the service.

DNS is lookup, not search.  DNS ought not ever encourage a "search" 
of it's data store.  Not because of privacy, but because we don't 
want mission creep.

4) The way I see NSEC is that we started out with the goal of 
pre-computed, fairly-fine-grained authenticated denial statements. 
We accomplished this in a manner that made zone enumeration possible. 
It would have been nice to not make zone enumeration possible, but it 
is a by product.  (Much like autos do not want to emit carbon 
monoxide - but in order to achieve transportation within the other 
restrictions, it happens.)

5) The way I see "improvements" to NSEC in this manner is like a 
second generation engineering effort.  (Like electric cars.)  It 
would have been real nice to not need to remove zone enumeration - 
either be declaring it a non-issue or by not having engendered it in 
the first place.

IMHO - we ought not fight the efforts to find a better version of 
NSEC.  But, at the same time, the effort to find a better NSEC ought 
not stand in the way of getting DNSSECbis fielded.

-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

"I can't go to Miami.  I'm expecting calls from telemarketers." -
Grandpa Simpson.

---

From: Roy Arends <[email-masked]>
Date: Thu, 29 Jul 2004 15:34:44 +0200 (CEST)

> wouldn't be spending their own money - they have zombies and botnets to

I was referring to expensive as cost in general (i.e. time, effort, etc)
not just valuta. I did not specify if investment were direct, or by
proxy.

The general approach for defense against attack vectors is to increase
their cost. Making attack vectors impossible is Deity.

Roy

---

From: Andras Salamon <[email-masked]>
Date: Thu, 29 Jul 2004 09:56:21 +0200

On Wed, Jul 28, 2004 at 09:05:31PM +0200, Miek Gieben wrote:
> How long would it take
> to do a dictionary attack on the .NL zone?

Thanks for reporting this experiment, very interesting.

> dictionary was used up.

I don't understand your extrapolation here.  Given a reasonably large
dictionary you obtained 5% of the domain names.  How do you propose
obtaining the other 95%, or even 80% of the rest?

Do you have another dictionary that is likely to give you a 20% hit rate
_and_ coverage of the rest of the namespace?  You could certainly create a
new dictionary of, say, 500K words formed by adding the English dictionary
to the Dutch one, and adding common domain suffixes like 123 or prefixes
like 0800.  If you then take the concatenation of every string in this
dictionary with every other string (as well as insertion of '-' between
the strings), you get a dictionary of 2*250*10^9 (500 billion) possible
domain names.  However, you are going to get at most a 10^6/(5*10^11) =
2*10^(-6) hit rate for this dictionary even with 100% coverage.  So you
would get at most 100*5*(10^3)*2*10^(-6) = 1 domain name per 100 minutes
even with 100% coverage.  If you parallelise, say 100 queries at a time,
that's still only 1 name per minute.  Hence, this method is not likely
to help those "direct marketers" who are looking out for the new names
being registered (this was cited by people on this list as a bogey man).
This method will only help those who want a rough list once (and are
prepared to wait several months and generate around 50TB of network
traffic to build it, at 100 bytes per query).

I wager that right now someone wanting to find domains will find it more
cost-efficient to simply scan web server logs, running a spider on search
engine results, or doing in-addr.arpa lookups based on assigned netblocks.

Obtaining 5% of a zone through an efficient method of guessing is
interesting.  However, I am not sure this is sufficient in itself to
argue that limiting zone walking is inherently useless.

On the other hand, if enough people really want a list of domains badly
enough to waste 50TB, 500bn DNS queries and several months gathering
it, then I think it would be better for the network as a whole for
the registries to consider either selling the data or making it freely
available.

-- Andras Salamon                   [email-masked]

---

From: Miek Gieben <[email-masked]>
Date: Thu, 29 Jul 2004 18:46:56 +0200

[On 29 Jul, @09:56, Andras wrote in "Re: dictionary attack on names ..."]
> I don't understand your extrapolation here.  Given a reasonably large

that's probably because the extrapolation is mathematical nonsense.

The point I was making is that:
	1) with no effort at all, I can get a listing zones, with
	   more effort I can probably get a longer listing.

	2) those people who think enumeration is going to be a problem
	   in DNSSEC are saying/claiming enumeration isn't a problem
	   in the DNS?

> obtaining the other 95%, or even 80% of the rest?

modifying John the Ripper to attack a nameserver instead of a local
passwd file? I've played with john the ripper a few years ago, it's 
lots of fun to run the incremental mode on a passwd file :-)

That said. I'm way too lazy to do this. My point is/was that there
are other ways to get a zone, besides AXFR and NSEC walking.

<snip>

> engine results, or doing in-addr.arpa lookups based on assigned netblocks.

I agree. And with some windows zombie hosts on the Internet this will
all go a lot faster still.

So dictionary attacks + spidering web logs + google attacks +
in-addr.arpa lookups will get you 80%/90% of a zone? 

> it, then I think it would be better for the network as a whole for

who says this isn't happening right now? If someone really wants to know
I propose the following experiment (for a TLD).

* Measure your current nameserver load
* Put your zone on a anonymous FTP site
* Measure your nameserver load again

If the load is lower I'm right, if the load is higher some else is
right :-) 

> the registries to consider either selling the data or making it freely

wonderfull idea,

grtz Miek

---

From: Jim Reid <[email-masked]>
Date: Thu, 29 Jul 2004 19:10:46 +0100

>>>>> "Stephane" == Stephane Bortzmeyer <[email-masked]> writes:

    Stephane> Do note that this attack works well against ccTLD (where
    Stephane> almost all the domain names are in the national(s)
    Stephane> language(s) or in english) but not against gTLD, where
    Stephane> domain names are in hundreds of different languages or
    Stephane> are made by companies like Interbrand and do not appear
    Stephane> in any dictionary.

Most languages used on the internet have on-line dictionaries.
Lists of brand names, trademarks and so on can be obtained too.
These can easily be compiled into the dictionary used for doing the
zone enumeration or whatever.

---

From: Florian Weimer <[email-masked]>
Date: Fri, 30 Jul 2004 12:03:48 +0200

> in 24 hours, even if AXFR is blocked. 

There are other methods to do that, for example passive DNS
replication: <http://static.enyo.de/fw/volatile/pdr-draft-7.pdf>

If you put a DNS zone on a public, authoritative name server, it is
public.  There is no way to change this.  Disabling AXFR makes
reconstructing the zone contents somewhat more complicated, but not
impossible (at least for the RRs which are actually used in the wild).

---

From: Florian Weimer <[email-masked]>
Date: Fri, 30 Jul 2004 14:18:27 +0200

* Stephane Bortzmeyer:

> their trademarks in order to harass the holder).

This is completely legal and has to be part of any effort to protect a
trademark.  I suppose that most organizations concerned with trademark
protection already systematically scan copies of the most important
zones.