Subject: Re: Denial Of Existence: Way Forward

From: Ben Laurie <[email-masked]>
Date: Wed, 03 Nov 2004 16:21:54 +0000

Samuel Weiler wrote:
> On Fri, 29 Oct 2004, Ben Laurie wrote:
> 
> 
>>If opt-in is dropped, then (from memory), the only remaining point
>>is whether hashing is done per-label or over the whole name.
> 
> 
> In San Diego, I did presentation comparing the two NSEC++ proposals,
> but I don't think a summary ever made it to the list (sorry about
> that).  The slides are in the meeting proceedings:
> 
> http://www.ietf.org/proceedings/04aug/slides/dnsext-7.pdf
> 
> To summarize, in addition to the choice of whether hashing is
> per-label or not [1], the two proposals had three "options": opt-in,
> allowing hash iterations, and defining a null hash function.  I think
> we can pick and choose among these, and I think both the iteration
> option and the null hash option are pretty trivial, but I don't recall
> us making any decisions about them.
> 
> In my presentation, I also faulted both proposals for not describing
> how to change hash functions or salts (or number of iterations)

I didn't understand this criticism at the time, and I still don't.

> and
> for not going into enough detail about wildcard processing.  Both of
> those need to be addressed.  I also worried about hash collisions,
> though people keep trying to convince me that the probabilities of a
> collision can be made vanishingly small.  I'd rather see a mechanism
> for rolling (or allowing for coexistence of multiple) hashs and/or
> salts, but I'm willing to drop the collision concern.

The current draft of NSEC2 does allow for coexistence, since the salt 
and iterations are included in each record. I can't remember if that is 
a change.

> [1] The choice of whether to do per-label or whole-name hashing could
> require the introduction of an EXIST RR and other changes to wildcard
> processing rules.  Each choice also reveals different information
> about the zone: whole-name hashing (NSEC2) exposes the names of empty
> non-terminals (via the EXIST RR); per-label hashing (DNSNR/NSEC3)
> exposes the structure of the zone but not the names.

Good point.

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

--
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: Samuel Weiler <[email-masked]>
Date: Wed, 3 Nov 2004 22:40:03 -0500 (EST)

> I didn't understand this criticism at the time, and I still don't.
...
> > ....  I'd rather see a mechanism
> > salts ....

I'm talking about the same thing in these two sentences.  The
proposals need to describe what is required to change salt/hash
function/iterations, even if that is expected to be a rare or
disaster-recovery-only (my-hash-function-had-a-very-bad-day-only)
occurence.  Is that clearer?

Allowing for coexistence makes it much easier, assuming coexistence
works.  DNSNR section 2.1.3 specifically excluded coexistence of
multiple salts and implicitly excluded multiple hashes:

	"The Salt field value must be the same for every DNSNR
	generated in the zone."

I can't find a current NSEC2 draft (was it ever in the i-d
repository?), but I don't think it specifically said "yes, you may
have multiple salts, etc.", nor did it discuss why that would always
work.  A previous version had salt and hash functions as zone
properties (in the NSECINFO RR).  The draft I have (-01, May '04)
still mentions NSECINFO in section 4.

-- Sam

---

From: Ben Laurie <[email-masked]>
Date: Thu, 04 Nov 2004 14:37:59 +0000

> occurence.  Is that clearer?

OK, I understand what you are saying, but not why you are saying it. If 
you want to change them, you just change them.

> 	"The Salt field value must be the same for every DNSNR

Roy has tried to persuade me that there's some reason this _must_ be 
true, but I can't currently recreate the logic[1].

> repository?),

Hmm. There was some mixup with boilerplates, it may never have made it.

> but I don't think it specifically said "yes, you may

You can find it here:

http://www.links.org/dnssec/draft-laurie-dnsext-nsec2-02.txt

Pending rediscussing with Roy why he thought this didn't work, I don't 
intend to update this document as you suggest. I can't see a particular 
problem with it, but I'd note that allowing extra salts does not solve 
the collision problem.

In any case, until we have reached some kind of consensus on the 
requirements stuff, I do not consider this to be anything more than a 
currently superfluous proposal. Should it become relevant, I will update 
it and get it properly submitted as an I-D.

Cheers,

Ben.

[1] I may be confused. Certainly its the case that for each salt/number 
of iterations/hash function, one must hash every name in the zone in 
order to find the correct (minimal) enclosing pair. But this is not a 
barrier to having multiple coexisting salts (etc.). It may be that this 
is what I discussed with Roy.

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 04 Nov 2004 17:08:15 +0100

> you want to change them, you just change them.

For what its worth, I also do not understand why this is needed.

At one point I thought the motivation was a miss-guided attempt to
mimic other security standards (i.e., signature algorithms).  For such
algorithms, it make sense to be support multiple hash algorithms, if
one hash algorithm is broken.  It might have lead people to think that
multiple hash algorithms must always be supported.

