Subject: [p2p-sip] Review of draft-bryan-sipping-p2p-02

From: ekr at networkresonance.com (Eric Rescorla)
Date: Sun, 12 Mar 2006 18:35:38 -0800

OVERVIEW
This draft describes a protocol and architecture for doing
"P2P SIP". What this means in practice is that registration
information is stored in a Distributed Hash Table, thus
in principle removing the need for centralized servers.

GENERAL COMMENTS

Use of SIP for DHT Functions
----------------------------
The protocol used in this draft uses SIP both for the usual
signalling functions and for DHT maintenance. This strikes
me as a poor design decision.

1. It means that while you will be able to use generic 
   DHT algorithms you won't be able to use a generic
   DHT service. There's nothing particularly special
   that this application requires from a DHT, so it seems
   like a classic architectural mistake to tie yourself
   to something specific.

2. It obscures what should be a clean architectural separation
   between lookup services (what the DHT is being used for)
   and signalling services (what SIP is used for now). This
   made some sense in the previous draft which actually 
   punned on the SIP messages (using INVITE to find the
   UA for the desired contact) but now that you're using
   REGISTER in order to explicitly separate these functions,
   there's really no value added here.

3. It's really confusing.

Security
--------
There are a number of known security issues with DHTs. In
the specific design described here:

1. There is no authentication for names. The authors write:

   "The lack of central authority to resolve name disputes in the
   namespace means that at some level this problem is unsolved.  The
   approach has tended to be to allow everyone to call themselves Wally
   then let the certificates sort them out.  Users with names that are
   often "stolen" by others will learn that theirs is a poor choice of
   name because it is too valuable, and they will select a less valuable
   name.  Equilibrium will prevail, or chaos."

I don't really understand how this works. If the attacker can 
insert itself at a single replica, it can create a systematic
inconsistency about the appropriate holder of a name. This
makes it very easy to mount an attack on a specific target. 
This draft seems to assume that it's specific names that are
valuable, but in many cases it's not the name itself but rather
the identity of the name holder that's valuable, so changing
your name won't help, at last not for long.

2. You need some mechanism for resolving which replica is 
correct. Otherwise, any inconsistency leads to what...?

3. The protection against Sybil attacks depends entirely on the
attacker not having access to a large block of routable
addresses. This is questionable at best with Pv4 and silly with
v6. Designing a protocol which is only secure on v4 seems unwise.
The discussion of this in 10.11 is clearly inadequate and I
don't really see how it can work unless you assume specific
address boundaries. 

It's not clear to me what constraints lead to this design. 
The use cases documents talk a lot about not necessarily
having access to a global nameservice, but the kind of
non-real-time access required for secure naming (e.g.,
to get DNSSEC "certificates") is very different from requiring
a full-time service. Having any kind of distributed naming
service obviates many of the security problems listed above.

These aren't security problems that can be solved by gluing on 
some crypto at the end of the day. Security for DHTs is a
major unsolved research problem, so this is rather worrisome.

DETAILED COMMENTS
S 7.2.1:

   ipport         =  IPV4address ":" port

And v6?

S 10.4:

   A P2P environment can do little to protect against an individual node
   compromising the registrations it is responsible for.  Accordingly, a
   UA cannot trust a response from a single node, whether it indicates a
   successful search or an error.  In the absence of other methods of
   verifying the response (such as having a certificate of the user
   being searched for and a signed registration that can be verified
   with the certificate) a UA should search for the primary registration
   and at least one replica.  Because the locations the replicas are
   stored are unrelated to the location of the primary registration, a
   single attacker is unlikely to be able to compromise both entries.
   As the overlay gains more nodes and more replicas are searched for,
   the odds of a compromise are reduced.

It's not clear to me why you think your replica model has superior
security properties to the "next N successors" model that chord uses.
In both cases, the attacker needs to compromise (or compromise
routing to) N nodes. And since the preimages of the next N node IDs
are randomly distributed in IP space, I don't see an advantage
here. Please explain.

S 10.7:

   computer.  Cao et al, [9] describe an approach that separates the
   storage of resource location information from the actual storage of
   the offline research.

