Subject: hash algorithm roll

From: "Olaf M. Kolkman" <[email-masked]>
Date: Thu, 03 Mar 2005 14:43:12 +0100

I've started a new thread.

I think we all agree that by using a scheme like the algorithm roll we 
can reliably move NSEC to NSEC3. Those validators that do not have NSEC3 
implemented will have a "signed record" that will tell them this zone 
will use NSEC3 and those validators that do not understand NSEC3 will 
treat the data from that zone as insecure.

A zone that would want to roll from NSEC to NSEC3  can do so gradually 
(if the signalling is done via algorithm rolls) as there is no
down-grade attack possible.

I am trying to assess if one can gradually go from NSEC3 with hash-algo 
'a' to NSEC3 with hash-algo 'b' and I do not think it is possible. 
Changing hash-algorithms would be a flag date event. Even if the server 
would hand out NSEC3s with both hash-algos stripping of one of the NSEC3 
RRs would go unnoticed as they are not tied together by an RRSIG.

I seriously wonder if a domainowner (whose custommers pay to get  secure 
delegations) would change the hashing algorithm so that a fair 
persentage of the validators in the field, that previously saw the zone 
as secure, now treat sub-domains become insecure.

In other words I think that hash-algorithm rollover has its problems 
unless we make clear to the validator which hash algorithms to expect.

(One of the signaling algorithms I can come up with is that the zone 
owner needs to use the same hashing algorithms in the NSEC3 as that are 
used in the signing algorithms. ugly ugly.)

--Olaf
   (namedropper)

--
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: Alex Bligh <[email-masked]>
Date: Thu, 03 Mar 2005 15:25:27 +0000

> treat the data from that zone as insecure.
...
> unless we make clear to the validator which hash algorithms to expect.

Just out of interest, is hash-algorithm rollover that important in
practice?

Would it be a Very Bad Thing (tm) if hash-algorithm rollover was handled
just like the NSEC->NSEC3 transition you describe - i.e. fix supported
hash algorithms in NSEC3, code in lots of hashes with variable
truncation parameters, deprecate any found to be terminally weak,
and if we end up with no usable hashes, invent NSEC4 with some working
ones and roll to that in the same way as NSEC->NSEC3?

Alex

---

From: Samuel Weiler <[email-masked]>
Date: Thu, 3 Mar 2005 15:05:47 -0500 (EST)

> Just out of interest, is hash-algorithm rollover that important in

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.

Perfect is the enemy of deployed.

-- Sam

---

From: Alex Bligh <[email-masked]>
Date: Thu, 03 Mar 2005 20:35:35 +0000

> taking less effort, and that's a good thing.

Actually I think I may have an engineering reason why not supporting
rollover is a good idea - it's (provably) never actually going to be
useful.

Let's assume:
A. NSEC3 (as finally published) supports the following types of hash
   i)   identity 'hash'
   ii)  trivially invertible (e.g. 32 bit XOR) test 'hash' so those
        worried about collisions can test it.
   iii) SHA-1
   iv)  SHA-512 truncated to n octets for various values of n
   v)   WHIRLPOOL (512 bit) truncated to n octets for various values of n
   and that all the above are mandatory

B. There exists some mechanism of doing a hash algorithm rollover
   (yes, some people may consider this counterfactual, but hang in there,
   I think I'm coming out on your side).

C. There is a (subsequent) requirement to do an algorithm rollover.

If so, one has to ask what on earth would have driven the requirement? The
only thing I can think of is that one or more of the useful hashes (iii)
(iv) and (v) is found to be broken in some way, i.e. partially invertible.
The zone publisher no doubt wants to prevent enumeration, or they'd be
using the identity hash, or would be unfussed about the breakage. Now, if
some, but not all of the useful hash algorithms in the standard are broken,
they can 'roll-over' to another (supported) algorithm - this isn't a real
roll-over problem, this is just "take your next version of the zone with
different algorithm NSEC3" - the resolver must either support NSEC3 and all
the algorithms on publication, or none. EG if SHA-1 is broken, the signer
can switch to (say) SHA-512 truncated, because he knows all resolvers must
support that.

So the only requirement for a real rollover (where you face the possibility
that a resolver does not understand an algorithm you've newly introduced)
is where ALL the hash algorithms available in the (as published) NSEC3 are
inadequate and so you've introduced a new algorithm (say a newly designed
SHA-1024). But then, by assumption, you CAN'T do a useful rollover - i.e.
you can't usefully support both old resolvers (which don't understand new
fangled SHA-1024), and new resolvers (that do), because to do so you'd have
to publish NSEC3 records generated with both hash algorithms, and that
would mean that an attacker need only signal that it is an old-resolver
(however that's done), receive the old NSEC3 records, and attack those.

The only type of rollover that's useful in the "help all my hash functions
have become useless and I'm now worried about enumeration" scenario is to
cease publishing NSEC3 records with ANY broken hash function. If you're
going to publish NSEC3 records at all, that means you ONLY publish with
new and (by old resolvers) unsupported hash functions. In this instance, it
seems to me a better type of rollover would be much like that suggested
between NSEC and NSEC3: generate NSEC4 RR's to replace all NSEC RRs
and say "this just isn't going to work with NSEC3-only resolvers".

Let's just make sure on publication there are some ridiculously long
hash functions in there so this "never happens" (watch me eat my
words later).

Alex

---

From: Mark Andrews <[email-masked]>
Date: Fri, 04 Mar 2005 08:05:42 +1100

> 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"?
 
--
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

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

> 	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

---

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

> 	NSEC3 get so big that we say "this proposal is broken"?

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

> for which there is mandatory resolver support at release time. Are they?

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

-- Sam

---

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

Sam,

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

> resolver knobs to turn off an algorithm, which would then mean that

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