However, as far as I understand, the hashed-NSEC idea does not require
a cryptographic strong hash function.  I suspect the idea would work
just as well with CRC-128.  So if my understanding is correct,
supporting arbitrary hash algorithms (possibly via an IANA registry)
would not serve any purpose, except to decrease interoperability.  The
properties we need from the hash function (large enough output set to
make it possible to avoid collisions by changing the salt) can be
verified empirically.

I invite people to think about the hashed-NSEC idea with CRC-128 as
the "hash" function.  I have not analyzed it, or even thought about
it, in any significant detail.  I may be wrong, but proving me wrong
on this, would contribute to a better understanding of the hash
requirements in the hashed-NSEC idea.  And give the satisfaction of
proving me wrong. ;)

Thanks,
Simon

---

From: Roy Arends <[email-masked]>
Date: Thu, 4 Nov 2004 17:10:35 +0100 (CET)

On Thu, 4 Nov 2004, Ben Laurie wrote:

> order to find the correct (minimal) enclosing pair.
>
> But this is not a

This is exactly what we discussed.

In San Diego, I was talking about salting requirements, Ben was talking
about multiple salt possibilities, hence the confusion between us at the
time. We agreed that multiple salts are possible, as long as the
salting requirement (every name MUST be salted with each salt) was
satisfied.

Therefor, the relevant section in the DNSNR draft needs to be updated,
since I did not anticipate having multiple salts.

Multiple salts are no problem, as long as every name is salted with each
salt. For every salt there will exist an NSEC-chain.

Roy

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 04 Nov 2004 17:49:04 +0100

> salt. For every salt there will exist an NSEC-chain.

Could you expand on the justification of this requirement?  In
particular, what will break if one of the chains do not cover all
names?

Of course, there must be some applicable NSEC record for each
question-tuple.  But do they also have to be part of a full chain?

To me, it seems the interesting property should be that clients should
be able to verify the returned NSECbis record.  Whether or not the
NSECbis records involved form a complete chain or not does not seem to
be critical to me.

One situation where having partial hashed-NSEC chains may be with
dynamic update.

Thanks,
Simon

---

From: Ben Laurie <[email-masked]>
Date: Thu, 04 Nov 2004 17:08:07 +0000

Simon Josefsson wrote:
> a cryptographic strong hash function.

It does require preimage resistance, though, which is not a property you 
find much in non-cryptographic hash functions.

> I suspect the idea would work

See above.

Cheers,

Ben.

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 04 Nov 2004 18:52:21 +0100

> find much in non-cryptographic hash functions.

Could you explain when the preimage resistance property required, to
prevent an attack?

I'm trying to work out a complete example (although simplified):

Let's say a client query for ("foo.example",IN,A).  Let's say
CRC128(foo.example) = 42.

Server realize "foo.example" doesn't exist, and return the NSECbis RR
that has a range that include 42:

17 NSECbis ... 96 ...
17 RRSIG ... NSECbis ...

The client verify the signature, and notices that 42 is in range, and
return a "domain does not exist" error, or whatever.

Since CRC-128 is not preimage resistant, an attacker can find many
domain names that produce 17, 42, 96, or any other CRC-128 value, as
the output.  What does he gain by doing so?

Perhaps the problem is when NSECbis is used to prove non-existence of
types on existing names?  I.e., client query for ("foo.example",IN,A)
but now only TXT records exists.  Again, CRC128(foo.example) = 42.

The server returns:

42 NSECbis ... TXT ... 50
42 RRSIG ... NSECbis...

The client verify the signature, compare CRC128(foo.example) with the
owner name of the returned NSECbis RR, and realize A is not mentioned
as an existing type on the list (only TXT is).

Here, again the attacker can compute strings that produce 42 and 50 as
output, but what does he gain?

Admittedly, one could claim that there is a wart in the design.
Attackers can construct query names that produce the same output as
existing names.  That follow immediately from the lack of preimage
resistance.  For example, the attacker might determine a query name
"gazonk.example" such that CRC128(gazonk.example) = 42, thereby (using
the last example above) implicitly proving that TXT records exists for
"gazonk.example".

Is this wart the only consequence you see?  If so, I don't understand
how this become anything but a denial-of-service attack, which the
attacker can do anyway.  The client presumably wouldn't ask for
gazonk.example, right?  If the attacker control what the client
queries for, it seems the attacker might as well point the client to
the attackers own zone, which the attacker control.

Thanks,
Simon

---

From: Samuel Weiler <[email-masked]>
Date: Thu, 4 Nov 2004 13:47:02 -0500 (EST)

[I wrote the below message last night before seeing this morning's
very interesting exchange.  Sorry for some redundancy.]

Yesterday, I said:

> Allowing for coexistence [of different salts/hashes] makes [changing
> salts/hashes] much easier, assuming coexistence works.