Is "research" really the word you want here?

---

From: dbarrett at quinthar.com (David Barrett)
Date: Sun, 12 Mar 2006 20:24:51 -0800

> -----Original Message-----
> From: Eric Rescorla
> Sent: Sunday, March 12, 2006 6:36 PM
> To: p2p-sip at cs.columbia.edu
> Subject: [p2p-sip] Review of draft-bryan-sipping-p2p-02
> 

It's my impression we're attempting to create P2P SIP, not a general DHT
service (though such a thing would be cool).  If we succeed in the former
while failing in the latter, that's still success in my eyes.

>    there's really no value added here.

While I can understand this perspective, I disagree.  I think a key failing
of SIP today is that it has far, far too many "clean architectural
separations" -- so much so that it's impossible to do anything without
reading hundreds of pages of highly redundant documentation.

I rather like the idea of just extending the base SIP protocol to include
the DHT, rather than rolling an entirely new protocol (*cough* ICE *cough*)
from scratch, using its own parsers, own state machines, own eccentricities,
etc.

> major unsolved research problem, so this is rather worrisome.

Given that a secure DHT is an unsolved problem, and given the IETF only
deals with solved problems, should we:

1) Standardize the best practices today, despite their insecurity.

	-- OR --

2) Wait until a secure DHT has been invented and reconvene.

I vote for #1.  I certainly don't vote for the unstated #3: "Simultaneously
invent and standardize a new variant of DHT that is secure (for some
definition of 'secure')."

-david

---

From: bryan at ethernot.org (David A. Bryan)
Date: Sun, 12 Mar 2006 23:54:04 -0500

I'll comment a bit about the SIP for DHTs question, REGISTER vs INVITE
and the replica key vs. successor choice. See inline...

> Use of SIP for DHT Functions

There are sort of 2 poins here. Using SIP for the DHT, and using
REGISTER to locate resources independently of INVITE.

So for point 1, there simply isn't, to my knowledge, a defined IETF
protocol for a DHT or to encode DHT messages. There is no specified
DHT protocol, so we either have to 1) use SIP or 2) invent a new
protocol or encoding. Now of course we can use all kinds of things --
HTTP to MSRP -- to push the info around, but why not SIP? The devices
I have in mind for this already speak SIP.

Now if there is a standard protocol for DHT messages (not a library
like OpenDHT, but a true protocol) I can definitely get on board with
that and think we could (and should) use that. As far as I know, there
isn't one approved by the IETF, and it seemed a task quite a bit
beyond my expertise (and the scope of a draft intended for SIPPING) to
try to suggest a generic DHT. So in summary, yep -- I agree if we had
a really good DHT protocol defined this should definitely use it, but
I don't know if one and I'm not sure designing it here is the right
approach. Any suggestions on this one?

In light of above perhaps the point would be moot if we had a DHT
protocol, but assuming for a moment that we don't have a generic DHT
protocol and we use SIP, and I'll talk about point 2.  Why the change
to REGISTER for search and not the original INVITE? We made that
change for two reasons. It actually seems more in line with the SIP
semantics. REGISTER is used in RFC 3261 to store and query
registrations, which is really what we are doing here, so we went to
using REGISTER for it. It also makes implementations much easier than
our previous INVITE doing DHT thing, since an unmodified UA on top of
a P2P lookup functions normally, and similarly, the only "odd"
messages -- that is, messages about DHTs -- floating around are
REGISTERS -- something a UA that is not P2P is likely to reject if it
receives, so interaction with non-P2P endpoints seems cleaner.

> 3. It's really confusing.

I suppose I can't really argue that ;) Suggestions to make it cleaner?
I sort of hoped that breaking it so things were done with register --
essentially only adding and querying registrations -- it would be
easier to understand.

> are randomly distributed in IP space, I don't see an advantage

So here you see one of our open problems, listed at the end. We are
using IP address for hash to get IDs, but we want to allow users to
have multiple nodes behind NATs, so we have suggested in the open
questions appending a port number to the hashed ID of the NAT. That
makes it difficult for an attacker in Sybil mode to simply generate
tons of IDs from one IP address simply by changing the port, as would
occur if we hashed ip:port. But, the downside is that it is trivial to
get sequential ones in such a case. Thus, we suggest the replica key.

