Subject: NSEC3 Issue 27: creating a flag octet.

From: David Blacka <[email-masked]>
Date: Wed, 11 Oct 2006 10:41:25 -0400

During the last NSEC3 workshop in September, the following suggestion
was made:

  Create a single octet in the wire format of both the NSEC3 and
  NSEC3PARAM records dedicated to flags.  Only one flag would be defined
  initially, the Opt-Out flag.

The purpose for this change would be twofold: 1) to allow a future
specification to define new flags for, e.g., dynamic update features. 2)
to make the wire format a bit friendlier to parse.

The main proposal for how to actually create this octet is to convert
the high order octet of the iterations field (which is where the Opt-Out
flag currently resides anyway) and dedicate it to flags, thus shortening
the iterations field.  The new maximum iterations value would be 65535.
 The Opt-Out flag would be defined to be the low-order bit in this field
(which would preserve the presentation format).

Obviously, there are possible variations to this proposal.  For
instance, we could keep the iterations field 3 octets long, add a flags
octet, and move the Opt-Out flag to it.  This would actually increase
the maximum number of expressible iterations to 16777215 (from 8388607).

Comments? Suggestions?

-- 
David Blacka                      <[email-masked]>
Sr. Engineer    VeriSign Infrastructure Product Engineering

--
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: Andrew Sullivan <[email-masked]>
Date: Wed, 11 Oct 2006 15:03:14 -0400

>   initially, the Opt-Out flag.

I think the flag octet is a good idea.

> the iterations field.  The new maximum iterations value would be 65535.

[. . .]

> the maximum number of expressible iterations to 16777215 (from 8388607).

I don't have an opinion on whether any of the alternative approaches
is a better idea.

A

-- 
Andrew Sullivan                         204-4141 Yonge Street
Afilias Canada                        Toronto, Ontario Canada
<[email-masked]>                              M2P 2A8
jabber: [email-masked]                 +1 416 646 3304 x4110

---

From: Mark Andrews <[email-masked]>
Date: Thu, 12 Oct 2006 10:48:29 +1000

> the maximum number of expressible iterations to 16777215 (from 8388607).

	As I pushed for this I'm in favour of it.
	2 octet iterations.
 
--
ISC Training!  October 16-20, 2006, in the San Francisco Bay Area,
covering topics from DNS to DHCP.  Email [email-masked].
-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: Wouter Wijngaards <[email-masked]>
Date: Thu, 12 Oct 2006 11:41:23 +0200

Hi,

As I said during the NSEC3 workshop, the stated need for iterations is
o To be able to differentiate the hashing (like the salt), to avoid
collisions.
o To make offline dictionary attacks much more expensive. It is
relatively easy to obtain a relatively large part of the NSEC3 chain (by
random probing for NXDOMAIN responses). The iterations field count will
prohibit quick dictionary attacks, it says in the draft.

The iterations field, as it would be used to defend against dictionary
attacks, thus has to increase as computing power increases. If computing
power doubles, iterations has to double to provide the same protection.
A 16 bit field can only double 16 times. Depending on how long you think
it takes for computing power to be 16x as powerful, at that time the
iterations field will be 'too small' to provide the same level of
defense against dictionary attacks. To allow for further growth, a
longer bitfield may be prudent.

A reply at the workshop was that a new hash algorithm, the '1024x SHA-1'
(or something along those lines) algorithm can be defined in that event,
that would provide an extension for the iterations field.

An alternative could be to use the iterations field as 15bit, and use
the high 16th bit to denote a 256x increase in value. This results in
the same range of values for iterations as before (albeit with less
granularity).

Note I am only discussing the 16-bit iterations. Flags field is fine.

I also have not met people that voiced a high iterations count was
important to their interests.

Best regards,
   Wouter

---

From: Roy Arends <[email-masked]>
Date: Thu, 12 Oct 2006 13:29:25 +0200

[email-masked] wrote on 10/12/2006 11:41:23 AM:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Hi,
> 

I propose we use the iterations value to represent a power of 2. Since we 
don't want X to be too high to be useless, we can use 5 bits to express X. 
The highest possible iterations value is now 2^31 which is already higher 
than the current max value (so I guess 4 bits will do as well). The rest 
of the bits can be used as flags. 

I can't really imagine a case where 2^X is too low, while 2^(X+1) is too 
high. 

This should be moore's law safe for another 45 years and uses a single 
octet for both flags and iterations.

Roy

---

From: David Blacka <[email-masked]>
Date: Thu, 12 Oct 2006 19:08:27 -0400

> longer bitfield may be prudent.

Fair enough.  However, we need to reconcile this with section 10.2.  The
table in 10.2 is based on the *ratio* of hash speed to verification
speed, and thus will remain fairly constant as general computing power
increases.

> that would provide an extension for the iterations field.

um, ick.  It would certainly work, though.

> important to their interests.

I'm of the opinion that if we feel we need to be able to express a
higher number of iterations, just allocate another octet to the field.
No big deal.  It is clear to me, however, that we don't really have any
clue as to what the maximum expressible iterations value should be.

---

