Subject: Re: [P2PSIP] comments on draft-ietf-p2psip-base-06 in WGLC

From: Cullen Jennings <[email-masked]>
Date: Wed, 17 Feb 2010 15:36:00 -0700

On Dec 10, 2009, at 2:30 PM, Roni Even wrote:

> 
> According to section 1 Reload is based on the concepts introduced in
> ietf-p2psip-concepts. The concept draft is currently expired and I noticed
> some contradictions between the two drafts. I think that the reload draft
> should progress with the concept draft.
> According to the concepts draft "The P2PSIP WG will not standardize how the
> peer-ID and the credentials are obtained, but merely standardize at least
> one acceptable format for each.  To ensure interoperability, it is expected
> that at least one of these formats will be specified as
> "mandatory-to-implement"."  According to RELOAD the node-id is mandated as a
> 128 bit value. According to the concept draft it can be as mandatory to
> implement format but others should be allowed.  I also think that section
> 5.4.1 allows for different node-id length (see "o  The length of the
> Resource-IDs and Node-IDs.  For DHTs, the hash algorithm to compute the hash
> of an identifier."

Sounds like the concepts draft needs some work. 

On the one topic of node-id being fixed length or variable length, we discussed the length of resource-id and and node-id a lot in the past. I have never seen someone raise the argument of we need Node-ID short than 128 bits. Several times people have raised the issue of we need node-id to be longer than 128. Specifically it is generally requested that they could be 160 bits because the output of SHA-1 is 160 bits. This request is generally fairly confused in that it's actually the Resource-Id they are confusing with the Node-ID. IN reload the resource-id are variable length and could be 160 bits. This was put in largely because Salman argued strongly that this would be needed to support unstructured overlays. The only time I can imagine that you could possible need more than 128 bits in a Node-ID is when you assign node-id randomly and you have more than approximately 2^64 nodes in a single DHT or you assign node-id non randomly and you have more than 2^128 nodes in a ring. I don't think anyone is arguing either of these are problems and I have not heard any other technical argument for making these larger. There are a bunch of advantages of fixed size but ignoring all that, it does not even seem like it's worth discussing if there is no technical reason to move to larger node-ids.

Good catch on section 5.4.1. Fixed that typo - thanks. 

Cullen Jennings
For corporate legal information go to:
http://www.cisco.com/web/about/doing_business/legal/cri/index.html

---

From: Salman Abdul Baset <[email-masked]>
Date: Wed, 17 Feb 2010 18:34:37 -0500 (EST)

I think it is fairly clear that mandatory-to-implement overlay algorithm 
must have a fixed length node-ID; otherwise, interoperability is a 
non-starter.

Unstructured overlays do not use a hash function to map resources to 
nodes, so node-ID length is a non-issue; it simply has to be unique.

DHTs, however, use a hash function to map resources to nodes, so node-ID 
length and hash function output length becomes an issue. The confusion 
lies in the ability to use a hash function that emits a greater than 
128-bit value, and then mapping it to the 128-bit node-ID by dropping the 
most significant bits. The argument is that by dropping the MSBs, we 
likely loose the randomness guarantees which are necessary from the load 
balancing perspective. Thus, we are restricted to using a 128-bit hash 
function for all DHTs (Kademlia, Pastry, CAN etc). Restricting the use of 
hash functions for all DHTs is not necessarily ideal from the viewpoint of 
future proofing.

-s

On Wed, 17 Feb 2010, Cullen Jennings wrote:

> On the one topic of node-id being fixed length or variable length, we discussed the length of resource-id and and node-id a lot in the past. I have never seen someone raise the argument of we need Node-ID short than 128 bits. Several times people have raised the issue of we need node-id to be longer than 128. Specifically it is generally requested that they could be 160 bits because the output of SHA-1 is 160 bits. This request is generally fairly confused in that it's actually the Resource-Id they are confusing with the Node-ID. IN reload the resource-id are variable length and could be 160 bits. This was put in largely because Salman argued strongly that this would be needed to support unstructured overlays. The only time I can imagine that you could possible need more than 128 bits in a Node-ID is when you assign node-id randomly and you have more than approximately 2^64 nodes in a single DHT or you assign node-id non randomly and you have more than 2^128 nodes in a rin!
 g.
> I don't think anyone is arguing either of these are problems and I have not heard any other technical argument for making these larger. There are a bunch of advantages of fixed size but ignoring all that, it does not even seem like it's worth discussing if there is no technical reason to move to larger node-ids.
>
> _______________________________________________
> P2PSIP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/p2psip
>
>

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 17 Feb 2010 15:55:34 -0800

On Wed, Feb 17, 2010 at 3:34 PM, Salman Abdul Baset <[email-masked]> wrote:
> length and hash function output length becomes an issue. The confusion lies
> in the ability to use a hash function that emits a greater than 128-bit
> value, and then mapping it to the 128-bit node-ID by dropping the most
> significant bits. The argument is that by dropping the MSBs, we likely loose
> the randomness guarantees which are necessary from the load balancing
> perspective. Thus, we are restricted to using a 128-bit hash function for
> all DHTs (Kademlia, Pastry, CAN etc). Restricting the use of hash functions
> for all DHTs is not necessarily ideal from the viewpoint of future proofing.

Huh?

Any reasonable hash function is just as random in the low-order bits (what you
get if you drop the MSBs) as in the high order bits. This is certainly
a necessary
condition for any cryptographic hash function to deliver the full
security of its
output length.

-Ekr

---

From: Salman Abdul Baset <[email-masked]>
Date: Wed, 17 Feb 2010 19:38:40 -0500 (EST)

> condition for any cryptographic hash function to deliver the full

Unless I misread your earlier post on this list, there may be a 
possibility of a collision attack. Although, as you pointed, it is a 
preimage resistance issue.

Rather than arguing about hash function properties, I think the most 
future-proof solution is:

-fix a hash function for the mandatory-to-implement DHT, which is already 
there in the draft.
-allow a large size hash function and corresponding length node-IDs to be 
used per overlay, by specifying them in the configuration file.

-s

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 17 Feb 2010 16:46:43 -0800

On Wed, Feb 17, 2010 at 4:38 PM, Salman  Abdul Baset
<[email-masked]> wrote:

> Unless I misread your earlier post on this list, there may be a possibility
> of a collision attack. Although, as you pointed, it is a preimage resistance
> issue.

Again, huh?

The collision resistance of a b bit hash function is approximately 2^{b/2}.
The collision resistance of the first (or last, or any) b' bits of a b bit
hash function is approximately 2^{b'/2}.

> used per overlay, by specifying them in the configuration file.

I don't understand why this is superior. Again, what's wrong with just having
fixed size node-IDs which are created by truncating a hash?

-Ekr

---

From: Salman Abdul Baset <[email-masked]>
Date: Wed, 17 Feb 2010 20:23:29 -0500 (EST)

> fixed size node-IDs which are created by truncating a hash?

Flexibility and future-proofing.

If we want to keep the 128-bit node-IDs, then we need to clarify in the 
draft that they can also be obtained by trucating a >128-bit hash function 
without worrying about collisions. For example, this will be helpful for 
someone who may notice the node-ID length difference between the original 
Chord paper and RELOAD Chord. We also need to clearly state that such a 
truncation is applicable for any DHT (Kademlia, Pastry, CAN) and not just 
Chord.

-s

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 17 Feb 2010 17:29:21 -0800

On Wed, Feb 17, 2010 at 5:23 PM, Salman  Abdul Baset
<[email-masked]> wrote:
>>> possibility

I have no problem with adding this clarification.

-Ekr

---

From: "David A. Bryan" <[email-masked]>
Date: Wed, 17 Feb 2010 23:20:01 -0500

So I'm replying to the parent, rather than the follow on conversation,
but I think that is appropriate, since the initial argument Cullen
makes confuses me a bit. (Ekr's point about the lower 128 being plenty
random is true, but sort of irrelevant to the debate about why we are
limiting this in the first place)

I guess my question is why do we have the 128-bit limit at all? The
argument here is "no one has argued for a reason to be >128", but this
seems like a cart before the horse argument. Sort of smacks of the
"640K should be enough for anyone" decision of yore... The better
question is why did the editors make limit it to 128? In general,
RELOAD (and certainly earlier drafts from others) had no such
restriction, and have erred in most other places on being flexible.
I've never heard a compelling argument in favor of it. I personally
don't recall the WG ever debating, and certainly not supporting such a
decision. Personally, I see only possible down sides here, and no
really good upside to limiting it. If one wants to impose a
restriction, the impetus is on them to justify that restriction. (I'm
fine with the default algorithm having a fixed value of course, but
not the protocol. That seems wrong to me)

In the absence of a *very* strong technical argument why truncation
and forcing us to a fixed length is a good idea, we should err on the
side of flexibility. If nothing else, reuse of code (i.e., allowing
reuse of code for DHTs that have already been implemented and tested
using >128 bit (or really, less, if they so desire), seems like a
logical reason. If we allow various sizes (and this 160 bit IDs), I
can grab off the shelf Chord algorithms. Similarly for various lengths
for other DHTs.

I can't see a single good technical reason *to* limit it. I personally
think variable length IDs (again, at the protocol level -- not at the
mandatory to implement DHT level) are a far better decision for
flexibility, code reuse, and general future-proofing. Again, since as
far as I recall, the WG never made a decision to impose this limit,
what are the advantages? I might be missing something, but I think the
right behavior is unless we have overwhelming reasons to limit it, we
don't. Can those supporting 128 bit IDs share what (they think) the
advantages are, and maybe we can then debate this point a bit?

Thanks,

David (as individual)

On Wed, Feb 17, 2010 at 5:36 PM, Cullen Jennings <[email-masked]> wrote:
> On the one topic of node-id being fixed length or variable length, we discussed the length of resource-id and and node-id a lot in the past. I have never seen someone raise the argument of we need Node-ID short than 128 bits. Several times people have raised the issue of we need node-id to be longer than 128. Specifically it is generally requested that they could be 160 bits because the output of SHA-1 is 160 bits. This request is generally fairly confused in that it's actually the Resource-Id they are confusing with the Node-ID. IN reload the resource-id are variable length and could be 160 bits. This was put in largely because Salman argued strongly that this would be needed to support unstructured overlays. The only time I can imagine that you could possible need more than 128 bits in a Node-ID is when you assign node-id randomly and you have more than approximately 2^64 nodes in a single DHT or you assign node-id non randomly and you have more than 2^128 nodes in a ring.