Now as you point out, this is still fatally flawed in IPv6. This draft
tries to avoid any central servers at all, and I am increasingly
convinced we need centrally issued certs with corresponding centrally
issued IDs to really make this work, but in here I tried to avoid
those all together.

I fully agree that security is still a very hard problem, one that
must be solved, and one we haven't addressed very well yet.

David

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

---

From: ekr at networkresonance.com (Eric Rescorla)
Date: Sun, 12 Mar 2006 21:39:07 -0800

> approach. Any suggestions on this one?

It's not clear to me why inventing an entirely new protocol is better
than simply standardizing a specific instance of (and documenting)
the protocol in a pre-existing DHT, like, say Bamboo... 

> essentially only adding and querying registrations -- it would be

Yes. Describe the system as generic operations rather than as
SIP operations and then describe a binding to SIP.

> get sequential ones in such a case. Thus, we suggest the replica key.

OK. I think you need to be clearer that this is why you want to
use keyed replicas, since you only discuss this appending
idea in the Open Issues section rather than in 7.4.2 where
the algorithm includes only the hash of teh port.

> Now as you point out, this is still fatally flawed in IPv6.

It's not just IPv6. There are serious security problems even
if you ignore the Sybil attack, as indicated above in my review.

-Ekr

---

From: lowekamp at cs.wm.edu (Bruce Lowekamp)
Date: Mon, 13 Mar 2006 07:42:27 -0500

> SIP operations and then describe a binding to SIP.

As the current draft is organized (and as I'm sure you're aware),
section 6 gives an overview of the generic operations, 7  does
synteax, and 8 describes specific semantics.  I disbelieve that it
would be possible to write something that would be totally generic,
then list a short set of SIP bindings.  While I realize you want to
find a "generic" DHT, there are a few problems with that.  One is that
no "generic" "standard" DHT exists, another is that to define one, we
would have to define all kinds of protocol syntax, headers, routing,
redirecting, etc.  My belief is that if we tried to write something
more generic and then said "hey, look, here are some SIP bindings that
happen to fit our protocol," someone who is more familiar with another
protocol would look at it and say that we failed to describe something
necessary (that we simply assume SIP provides, like tags), or we make
an assumption that is unique to SIP.

Fortunately, the SIP devices we are targetting have a SIP stack that
already handles what we need, so we build on top of it.  If we try to
define something more generic, we get into extensive issues of what
the minimum requirements are to support it, etc.

Bruce

---

From: lowekamp at cs.wm.edu (Bruce Lowekamp)
Date: Mon, 13 Mar 2006 08:11:05 -0500

> your name won't help, at last not for long.

Hmmm.  This may not be clear from the draft (and actually, I think
parts of the draft may not have been updated to reflect this thought,
which is entirely our fault), but resource name -> location is not a
one-to-one mapping, it's one-to-many (as conventional SIP supports
multiple Contacts in a REGISTER).  As defined right now, some of those
contacts could be forged.  Without further extension, clearly our
protocol defines no way for a UA to identify the "correct" mappings. 
Thus, without some sort of certificates or central authority, there is
no way to verify that the contact registration you are currently
examining is legitimate.   I don't think I would want to deploy this
current protocol on a public network without certificates.

The goal is to leave it easy to insert forged registrations, but
impossible to make someone believe they are real.

> correct. Otherwise, any inconsistency leads to what...?

If you have the above certificates, it's easy to verify.

>    ipport         =  IPV4address ":" port