I think I've been looking at "coexistence" too naively -- there's more
subtlety here than I first realized, and probably more than I realize
now.

First, the term "coexistence" is overloaded, at least the way I was
looking at it.

One form of "coexistence" is "multiple hashes/salts[1] are in use in a
zone at one time".  Or: "some NSEC records in a zone can use hash/salt
X, while some use Y".  Or even: "each NSEC record may have its own
unique salt".  As I was imagining it, that doesn't work.  Unless
someone beats me to it, I can more about that in a later message.
I'll keep using the word "coexistence"  for this, since it's about
what data is actually in the zone file.

The other thing I was describing with that label was "a client, having
seen (and cached) an NSEC record from a zone then seeing another NSEC
using a different hash/salt will behave as expected".  This doesn't
necessarily mean that both hashes/salts are "in use" at the same time
-- perhaps the zone entirely changed hashes/salts, but some NSECs with
the old hash/salt are still cached in upstream caches.  I suspect this
just works, but I think we haven't thought about it enough (nor
implemented enough code and tested it enough). If not, it MAY be easy
to make work.  In any case, "coexistence" is a bad label for this.
For want of a better term, I'll call it "non-interference (of multiple
hashes/salts from the same zone)", since it refers more to client
behavior than zone contents.

To summarize using these new labels: as NSEC2/DNSNR are defined,
multiple hashes/salts MAY be non-interfering.  "Coexistence" as
described above, does not work.  [Addendum, as of Thursday morning:
since last night, Roy and Ben have talked about why.  Simon's question
suggests that more explanation is needed.]

-- Sam

[1]  Throughout this message, I use "salt/hash" to mean "salt and/or
hash function and/or number of hash iterations", since changing either
is approximately equivalent.  Changing hash functions is actually a
bigger problem than changing salts or number of iterations, for
reasons to be talked about later.

---

From: Samuel Weiler <[email-masked]>
Date: Thu, 4 Nov 2004 13:55:36 -0500 (EST)

> question-tuple.  But do they also have to be part of a full chain?

I'm having a hard time coming up with simple examples, so let's see if
questions are enough:

If there is not a complete chain, how do you ensure that you'll have a
NSEC covering each possible Q-tuple?  And that no NSEC covers existing
names (except during the NSEC TTL or RRSIG lifetime after adding a new
name)?

Or: how do you know what to put in the 'next name' field of an NSEC?
For the owner name, it's easy: you use the hash of the 'natural' owner
name.  But you can't use the hash of the lexically next name in the
'next name' field.  With NSEC++, we discard the 'natural' lexical
ordering: we instead hash all of the names, sort the hashes, and
insert the lexically next hash.  The lexically next hash should have
no relationship with the lexicaly next name.

> One situation where having partial hashed-NSEC chains may be with

Expand on this some idea more.  Are you imagining one NSEC chain of
the "permanent" names and another of the updated names?  If so, one
chain can be used to spoof away names in the other chain.  If you're
imagining incomplete chains, see the questions above.

-- Sam

---

From: Samuel Weiler <[email-masked]>
Date: Thu, 4 Nov 2004 14:07:37 -0500 (EST)

> you want to change them, you just change them.

Caching and resolver state.  What happens when an NSEC using one
hash/salt/etc. is cached, then a different one is seen?

Or what happens when one answer contains two NSECs from the same zone
based on different parameters (ie. the NSEC proving no exact match and
the NSEC proving no wildcard match have different parameters)?  A
resolver must already have logic to find and distinguish between the
two NSECs.  With this kind of answer, it would have to do BOTH hashes
on both the exact name and wildcard name to distinguish them.  Then,
too, you should never see such an NSEC constructed by a cache -- if
auth servers use consistent parameters throughout, it gets simpler.
But if you want to allow inconsistency at the auth servers (and within
one answer), resolvers need to be explicitly told what logic to use.

In any case, resolvers need to be told to expect inconsistent
parameters from zones, and I think some serious testing of that would
be needed.  If you want to allow inconsistency at the auth servers,
even more testing will be needed.

Or maybe I'm just being too paranoid.

> it and get it properly submitted as an I-D.

Fair enough.

-- Sam

---

From: Roy Arends <[email-masked]>
Date: Fri, 5 Nov 2004 09:02:03 +0100 (CET)

> particular, what will break if one of the chains do not cover all

Sure, you must have at least one entire NSEC-chain. A second set of NSEC's
does not have to cover every name. But the second set of NSEC's has to be
complete before the first set is deteriorated.

Sidenote: the NSEC's from the incomplete set of names MUST NOT form a
complete chain.

Roy

---

From: Alex Bligh <[email-masked]>
Date: Fri, 05 Nov 2004 08:44:58 +0000

> a cryptographic strong hash function.

