Subject: nsec2 large label pain

From: [email-masked]
Date: Mon, 24 May 2004 14:12:02 +0200 (CEST)

I'd like to address an issue due to large labels in NSEC2.

SHA1 output is 160 bits. Represented in hexadecimal thats 40 bytes for the
owner name and the next domain name as well. The signature of the NSEC2
has the same owner name. Thats 120 Bytes extra per NSEC2 compared to nsec
(minus 3 times the original label length). This has negative implications
for packet-size, zone-size and truncation. I'd like to see that reflected
in the draft.

Roy

--
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: Simon Josefsson <[email-masked]>
Date: Mon, 24 May 2004 15:05:26 +0200

> for packet-size, zone-size and truncation. I'd like to see that reflected

Can't you use standard DNS name compression techniques on the SIG
owner name?  If so, it is more like 80 bytes, minus the original label
length, extra.  If this size increase is a major obstacle for people,
it may be possible to explore hash truncation.

Regards,
Simon

---

From: Marcos Sanz/Denic <[email-masked]>
Date: Mon, 24 May 2004 15:23:58 +0200

> it may be possible to explore hash truncation.

Rather to explore an alternative representation to hexadecimal?

Regards,
Marcos

---

From: [email-masked]
Date: Mon, 24 May 2004 16:09:36 +0200 (CEST)

On Mon, 24 May 2004, Simon Josefsson wrote:

> owner name?

Absolutely. You can.

> If so, it is more like 80 bytes, minus the original label
> length, extra.

<nit> plus the compression-pointer.

> If this size increase is a major obstacle for people,

There are several ways to 'fix this', including a new label type (type
HASH or something evil) if you like.

There are other obstacles as well. Current label length restricts the
message digest size (if represented in hex) to 248 bits. This excludes
functions like sha-256/384/512.

Roy

---

From: Marcos Sanz/Denic <[email-masked]>
Date: Mon, 24 May 2004 16:28:48 +0200

> functions like sha-256/384/512.

If we forget hex (with a byte-utilization rate of 50%) and do kind of 
base64 (75%), then sha-256 can still be used.

Regards,
Marcos

---

From: Peter Koch <[email-masked]>
Date: Mon, 24 May 2004 16:33:49 +0200

> HASH or something evil) if you like.

this rings the complexity bell, but see below[*].

> message digest size (if represented in hex) to 248 bits. This excludes
252?

> functions like sha-256/384/512.

