Subject: Re: hash algorithm roll

From: Samuel Weiler <[email-masked]>
Date: Fri, 4 Mar 2005 03:28:52 -0500 (EST)

On Fri, 4 Mar 2005, Mark Andrews wrote:

> > Perfect is the enemy of deployed.
>
> 	But when does the list of things that can't be done w/
> 	NSEC3 get so big that we say "this proposal is broken"?

Now.  But that's the wrong question. The question is: when is NSEC3 so
broken that we must stop it?  The answer is: when we can no longer
ignore it and just use something else -- when NSEC3 starts polluting
non-participating zones.

So far, I haven't found any brokenness that rises to that level.

-- Sam

--
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: Ben Laurie <[email-masked]>
Date: Fri, 04 Mar 2005 10:23:13 +0000

Mark Andrews wrote:
>>>Just out of interest, is hash-algorithm rollover that important in
>>>practice?
>>
>>Happily, we have a requirements document for this problem
>>(draft-ietf-dnsext-signed-nonexistence-requirements-01.txt).
>>It does not include hash function rollover as a requirement.
>>
>>The more time I spend on this, the more willing I become to answer
>>"no" -- I'm willing to accept not being able to roll hash functions.
>>I'm even willing to accept the current document's instructions for
>>what to do with NSEC3 RRs w/ unknown hashes: discard them.  I don't
>>think it's good engineering, but if it's sufficient for those who want
>>NSEC3, it will get us NSEC3 (and hopefully signed zones) sooner while
>>taking less effort, and that's a good thing.
>>

Is it possible to roll hash functions in _any_ of DNSSEC?

Cheers,

Ben.

-- 
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: "Olaf M. Kolkman" <[email-masked]>
Date: Fri, 04 Mar 2005 11:38:40 +0100

> Is it possible to roll hash functions in _any_ of DNSSEC?

Yes, by means of changing the key algorithm (RSAMD5->RSASHA1).  Some 
thought has been going into how to prevent attacks during the rollover. 
And the rolling can be done more or less gradually (you can have a 
period in which two signature algorithms are used).

I've tried to argue that a hash-roll in NSEC3 ends up needing a 
flag-date (IMHO that is prohibitive).

Another question, how bad is it that we cannot change hashing 
algorithm?  If HASHSAM is vulnarable than there is a 'timescale' 
attached to that vulnarability (it takes X cycles to find a 
collission).  As long as HASHSAM data lost its relevance before X cycles 
of computing power can be performed you can stay in business. You make 
sure your signature validity intervall is short enough and you use a 
different salt each time you generate new sigs.  ( I might be too naive 
here, crypto analysis is just not my field).

--Olaf
  (namedropper)

---

From: Alex Bligh <[email-masked]>
Date: Fri, 04 Mar 2005 10:50:01 +0000

--On 04 March 2005 11:38 +0100 "Olaf M. Kolkman" <[email-masked]> wrote:

> And the rolling can be done more or less gradually (you can have a period
> in which two signature algorithms are used).

Isn't that a different kind of roll - i.e. a roll between one algorithm
the resolver MUST support and another algorithm the resolver MUST support
(in modern DNSSEC).

I can't see why that kind of roll would be problematic in NSEC3. What
is problematic is a roll between one the resolver MUST support and
one the resolver MAY NOT support. Do those exist elswhere?

> Another question, how bad is it that we cannot change hashing algorithm?
> If HASHSAM is vulnarable than there is a 'timescale' attached to that
> vulnarability (it takes X cycles to find a collission).  As long as
> HASHSAM data lost its relevance before X cycles of computing power can be
> performed you can stay in business. You make sure your signature validity
> intervall is short enough and you use a different salt each time you
> generate new sigs.  ( I might be too naive here, crypto analysis is just
> not my field).

I don't think that works, because you just walk the hash linked list once,
downloading each NSEC3 record, then analyze the data off-line. The only
defense here is if the hash takes longer to crack that the data itself is
useful (rather than the hash taking longer to crack than the data stays up
for).

May be I misunderstood the argument entirely, but noone is claiming
roll between salts is hard, or (for that matter) roll between algorithms
for which there is mandatory resolver support at release time. Are they?

But you say:
> (it takes X cycles to find a collission)

I don't think it's collisions we are worried about, is it? I think it's
inversions. (i.e. being able to determine x from H(x) ). If two RR's hash
to the same value ( H(x) = H(y) where x,y are in the zone file), this can
be sorted at signing time. If an existing RR happens to have the same hash
as a QNAME for a non-existing RR ( H(x) = H(q) where x is in the zone file,
and q is not, but is queried for), we can use the "return identity hashed
version" trick, and they discover one name. If *this* is the attack you are
worried about, then I agree, it will take them so many cycles to find these
hash collisions, that they have no chance of getting a substantial
proportion of the zone file that way.

Alex

---

From: Ben Laurie <[email-masked]>
Date: Fri, 04 Mar 2005 10:54:19 +0000

> flag-date (IMHO that is prohibitive).

I'd argue that you only need to roll NSEC3's hash if you roll the hash 
for signing.

> here, crypto analysis is just not my field).

Well, we've also discussed at length how bad it is being able to find 
collisions, and the answer seems to be "not very bad" (though it is 
obviously undesirable). The other way a hash might be broken is to allow 
preimages to be found (i.e. reversing the hash) - the impact of this is 
that domain names are revealed, not that proof-of-nonexistence stops 
working. This is bad from the POV of people who want domain names not to 
be revealed, but not bad from the POV of whether the zone remains secure.

