Subject: Re: wildcards again [Re: Avoiding collisions - desirability & possibility thereof (was Re: dictionary attack on nameservers) ]

From: Alex Bligh <[email-masked]>
Date: Fri, 17 Sep 2004 12:51:42 +0100

Peter,

--On 17 September 2004 13:31 +0200 Peter Koch <[email-masked]> 
wrote:

>> ;; ANSWER SECTION:
>> H.example.alex.org.uk.  494     IN      MX      10 target.example.com.
>>
>> No mention of:
>> ;; ANSWER SECTION:
>> H.example.alex.org.uk.  360     IN      TXT     "HASH"
>>
>> Or are you saying that's changed in DNSSEC?
>
> No, I'm saying that these observations suggest the nameserver
> implementation used to serve the zone is not protocol conformant (with or
> without wcard- clarify). They also stumble over a QNAME like
> 'foo.*.example.alex.org.uk'.

Robert pointed that out off list - I used UltraDNS as the sandbox is behind
a firewall. So I tried on the sandbox on Bind 9, and it returns NOERROR,
but no data.

So my question is, if the zone is
     * IN MX 10 target.
   www IN A 10.11.12.13
   H IN NSEC' blah

And the hash of www is H, what breaks if, on a query of type MX for H,
it returns:
   H IN MX 10 target