From: "Hilarie Orman" <[email-masked]>
Date: Thu, 12 Oct 2006 17:49:10 -0600

The range of a hash function decreases with each iteration.  Iterating
1000's of times is probably a bad idea.

Hilarie

---

From: Alex Bligh <[email-masked]>
Date: Sun, 15 Oct 2006 16:38:42 +0100

> 1000's of times is probably a bad idea.

Mmm.... that's an interesting point, but I would have thought it could
only occur if you hash merely the output of the previous hash, and
would be avoided by hashing the output of the previous hash AND
the original input; I'll stick my neck out and claim that can't have
a range smaller than the range of a single iteration of the hash.

Alex

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Thu, 19 Oct 2006 09:23:09 +0200

>   initially, the Opt-Out flag.

I am not sure if this particular thread reached closure, if Roy's  
proposal doesn't get  pushback and Alex' head is not blown off I  
propose Roy's proposal to have the itterations fields reflect the  
power of two be reflected in the draft.

I would hope we can have a last-callable rev before deadline[*]?

--Olaf

[*] October 23, Monday - Internet Draft final submission cut-off by  
09:00 ET (13:00 UTC/GMT)

---

From: David Blacka <[email-masked]>
Date: Thu, 19 Oct 2006 10:14:15 -0400

Olaf M. Kolkman wrote:
> proposal doesn't get  pushback and Alex' head is not blown off I propose
> Roy's proposal to have the itterations fields reflect the power of two
> be reflected in the draft.

I, at least, am not a big fan of Roy's proposal and would prefer that it
not be the default position.  A more reasonable default position would
be the original proposal: one flag octet, 2 iterations octets. Or even
the alternate original proposal: one flag octet, 3 iterations octets.

I have several concerns with Roy's proposal:  1) it may not leave enough
unallocated flag bits for future use, 2) it is not at all granular
(i.e., only 32 different iteration values), and 3) it is still a format
that involves shifting and masking to decode, and for what? a savings of
2 octets?

I'm not saying that Roy's solution wouldn't work or even that it isn't
adequate (as I don't know), but one of the motivating factors for
creating the flag octet was to make the wire format simpler.

---

From: Wouter Wijngaards <[email-masked]>
Date: Fri, 20 Oct 2006 20:16:34 +0200

> creating the flag octet was to make the wire format simpler.

I think that Alex Bligh's statement about range is false. I also agree
with David that encoding can be simple for the nsec3 iterations. Not a
special case encoding.

So I am for a one byte flag octet, and two octets for iterations.

Advantage is that a max of 64k iterations is not a DoS in itself, where
millions of iterations are quite something else. The iterations provide
a nice bit of extra protection against offline dictionary attacks.
Realize that online dictionary attacks (just try names) are completely
possible, and much easier. Also two bytes makes a maximum iterations
count much less pressing and the section on that much less important,
which is good.

Best regards,
   Wouter

---

From: Alex Bligh <[email-masked]>
Date: Fri, 20 Oct 2006 20:17:13 +0100

Wouter,

--On 20 October 2006 20:16 +0200 Wouter Wijngaards <[email-masked]> 
wrote:

> I think that Alex Bligh's statement about range is false.

I'm assuming you mean my counter-assertion to Hilarie's proposition.

I'm quite prepared to be shown to be wrong, and I must admit the assertion
was only gut feeling, but let me explain where I was coming from.

Let's say you have a hash function H(x), and use H(x^y) to indicate
function H() being applied to both X and Y. I've used '^' to mean
an operator as an operator whose range is no smaller than the domain
of either of its parameters. XOR is a good indicator, but most (all?)
good hash functions can do this by simply operating over a larger
data set, you could view "^" simply as concatenation.

Also use |x| to mean the size of data set x, so |H(x)| is the
range of hash function X.

Hilarie asserted that repeatedly applying the same hash to a given
data set (i.e. feeding the output of H(x) back as the input, so
H(x), H(H(x)), H(H(H(x))) etc.) will inevitably reduce its range.
This is no doubt correct in practice, though I must admit I'm not
convinced we need worry about it. For instance, SHA-256 has a 256
bit range (i.e. the output is a 256 bit hash), and its input domain
is (effectively) infinite. However H(H(x)) clearly takes the hash
of a 256 bit range. We know from the three properties of hash
functions that a good one is collision resistant. This implies
(and I'll wave my hands here though the result is not controversial)
that there is a uniform distribution over the output range of
the hash function (else they would not be so effective in PRNGs).
That of course does not imply that it is possible to produce
EVERY result in its output range, but it implies holes are "rare";
else you aren't really getting a 256 bit hash, you are getting
a less than 256 bit hash. You can see this because if it is
the case that |H(H(x))| < |H(x)| then there must be an x, y
where x<>y (inside the 256 bit range) where H(x)=H(y); As we
good hashes are collision resistant, and need to be
particularly collision resistant with regard to small localised
changes. But there is an inevitability that at least for some H,
|H(x)| > |H(H(x))| > |H(H(H(x)))| etc, though (I suggest) probably
that much smaller. I would expect not more than (say) an tenth of
a bit.

My assertion is that to the extent that the above is a problem,
it can be fixed by mixing in the original hash value. So we have
  H(x)
  H(H(x)^x)
  H(H(H(x))^H(x)^x)
  H(H(H(H(x)))^H(H(x))^H(x)^x)
now in case that looks like a lot of memory storage, note that the term
which is mixed in is simply the previous result. Now we know from our
assumptions above that the ^ operator's range is no less than the the
larger of its input domains. This means (taking the last example) that the
range of the outer hash function is no less than the range of H(x). Hence
the range of the overall function has not been substantially reduced (i.e.
not reduced more than a single H(x) application)

I may well have got this wrong, and I recognize that the above is certainly
not a formal mathematical proof (I have a horrible cold, and namedroppers
is perhaps not the place anyway) but instinctively this seems right to
me.

Hilarie's original point was (I think) that applying a hash a zillion
times may do more harm than good, or at least produce unanticipated
results. I have to say I share some of Hilarie's concern there and
it's certainly a point worth thinking about. I /think/ my solution
/probably/ addresses it (as it makes the input to the 'next' hash
function have a far larger domain than simply taking the 256 bit output
range), but I'm not going to swear to it. I also think it's harmless
in that it can't make things worse (apart from use CPU cycles which
is I think the whole idea!).

I'd be interested in /why/ you think my assertion is wrong though,
Wouter - quite prepared to accept there may be an error in
my hand-waving^Wlogic.

Alex

---

From: Wouter Wijngaards <[email-masked]>
Date: Fri, 20 Oct 2006 22:44:35 +0200

Hi Alex,

You ask for a reply.

I'll be fairly brief on it. This is not a math mailing list ;)

> I'm assuming you mean my counter-assertion to Hilarie's proposition.

Yes

> was only gut feeling, but let me explain where I was coming from.

OK

> <snip> But there is an inevitability that at least for some H,

I agree up to here.

> not reduced more than a single H(x) application)

