Subject: A binary online attack on NSEC2

From: Greg Hudson <[email-masked]>
Date: Wed, 2 Jun 2004 15:08:39 -0400

(Apologies if this turns out to be half-baked.)

Let's say I want to find all the records between a.example.com and
z.example.com, neither of which exist, and example.com is using NSEC2.

I query for a.example.com and z.example.com, and note the NSEC2
records.  If I get the same NSEC2 records, I know there are no records
between a and z, and I'm done.

If I'm not done, I query for m.example.com.  If I get the same NSEC2
record as I did for a, I can discard half the search space; likewise
if I get the same NSEC2 record as I got for z.  If I get a third,
different NSEC2 record, then I know there are records in both halves
of the search space.  If m.example.com actually exists, I note that
down and query l.example.com and n.example.com to find an NSEC2
record.

To partition the search space between y.example.com and z.example.com,
I query for ym.example.com.

(There are, of course, other valid characters in DNS labels besides
[a-z], but that's a detail.)

As far as I know, this attack should be totally practical, easy to
parallelize (each time you find that there are records in both half of
the search space, you can split the resulting problem between two
machines with no further communication between the two until you
assemble the list of records at the end), no more easily prevented
than an NSEC walk, and should generate more load than an NSEC walk.

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