Depends which hash property you are talking about. What you don't
want is inversion (i.e. you know H(x), can you discover x?). It
requires some cryptographically strong properties to prevent this
(or rather make the problem computationally infeasible).

> would not serve any purpose, except to decrease interoperability.

I may be partly responsible for this confusion. I jumped on the proposal
to support alternative hash algorithms for various reasons:

a) When we were back discussing the possibilities of hash collisions (i.e.
H(a)=H(b) where a != b), I pointed out these only happen because (most)
hash functions are not guaranteed to be injective (in fact the ones we
consider are guaranteed not to be injective, i.e. we know collisions will
exist, they are just infinitesimally rare and don't know where they are).
However, for those who are really worried about such things and don't
care about enumeration, but did want to use NSEC2 for something else
(opt-in being discussed at the time), they could use the identity function
as a hash (i.e. H(x)=x) which clearly never collides.

b) Shorter hashes may be useful for those not overly worried about
enumeration who are worried about size of zone file / amount of
on-wire data etc. / computational resources. For all but the latter,
truncated hashes are just as good.

I think (b) is the only really significant reason to support alternative
hashes, though if you are doing this, you might as well support the
identity hash, just as a debugging tool (may be a "reverse the
order of the octets in each label" hash too). If one is truncating,
one could imagine a zone signing thing which automagically sized the
hash sensibly (for minimal chance of collision for incremental update
but also minimizing zone file size). The interoperability concerns
come down to which hashes you make mandatory to support. I would
suggest if we are going this way, we chose one (long) hash, and
the identity hash (as mandatory), reserve all other codes (rather
than go the IANA route), and have another field which is the number
of octets to truncate each hash to.

I cannot see a reason to support multiple hashes for the same record.

Alex

---

From: Alex Bligh <[email-masked]>
Date: Fri, 05 Nov 2004 08:48:36 +0000

> the output.  What does he gain by doing so?

If it's not preimage resistant, these can then be sifted by (for instance)
only looking at ones which match /[a-zA-Z-]+/. Unless I'm missing something.

Alex

---

From: Roy Arends <[email-masked]>
Date: Fri, 5 Nov 2004 09:51:59 +0100 (CET)

> Could you explain when the preimage resistance property required, to

I came to a similar question when writing the DNSNR/NSEC3 draft (section
3.2.2/3.2.3). The following analysis applies to the second-preimage
resistance property. All in all my conclusion was that since the need for
preimage requirement is low, truncation of hashes can be used.

Ofcourse, using the exact same analysis, the use CRC-128 can be defended.

Roy

3.2.2  Second Preimage Requirement Analysis

   A collision resistant hash function has a second-preimage resistance
   property.  The second-preimage resistance property means that it is
   computationally infeasible to find another message with the same hash
   value as a given message, i.e, given x, to find a second-preimage X'
   <> X such that hash(X) = hash(X').  The probability of finding a
   second preimage is 1 in 2^160 for SHA-1 on average.  To mount an
   attack using an existing DNSNR RR, an adversary needs to find a
   second preimage.

   Assuming an adversary is capable of mounting such an extreme, the
   actual damage is that a response message can be generated which
   claims that a certain QNAME (i.e.  the second pre-image) does exist,
   while in reality QNAME does not exist (aka false positive), which
   will either cause a security aware resolver to re-query for the
   non-existent name, or to fail the initial query.  Note that the
   adversary can't mount this attack on an existing name, solely on a
   name that the adversary can't choose and does not yet exist.

3.2.3  Possible Hash Value Truncation Method

   The previous sections outlined the low probability and low impact of
   a second-preimage attack.  When impact and probability are low, while
   space in a DNS message is costly, truncation is tempting.  Truncation
   might be considered to allow for shorter ownernames and rdata in case
   of labels with hash values.  The author seeks comfirmation on the
   assumption that truncation decreases resilliance on colliding hash
   values though the overall security model does not significantly
   deteriorate.

   An extreme hash value truncation would be truncating to the shortest
   possible unique label value.  Considering that hash values are
   presented in base32, which represents 5 bits per label character,
   truncation must be done on a 5 bit boundary.

   Though the mentioned truncation can be maximised to a certain
   extreme, the probability of collision increases exponentially for
   every truncated bit.  Given the low impact of hash value collisions
   and limited space in DNS messages, the balance between truncation
   profit and collision damage may be determined by local policy (but
   see first paragraph where 'the author seeks').

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 05 Nov 2004 10:22:32 +0100

> (or rather make the problem computationally infeasible).

Ah, right.  This should be mentioned as the primary requirement on the
chosen hash.

CRC-128 is fully invertible for input strings < 16 bytes, because of
the linearity.  However, if we assume the salt is 16 bytes (as in
NSEC2), or longer, it is no longer possible to invert it.

> only looking at ones which match /[a-zA-Z-]+/. Unless I'm missing something.

I don't understand.  Are you saying that th attacker finds domain
names /[a-zA-Z-]+/ that "hash" to 17, 42, or 96?  That's possible.
But then what does he do with does names?

Thanks,
Simon

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 05 Nov 2004 10:39:20 +0100

Roy Arends <[email-masked]> writes:

> resistance property.

That was a useful section.  I believe it, and similar sections on
other properties (like non-invertible and preimage resistance), should
go into a document based on the hashed-NSEC idea.

Some specific comment:

>    property.

If you want, you may add a reference to this excellent paper for the
background:

http://www.cs.ucdavis.edu/~rogaway/papers/relates.html

>    The probability of finding a
>    second preimage is 1 in 2^160 for SHA-1 on average.

This is only conjectured, right?

>    name that the adversary can't choose and does not yet exist.

One might make it explicit that this result in a Denial-Of-Service
attack.  Something which is possible anyway.

>    values though the overall security model does not significantly

For what it's worth, I cannot prove that truncation is safe, so I also
encourage more investigation into truncation.  In an earlier version
of the NO draft, it was suggested that truncation should be done to
the closest unique prefix.  Obviously, that didn't work, but it took
me a week to realize it.

Thanks,
Simon

---

From: Ben Laurie <[email-masked]>
Date: Fri, 05 Nov 2004 10:01:12 +0000

> Sidenote: the NSEC's from the incomplete set of names MUST NOT form a

Because you can't predict the order of the hashes, although this 
requirement is theoretically believable, it is practically impossible to 
generate a partial NSEC chain without hashing all names first, in which 
case you may as well generate a complete one.

Cheers,

Ben.

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 05 Nov 2004 11:03:00 +0100

> Sidenote: the NSEC's from the incomplete set of names MUST NOT form a

How do this statement match your earlier (quoted above)?

I read your first post as suggesting that multiple salts would work,
if you create a complete chain using each salt.  Now you are saying
the opposite?  I.e., multiple salts work, but there must only be one
complete chain?

FWIW, I would agree with your last message.  One chain with one salt
is how you typically would start out, and later you can introduce new
salts, and there is no requirement to produce a complete chain with
the new salt.  I'm not sure I understand why the new salt cannot be
used to build a complete chain, though.

Perhaps I misunderstood your first post, hence my question above.

Thanks.

---

From: Ben Laurie <[email-masked]>
Date: Fri, 05 Nov 2004 10:01:36 +0000

> One situation where having partial hashed-NSEC chains may be with

A partial chain will deny records that exist.

---

From: Ben Laurie <[email-masked]>
Date: Fri, 05 Nov 2004 10:03:06 +0000

> the output.  What does he gain by doing so?

A filtered list of domains to query for existence - i.e. a very cheap 
brute force attack.

Cheers,

Ben.

---

From: Ben Laurie <[email-masked]>
Date: Fri, 05 Nov 2004 10:04:25 +0000

> only looking at ones which match /[a-zA-Z-]+/. Unless I'm missing 

There is no requirement to recognise the form of the name. If you can 
invert the hash function (even if the inverse is multi-valued) then you 
get a list of names that might exist that is very much smaller than the 
exhaustive list.

Cheers,

Ben.

---

From: Ben Laurie <[email-masked]>
Date: Fri, 05 Nov 2004 10:06:21 +0000

> exist, they are just infinitesimally rare and don't know where they are).

All fixed-length hash functions have this property (obviously).

---

From: Ben Laurie <[email-masked]>
Date: Fri, 05 Nov 2004 10:20:09 +0000

Samuel Weiler wrote:
> unique salt".  As I was imagining it, that doesn't work.

Its clear that doesn't work in practice, though there isn't anything 
theoretically wrong - the issue is that finding a set of salts that 
covers the zone would be hard.

> Unless
> implemented enough code and tested it enough).

You may not have thought about it enough, but it seems to me quite 
obvious it works. The reason being that an NSEC record denies an 
interval, and that interval is defined entirely by the NSEC record 
alone, so the age of it is immaterial (except, of course, that new 
records may now exist in the interval, but that is a TTL issue, not a 
hashing/salting issue).

> If not, it MAY be easy

Which question?

> reasons to be talked about later.

I don't buy this.

Cheers,

Ben.

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 05 Nov 2004 11:28:35 +0100

> A filtered list of domains to query for existence - i.e. a very cheap 

Ah, I understand now.

However, the traditional "preimage resistance" property is how
difficult it is to find ONE input that hash to a known value.  Even if
that is possible, it seems it could still be computationally
infeasible to derivate a list of such names, containing enough entries
to be useful in a dictionary or brute force attack.  So preimage
resistance seem to be a stronger property than what is needed to guard
for this attack.  Perhaps we could define "enumerated preimage
resistance" to be the property applicable here.

To clarify my position: Hashed-NSEC should ideally use the strongest
known hash function, to be on the safe side.  But considering how the
hashed-NSEC idea fail given various "bad" hashes is a good exercise in
understanding the assumptions.

Thanks,
Simon

---

From: Roy Arends <[email-masked]>
Date: Fri, 5 Nov 2004 11:33:49 +0100 (CET)

On Fri, 5 Nov 2004, Simon Josefsson wrote:

> if you create a complete chain using each salt.

CHAIN is the keyword.

My statement should have been:

Multiple CHAINS are no problem, as long as every name is salted with each
salt. For every salt there will exist an NSEC-chain.

With NSEC chain I mean an ordered circulair linked list of optionally
hashed ownernames.

> Now you are saying

No. multiple salts work, but there must at least be one complete chain.

> the new salt.

As long as the 'old' chain is complete.

> I'm not sure I understand why the new salt cannot be used to build a
> complete chain, though.

It can, no problem.

This is what I ment:

given four names (a,b,c,d) and salt X, you'd start out with

      1      2      3      4
H(a,X)-H(b,X)-H(c,X)-H(d,X)-H(a,X)

This is a circular ordered list (assume H(name,salt)=name).

Now we introduce salt Y for two names (b, c) but not for (a,d)

We are able to create the NSEC: H(b,Y)-H(c,Y)
But not the NSEC chain: H(b,Y)-H(c,Y)-H(b,Y)
Since H(c,Y)-H(b,Y) would deny existence of d.

The new salt can be used to form NSEC records, but to be able to form a
_complete_chain_, all names must be included in the chain.

Roy

---

From: Roy Arends <[email-masked]>
Date: Fri, 5 Nov 2004 12:10:29 +0100 (CET)

> http://www.cs.ucdavis.edu/~rogaway/papers/relates.html

Thanks, great paper.

> This is only conjectured, right?

Cuius rei demonstrationem mirabilem sane detexi hanc marginis exiguitas
non caperet.

:-)

