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: "Christian Huitema" <[email-masked]>
Date: Wed, 28 Jul 2004 14:19:45 -0700

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

There are many other ways to achieve this result. You could also bang
your dutch dictionary words one by one against a bunch of search
engines, and parse the pages for HTTP URL that belong to the .NL domain.
You will very quickly get several thousand names, including the likes of
"example123.nl"...

-- Christian Huitema

---

From: [email-masked] (Ted Lindgreen)
Date: Thu, 29 Jul 2004 10:06:24 +0200

[Quoting Roy Arends, on Jul 29,  9:10, in "Re: dictionary attac ..."]

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

When talking "more expensive", it is relevant to weight:

1. how much more expensive
2. the cost of the lock
3. the value of what is being protected

ad 1. It has being shown (several times) that (90-99%) zone
      enumeration without AXFR is simple and dirt cheap.
      Most of us know that both spammers and domainname-traders
      are doing this already for years on a daily basis with
      all TLDs that have blocked AXFR.

ad 2. The cost of the proposed lock (NSEC2/3/X) means a new
      protocol change, which is rather expensive.

ad 3. We are talking about the protection of one little aspect
      (100 against 99% enumeration) of otherwise public
      information. It has also been argued ((several times) that
      for most, if not all, evil usage of zone-enumeration 90+ %
      enumeration suffices.

To me it seems that in this case the weighting is completely out
of balance.

Regards,
-- ted

---

From: [email-masked] (Ted Lindgreen)
Date: Thu, 29 Jul 2004 10:19:29 +0200

[Quoting Peter Koch, on Jul 29,  9:54, in "Re: dictionary attac ..."]

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

I am probably naive, so please enlighten me: for what "people" would
this last few percents (which probably consists mainly of short-lived
bogus domains like spammer1234.tld) be of such high interest?

Certainly not for the spammer, domainname-grabber, data-miner, etc
type of "people"?

Regards,
-- ted

---

From: [email-masked] (Geoffrey Sisson)
Date: Thu, 29 Jul 2004 10:12:43 +0100 (BST)

> people can walk DNS zones so easily right now?

I can't speak for everyone, but we (Nominet) are advised that we have 
a responsibility to protect the confidentiality of data in the .uk zones,
even if this cannot be done perfectly.

Also, I use to think that, even if "NSEC+" were available, that NSEC
was sufficient for {in-addr,ipv6,e164}.arpa.  Now I'm not so sure.
While any one zone in these hierarchies is trivially enumerable w/o
NSEC, the elaboration of the aggregate trees is a bigger problem which
is considerably reduced by NSEC.  (Okay, maybe not so hard to elaborate
e164.arpa yet by any means . . .)  The reverse trees and enum may prove
to be killer apps for NSEC+.

Peter Koch <[email-masked]>

> the last 10% that makes 90% of the price ...

I think this is also a good summation.

Regards

Geoff

---

From: [email-masked] (Ted Lindgreen)
Date: Thu, 29 Jul 2004 11:28:08 +0200

[Quoting Jay Daley, on Jul 29, 10:47, in "Re: dictionary attac ..."]

> If someone really has done this against a large zone then please let us 
> know.  If you want to test it against ours then please let me know so that 
> we can prepare for it.

I am not sure what you call "a large zone", so also not if .nl
qualifies (it is in the top-5 or so of largest zones, but, of
course, much smaller than .com).
The .nl domain has some 1.3M delegations, some 30k domains are
newly registered and some 5k are released per month (from data
over the first few months of 2004).

I know of a number of registrars who keep daily updated, and
very accurate lists of registrered and returned domain names.
For .nl and also for other TLDs.

These guys use various techniques to keep their lists accurate
and up-to-date. Although highly effective, these techniques are
neither complicated, nor costly for the registrar.
However, their load the .nl nameservers is significant, and thus
one can easily see and determime who/what is causing it in the
nameserver-traces which we routinely investigate in our testlab.

As for your second question: I do not think that any preparation
by your side is needed for us to "attack" your TLD, as the load
of our "attack" on the .nl zone was not even noticed (but will,
of course, be clearly visible in the nameserver-traces).

Regards,
-- ted

---

From: [email-masked] (Ted Lindgreen)
Date: Thu, 29 Jul 2004 12:30:16 +0200

[Quoting Geoffrey Sisson, on Jul 29, 11:36, in "Re: dictionary attac ..."]

> There's a time consideration which this analysis doesn't take into
> account: If `perfect' snapshots (less negligible effects due to routine
> IXFRs) of the owner names in zones can be obtained frequently and with
> low latency, then new possibilites become available.
> 
> It's one thing to have a photo; another to have a film.

I am affraid I have lost it now, please enlighten me:

1. the argument against enumeration is the European (and/or
   other) privacy legislation;
2. it is clear that 99% enumeration on a daily basis is currently
   practice (perhaps not desirable, but real practice);
3. NSEC may provide for 100% correct snapshots, valid in the
   interval between zone-updates.

Do I correctly understand that you are saying that 2 is "a photo"
and 3 is "a film"?

And with that, must I understand the privacy-lawyer's opinion that
for information, which is in the DNS for deliberate publication,
"filmshots at zone-update intervals" are unacceptable, while
"daily photo's" are current practice?

I am affraid I have really lost it...
-- ted

---

From: [email-masked] (Ted Lindgreen)
Date: Thu, 29 Jul 2004 13:58:10 +0200

[Quoting Jay Daley, on Jul 29, 12:40, in "Re: dictionary attac ..."]

> With respect this is still anecdotal.  Where is the real data?  i.e. "By 
> dictionary attack X managed to guess Y% of the 1.3m names".

Dear Jay,

Thank you for calling our work "anecdotal".

You dispute the existance of cybersquatters, spammers, etc. using
fairly accurate lists of existing domainnames.  You even dispute
the possibility of those techniques, and want us to come up with a
full quantitative analysis of one such technique.

However, NLnet Labs is not founded (nor funded) to prove the obvious,
and therefore we will not waste more time this than we have done
already.

For us it suffices, that:
1. with very little work we could do a dictionary attack on .nl,
   revieling the number of domainnames we expected (feared);
2. from work with/at the .nl registry and registrars we know that
   a number of registrars maintain accurate and uptodate lists of
   many TLDs, despite that most of these TLDs have closed AXFR
   many years ago;
3. from work in our testlab with traces of .nl nameservers we have
   seen how some of those registrars obtain part of the info in 2;
4. from other postings in this thread it is clear that others have
   seen various other methods to obtain good lists of registered
   domainnames in the current DNS even when AXFR is blocked.

If you can prove, or at least provide reasonable evidence, that in
a world where above already takes place, NSEC2/3/X versus NSEC makes
enough of a difference to necessitate a redo of the protocol, please
do so.
Sofar, I've only heard about "some privacy-laywer's opinion", vague
"new possibilities" that perfect against 99% accuraty could allow for
(ghost-hunting), and thirdly, fear that nameservers could suffer
overload from NSEC walking (which is provably incorrect: the current
attack-techniques impose already a much greater load, plus that just
making the zone file available via ftp is even more effective).

Please explain to us why NSEC2/3/X is REALLY needed, instead of
asking us to prove the obvious.

-- ted

---

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

> asking us to prove the obvious.

Sorry, unless I'm dropping mail message you have not shown that over x% of
the zone file can be obtained through dictionary attacks in a small amount
of time, where x is a large number (let's say 90% or 95%). Mark Gieben
acknowledged this in the post where he said "Statistics==Lies".

You have merely shown where x is a small number, it can be obtained, and
extrapolated. For the reasons posted on this list, and which indeed should
be obvious, if you can find (say) 25% if (say) 10 hours, that by no means
suggest you can find 90% in less than 40 hours.

The reasons for the requirement for non-traversal of zones (NSEC2/NSEC3)
have been expounded at great length; I don't see any purpose in repeating
them again. As far as I can tell, the w/g reached consensus that there was
a requirement (perhaps not one you have) but that it would not form part of
DNSSECbis.

You have neither demonstrated that that requirement has gone away (as even
if you could demonstrate the .NL zone file can be recovered 100% accurately
by dictionary attack in a small amount of time, that does not necessarily
extinguish a requirement elsewhere - see comment on .com), nor have you
demonstrated that your original thesis (that nearly all of the zone
contents could be retrieved by dictionary attack) is true.

If it's true that you don't have the resources or appetite to perform your
statistical test, can I suggest you post your perl programs and methodology
in detail, and let someone else demonstrate whether or not a dictionary
attack can actually reveal let's say over 95% of a zone file, and the
number of queries it took.

The whole thesis of those proposing NSEC2/3 has been that DNSSEC should not
make the situation substantially WORSE. If it is the case that existing
attacks are just as easy to perform by the attacker as NSEC enumeration,
then that would have some weight. We already know dictionary attacks cannot
in the general case yield a complete zone. Your suggestion that they can
yield a nearly complete zone (for values of nearly like 95%) for effort
comparable with an NSEC enumeration is at the moment not supported by any
data I have yet seen - if it is incorrect, it's probably also disprovable.

If you are going to claim you have a new argument based on new data, please
supply that data, not go half way then claim you are neither "founded
or funded" to produce the relevant results.

Alex

---

From: [email-masked] (Ted Lindgreen)
Date: Thu, 29 Jul 2004 14:59:45 +0200

[Quoting Alex Bligh, on Jul 29, 14:42, in "Re: dictionary attac ..."]

> a requirement (perhaps not one you have) but that it would not form part of

I'm affraid you are misinformed: the w/g has NOT yet reached consensus
on this a requirement.

Discussing and, if necessary, then formulating such a requirement
is a task the w/g still has to do. The (rough) consensus that was
reached, and perhaps confused you, was that the w/g would discuss
this topic at some later time, and not as part of the DNSSECbis
document set.

-- ted

---

From: Greg Hudson <[email-masked]>
Date: Thu, 29 Jul 2004 12:43:50 -0400

On Thu, 2004-07-29 at 04:44, Jay Daley wrote:
> I'm sorry to be picky but I don't think the above is true. 

Your subsequent analysis only addresses dictionary attacks.  But other
attacks have been mentioned here (web-crawling, PTR walking), although
we don't really have numbers on how effective any of the attacks are. 
(As many people have pointed out, "a dictionary attack got me 5% in a
short amount of time" doesn't really prove or even suggest anything.)

---

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: "Jay Daley" <[email-masked]>
Date: Thu, 29 Jul 2004 20:21:44 +0100

Jim

Jim wrote on 29/07/2004 07:08:15 pm:

> Nope. The smaller the zone, the easier it may be to enumerate with a
> stupid dictionary attack. A serious attempt at enumeration wouldn't
> just do a simple dictionary attack: it would try "generic hyphen
> generic", "generic plus string of digits" and so on. This is no
> different from how most password crackers work. The dumb ones just use
> a dictionary.  The clever ones also try manipulations on the names in
> the dictionary: obvious suffixes and prefixes, reversed names, etc,
> etc.

That is precisely my point.  As the register grows the namespace becomes 
more complex, which then leads to searching ever increasing numbers of 
possiblities for ever decreasing results.  This appears at first sight to 
be a limiting function and what we are all arguing about it where that 
limit is.  My view, as expressed before is that 99% is wildly optimistic.

Jay

---

From: Eric Brunner-Williams in Portland Maine <[email-masked]>
Date: Sat, 31 Jul 2004 00:32:13 +0000

> There isn't a binary private/not-private flag; it's very much about
> exactly what you're allowed to do with the data

This issue was debated at length in the provreg wg. You may not know
this, and may not appreciate the outcome.

In a nutshell, a policy object was adopted for provisioning sessions,
proximal to the p3p compact policy, and a binary toggle was added at
the last minute on data elements. I'm the author of the first proposal,
and I'll let you discover who was the author of the second, and infer
the process issues.

The context was publication via :43, and more generally, bulk transfer
and any other publication mechanism, including zone file publication,
and the protocol EPP.

Cheers,
Eric

---

From: Jim Reid <[email-masked]>
Date: Sat, 31 Jul 2004 05:55:41 +0100

>>>>> "Alex" == Alex Bligh <[email-masked]> writes:

    Alex> A successful but necessarily incomplete zone enumeration is
    Alex> in my book an oxymoron.

We can agree to differ. IMO a successful zone enumeration is one that
achieves the goals of whoever is doing the enumeration. That may well
be the whole zone. But it might be the set of names that exist between
iam.co.uk and izm.co.uk.