You're absolutely right that there is a problem with this level of
security in v6.  First, though, let's address v4.  We've discussed
previously that the port number should probably be removed from the
hashed portion when generating the NodeID.  Given that, I think we can
safely assume that no attacker will have access to a large block of
addresses.  At least, I suspect that anyone who would have that much
control would have to also be in control of routing (by virtue of
either being an ISP or controlling a VLAN we're on), and can attack
the protocol in any way they see fit.

I wrote that BNF and left out v6 quite deliberately, for a couple of reasons:

- security, as you mention, is an interesting issue.  It's a lot more
challenging there, and I'm not personally familiar enough with how
addresses are being assigned in actual ipv6 deployments to address all
of the issues.  I guess the first question is whether we can identify
the portion of the address that is ISP-assigned and the portion where
the host has control.
- transition is difficult for hybrid v4/v6 overlays.  A node needs to
have a single, static NodeID (at least for the duration of each
session associated with the overlay).  If some nodes are v4 and some
are v6, how do we determine the naming domain of the overlay.  I
considered adding another parameter to the node-id header to describe
this, but I'm not quite sure what it should be.  One possible solution
is to adopt a STUN-like system where each node at startup queries one
of a set of servers for that overlay to determine their proper
"mapped" address (except here mapping into the native space of the
overlay).  That would probably have to be signed by the generating
server to make verifying it cheap.

I think there is obviously a lot of work to be done here.

> are randomly distributed in IP space, I don't see an advantage

The act of inserting a compromised single node gives you an advantage
in compromising the routing to the (non-compromised) successor.  Even
though they're randomly distributed in IP space, they're neighbors in
the overlay, so most other nodes in the network will learn about the
successor through the compromised node.  Therefore, by storing
replicas at successors, the replica is dependent on the possibly
compromised node.  Getting to the successor, even if you know about
the compromised node, also requires some amount of linear search.  By
keying the replicas and distributing them throughout the DHT, there is
no dependency between the N nodes that would be required to compromise
the system, so an attacker would have to be able to compromise N
indepdendent nodes.  Also, searching for each replica is a logarithmic
operation.

> Is "research" really the word you want here?

ugh.  resources.  fixed in the source...

Thanks,
Bruce

---

From: ekr at networkresonance.com (Eric Rescorla)
Date: Mon, 13 Mar 2006 06:17:56 -0800

> an assumption that is unique to SIP.

I think we're talking about different things when we say "generic".
What I mean is to pick a DHT (e.g., Chord, Bamboo) and then 
describe your system in terms of the operations that that
DHT provides (INSERT, SUCCESSOR, etc.) Then when you've done that
describe how to implement those messages in SIP.

> the minimum requirements are to support it, etc.

Yes, I think that kind of architectural division and clarity is
a feature, not a bug.

-Ekr

---

From: ekr at networkresonance.com (Eric Rescorla)
Date: Mon, 13 Mar 2006 06:40:32 -0800

> the protocol in any way they see fit.

No, I don't think that's a safe conclusion. 

1. Many people do have very large blocks of addresses. Xerox,
   for instance, has a /8. 

2. A large NATed network will occupy a large number of
   nodes in the ring--and legitimately--they'll just be
   contiguous and densely packed in your design. [0]
   I haven't thought through the implications of that
   yet.

> the portion of the address that is ISP-assigned and the portion where

In theory yes, in practice, who knows. The addressing architecture
could change.

> indepdendent nodes.  Also, searching for each replica is a logarithmic

Sure, but it's an "all your eggs in one basket" versus "many baskets"
things. In the design you describe, the chance that at least one
replica will be compromised by a compromised node is much higher
than in the design where they're all in the successor set. So,
you may always get one valid replica, but there's also a high
chance of inconsistencies. Unless there's some resolution procedure...

In any case, if your goal is to assume that someone gets a
a large subset of the replica set and can then work things out
for themselves, there's quite a large literature about how to protect
routing in the case of some set of compromised nodes. Why do
you think that this is the optimal technique as opposed to
that described, by e.g., Wallach?

-Ekr

[0] Note that this design tends to defeat the goal of having
    even distribution throughout the DHT. Imagine the
    degenerate case of a ring consisting of 1000 machines
    behind a NAT and then a single machine outside the
    NAT. That other node is responsible for 99% of the
    address space. This is also a problem with having
    a partial

---

From: bryan at ethernot.org (David A. Bryan)
Date: Mon, 13 Mar 2006 09:57:15 -0500

> describe how to implement those messages in SIP.

I'm fine with that, but most (all) of the DHTs I have seen so far have
some drawbacks -- chord is recursive for example, so intermediate
nodes pass twice as many messages as the sender and receiver, which
looks like a bad design and possible DOS issue to me, but perhaps not.

I'm a bit concerned that finding a perfect DHT, and simply lifting it
and standardizing it will gain us little -- all the same effort but
not quite right. I *don't* think we want to design one from scratch,
but if we are going to express it in terms of their operations and
have no room to tweak it at all, it does limit us a bit. Reworking the
paper to seperate the sections is certainly a good idea, however.

--David

---

From: lowekamp at cs.wm.edu (Bruce Lowekamp)
Date: Mon, 13 Mar 2006 10:21:39 -0500

> 1. Many people do have very large blocks of addresses. Xerox,

I think the heart of this issue goes to use-cases and architectural
goals.   On the one hand, it's very nice to have a simple protocol
that a few people can set up and use to talk with each other.  On the
other hand, if we want to develop the One True (dht) Ring, then we
have to defend against someone who conceivably could allocate a node
anywhere in a /8 network.   I'd like to see a protocol where the first
case can be done easily, and security extensions are available so that
the One True Ring works reliably.  For most applications I want to
think about right now, my feeling is that a lightweight protocol that
is resistant to attacks that do not assume someone has ISP-level
control over their attacks is sufficient.  I would like to see/work to
develop a protocol that can also be extended to be secure in the face
of more determined attacks.  One interesting thing about attacking a
DHT is that the ease with which attacks can be done depends greatly on
the size of the network.  An open overlay with only a few nodes is
trivially easy to disrupt.  Right now seeding the Identifier is a way
for a private overlay to be protected, but I agree that small open
overlays are a challenge.

>    I haven't thought through the implications of that

Large NATed companies are an interesting challenge.  As you mention,
the issue is that they can disrupt the uniform spacing assumption that
a lot of the analysis makes.  There is some practical limit to the
number of nodes that can be behind one NAT address, but if the number
of nodes is large compared to the total number in the overlay (or,
more accurately, if the number of nodes/number of NATs grows large for
the entire network) there are some issues.  The one I see is that as
you lose uniform spacing of nodes, but presumably not uniform spacing
of resource-IDs, you are going to wind up with some nodes that are
responsible for storing a much larger than normal share of the
registrations because they just happen to be responsible for a large
gap in the ring.  So maybe some support for further distributing
registrations would be appropriate?  I haven't thought about it.  I'm
sure some people would say that as soon as v6 is adopted NATs will
disappear, but I think we need a better answer for this question.

> that described, by e.g., Wallach?

I make no claims of optimality!!!  I'm trying to work on feasibility.

If we use certified NodeIDs, as Wallach does, then I think this is
great.  However, while it helps the One True Ring, it doesn't help the
bunch of friends setting up a network (except for those of us who can
set up a CA for recreational purposes).

I think the one common theme here is the tradeoffs between a protocol
that can be used easily in a small, closed environment versus one that
could be used to run a large, globally-open communications system. 
You're entirely right that this draft doesn't address nearly all of
the security issues for doing the later.  I think the main question
here is whether the ideas in here are the type that can be used to
build a simple protocol that works in the first case, but can have
security extensions such that it also works in the second case.

Bruce

---

From: lowekamp at cs.wm.edu (Bruce Lowekamp)
Date: Mon, 13 Mar 2006 10:29:58 -0500

> describe how to implement those messages in SIP.

Ah, I see what you're saying now.  I think a lot of the feedback that
this draft received last time was that integrating a specific overlay
algorithm (iterative Chord) was likely a mistake, as hopefully there
would eventually be more widely accepted (hopefully IETF) overlay
algorithms.  For this version of the draft, I tried to extract the
Chord-specific portions of the discussion and put them into a separate
section to make it clear that the specific algorithm isn't inherent to
the concept.  But that does remove the "this is SUCCESSOR" part from
the earlier section.  I guess it would be clearer if earlier there was
a "these are the generic DHT operations that we will implement."   I
still don't want to define the whole thing in terms of Chord,
specifically.

Bruce