Yes, this is only conjectured.

Roy

---

From: Ben Laurie <[email-masked]>
Date: Fri, 05 Nov 2004 11:49:30 +0000

> Since H(c,Y)-H(b,Y) would deny existence of d.

This is incorrect, since we do not have a < b => H(a) < H(b).

That is, we don't know whether H(a) or H(d) falls between H(b) and H(c) 
or not.

Cheers,

Ben.

---

From: Roy Arends <[email-masked]>
Date: Fri, 5 Nov 2004 12:52:53 +0100 (CET)

> This is incorrect, since we do not have a < b => H(a) < H(b).

assume H(name,salt)=name, as I wrote above. I chose linearity for clarity.

Roy

---

From: Ben Laurie <[email-masked]>
Date: Fri, 05 Nov 2004 12:07:06 +0000

Simon Josefsson wrote:
> difficult it is to find ONE input that hash to a known value.

This is second preimage resistance, surely?

> Even if

We don't care whether a list is available or just a single preimage, 
surely, so long as the actual name hashed is in the list.

> understanding the assumptions.

Indeed.

Cheers,

Ben.

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 05 Nov 2004 13:27:22 +0100

Ben Laurie <[email-masked]> writes:

>>> A filtered list of domains to query for existence - i.e. a very
>>> cheap brute force attack.
>> Ah, I understand now.

