Subject: [p2p-sip] update to draft-bryan-sipping-p2p

From: lowekamp at cs.wm.edu (Bruce Lowekamp)
Date: Sun, 5 Mar 2006 22:48:44 -0500

We have submitted an updated version of the draft "A P2P Approach to
SIP Registration and Resource Location", draft-bryan-sipping-p2p-02.
Until it is available in the archive, you can find it here:

http://www.p2psip.org/drafts/draft-bryan-sipping-p2p-02.html

or here

http://www.p2psip.org/drafts/draft-bryan-sipping-p2p-02.txt

depending on the format you like.

David Bryan
Bruce Lowekamp
Cullen Jennings

---

From: enrico.marocco at telecomitalia.it (Enrico Marocco)
Date: Tue, 07 Mar 2006 10:25:17 +0100

I'm happy to see that the work is going on! Anyways, after reading the
new version of the draft, I have some doubts:

+ conflicts on Node-ID: as noticed in "Open Issues", conflicts on node
   ids are likely to happen.  Unfortunatly, they can be due not only to
   natted addresses; indeed nothing prevents a well balanced hash
   function to return the same value for two totally different
   "hostports".  Just off the top of my head, I would generate node ids
   as hash("sip:<addr>:<port>;idtag=<rand>") and would define/pick a
   response code for conflict reporting.  In this way, a node would be
   able to generate unique identifiers;

+ redundancy: if I understood well, the proposed mechanism is quite
   different from the chord's one.  Rather than storing copies of each
   record in responsible node's successors, it stores replica in random
   positions.  Thus, the number of messages required for "put" (always)
   and "get" (upon failure) operations doubles or trebles depending on
   the redundancy level.  I think that the (weak) security benefits that
   this solution provides, could also be achieved with a significant
   reduction in the number of messages if the registering node directly
   asks responsible's successors to store replica.

How do you think to deal with them?

Enrico

Bruce Lowekamp wrote:
> _______________________________________________
> p2p-sip mailing list
> p2p-sip at cs.columbia.edu
> https://lists.cs.columbia.edu/cucslists/listinfo/p2p-sip

---

From: lowekamp at cs.wm.edu (Bruce Lowekamp)
Date: Tue, 7 Mar 2006 09:05:48 -0500

Enrico,

Thanks for your comments.  Both of these points raise the important
issue of how to balance a desire for efficiency with securing the DHT
from attacks.   We have tried to push the protocol toward something
that we think can run on open, public networks that may be subject to
attacks.  Of course, it's still not completely secure, but I think
it's making progress.  Also, it may be possible that some people will
want to set up a DHT that is more efficient rather than secure from
attackers (and, if using HMAC NodeIDs, may simply wish to rely on the
shared secret for security).   In that case, other algorithms might be
more appropriate.

Specific comments inline:

>    able to generate unique identifiers;

The problem with allowing a node to generate a unique identifier is
that it opens the DHT up to various attacks, such as the Sybill
attack.  Essentially, if you can generate your own NodeID, you can
insert yourself anywhere (and in as many places) in the ring as you
would like.  Even worse, you can let the ring operate perfectly
normally, but carefully insert yourself to be the primary location for
the ID of a particular user who you wish to attack.  I actually am
leaning toward the need to remove the port number from the hashed
portion altogether, as it gives a naive attacker tens of thousands of
possible IDs to use.  Obviously we would have to deal with collisions
on IDs there.

>    asks responsible's successors to store replica.

This is the most obvious tradeoff of performance vs security.  Again,
consider an attempt to attack the ID of a particular user by acquiring
a node with a NodeID that makes you responsible for storing that
user's registration.  Now you receive a query and respond to it with
your corrupt pointer (assuming a reasonable security system,
presumably you can only attack with DOS rather than impersonation). 
If the successors are storing the replicas, then you can also prevent
the querying node from checking a replica by using false entries in
your finger table.  However, if the replicas are stored at other
locations around the ring, you don't have nearly as much power to
influence those entries or affect how the querying node will locate
them.

You make an excellent point that this scheme has more overhead than
simply using successors.  Our goal is that if we make it difficult
(but not impossible) to choose a NodeID for an attack, and make it
difficult (but not impossible) to misdirect a querying node looking
for a replica, then the combined effect will make it essentially
impossible to use certain kinds of attacks against the network.

Bruce

---

From: bryan at ethernot.org (David A. Bryan)
Date: Tue, 7 Mar 2006 10:16:02 -0500

