Subject: Re: dictionary attack on nameservers

From: Florian Weimer <[email-masked]>
Date: Wed, 18 Aug 2004 16:25:40 +0200

* Phillip Hallam-Baker:

> At blackhat there was a presentation on the ongoing .il vs .ps cyberwar.
> This began with an attack on various pro-Palestinian groups and was shortly
> followed by a retaliation on pro-Israeli sites and the entire .il domain.
>
> It is pretty clear that whoever is running the .il domain is not going to
> implement any scheme that makes it easier to walk the domain.

Can you be more specific about the kind of attacks?

Most of the attacks I know do not benefit from the knowledge of domain
names.

--
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: Roy Arends <[email-masked]>
Date: Wed, 18 Aug 2004 16:47:30 +0200 (CEST)

> Most of the attacks I know do not benefit from the knowledge of domain

Err, most of the attacks I know involves a target. If the target is the
.de domain, the attack would benefit from the knowledge of zones under the
.de domain.

However, if .il has a problem with enumeration, they might as well demand
a restriction on XFR's ;)

Roy

---

From: Florian Weimer <[email-masked]>
Date: Wed, 18 Aug 2004 17:09:53 +0200

> .de domain, the attack would benefit from the knowledge of zones under the

How so?  I need a list of the name servers for .DE, and detailed
routing information is also desirable (including the router
vendors/software versions that are involved).

---

From: Roy Arends <[email-masked]>
Date: Wed, 18 Aug 2004 17:15:00 +0200 (CEST)

> vendors/software versions that are involved).

I don't, I'd enumerate them thru nsec. Call me lazy.

Roy

---

From: Bruce Campbell <[email-masked]>
Date: Wed, 18 Aug 2004 17:57:01 +0200 (CEST)

> I don't, I'd enumerate them thru nsec. Call me lazy.

It won't be too long before some Registry coddles up a nameserver that
detects nsec/other-based enumuration query trends, and starts dynamically
inserting bogus records to lead the attacker through a twisted trail of
normally-non-existent domains (ala web page scripts that provide lots of
bogus email addresses to fill a scrapper's database with crap).

Has all sorts of connotations ala sitefinder, but as a next escalation
path, it'd work.

--==--
Bruce.

---

From: Paul Vixie <[email-masked]>
Date: Wed, 18 Aug 2004 17:02:22 +0000

> Has all sorts of connotations ala sitefinder, but as a next escalation

not only that, when i consider how much easier it'll be for robotic
telemarketers to reach me by SIP, i think it's going to be necessary
even without NSEC.  (the ip6.arpa and e164.arpa zones are easy to
enumerate since their names are so predictable.)  so, you can probably
expect isc to solicit funding for a bind9 feature that does what you're
describing, within a short year or two.

---

From: kent crispin <[email-masked]>
Date: Wed, 18 Aug 2004 11:37:01 -0700

> vendors/software versions that are involved).

Some real-world router/switch names:

500.Serial3-7.GW6.LAX9.ALTER.NET
POS7-0.BR2.LAX9.ALTER.NET
so-6-0-0.mpr4.sjc2.us.above.net
bb1-hou-P1-0.atdn.net
pop1-atl-P4-0.atdn.net
so-10-0.hsa1.Raleigh1.Level3.net
so-0-3-0.bbr1.LosAngeles1.Level3.net
eth2.dist1-1.sr.sonic.net
sl-gw19-rly-9-0.sprintlink.net
sl-bb27-rly-12-0.sprintlink.net
tbr1-cl2.dlstx.ip.att.net

Note that there is real information encoded in those names.

The ability to completely list of all the domain names under, for
example, Level3.net, would give a tremendous amount of information
about the structure of their network.  One could gather the same
information using thousands of traceroutes, or perhaps by a very
carefully crafted dictionary attack, but the amount of work involved
would be orders of magnitude greater. 

Regards
Kent
-- 
Kent Crispin 
[email-masked]    p: +1 310 823 9358  f: +1 310 823 8649
[email-masked] SIP: [email-masked]

---

From: Bill Sommerfeld <[email-masked]>
Date: Wed, 18 Aug 2004 16:40:40 -0400

> bogus email addresses to fill a scrapper's database with crap).

Indeed.  Chain walking should involve detectably different access
patterns from normal DNS operation..

Filesystems have done this sort of access pattern detection for years;
the difference here is that filesystems usually want to deliver
*improved* QoS for sequential access :-)

Outline of an algorithm:

With only one replica of a zone, it's easy -- if you hit a "green"
name, the next name gets painted "yellow"; if you hit an "yellow"
name, the reply spends some time in a penalty box and the next name
gets painted "red"; if you hit a "red" name, the server gets creative;
colors decay back to green over time.

To generalize to multiple replicas, paint multiple subsequent names
rather than just one; with a large enough window, with queries spread
across N replicas, at least one replica must see an in-window value
and the sequential-access detector will fire, derailing the scan on
that server..

Sensitivity to attack rate and false-positive rate can be adjusted by
tweaking the window size, the color count and the decay timer..

Popular names can be locked green permanently -- the walk-detector
will fire quickly enough once you get into dustier parts of the zone.

						- Bill

---

From: Roy Badami <[email-masked]>
Date: Wed, 18 Aug 2004 22:33:09 +0100

>>>>> "Bill" == Bill Sommerfeld <[email-masked]> writes:

    Bill> Outline of an algorithm:

Very neat.  So lets think of what countercountermeasures at attacker
might take.

Assume for sake of argument a single client performing the scan.

Instead of performing a single scan, it performs many scans in
parallel, round robbining between them.  eg do 1000 scans in parallel,
each staring at different points in the namespace.  So now each of my
scans is 1000 times slower, to give the names time to decay back to
green.

You increase your decay timeout in response; I respond by increasing
the number of parallel scans.  Who will win?  I fear you may hit the
limit of how large you can set the decay timeout without seriously
impacting name resolution performance long before I hit the
implementation limits of this approach, although it's not clear.

Of course, in reality scans by the bad guys are going to be done not
by a single machine, but by armies of zombies each scanning a small
portion of the namespace.  But I don't think that makes much
difference to the analysis; each machine is scanning a portion of the
namespace, and it can split that portion into 1000 subportions and
round-robin between them.

	    -roy

---

From: Roy Arends <[email-masked]>
Date: Thu, 19 Aug 2004 09:07:19 +0200 (CEST)

> round-robin between them.

Oh boy, this is fun, how about this one:

setup a zone, say gotcha.example.com, create a nameserver, delegate your
targets as cnames under gotcha.example.com.

Quickly scan a class B for resolvers, take the bulk (say 2000), and ask
them for stuff under gotcha.example.com. Ofcourse, depending on the result
of one query, you'd enter the target name (as cname) under gotcha.

If 2000 is not enough, scan class A. If example.com becomes to visible,
buy some new.

So, as a defense, why not try to prevent before trying to setup detection ?

Roy

---

From: Jim Reid <[email-masked]>
Date: Thu, 19 Aug 2004 09:04:40 +0100

>>>>> "Bruce" == Bruce Campbell <[email-masked]> writes:

    Bruce> Proposed solutions to enumeration problems should be
    Bruce> limited to domains with 'loose' naming schemes (ie, the
    Bruce> forward zones).

If the WG finds a solution to zone enumeration for these sorts of
zones -- and that's a very big if -- I fear someone else will then pop
out of the woodwork and insist the WG finds a solution that works for
e164.arpa or ip6.arpa, etc, etc.

---

From: Alex Bligh <[email-masked]>
Date: Thu, 19 Aug 2004 09:51:13 +0100

> colors decay back to green over time.

Do you propose that the colour state be a per-querier per-name attribute
(in which case it's going to be defeated by a distributed attack) or simply
a per-name attribute?

One thing I can't quite understand is what "get creative" means in this
context. Delay a reply? (in which case just say add a "-" to the name and
retry), or start leading the querier "down the garden path" by fabricating
names within the appropriate interval (in which case at face value you need
online signing, though admittedly this can be rate-limited).

Alex

---

From: Greg Hudson <[email-masked]>
Date: Thu, 19 Aug 2004 05:05:51 -0400

On Thu, 2004-08-19 at 04:51, Alex Bligh wrote:
> (in which case it's going to be defeated by a distributed attack)

I'm not dead-set against NSEC[23], but I'm seeing an inconsistency
between two different lines of argument for hashed nsec records:

  "DNSSEC makes enumeration too easy.  We need hashed nsec records."
  "But hashed nsec records won't make it that much harder to enumerate."
  "That's okay; security is all about raising the bar for attackers."

  "DNSSEC makes enumeration too easy.  We need hashed nsec records."
  "But you can make DNSSEC enumeration harder through clever tricks."
  "Oh, no, that will never work; people will just use armies of zombies
to conduct their enumeration."

Perhaps it could be argued that hashed nsec records raise the bar much
higher than implementation-specific defenses can, but I'm not wholly
convinced that's true.

(I continue to believe that the most practical way to deal with the
enumeration problem is to allow domains to punt on authenticated
denial.  But that idea doesn't seem very popular.)

---

From: Alex Bligh <[email-masked]>
Date: Thu, 19 Aug 2004 10:39:57 +0100

> to conduct their enumeration."

I can see your point but
a) armies of zombies isn't a clever trick - that's how whois mining is
   currently done - they need to do it ANYWAY to prevent traceability.
b) As far as I can tell, Bill's proposal worked equally well (indeed
   in terms of minimizing required state to be held better) without
   the "per querier" stuff - I was just checking what he meant.