I agree and disagree. I agree the ^ operator does not reduce range. It
does not _increase_ the range either. It does alter every value to one
other value, which is nice. Taking a set of values and Xoring them (or
so) makes all values different, but you end up with the same number of
elements in your result set.

So I think the second H application loses another little bit of range.
Because the outputs from the previous H lost a bit, and ^ did not
increase (but only alter the values) the range, the second H operates on
a smaller set of possible inputs. And will have (a very small fraction)
of collisions, further reducing the number of outputs from it. And this
continues every iteration.

Until infinity, where only one value is left, which H changes into a new
value every iteration (like random()) and the iterations count
determines the outcome. Luckily, our bitranges are smaller than infinity.

You lost a bit, and if its 1/10bit for every iteration, then doing 32 or
64 iterations is very different from doing (say) 43 iterations (in that
you lose only 4 bits). Therefore more granularity in the iterations
would be nice. Not that important as you say, just give people the
opportunity to enter their own value (the operator can do the maths).
And it is nicer to encode (and thus implement).

If the operators think that particular numbers are good or bad, let them
do so.

> is perhaps not the place anyway) but instinctively this seems right to

:-)

> Wouter - quite prepared to accept there may be an error in

Because I think the second H application reduces range as well. Because
also the second H application has collisions. Though I could be wrong,
hash functions are weird things.

Even if I'm wrong, lets go for 1 octet flags, 2 octets iterations? It is
then less optimally encoded, but so very easy to use.

Best regards,
   Wouter

---

From: Roy Arends <[email-masked]>
Date: Mon, 23 Oct 2006 02:31:59 +0200

> > proposal doesn't get  pushback and Alex' head is not blown off I 
propose
> creating the flag octet was to make the wire format simpler.

I've updated the draft to reflect a 1 octet flags field and two octet 
iterations (where iterations is linear, as it was before, and not 
exponential). In essence, the change is that we go from 1 flag/23 bit 
iterations to 8 flags/16 bit iterations.

Roy

---

From: Alex Bligh <[email-masked]>
Date: Mon, 23 Oct 2006 19:21:38 +0100

Wouter,

>> larger of its input domains. This means (taking the last example) that
>> the range of the outer hash function is no less than the range of H(x).
>> Hence the range of the overall function has not been substantially
>> reduced (i.e. not reduced more than a single H(x) application)
>

Ah, but you end up with the same number of elements in your result
set as the LARGER of the two sets (x), not the smaller H(x). So the
input to the second H() is as large as (x), not merely as large
as H(x). This is the point where our logic diverges.

Anyway, it looks like we need not do this (even though it's harmless
in my opinion).

> then less optimally encoded, but so very easy to use.

Yes I think in practical terms this works, and Roy seems happy with it.

I'm wondering if we should have a security considerations entry which
says something to the following effect.

	It may be theoretically possible to select a hash algorithm which
	would be otherwise suitable for the purpose but whose range is
	reduced significantly by repeated iterative application. Such a
	hash function would be more likely to suffer collisions with a high
	number of iterations. No currently defined hash functions are known
	to the authors to degrade significantly with practical numbers of
	iterations. However, this consideration should be borne in mind
	when selecting new hash functions.

Alex