One other option that has been discussed is to use as Node ID the
result of a hash with some number of digits for the port, un-hashed
appended to the has result. This has the result of placing multiple
nodes behind a NAT close to each other in the overlay, which obviously
has implications, but allows users to have multiple nodes behind a
NAT, while preventing the Sybil attack Bruce mentioned. The positive
is that the nodes that are likely to be most affected by attacks are
yoour neighbors, which in this case are (likely) to be your own node
if you are creating multiple identities, but the down side is that you
can thus create long sequences of successors, which also may be a
problem (depends on how your DHT is architected)

I don't think I have the original Sybil paper on p2psip.org, but I'll
put it up in the next week or so for those that haven't read it:

www.cs.rice.edu/Conferences/IPTPS02/101.pdf

--David

---

From: enrico.marocco at telecomitalia.it (Enrico Marocco)
Date: Tue, 07 Mar 2006 17:37:38 +0100

> attack.

Partially agreed.  This way you are allowing the user to register an
indefinite number of nodes from the same machine; the draft limits that
number to 65534.  Probably, for addressing security threats like the
Sybill attack, other measures are needed.

>          Essentially, if you can generate your own NodeID, you can
> the ID of a particular user who you wish to attack.

This is not trivial: it implies breaking of sha-1 (which is known to
require ~2**69 operations). If we think that sha-1 is not secure for our
purpose, the right thing would be switching to sha-2.

>                                                                Again,

If you think a node is corrupted (maliciously or not) you can reach both
its predecessor and its successors starting from an arbitrary point of
the network without asking it. Moreover, browsing the finger table and
the successor list provided by the node queried just before the bad one,
you can reach them with very few messages.

The most dangerous case would be when malicious nodes could occupy
contiguous positions; luckily, this could be avoided using a strong hash
function.

Enrico

---

From: enrico.marocco at telecomitalia.it (Enrico Marocco)
Date: Tue, 07 Mar 2006 17:54:16 +0100

> problem (depends on how your DHT is architected)

This doesn't prevents from conflicts on node ids.

Just off the top of my head, if the problem is avoiding too much uses of 
the same address, why not just storing the information in the dht 
itself? Up on a node join, the accepting node could insert/update a pair 
like <"ip address", counter> and could allow the registration only if 
counter is below a given threshold.

Enrico

---

From: lowekamp at cs.wm.edu (Bruce Lowekamp)
Date: Wed, 8 Mar 2006 02:00:03 -0500

> purpose, the right thing would be switching to sha-2.

Well, no, you don't need to break sha-1.  All you need to do is
calculate an address that hashes to an ID in between the ID of the
user you wish to DOS and the ID of the current node.  Assuming uniform
distribution of hashes (on average, true with sha1), your chances of
being able to do this scale with the number of nodes in the network. 
For small networks (a few hundred), you can trivially insert yourself
into almost any point in the network by using different port numbers. 
Obviously as the network grows, this type of attack (against a
predetermined user) becomes harder.

> you can reach them with very few messages.

True, but is this solution more efficient than simply storing a
replica at a random location?  At a random location, you still benefit
from log(n) search, whereas if you start searching linearly.  I'm
really not sure of the answer here.

Also, how do you know which node is bad?  An advantage of the random
replica is that you are unlikely to need to worry about correlation
between your two queries.  If you use successive replicas, you now
need to worry about which node is corrupt, which makes the problem
much harder.

> contiguous positions; luckily, this could be avoided using a strong hash

As above, this depends on the number of nodes in the network (if your
port number is included in the hash).

Bruce

---

From: enrico.marocco at telecomitalia.it (Enrico Marocco)
Date: Wed, 08 Mar 2006 10:11:56 +0100

> predetermined user) becomes harder.

Right. But a mechanism for aviding id spoofing (or whatever we call it)
could still be easily deployed:
+ define the node URI as: "sip:<h>@<addr>[:<port>];idtag=<cnt>", where:
   - h = hash("sip:<addr>;idtag=<cnt>") is the hash value;
+ when a new register is received for a node URL with idtag > 1, perform
   a lookup of the same URL but with a decremented idtag. If it fails,
   kick out the joining node.

> really not sure of the answer here.

But this solution introduces overhead only when a inconsistent state is
detected. Obviously, as you noticed, it relyes on the difficulty of
spoofing ids and, in particular, on the difficulty of placing chains of
malicious nodes.

> need to worry about which node is corrupt, which makes the problem

In each scenarios, when you are looking for successive replicas, you are 
supposing the first query was performed on a bad node; I don't think 
anyone wants to seek replicas whenever a call cannot be established.

> port number is included in the hash).

You're right.
Again, I think that we can find a good and still simple solution for 
resolving conflicts, avoiding spoofing and avoiding multiple identities 
relying on the dht itself.

Enrico