> higher than implementation-specific defenses can, but I'm not wholly

I think if it could be shown there were anti-abuse mechanisms (Bill's
or others) that raised the bar a comparable amount to hashed NSECs,
didn't cause excess breakage, and didn't require large amounts of CPU
(i.e. came at comparable expense) we'd be all ears - it would seem
rather easier than changing the protocol.

However, it seems to me hashed NSEC actually does raise the bar quite high
(meaning that for an anti-abuse mechanism to be comparible, it also has to
be pretty good). That's because right now (non-DNSSEC) the bar is (it seems
to me) pretty high (Paul's in-addr.arpa attack yielded approx 3% of .de I
think), it's very low with NSEC (100%), and the most effective attack on
the hashed NSEC approach appears to be the brute force attack, and that
gave results on .de that (IIRC)
a) gave only a small % of the zone file (again see .de data)
b) refined the attack dictionary poorly - i.e. the malefactor was not
   much better after the attack than they would be had they just used
   the 37^7 possibilities available before the attack.

Alex

---

From: Damien Miller <[email-masked]>
Date: Thu, 19 Aug 2004 22:06:16 +1000

>    the "per querier" stuff - I was just checking what he meant.

I don't really see how defining a window of "coloured" nsec records
would work for anything but the largest zones. I'd expect most 3rd+
level domains to have very few records, so the window would need to be
so small as to risk penalising valid queries.

-d

---

From: Edward Lewis <[email-masked]>
Date: Thu, 19 Aug 2004 08:40:40 -0400

>tweaking the window size, the color count and the decay timer..

While I admire the art of this, it grates against the spirit of what 
I think DNS should be.  That is a lightweight, core, etc., lookup 
service.

What concerns me the most is that to do this the server has to 
maintain a query history.  History is another word for state - 
building up state is a problem for DOS defense.  Building and 
maintaining state is a lot of work - not at all light weight.

My other concern is that I've had bad experience with infrastructure 
systems that try to guess the intent of the data stream.  Especially 
with DNS, where everything you put in the zone is meant to be 
accessed.  How do you detect the difference between a sudden external 
event (like emergency response to a natural disaster) versus 
malicious mining?  What happens if you prevent first responders from 
getting needed data?

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

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

---

From: Chris Thompson <[email-masked]>
Date: Thu, 19 Aug 2004 14:04:50 +0100 (BST)

Bill Sommerfeld writes:
...
> colors decay back to green over time.

It seems to me that this algorithm, and the more elaborate ones along
the same lines, defend only only against zone enumeration which proceeds
sequentially through the name space. There is another sort of enumeration
using NSEC records that doesn't work like that:

 . at any point, I have a number of NSEC records in hand, describing
   intervals free of names (and endpoints that putatively do have
   RRsets)

 . pick a name (pseudo-)randomly from the set of uncovered intervals
   and look it up 

 . this gives me another NSEC record to add to my set (or possibly
   a known RRset, although I can make that last possibility pretty
   unlikely if I want)

 . eventually I will get a set of NSEC records covering the whole
   name space

This isn't quite as trivial to program as the sequential walk, but
it seems to me to be very nearly as efficent.

Chris Thompson               University of Cambridge Computing Service,
Email: [email-masked]    New Museums Site, Cambridge CB2 3QH,
Phone: +44 1223 334715       United Kingdom.

---

From: kent crispin <[email-masked]>
Date: Thu, 19 Aug 2004 02:20:49 -0700

[ Moderators note: Post was moderated, either because it was posted by 
   a non-subscriber, or because it was over 20K.  
   With the massive amount of spam, it is easy to miss and therefore 
   delete relevant posts by non-subsrcibers. Please fix your 
   subscription addresses. ]