So, in short, I would _strongly_ argue that hash-rolling for NSEC3 is a 
red herring - if it is ever needed, then it can be rolled at the same 
time as the signature algorithm is rolled.

Cheers,

Ben.

---

From: Alex Bligh <[email-masked]>
Date: Fri, 04 Mar 2005 16:27:25 +0000

Sam,

--On 04 March 2005 11:01 -0500 Samuel Weiler <[email-masked]> wrote:

> I have claimed that the NSEC3 doc fails to describe how to change
> salts (in fact, it says that the salt much be consistent throughout
> the zone, which weakly implies that a change cannot be made).  I
> believe Ben's argument that rolling between salts is possible, but I
> think the document needs more explicit guidance on how to do it.
>
> http://ops.ietf.org/lists/namedroppers/namedroppers.2005/msg00407.html
>
> Without having thought about it much, I also think I agree that the
> second item is possible -- you can roll between hash algorithms that
> are mandatory-to-implement when NSEC rolls off the assembly line.

OK - understand you up to here (provided in the last line you mean
NSEC3, NSEC' or whatever).

> However, I urge caution in relying on that without signalling at the
> zone cut -- presumably the reason you want to roll is weakness in one
> of the hash algorithms.  In which case, you may want to include
> resolver knobs to turn off an algorithm, which would then mean that
> "mandatory" wasn't.

This bit I don't understand. Remember that if the NSEC3 hash is weak (in
that it risks failing a preimage test, i.e. that someone may be able to
deduce x from H(x) ), the effect is that the zone risks enumeration. This
is not a comparable situation to signatures, where the resolver may say
"Oh, that's been signed using BROKENHASH and though it says the hash is
BROKENHASH(X), and thus the message is X, I know it is possible for an
interloper to construct a Y such that BROKENHASH(X)=BROKENHASH(Y), so I no
longer want to trust signatures with a hash generated with BROKENHASH". In
the case of NSEC3, there is no advantage to the resolver in turning off a
hash algorithm - it buys the resolver no extra security - the worst that
happens is they get to determine that the signer of the zone may well have
accidentally allowed people to enumerate it.

What may well happen is the zone *signer* decides to sign no more
zones with the (possibly) broken hash algorithm - he instead chooses
another one (with mandatory support).

My thesis is that it's only ever going to want to be a server (or rather
signer) that wants to stop using a hash algorithm.

For completeness (before someone else brings it up) there is one reason I
can think of why a resolver MIGHT want to stop supporting an NSEC3 hash
algorithm that is "mandatory-to-implement when NSEC3 rolls off the
production line" - that's if it turns out there is some submarine patent on
it. That's (incidentally) why I was proposing SHA-512 (truncated) be the
only (serious) mandatory hash algorithm, on the basis that if it turns out
the SHA family is subject to submarine patent claims, I think we can safely
say we have more to worry about than NSEC3.

Alex

---

From: Samuel Weiler <[email-masked]>
Date: Fri, 4 Mar 2005 11:39:18 -0500 (EST)

> > ... you can roll between hash algorithms that are
> > mandatory-to-implement when NSEC rolls off the assembly line.
>

Oops.  Yes, I meant NSEC3, NSEC++, etc.

> > ... presumably the reason you want to roll is weakness in one of
> > the hash algorithms.  In which case, you may want to include
> > resolver knobs to turn off an algorithm, ...
>
> This bit I don't understand. Remember that if the NSEC3 hash is weak
> ... the effect is that the zone risks enumeration. This is not a
> comparable situation to signatures, ...

Thank you for patiently pointing that out -- I think you're right.

-- Sam

---

From: Samuel Weiler <[email-masked]>
Date: Fri, 4 Mar 2005 11:01:52 -0500 (EST)

> one the resolver MAY NOT support. Do those exist elswhere?

Olaf's choice of example may have led you astray.  We believe it is
possible (read: safe) to roll between any algorithms, inlcuding new
ones (CryptOlaf) and private ones (see -records section A.1.1 and the
experiments draft), no matter the requirement level.  We also believe
that even for mandatory-for-resolvers-to-implement algorithms (except
for ones defined now, contemporaneously with the other DNSSECbis
changes, including DS and the type code roll) there will be old
resolvers out there that don't implement them.

> useful (rather than the hash taking longer to crack than the data stays up

Good analysis, and one that partially addresses Ben's point in a later
message that "I'd argue that you only need to roll NSEC3's hash if you
roll the hash for signing." -- The hash algorithm used as part of
signing can actually be weaker than the NSEC3 one, since it doesn't
need to withstand off-line attacks into the distant future.

-- Sam

---

From: Ben Laurie <[email-masked]>
Date: Sat, 05 Mar 2005 10:49:04 +0000

> say we have more to worry about than NSEC3.

Its possible that we should mandate both SHA-1 (despite recent 
weaknesses) and SHA-512, simply because not everyone has SHA-512 
implementations yet.

I am not religious on this point, however.

Cheers,

Ben.

---

From: Alex Bligh <[email-masked]>
Date: Sat, 05 Mar 2005 16:49:02 +0000

> I am not religious on this point, however.

But if you mandate both, everyone will have to implement SHA-512 anyway
(at the resolver end). You only make life easier for the signers.

Alex

---

From: Ben Laurie <[email-masked]>
Date: Sat, 05 Mar 2005 17:19:46 +0000

> (at the resolver end). You only make life easier for the signers.

True. Doh.