(i.e. ignores the NSEC' record).

Alex

--
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: Robert Elz <[email-masked]>
Date: Fri, 17 Sep 2004 19:31:53 +0700

Date:        Fri, 17 Sep 2004 12:51:42 +0100
    From:        Alex Bligh <[email-masked]>
    Message-ID:  <864823E63085C47CEEC82009@[192.168.100.25]>

  | And the hash of www is H, what breaks if, on a query of type MX for H,
  | it returns:
  |    H IN MX 10 target
  | (i.e. ignores the NSEC' record).

The "ignores the NSEC' record" is not nearly as easy as it seems like
it might be (as a message from Mark Andrews pointed out a few days ago).

But even if it is easy, explaining how wildcards work now is difficult,
and than's when it is all simple, and clean, and consistent (difficult
because it sometimes isn't what people are hoping for, or are expecting
based upon the assumption that wildcards do pattern matching).

Expecting anyone to ever understand the things if we start adding special
cases to the algorithm is beyond hope.

kre

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Fri, 17 Sep 2004 14:47:50 +0200

On Fri, 17 Sep 2004 12:51:42 +0100

>  (i.e. ignores the NSEC' record).

In other words you would propose that the searching algorithm would be
modified based on the qtype queried? 

If so ...auucchhh.... :-) 

NB it is not that one cannot propose a change to the full standard,
wildcard carify proposes (will propose) a change on how wildcard owned
CNAMEs are dealth with.

A Little Side Track (I am not sure if these scenarios have been
scetched, apologies if I am duplicating arguments)

EBS1 (Evil Bastard Scenario 0ne):

I own secret-wg.org.

Tomorrow I am going to register 
 HASH(salt=0x00, secret-wg.org).org
 HASH(salt=0x01, secret-wg.org).org
 ...
 HASH(salt=0xff, secret-wg.org).org

Just to make the changes on a hash collission in secret-wg.org 2^24
instead of 2^32. The hash colission being an anoyance during signing
because you have to regenerate all NSEC2s with a different salt not
because you happen to hit a "real" name.

This can be distributed over mulitple registrants can do this each carying 
their part of the registration costs:

 HASH(salt=0x00, secret-wg.org).org
 HASH(salt=0x01, kolkman.org).org
 ...
 HASH(salt=0xff, marnick.org).org
 ...
 HASH(salt=0xffff, geerthe.org).org

you could actually do a DDOS attack on the zone signing process if the
salt space is to small. Practically I think 32bits of salt is
sufficient to mitigate this, so is registration policy.

EBS 2:

Today the .org registry generates their NSEC2s with salt(0x4e8aeb32).
I register
HASH(salt=0x4e8aeb32, secret-wg.org).org
That forces the .org registry to roll their salt to e.g. salt(0x23a5883d)
at which point I register
HASH(salt=0x23a5883d, secret-wg.org).org

Problematic? Maybe.. I force them to sign all NSEC2 RRs for all owner
names in their zone while otherwise they could have used incremental
signing.

The underlying assumption for this is that one version of the zone
would have the same salt for all the NSEC2 RRs. This would not occur
if the NSEC RRs would have owner names in a different namespace in
wich you would not be able (or allowed) to register names (a policy
and not a protocol issue).

--Olaf
  as namedropper.

---------------------------------| Olaf M. Kolkman
---------------------------------| RIPE NCC

---

From: Alex Bligh <[email-masked]>
Date: Fri, 17 Sep 2004 14:27:36 +0100

Olaf,

> wildcard carify proposes (will propose) a change on how wildcard owned

I'm not so much proposing it as trying to work out what it would break.

Incidentally, is the searching algorithm based on the QCLASS queried?
It seemed peculiar to me that NSEC records were of QCLASS "IN"
given I suppose they should be equally applicable to HS records etc.
If the searching algorithm is indeed currently based on QCLASS (or
if changing that doesn't break much given lack of other classes),
then perhaps having NSEC' as a CLASS rather than a TYPE would fix
both the above, and the colliding namespace problem.

...
> sufficient to mitigate this, so is registration policy.

This is perhaps not as stretched a scenario as you might think even with
LONG salts if one is dumb about the cyclic algorithm used (that's why I
said "cyclic function of cycle-length N"). The reason is because whilst one
can show that the expected number of recalculations is less than 2, if an
attacker KNOWS the cyclic algorithm used to produce subseqeuent salts, they
could in theory generate names that would collide with a large number of
subsequent salts. This suggests that the salts themselves should be
produced using a cyclic algorithm known only to the signer, for instance:
 S(i) = H( i, private value)

[pointless aside: perhaps the registry concerned won't mind the extra
CPU cycles with all that extra income flowing in]

> names in their zone while otherwise they could have used incremental

Indeed - you can speed up roll of the salt.

To the extent this is a problem, it could be resolved/mitigated either by
a) Ensuring the NSEC' records are in a separate namespace completely
   (see other thread) [resolution] (evil grin: perhaps we should chose
   the currently maldefined "salt.*.example.com IN NSEC ..."); or
b) Ensuring that NSEC' records representation is unlikely to clash
   with incrementally added namespace; for instance, ensure all
   NSEC records are of the form "_23a4883d NSEC..." (etc.) - that's only
   going to be susceptible when you can add NSEC records beginning
   with "_" (evil grin: perhaps we should chose "*23a4883d NSEC ...").

> and not a protocol issue).

Yep I think that's (a) above.

Another way of mitigating this might be to have multiple NSEC' chains,
each with a different salt. Then you only have to roll one complete
chain.

Alex

---

From: Ben Laurie <[email-masked]>
Date: Wed, 22 Sep 2004 15:22:34 +0100

> cases to the algorithm is beyond hope.

I don't really buy that adding "ignore NSEC' records" is really going to 
confuse people to any noticable extent.

Cheers,

Ben.

-- 
ApacheCon! 13-17 November! http://www.apachecon.com/

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: Ben Laurie <[email-masked]>
Date: Wed, 22 Sep 2004 15:22:59 +0100

> because you happen to hit a "real" name.

Eh? This makes the chances 2^104, not 2^24, surely?

> HASH(salt=0x23a5883d, secret-wg.org).org

No, if you want to force them to change their salt, you must find a hash 
collision with the current salt, work factor 2^80.

> names in their zone while otherwise they could have used incremental

Now you've lost me.

> would have the same salt for all the NSEC2 RRs.

It has to, or the proof doesn't work.

> This would not occur

Hmm. In that case, I have not understood your examples. :-(