> (in which case it's going to be defeated by a distributed attack) or simply

In which case, of course, it provides an avenue for trivial DOS
attacks.

---

From: Ben Laurie <[email-masked]>
Date: Sun, 22 Aug 2004 12:13:07 +0100

> bogus email addresses to fill a scrapper's database with crap).

Dynamic insertion of records would require a signing key to be available 
to all nameservers.

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 29 Aug 2004 03:10:52 -0000

Greg Hudson writes:
> I continue to believe that the most practical way to deal with the
> denial.  But that idea doesn't seem very popular.

A client looks up _goofy._tcp.your.dom. You say, without authentication,
that you don't have any such domain. What should the client do?

   * Take your word for it and use your A record instead? Bzzzt. That
     would allow attakers to forge denials for _goofy._tcp domains that
     really do exist, thus sending _goofy._tcp to the wrong IP address.

   * Discard your packet and wait for an authenticated denial? Well,
     yes, this is required for security, but it's never going to work,
     because you don't support authenticated denial. Client gives up.

You could say that we should stop deploying things like _goofy._tcp, but
some people will insist that certain names of this type are already
being used and have to be supported.

This doesn't mean that you need to respond to any.random.name.your.dom.
A good security protocol would allow signing the nonexistence of some
selected names without revealing anything about other names.

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago

---

From: "D. J. Bernstein" <[email-masked]>
Date: 29 Aug 2004 03:32:29 -0000

Roy Arends writes:
> Quickly scan a class B for resolvers, take the bulk (say 2000), and
> ask them for stuff under gotcha.example.com.

Why does the IETF condone promiscuous DNS caching?

I'm reminded of the situation in 1996, when qmail (version 0.91) became
one of the first MTAs to prohibit relaying by default. People at the
time didn't realize that relaying was going to be massively abused.

---

From: Greg Hudson <[email-masked]>
Date: Sun, 29 Aug 2004 09:35:53 -0400

>      really do exist, thus sending _goofy._tcp to the wrong IP address.

Well, yes, this would be a risk.  But the attacker couldn't redirect
traffic to an IP address of his choice, so for practical purposes, the
attack would probably be limited to a denial of service.  And the whole
idea of punting on authenticated denial is that you accept the denial of
service risk in return for preventing the enumeration risk.

>    * Discard your packet and wait for an authenticated denial?

There would be a signed indication that your.dom punts on authenticated
denial, so there would be no ambiguity to the client.

(One idea which would work with today's DNSSEC implementations is to
create a signed nsec record spanning the entire domain.  But people
were--perhaps rightly--concerned that such a record might be cached and
used in response to other queries, leading to accidental denial of
service.  So to do this right, we would probably need a DNSSEC
extension.  As I said, though, the idea doesn't seem to be very popular
here, so there isn't necessarily much sense in pursuing it.)

---

From: Doron Shikmoni <[email-masked]>
Date: Tue, 31 Aug 2004 01:59:24 +0300

[I've been lurking on this list for a long while, though hardly ever
posted; by way of introduction, relevant part is I'm a security guy /
networking guy / TLD operator (25+ / 25+ / 8+ yrs, resp), and also
a member of ICANN SSAC, so my interest in DNSSEC is kind of multi-faceted].

>>>denial.  But that idea doesn't seem very popular.

It indeed doesn't seem very popular. For my own $.0002, I believe it would
be a good solution to the problem (a problem which I perceive to be very 
real).

>denial, so there would be no ambiguity to the client.

This concern may be addressed if a DNSSEC extenstion is introduced, with
a way to assert that _this_zone_allows_unsigned_denials_. It would be
a signed assertion, which will be sent along with rcode 3 responses.
In a sense, it would address a part of the first concern as well, or
at least "match the expectations" of the zone owner, in terms of threat
(because unsigned NXDOMAINs will be accepted by security-aware resolvers
only if the zone owner permitted them).
Obviously it introduces a security tradeoff (not completely unlike that
of opt-in), and places the choice with the zone owner.

In fact, I sketched something to that effect a few months ago. Is there
interest in discussing such an approach?

>here, so there isn't necessarily much sense in pursuing it.)
Is there?

Cheers,
Doron

---

From: Roy Badami <[email-masked]>
Date: Tue, 31 Aug 2004 00:42:05 +0100

>>>>> "Doron" == Doron Shikmoni <[email-masked]> writes:

    >>  Well, yes, this would be a risk.  But the attacker couldn't
    >> redirect traffic to an IP address of his choice, so for
    >> practical purposes, the attack would probably be limited to a
    >> denial of service.  And the whole idea of punting on
    >> authenticated denial is that you accept the denial of service
    >> risk in return for preventing the enumeration risk.

Different 'you' though, given that most of this discussion revolves
around TLDs, which hence contain lots of zone cuts.

If (hypothetically) Nominet decides not to implement authenicated
denial in .org.uk, then I have to worry about the fact that even a
security aware resolver might be tricked into believing that names
under my domain, gnomon.org.uk, don't exist.  So, from my point
there'd still be benefit in using some other mechanism (such as DLV)
to declare to the world that my domain exists and is secure.

	   -roy

---

From: Ted Hardie <[email-masked]>
Date: Mon, 30 Aug 2004 16:46:33 -0700

At 1:59 AM +0300 8/31/04, Doron Shikmoni wrote:
>be a good solution to the problem (a problem which I perceive to be 
>very real).

It is indeed very unpopular with applications folks.

>a signed assertion, which will be sent along with rcode 3 responses.

Let's imagine I say "The zone example.com allows unsigned denials".
An application gets back an unsigned denial for www.example.com.
Possibly example.com doesn't have web traffic or use this convention
for its web traffic; possibly an attacker was able to insert a denial for
www.example.com. The application doesn't know which.  Had example.com
not chosen to allow unsigned denials for example.com, the application
_would_ know which.

Several folks have argued that it is up to the zone maintainer to make this
choice, and that the applications will simply have to live with this
ambiguity.  We will already have to live with this ambiguity, after all,
for zones who choose not to deploy DNSSEC at all.

While I understand the impetus, I believe it's the wrong engineering
trade-off to make.  Having the application have a clear sense of
what level of data integrity to expect from the DNS is a major
benefit to the applications.  The muddier the water, the higher the
likelihood that the application will get the security story wrong.
Given that user behavior depends on this (do I send my credit
card details in the face of a warning that something that should
be assured by a digital signature was not? how about if it is not
and I'm not sure it should be? how about if it is not and I'm sure
it should not be?), it is in our best interests to get this to be as
clear as possible.  Having half measures where bits of the data are
integrity-protected and bits are not just seems like it invites problems
far worse that enumeration.  To put it another way:  authenticated
denial is a key part of data integrity for a lookup system.  Leaving
it out means the system does not provide data integrity.

To be honest, I think the security story pre-DNSSEC is clear
and that it will be a long while before it is clear again.  Of course, the
story is:  you are at constant risk.  Getting past that to some level of
data integrity requires going through a phase where some zones' data are
protected against tampering and some are not; that's going
to muddy the security waters a bit, like it or not (since we
have no Internet Police out there forcing people to use DNSSEC
as it is deployed).  I'd love it if we could get to a security
story that is just as clear:  data coming from the DNS is
integrity protected.  It's going to be a long road to get there,
but if we don't start walking sometime, we'll never get there
at all.

To quote Jim Reid:

"Meanwhile, large chunks of the name space continue to be unsecured."

Can we start walking?
			regards,
				Ted Hardie

---

From: Roy Arends <[email-masked]>
Date: Tue, 31 Aug 2004 10:19:44 +0200 (CEST)

> be a good solution to the problem (a problem which I perceive to be very

Please keep in mind that authenticated denial is also used for proof of
absence of wildcards, or absence of matching names when wildcards exists.

Punting on authenticated denial is not that straightforward.

Roy

---

From: Edward Lewis <[email-masked]>
Date: Tue, 31 Aug 2004 08:06:03 -0400

>be a good solution to the problem (a problem which I perceive to be 

Along with Ted Hardie's answer, another point is that I think once 
DNSSEC added the DS RR, authenticated denial became essential.

It used to be that a secured parent zone would indicate that a child 
was insecure by adding a signed NULL KEY RR to the referral.  If 
there was no NULL KEY RR, then the validator would assume the child 
was secured.  In the face of a stripping attack (or a cache's failure 
to include the KEY RR), the validator would fallback to expecting the 
child to be secure.  As DNSSEC was never out to defend against denial 
of service, this was the "safe choice."

Now, the DS RR is used to tell the validator the child is secure. 
Without it, the child is insecure.  With the same stripping attack 
(or omission), validators would fallback to insecurity for zones.  I 
don't think that this is very desirable.

So I think that once we added the DS RR and removed the NULL KEY RR, 
authenticated denial became essential.   If we added the ANTI-DS RR, 
then we go back to not needing authenticated denial for DNSSEC's sake.