I think it depends on which of the hash value you are interested in.

You only know the input to the hash function for H(x) = 42, in my
example it was x = "foo.example", but for H(x) = 17, H(x) = 96 or any
other output, you don't a priori know x.

So for H(x) = 42, the x is known, so it is the second preimage
resistance property that applies.

But for H(x) != 42, the x is not known, so it is the preimage
resistance property that applies.

That is unless I have misunderstood hash function properties, somehow.
There is a nice graphical explanation at the bottom of:

http://www.unixwiz.net/techtips/iguide-crypto-hashes.html

> surely, so long as the actual name hashed is in the list.

There could be many preimages, and only one of them (i.e., the
original existing name that hash to the known value) give any
information to the attacker.

So even if an attacker is able to break the preimage resistance
property, it might not help unless he can create many such preimages,
and use them as input to a dictionary or brute force attack, to
discover the real name that hash to that particular value.

Perhaps this is just the non-invertible property, after all, with a
special oracle.  What I mean is: The attacker is able to invert the
hash function, if she can break the (enumerated) preimage resistance
and has access to a oracle that knows which names exists (i.e., online
query to DNS itself).

Thanks,
Simon

---

From: Ben Laurie <[email-masked]>
Date: Fri, 05 Nov 2004 13:17:02 +0000