First of all, is it really necessary to have so "wide" fingerprints or isn't
the goal better achieved otherwise? Even with a more efficient encoding
(now's time again for the 8 bit debate ...) you'd end up with no more than
504 bits in a label. Practical considerations might lead to a 5/8 encoding,
using e.g. A-Z0-5, large enough for 256 bit. But then, why should the hash
be restricted to one label only, other than that longer hashes restrict
the overall available length of the zone name?

[*] The "new" label type could be bitstring (RFC 2673) or something similar.
This would solve one anomaly of the current proposal: owner names of NSEC2
RRs are names that exist in the zone, but their non-existence is proven
by those NSEC2 RRS, too (not necessarily by the one they own, but by others).
If bitstring labels were used this would open up a "shadow namespace", so
hash owners wouldn't conflict with what they're trying to prove.
For similar reasons the NO draft moved the hashes to a subdomain, IIRC.

-Peter

PS: The draft doesn't yet specify exactly how the hash is calculated and
    how to apply the seed. I'd guess that the seed - if any - needs to be
    used twice, like in HMAC.

---

From: [email-masked]
Date: Mon, 24 May 2004 16:38:09 +0200 (CEST)

> base64 (75%), then sha-256 can still be used.

Base64 encoding is not possible for a label due to canonicalizing. The
best one can do is base32 encoding (62.5%).

Roy

---

From: Marcos Sanz/Denic <[email-masked]>
Date: Mon, 24 May 2004 16:43:40 +0200

> best one can do is base32 encoding (62.5%).

SHA-256 still works, though. Do we need something bigger?

Regards,
Marcos

---

From: Ben Laurie <[email-masked]>
Date: Mon, 24 May 2004 16:43:47 +0100

> for packet-size, zone-size and truncation. I'd like to see that reflected

I did put a note about it. Do you have a particular suggestion for what 
we should say where? Or shall I invent some words myself?

Can we do base 64 to reduce size? I realise this (theoretically at 
least) introduces character set issues. If we respect those, can we do 
base 37 - this reduces 160 bits to 31 bytes (i.e. an overhead of 93 
bytes minus three times the original label length)? Is that worth the 
ugliness?

Incidentally, someone said yesterday that the average label length in 
some TLD (.com?) was 15 characters, IIRC, so this would give an average 
overhead of 48 bytes. Given that DNSSEC (according to Olaf) introduces a 
350 byte overhead already, that doesn't sound _too_ bad to me.

Cheers,

Ben.

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 24 May 2004 16:54:30 +0200

> SHA-256 still works, though. Do we need something bigger?

Considering that the strongest signature algorithm specified uses
SHA-1 today, I suspect it is not an immediate concern, at least.

Also, I don't know whether the attacks that are enabled if you even
truncate the hash values are serious.  That is, answer this question:
if you truncate the hash to, say, 64 bits, what can an attacker do?
Truncate to 32 bits?  It seems non-obvious that this can be abused in
any useful way, but I may be missing something.

Regards,
Simon

---

From: Marcos Sanz/Denic <[email-masked]>
Date: Mon, 24 May 2004 17:07:07 +0200

Simon,

> truncate the hash values are serious.

The security properties of hashes are known to me. I am sorry to say I 
cannot make the same statement about *truncated* hashes.

Before taking such a step I would like to see some competent 
crypto-advisor giving his "urbi et orbi"..

Best,
Marcos

---

From: Jim Reid <[email-masked]>
Date: Mon, 24 May 2004 16:11:26 +0100

>>>>> "Marcos" == Marcos Sanz/Denic <[email-masked]> writes:

    >> Base64 encoding is not possible for a label due to
    >> canonicalizing. The best one can do is base32 encoding (62.5%).

    Marcos> SHA-256 still works, though. Do we need something bigger?

Yes. Perhaps not today, but one day we might. It would be prudent to
plan for that now. Or else we'll have a flag day at some point in the
future when a longer hash string becomes essential. Remember it wasn't
long ago that MD5 was the flavour-of-the-month hash function. Who's to
say if SHA-N won't suffer the same fate in a couple of years?

---

From: Marcos Sanz/Denic <[email-masked]>
Date: Mon, 24 May 2004 17:25:23 +0200

Jim,

> say if SHA-N won't suffer the same fate in a couple of years?

In the worst case, SHA would be flawed and its output size would play no 
role...
NSEC2 already offers provisioning for alternative hash types.

Best,
Marcos

---

From: Ben Laurie <[email-masked]>
Date: Mon, 24 May 2004 17:59:07 +0100

>     used twice, like in HMAC.

Indeed the draft does need to nail down the exact calculation - I was 
intending to do that in the next iteration.

HMAC uses the seed twice to avoid extension attacks, which are not 
relevant to the problem in hand. I'd suggest not using HMACs simply on 
the grounds that its another thing for implementers to worry about (and 
there is an overhead in terms of memory consumption for HMAC 
calculation), but I don't feel all that strongly about it. That said, I 
was planning to use the salt in each iteration of the hash.

What I had in mind was this:

Let H(x) be the hash of x and || denote concatenation. Define:

H_0(salt,x)=H(x || salt)

H_k(salt,x)=H(H_{k-1}(salt,x) || salt)

Then the calculated hash is H_{iterations}(salt,name). BTW, I append the 
salt for technical correctness (it prevents precalculation when the salt 
is at least as long as the hash function block size).

Cheers,

Ben.

---

From: Ben Laurie <[email-masked]>
Date: Mon, 24 May 2004 18:14:40 +0100

> crypto-advisor giving his "urbi et orbi"..

Although some crypto advisors want to get wobbly about truncated hashes, 
this one says that if they didn't work well, they'd constitute an attack 
on the untruncated hash.

My concern about truncation would be more mundane: reduced utility for 
the purpose in hand, since collisions would prevent proving nonexistence.

That said, we could add to our risk by including a bitlength as another 
option in NSECINFO (or NSEC2 if we move options there).

Cheers,

Ben.

---

From: Ben Laurie <[email-masked]>
Date: Mon, 24 May 2004 18:07:39 +0100

> SHA-256 still works, though. Do we need something bigger?

SHA-1 means that for a 1 in 2 chance of a single collision, you need 
around 10^24 names. I imagine that makes it sufficient for now?

I could add SHA-256 as an option. Fine by me.