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: [email-masked]
Date: Mon, 24 May 2004 16:38:09 +0200 (CEST)

On Mon, 24 May 2004, Marcos Sanz/Denic wrote:

> > 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.
>
> If we forget hex (with a byte-utilization rate of 50%) and do kind of
> 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: Marcos Sanz/Denic <[email-masked]>
Date: Mon, 24 May 2004 17:07:07 +0200

Simon,

> Also, I don't know whether the attacks that are enabled if you even
> 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: Marcos Sanz/Denic <[email-masked]>
Date: Mon, 24 May 2004 17:25:23 +0200

Jim,

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

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

Peter Koch wrote:
> 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.

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: "Hallam-Baker, Phillip" <[email-masked]>
Date: Mon, 24 May 2004 10:39:00 -0700

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

There are two issues, strength of algorithm and the risk of attack.

It may well be better to use SHA-256 and truncate to some length than to use
SHA-1. From a purely cryptographic point of view SHA-256 is a much better
scheme, it is also likely to be supported better in future hardware
acceleration etc.

Rather than use hex I would use BASE32 encoding, several people have
proposed schemes that use ten numbers and 22 characters as a case-proof
symbol set. This means that you get five bits per character rather than
four. So a 160 bit digest is only 32 characters.

How long should the digest be? Since we are using it to mask a label 
that is itself bound in size we don't need very many bits at all. 

In fact the size of the range of the hash need only be the square of
the size of the domain.

I don't think it very likely that we will have individual zones with more
than 2^64 different labels. So the probability of collision will be
negligible if have a hash with 2^128 bits.

If label size is an issue we could argue over likely domain sizes etc.

		Phill

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Mon, 24 May 2004 10:48:58 -0700

>From a pure algorithm perspective the concern here is that MD4 is
broken, MD5 is deeply compromised and both MD5 and SHA-1 are both
incremental advances on MD4.

I have no reason to doubt the security of SHA-1 at this time,
but we are past the point where it is appropriate to use it
in a NEW specification environment. The whole point of AES was
to address these issues industry wide.

The length of the algorithm output is not an issue, both SHA-1 and 
SHA-256 provide more than sufficient bits. We should probably 
truncate in either case.