> and has access to a oracle that knows which names exists (i.e., online

On reflection, I believe the property we are after is not a standard one 
for cryptographic hashes, which is probably why we're arguing about 
which of the standard properties it is!

As you say, what we want is that the hash should not be invertible - or, 
more strictly, that we shouldn't be able to produce a list of inputs 
amongst which the actual input is guaranteed (or even likely) to be.

Of course, any hash with that does not have this property will not be 
preimage or second preimage resistant (the latter if the list is always 
longer than one element), but a hash which was OK for our use might not 
be cryptographically strong. For example, if it were possible to produce 
a list of inputs for a particular output which was guaranteed to _not_ 
include the original input, this would work for us, but not as a 
cryptographic hash. Its trivial to produce artificial examples of this, 
but I can't think of a real hash function with the property.

Cheers,

Ben.

---

From: Ben Laurie <[email-masked]>
Date: Fri, 05 Nov 2004 14:15:21 +0000

> assume H(name,salt)=name, as I wrote above. I chose linearity for clarity.

Choosing things for clarity that aren't true is not usually a great idea!

---

From: Roy Arends <[email-masked]>
Date: Fri, 5 Nov 2004 15:54:15 +0100 (CET)

> Choosing things for clarity that aren't true is not usually a great idea!

What is not true about the statement H(name,salt)=name ? I chose that to
make sure the ordered hash-chain is linear to the original name-chain. Is
it that unthinkable that one implements a NULL hash function ? It is even
in the DNSNR draft to have none-hashed values for the DNSNR/NSEC3 owner
name.

But, lets do the excersize without linearity.

Lets NOT assume H(name,salt)=name, and go with a real hash function
H(name,salt)=hash. given four names (a,b,c,d) and salt X, you'd start out
with

H(a,X)=g
H(b,X)=z
H(c,X)=l
H(d,X)=q

You'd get:

      1      2      3      4
H(a,X)-H(c,X)-H(d,X)-H(b,X)-H(a,X)

or, maybe more clear:

    g - l - q - z - g

This is a circular ordered list.

Now we introduce salt Y for two names (b, c) but not for (a,d), where

H(b,Y)=s
H(c,Y)=p

We are able to create the NSEC: H(c,Y)-H(b,Y) or [p - s]
But not the NSEC chain: H(c,Y)-H(b,Y)-H(c,Y)
Since H(b,Y)-H(c,Y) would deny existence of H(d,Y) which is not H(b,Y)
nor H(c,Y).

Thanks,

Roy

---

From: Ben Laurie <[email-masked]>
Date: Fri, 05 Nov 2004 16:09:57 +0000

Roy Arends wrote:
> it that unthinkable that one implements a NULL hash function ?

It is certainly not unthinkable, but non-NULL hash functions do not 
behave like NULL ones. What is not true about H(name,salt)=name is that 
it does not apply to all hash functions.

> It is even

The problem is that, for example, H(a,Y) might be q, so H(c,Y)-H(b,Y) 
denies (incorrectly) the existence of a.

Cheers,

Ben.

---

From: Roy Arends <[email-masked]>
Date: Fri, 5 Nov 2004 17:16:21 +0100 (CET)

> denies (incorrectly) the existence of a.

I totally agree. This means every name has to be hashed for each salt.

Roy

---

From: Ben Laurie <[email-masked]>
Date: Fri, 05 Nov 2004 16:23:11 +0000

> I totally agree. This means every name has to be hashed for each salt.

Right.

---

From: Alex Bligh <[email-masked]>
Date: Fri, 05 Nov 2004 17:28:32 +0000

--On 05 November 2004 10:04 +0000 Ben Laurie <[email-masked]> wrote:

>> If it's not preimage resistant, these can then be sifted by (for
>> instance) only looking at ones which match /[a-zA-Z-]+/. Unless I'm
>> missing  something.
>

My point is knowing what likely domain names look like means you
are able to sift such a list very fast (without a query).

Alex

---

From: Alex Bligh <[email-masked]>
Date: Fri, 05 Nov 2004 17:27:31 +0000

Simon,

> NSEC2), or longer, it is no longer possible to invert it.

I am not a cryptographer, but many functions that munge things together
losely called hash functions are not invertible for some values,
and are trivially invertible for others. CRC-128 being an example
if what you've said are correct. Hash functions may be overkill,
but at least they provably do the job.

> But then what does he do with does names?

I mean if you have Y=H(x) to a small set of possibles x1, x2, ...
for which H(x(n))=Y (i.e. they all have the same hash value), then
you can reasonably trivially eliminate most of the set by looking
at characteristics.

For instance, if the hash function was "take the octet value as
a number, and take it modulo a large prime", then you could sequentially
add the large prime to H(x) and see when all octets fall match the
regexp above. That would allow you to sift through the names very
quickly.

Alex

---

From: Alex Bligh <[email-masked]>
Date: Fri, 05 Nov 2004 17:36:11 +0000

--On 05 November 2004 13:17 +0000 Ben Laurie <[email-masked]> wrote:

> for cryptographic hashes, which is probably why we're arguing about which
> of the standard properties it is!

Seems to me that second preimage resistance is a sufficient but (perhaps)
not a necessary condition (though I am not sure we've proved it's not
necessary). As such, I'd have thought the obvious thing to do was to
go for a function with the property, then truncate to appropriate length.
I cannot see any *disadvantage* in doing that, unless someone can show
there is a faster algorithm which is not invertible.

Alex

---

From: Alex Bligh <[email-masked]>
Date: Fri, 05 Nov 2004 18:30:43 +0000

Ben / Simon,

--On 05 November 2004 17:36 +0000 Alex Bligh <[email-masked]> wrote:

> necessary).

Actually, on further thought, and a quick look at the following URL
to check my terminology is right:
  http://www.bletchleypark.net/cryptology/Hash_Functions.pdf

I think if we assume (in deployment terms) the size of a domain is of
comparable size to the size of a distributed attack network (or at least is
not orders of magnitude larger), then the property we want is that knowing
H(x) does not help us find x.

This isn't quite second pre-image resistance - it's one-way or
(first) pre-image resistance. I believe that this is a weaker
requirement than second pre-image resistance as in second preimage
resistance you are given an extra piece of information: some (other)
value that hashes to the same number.

So I think what we need is first-preimage resistance (and that is
both necessary and sufficient) FOR THE PURPOSE OF PREVENTING
ENUMERATION.

However, we've also decided that people being able to find things
that collide (i.e. knowing x, H(x), find a y such that H(y)=H(x)),
is a bad thing (see archives).

If we have first preimage resistance but not second preimage resistance,
then it's going to be (by definition) computationally feasible to
create collisions.

Therefore, I think to be safe both from enumerations, and deliberate
collisions, assuming a distributed attack, both first and second
preimage resistance is both necessary and sufficient.

What I do not think is necessary is strong collision resistance,
but as far as I know it comes for free with all sensible hash
functions.

I'd have thought truncated SHA-256 would be a sensible choice.

Alex

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 05 Nov 2004 23:47:55 +0100

> but at least they provably do the job.

Of course.  My goal with introducing CRC-128 is to make it a vehicle
for discussing exactly what properties are required of the hash
function.  I'm not seriously proposing to use CRC-128, but thought it
might be a useful function for discussion, since it is one of the
simplest and most well known function that behave like a hash function
but is not cryptographically strong.  If we only use (presumed) good
functions like SHA-1 in discussion and examples, intuition about that
specific function might fool you wrt to which properties are required,
and which attacks are possible if some properties do not hold.

> you can reasonably trivially eliminate most of the set by looking

Yes, I understand it now.  You don't even have to rely on
characteristics, you can ask DNS directly, if the set x_i is not too
large.  But being able to compute the set x_i is not a well-known hash
property.  Preimage resistance is the property of computing one
_single_ element of that set.

And as Ben said, if the hash function is designed so that the set x1,
x2, ... that can be feasible computed include all candidates _except_
the real existing name, then the hash function would still be usable
for the hashed-NSEC idea, but would not have the preimage resistance
property.  So preimage resistance is not sufficient.  Preimage
resistance may be necessary, but that is not obvious to me at this
point.

Thanks.

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Fri, 05 Nov 2004 09:12:10 -0500

>salt. For every salt there will exist an NSEC-chain.

I am lost, can you provide a summary of the arguments that lead to this 
conclussion?

--Olaf
  namedropper

---

From: Alex Bligh <[email-masked]>
Date: Sat, 06 Nov 2004 14:37:04 +0000

--On 05 November 2004 23:47 +0100 Simon Josefsson <[email-masked]> wrote:

> large.

The point is that elimination by property occupies a few CPU cycles,
DNS involves several milliseconds. For a leaf label of length 8
octets, there are 256^8 possible values, of which only 63^8 are
fall within the regexp (yes I know it's less than that if you don't
have '-' at start and end, and far fewer if DNS records are stored
in consistent case). That in effect reduces the time taken to
find which of the set corresponds by a factor of 75,000. Let's call
it 10^6 for simplicity.

So if your set was of size (say) 10^12, without sifting, you'd
have to make 10^12 DNS queries, which at (say) 1ms each, running
1000 in parallel, would, take 10^6 seconds or 11 days per name.
However, with sifting, you instead take 1/75000th that time as you
need to make far fewer queries - 13 seconds per name - 2 years to
enumerate co.uk without spreading the load between machines.

> But being able to compute the set x_i is not a well-known hash

First preimage resistance is the property of finding ANY single element of
the set, not the entire set. That is true and I'd missed that. However, you
don't need to find the entire set to have a good stab at enumerability.
However, clearly if first preimage resistance is a sufficient (but not
necessary) property for the "set" preimage resistance you describe; see
other message for why I think you need second preimage resistance anyway.

Alex