Subject: Re: online signing draft

From: Ben Laurie <[email-masked]>
Date: Tue, 09 Nov 2004 16:02:41 +0000

Samuel Weiler wrote:
> Better Increment & Decrement Functions

Geoff and I have been working on a rigorous definition of these, which I 
hope he'll post later today.

Cheers,

Ben.

--
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: Andras Salamon <[email-masked]>
Date: Sun, 14 Nov 2004 13:32:08 +0200

On Mon, Nov 08, 2004 at 06:28:08PM -0500, Samuel Weiler wrote:
>        Minimally Covering NSEC Records and DNSSEC On-line Signing
>             draft-weiler-dnsext-dnssec-online-signing-00.txt
> 
>    This document presents a way to prevent zone walking by
>    constructing NSEC records that cover fewer names.  These records
>    can make zone walking take approximately as many queries as simply
>    asking for all possible names in a zone, making zone walking
>    impractical.

Let n(Z) be the size of zone Z, f(Z) be the number of queries typically
generated by a brute force enumeration of zone Z, and k(Z) be the number
of enumerations sought each day by people trying to enumerate zone Z,
and we have been told previously that k(Z) is likely to be a number in
the hundreds (if not more).  Usually f(Z) >> n(Z).

With online-signing-00, we are then back to O(f(Z)*k(Z)) daily queries
being sent to name servers authoritative for zones Z, just like today.

However, today without DNSSEC each query costs O(1) time to generate and
O(1+log n(Z)) time to answer.  With online signing, we still have each
query costing time O(1) but answers now costing O(q+1+log n), where q is
a constant dependent on the length of the encryption key and the server's
crypto hardware accelerator.  As far as I can tell, this is at least
an order of magnitude more work for the servers, given usual values of
the constant q.  This breaks requirement 15 (minimisation of asymmetry)
in signed-nonexistence-requirements-00.

Given requirement 15, shouldn't we also revisit increasing the time on
the _query_ side of DNSSEC, so each query takes time O(q) to generate
and process?

As far as I can see, there will always be asymmetry if one can make a
trivial distinction between positive and negative answers.  After all,
an enumerator isn't interested in verifying signatures on responses.
Precomputed NSEC records are a way to keep the server side cost down to
O(1), but allow enumeration if there are only O(n(Z)) precomputed records,
or otherwise require infeasibly large space, approaching f(Z).

In DNSSEC-ter, could we not drop this distinction, and instead always
return responses to queries, accompanied by indicator records which
have to be decrypted to determine if the response is actually a dummy?
These records would indicate whether the response is a dummy, and if
not they would serve the same function as NSEC records.

A www.example.com? ->
www.example.com. A 10.0.0.1
                 ISEC <encrypted indicator, null>

A wwx.example.com? ->
wwx.example.com. A 127.0.1.2
                 ISEC <encrypted indicator, cf. NSEC>

However, I don't yet see how in the above scheme responses could be chosen
to always be "harmless" without being identifiable by an enumerator as
being negative responses (eg. IPv4 addresses in the block 127/8 as above).

The other alternative seems to be to find a way to generate and store
at least O([n(Z)]^2) precomputed signed NSEC responses.  For zones with
1m domain names, this doesn't seem feasible either.

-- Andras Salamon                   [email-masked]

---

From: Alex Bligh <[email-masked]>
Date: Sun, 14 Nov 2004 13:32:44 +0000

--On 14 November 2004 13:32 +0200 Andras Salamon <[email-masked]> wrote:

> crypto hardware accelerator.

Actually a ratio of that constant to the processor time to do a lookup.
IE as its O() it depends on the relative speed of lookups to crypto.

> As far as I can tell, this is at least
> the constant q.

As you say, depends on q and log n, but yes.

> This breaks requirement 15 (minimisation of asymmetry)

Yes. The other side of the same coin is it is trivial to perform an
effective denial of service attack by querying random QNAMEs. Whilst
one might chose to drop ones that don't (say) have LNH composition
in high load environments, zones are normally sufficiently sparse
that it would be possible to generate unique (i.e. uncachable
authoritative server side) queries that are distinctly plausible.
For instance, 6 letter strings have over 10^10 combinations, and
[consonant][vowel][consonant][vowel][consonant][vowel]
[consonant][vowel][consonant][vowel][consonant][vowel][consonant]
has over 10^13 combinations.

Cycling through those from sufficient parallelized zombies will,
I would have thought, saturate any crypto processor. Whilst it's
possible to start dropping synthetic NSECs (apparently acceptable
to some as "authenticated denial is less important" - to them), that's
a ridiculous argument as you might as well just go with opt-in if
that were the case and drop the crypto processor requirements and
script kiddie opportunity.

> the _query_ side of DNSSEC, so each query takes time O(q) to generate

That assume that the solution you want on the resolver side does have an
element that takes O(q) time to process! Whilst the latter is possible, I'm
not sure it is desirable, not least because of the asymmetry problem. I'm
not sure whether you are just suggesting this as a straw man, but saying
we'll make all queries more resource intensive, because by only making
minimal changes to the protocol we've been left with making some responses
more resource intensive, and otherwise there will be asymmetry, to me
suggests that we have to look beyond minimal changes to the protocol.

>                  ISEC <encrypted indicator, cf. NSEC>

Perhaps I am missing something here, but now rather than do f(Z) cheap
queries, does the attacker not instead have to do n(Z) expensive queries?
(i.e. he can work his way through the zone by enumeration, but has to
decrypt each answer). Assuming the decryption is about as hard as the
online signing, and f(Z) >> n(Z) (as you yourself posit), doesn't this make
the job rather easier for the attacker?

Alex

---

From: Andras Salamon <[email-masked]>
Date: Mon, 15 Nov 2004 11:56:48 +0200

On Sun, Nov 14, 2004 at 01:32:44PM +0000, Alex Bligh wrote:
> not sure it is desirable, not least because of the asymmetry problem.

It seems the way to fix asymmetry is either to reduce the server side
time, or to increase the resolver side time: so why is increasing resolver
side time not desirable?

> I'm

I'm struggling to follow your reasoning here.

I was trying to look at _how_ the resolver side could be made to incur
O(q) time, without mandating major changes to resolvers which are
uninterested in the additional DNSSEC information.

Overall, I am tending toward your conclusion that major protocol changes
may be required if asymmetry is to be avoided.  The one solution I put
forward relies on returning RRs for non-existent domain names, which
seems to lead to unsafe values being returned, or otherwise allows
trivial recognition.  The other solution would require a very large
number of precomputed signed negative answers.  There may be other,
smarter ways of going forward.

Any further ideas for solving the asymmetry problem, or for rigorously
showing it can't be solved while keeping backward compatibility?

> queries, does the attacker not instead have to do n(Z) expensive queries?

I should have explicitly mentioned that I was thinking of epsilon
semantics for NSEC records when I wrote the above, ie. f(Z) expensive
queries would be required.

---

From: Alex Bligh <[email-masked]>
Date: Mon, 15 Nov 2004 12:13:24 +0000

Andras,

>> element that takes O(q) time to process! Whilst the latter is possible,
>> I'm not sure it is desirable, not least because of the asymmetry problem.
>

Because reducing asymmetry is not the only objective. Having a protocol
that requires minimal CPU both ends would be ideal. (Reductio ad
absurdum: make name resolution NP-Complete both ends).

>> minimal changes to the protocol we've been left with making some
>> responses more resource intensive, and otherwise there will be
>> asymmetry, to me suggests that we have to look beyond minimal changes to
>> the protocol.
>

May be I misunderstood your changes - I thought you were proposing
in essence that resolvers needed to decrypt replies? That's a pretty
major change to resolvers isn't it?

I guess what I am saying is that IF, in order to support something
like NSEC-epsilon, we need to make major changes to the resolvers
to prevent asymmetry (which make them slower), THEN we should be
questioning whether or not NSEC epsilon is the right solution,
because we can, with the same degree or lesser degree of intrusiveness
both server side and resolver side, produce a solution that does
not have asymmetry properties, and moreover avoids asymmetry by making
the server faster rather than the resolver slower.

> Any further ideas for solving the asymmetry problem,

hashed NSEC' (arguably there is mild asymmetry here in terms of
hash lookups, but probably no greater than say UDP checksum
on inbound packets - a calculation which an attacker could simplify
knowing how his packets change byte by byte).

> or for rigorously

I am thinking about that, but I think proving that in a rigorous
sense may be hard.

> queries would be required.

Doh! My bad.

Alex