Subject: [P2PSIP] Chosen-location attacks, HIP-HOP and central authorities

From: "Marcus Leech" <[email-masked]>
Date: Tue, 13 Nov 2007 09:36:24 -0500

In a recent thread, Ekr writes:

> Note that this can't be fixed purely by rate limiting at some central 
> authority (though puzzles can help) because the computation is 
> performed completely offline. The fix is to have the central authority

> dispense peer-ids, but then this breaks the binding between public 
> keys and identities which is one of the major attractions of HIP.
>
> -Ekr

I guess I don't understand why a central authority helps, except to act
as a rate-limiter.

If our "attacker" has access to a large pool of source addresses, and
assuming models where "joining" the
  mesh is an anonymous operation, I can't see how you can protect
against a barrage of requests (perhaps spread over
  longer time periods) arriving from a vast flotilla of source
addresses, where the idea is that *one* of those requests will
  yield a topologically "useful" PeerID.

If the notion is that *only* authenticated nodes may "join" an overlay,
then I can see rate-limiting based on the
  identity of the requestors, but in the anonymous case, I can't see how
you can make this work.

_______________________________________________
P2PSIP mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/p2psip

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 13 Nov 2007 06:46:04 -0800

At Tue, 13 Nov 2007 09:36:24 -0500,
>   identity of the requestors, but in the anonymous case, I can't see how

1. You assign peer-ids at a central location so that each attacker oracle
   query is quite expensive.
2. You either require authentication or some kind of proof of work to
   get a peer-id, so this slows down chosen location attacks even
   more.
-Ekr

---

From: "Marcus Leech" <[email-masked]>
Date: Tue, 13 Nov 2007 10:10:27 -0500

1. You assign peer-ids at a central location so that each attacker
oracle
   query is quite expensive.
2. You either require authentication or some kind of proof of work to
   get a peer-id, so this slows down chosen location attacks even
   more.
-Ekr

It would be useful to consider the anonymous case, with proofs-of-work
required
  (presumably asymmetric in favour of the central authority), what
constitutes
  an "adequate" delay mechanism for reasonable projections of overlay
size.

Pulling numbers out of my butt here, if the network size is O(10**5),
and the
  work function typically takes a second or two to compute, the
attacking
  flotilla needs to be able to expend O(10**5) CPU-seconds to surf the
PeerID
  space to find one that's "useful".

It seems to me that for small overlays, the central authority model
(assuming
  anonymity) can't protect against oracle-type attacks unless the work
factor
  of the proof function gets suitably large, correct?

Let's pretend that the current Internet is O(2**32) in size.  What is a
reasonable
  number for the ratio between total number of nodes, and those that are
peers in
  an overlay.  Is 1:1 a reasonable number?  Is 10:1 a reasonable number?
Is 100:1
  a reasonable number?  I just don't know, and it would certainly be
useful to have
  reasonable estimates to drive the analysis of whether the central
authority model
  can be made to work for suitably-robust definitions of "work".

But perhaps I just have a bullet lodged in my brain, and I'm not
thinking things out
  clearly.

---

From: Henning Schulzrinne <[email-masked]>
Date: Tue, 13 Nov 2007 10:27:54 -0500

I find the notion of proof of work somewhat dubious for this  
application. With today's massive botnets, you'd have to impose proof- 
of-work on the order of days on a fast processor to make any  
difference. If a single sybil is fatal, even with the assumptions of  
roughly 10^5 attempts at guessing, it takes a single node a bit more  
than a day to subvert the DHT. With the typical 100,000 node botnet,  
it's one second until one of them hits pay dirt.

Henning

---

From: Enrico Marocco <[email-masked]>
Date: Wed, 14 Nov 2007 10:48:58 +0100

Probably a bit out of scope for this thread, I'd like to note that there
are other ways of discouraging peers from trying to get arbitrary
positions in the overlay.  A notable example is Skype's approach, where
ordinary nodes are promoted to super nodes only once in a while by some
obscure element higher in the hierarchy.  A similar but much less
notable approach <self-promotion>is what we propose in
draft-marocco-p2psip-xpp-pcan, where a client becomes peer only when
invited by a peer already in the overlay, and its location (or peerID or
whatever) is assigned by the inviting peer </self-promotion>.

We would really appreciate comments about this as well.

Enrico

---

From: Rubén Cuevas Rumín <[email-masked]>
Date: Wed, 14 Nov 2007 12:30:36 +0100

Dear Henning and all,

have deeply investigated the problem presented in this thread ( Even I 
have some numbers about it).

If we consider proof-of-work as crypto-puzzles (or something similar) 
the attack can be performed in a relative short period of time. In 
addition, if you use crypto-puzzles you must take into consideration 
that not all the DHT nodes have the same CPU capacity, and then you 
should adjust the complexity of the crypto-puzzle in order to allow 
those less powerful nodes to solve it in a bounded time.

What I consider the best option for a proof-of-work is to solicit the 
user to introduce a CAPTCHA before getting the Peer-ID. The advantages are:
   - Require the human intervention, and then the attack cannot be 
automated.
   - The time spent to get one id is reduced for honest users (just few 
seconds) but increase linearly with the number of Peer-IDs solicited, 
making the attack costly in terms of time (for instance in the case of 
105 nodes in the DHT).
   - This is a proof-of-work which every user independently on the CPU 
capacity of his computer can perform. Then, the entry barriers to the 
system are really low.

I hope this could help in somehow and I would like your opinion.

All the best,
                    Rubén.

Henning Schulzrinne escribió:
> application. With today's massive botnets, you'd have to impose 
> proof-of-work on the order of days on a fast processor to make any 

-- 
Rubén Cuevas Rumín
Universidad Carlos III de Madrid
Departamento Ingeniería Telemática
Avenida de la Universidad, 30
28911-Leganés (Madrid). España
email: [email-masked]
Tlf: +34 91-6248859
Fax: +34 91-6248749
Web: http://www.it.uc3m.es/~rcuevas

---

From: Rubén Cuevas Rumín <[email-masked]>
Date: Wed, 14 Nov 2007 12:33:13 +0100

Dear Enrico and all,

In the scheme you proposed I find that if a malicious client (i.e. an 
attacker) gets to be promoted to peer he can invite other malicious 
clients controlled by him to be peers as well.  Even more, if we 
consider that the malicious peer is the one which assigns the Peer-ID 
(i.e. the position in the DHT) of the new promoted client it would be 
easier that an attacker can allocate several peers in the desired 
positions to perform an attack.

What do you think?

All the best,
                       Rubén.

Enrico Marocco escribió:
>> ------------------------------------------------------------------------
>>

---

From: Enrico Marocco <[email-masked]>
Date: Wed, 14 Nov 2007 13:50:42 +0100

Rubén Cuevas Rumín wrote:
> clients controlled by him to be peers as well.

Which is still better than letting any malicious peer happily join the
overlay.  The problem here is identifying malicious nodes before and/or
after they join the overlay: how they join, i.e. actively or passively,
doesn't really matter.

>                                                 Even more, if we

Well, this is avoided allowing the inviting peer to assign entering
nodes only IDs it is authoritative for; this way, any new peer becomes
authoritative on a sub-interval of its parent's hash space and cannot
make more damage than its parent could before its entrance.

-- 
Ciao,
Enrico

---

From: Enrico Marocco <[email-masked]>
Date: Wed, 14 Nov 2007 14:05:24 +0100

>   - Require the human intervention, and then the attack cannot be

Let me be the first one arguing that CAPTCHAs may be automatically
solved without the (conscious) human intervention:
http://blog.trendmicro.com/captcha-wish-your-girlfriend-was-hot-like-me/

-- 
Ciao,
Enrico

---

From: Spencer Dawkins <[email-masked]>
Date: Wed, 14 Nov 2007 08:03:23 -0600

Hi, Ruben,

Ignoring Enrico's point about solving CAPTCHAs without human intervention...

I (guess I) understand why web servers use CAPTCHAs, because the intention 
is that they are accepting input from humans, so "proving" that you are a 
human makes sense.

Is it your intention that P2PSIP would not be used for embedded systems 
(with no human to intervene)?

Thanks,

Spencer

----- Original Message ----- 
From: "Rubén Cuevas Rumín" <[email-masked]>

---

From: Rubén Cuevas Rumín <[email-masked]>
Date: Wed, 14 Nov 2007 15:26:28 +0100

Spencer Dawkins escribió:
> I (guess I) understand why web servers use CAPTCHAs, because the 
> intention is that they are accepting input from humans, so "proving" 
> that you are a human makes sense.
>
> Is it your intention that P2PSIP would not be used for embedded 
> systems (with no human to intervene)?
>
Hi Spencer,

To the best of my knowledge  all the SIP-compliant devices must be 
configured by human intervention (e.g, the URI, the SIP-Registar...). 
Then, adding the CAPTCHAs does not introduce any new barrier.

Maybe I am wrong. Which kind of embedded systems are you thinking about?

Thanks,
                  Rubén.

> Thanks,
>
> Spencer
>
> ----- Original Message ----- From: "Rubén Cuevas Rumín" 
> <[email-masked]>
>

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Wed, 14 Nov 2007 08:32:20 -0600

>   - Require the human intervention, and then the attack cannot be 

CAPTCHAs have been proven to be broken with results hovering in
the >= 80% accuracy range.  See [1,2].

[1] Luis von Ahn, Manuel Blum, and John Langford, "Telling Computers
  and Humans Apart," Comm. of ACM, 47(2), pp. 57-60, 2004.
[2] Luis von Ahn, Manuel Blum, Nicholas Hopper, and John Langford,
  "CAPTCHA: Using Hard AI Problems for Security," Proceedings of
  2003 Eurocrypt.

Both of these papers are available online through a search on Citeseer
or Google.

Regards,

- vijay
-- 
Vijay K. Gurbani, Bell Laboratories, Alcatel-Lucent
2701 Lucent Lane, Rm. 9F-546, Lisle, Illinois 60532 (USA)
Email: vkg@{alcatel-lucent.com,bell-labs.com,acm.org}
WWW:   http://www.alcatel-lucent.com/bell-labs

---

From: Rubén Cuevas Rumín <[email-masked]>
Date: Wed, 14 Nov 2007 15:38:46 +0100

> make more damage than its parent could before its entrance.
In this case you need to be able to demonstrate that your Peer-ID has 
been assigned by the /authoritative Peer/ of the interval which is not 
trivial since we should consider the implicit dynamism on the p2p 
systems. Then, if the authoritative Peer on the interval (the one who 
assigned my Peer-ID) leaves the DHT it becomes difficult to demonstrate 
that my Peer-ID is a valid one. In additon, when a Peer leaves the 
network and have assigned an interval, we should provide some policy to 
reassign the  authority (the /authoritative Peer/) on the intervals.

I think it would be easier the following: When a peer firstly join the 
network,it ask for a Peer-ID to a central entity which returns a 
certificate including the Peer-ID. This Peer-ID will be a long term id, 
then in following join procedures the peer does not need to contact to 
the central entity.
In addition, in order to obtain the Peer-ID the user should solve a 
captcha (we are discussing about this in parallel). This only prevents 
the automatization of obtaining a high number of Peer-IDs.
In addition, the central entity can deploy some type of Access Control 
Policy. For instance, it can check if multiples Peer-IDs are being 
solicited from the same IP or from the same IP prefix and then detect 
attacks (e.g if the normal solicitation rate is 100 Peer-IDs per hour 
and at some point  the central entity receives 1000 Peer-IDs 
solicitations in an hour from a given IP prefix it can be intended as an 
attack).

Thanks,
                         Rubén.

---

From: "David A. Bryan" <[email-masked]>
Date: Wed, 14 Nov 2007 09:45:18 -0500

The technique described below, (with a central CA issuing IDs, but
minus the captcha), is (more or less) what most of the currently
proposed protocols have been advocating for a couple of years now.

What does the captcha gain? If you are going to rate limit at the
server anyway. I can see the captcha being one possible idea, but
others (micropayment, proof of identity with an uncharged credit card
etc.) have been proposed as well, and I personally think that type of
thing is a provisioning/admin decision that is out of scope of the WG.

BTW I don't really like the captcha idea for a number of reasons. A
simple IP phone may or may not have a screen, and if it does, it might
be alphanumeric, so not sure this could be universally deployed in any
case.

David (as individual)

-- 
David A. Bryan
[email-masked]
+1.757.565.0101 x101
+1.757.565.0088 (fax)
www.SIPeerior.com

---

From: Enrico Marocco <[email-masked]>
Date: Wed, 14 Nov 2007 15:56:55 +0100

> reassign the  authority (the /authoritative Peer/) on the intervals.

The point is not the Peer-ID itself, it is telling to all the peers
involved in the join procedure -- e.g. successors and predecessors in
Chord, neighbors in CAN -- that the new node has been invited by a
trusted peer.  This is something which may easily be done by the
inviting peer (which, btw, in most of DHT algorithms would have to
notify other peers about the entrance anyway).

-- 
Ciao,
Enrico

---

From: Rubén Cuevas Rumín <[email-masked]>
Date: Wed, 14 Nov 2007 16:06:29 +0100

Dear Vijay,

I have read [1] and they say that one type of CAPTCHA (reading distorted 
images) has been  broken, but not all types of CAPTCHAs.

All the best,
                         Rubén.

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Wed, 14 Nov 2007 09:31:55 -0600

> be alphanumeric, so not sure this could be universally deployed in any

In published literature and prevailing systems, there is a notion
of audio CAPTCHAs [1,2].  For example, there is a Google plug-in that
will speak out the visual CAPTCHA for the sight-impaired users; all
they then have to do is to type the numbers they hear.

In multi-media communication systems (closer to the P2PSIP domain),
audio CAPTCHAs can be used by having the caller hear an announcement
and repeat a sequence of digits and words before the called party is
alerted.

But even this has drawbacks.  For one, there has been some work [3]
that allows a minimally trained automaton to respond to the voice
CAPTCHA with about 33% accuracy.  Second, at least for SPIT
prevention, audio CAPTCHAs can be mitigated by outsourcing
session establishment to low-cost countries where a human army can
speak out the audio CAPTCHAs.

In the context of the P2PSIP discussion of providing "proof-of-work",
audio CAPTCHAs may be a better alternative to traditional text/image
based CAPTCHAs.  That is until the automaton-based approach in [3]
can be trained really well.  Furthermore, if we require an audio
CAPTCHA to be a pre-requisite for getting a Peer-ID, that would
mean that all peers must possess fairly sophisticated capabilities
for acting on the results of the audio CAPTCHA tests.

[1] Jonathan Holman, Jonathan Lazar, Jinjuan Heidi Feng, and John
  D'Arcy, "Developing usable CAPTCHAs for blind users," Proceedings
  of the 9th international ACM SIGACCESS conference on Computers and
  accessibility Assets, pp245-246, October 2007.
[2] Tsz-Yan Chan, "Using a text-to-speech synthesizer to generate a
  reverse Turing Test," Proceedings of the 15th IEEE International
  Conference on Tools with Artificial Intelligence (ICTAI’03), pp.
  226-332, November 2003.
[3] "Defeating audio (voice) CAPTCHAs," http://vorm.net/captchas/

- vijay

---

From: Rubén Cuevas Rumín <[email-masked]>
Date: Wed, 14 Nov 2007 16:39:15 +0100

David A. Bryan escribió:
> server anyway
My point is not to establish a rate limit (this could suppose to 
increase the entry barriers to the system) , but limit the rate to the 
prefix  from  the attack is being performed. 
> . I can see the captcha being one possible idea, but
I agee that the CAPTCHA is not the unique solution and probably we can 
find a much better one. However, in front of the two solutions you 
presented CAPTCHAs have some advantages: It is /free/ ( vs. 
micropayment) and it is anonymous (vs. uncharged credit card).
> be alphanumeric, so not sure this could be universally deployed in any
Well, there are several types of CAPTCHAs which can be addapted to the 
device features. For instance, in the case of the phone we can use sound 
based CAPTCHAs. This is something like you listen to something and you 
have to type it, then the CA can check if you typed the correct word.

Thanks,
                 Rubén.

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Wed, 14 Nov 2007 09:44:17 -0600

> images) has been  broken, but not all types of CAPTCHAs.

Ruben: Right; see my follow-up email on audio CAPTCHAs.  Regarding
reading distorted images, that is the technique used most widely
on the web even today.

I remember reading about another type of CAPTCHA that involves
a group of pictures -- three out of four pictures would be
rodents and the fourth one would be a lion, say.  You would be
asked to pick out which image does not mesh with other ones.
Such tests are relatively easy for humans to do (we can tell
a lion apart from a mouse), but it is hard to provide that much
context to a computer.

- vijay

---

From: Rubén Cuevas Rumín <[email-masked]>
Date: Wed, 14 Nov 2007 16:54:59 +0100

> notify other peers about the entrance anyway).
I get you. This is a more philosophical discussion. Is it possible to 
identify malicious nodes?

 From my point of view this is a really hard task. First of all, we 
should consider that it is not possible to  distiguish between malicious 
nodes and misbehaving nodes (for instance, due to a software failure).
If we focusin the DHTs, for instance: the Responsible Node of a record 
(this is the one with the closest Peer-ID) decides not  answering (or 
give wrong responses)  to the  queries  soliciting this  record.  You 
should demonstrate that the malicious node is storing the record and it 
is the only one which actually knows and can confirm this. It is really 
hard to identify this type of attack. Even more, this node can decide to 
answer correctly some times making harder to be detected.

For the best of my knowledge, the identification of malicious nodes in 
DHT networks is still an open issue.

What do you think?

Cheers.
                   Rubén.

---

From: Henning Schulzrinne <[email-masked]>
Date: Wed, 14 Nov 2007 11:58:31 -0500

> a lion apart from a mouse), but it is hard to provide that much

It's subject to the same outsourcing attack as all other CAPTCHAs.  
Plus, this type of image picking game is not too helpful, since it  
would have a 25% chance of being solvable by random guess.

As noted by others, I'm confused as to why this is of concern to this  
working group. It seems highly unlikely that the working group will  
recommend a particular Turing test, audio, video or otherwise.

Henning

---

From: Dean Willis <[email-masked]>
Date: Wed, 14 Nov 2007 11:09:11 -0600

On Nov 14, 2007, at 5:30 AM, Rubén Cuevas Rumín wrote:

>
> What I consider the best option for a proof-of-work is to solicit  
> the user to introduce a CAPTCHA before getting the Peer-ID. The  
> advantages are:
>   - The time spent to get one id is reduced for honest users (just  
> few seconds) but increase linearly with the number of Peer-IDs  
> solicited, making the attack costly in terms of time (for instance  
> in the case of 105 nodes in the DHT).
>   - This is a proof-of-work which every user independently on the  
> CPU capacity of his computer can perform. Then, the entry barriers  
> to the system are really low.
>

I think that, in the US, the agency overseeing the laws dealing with  
person with disabilities (especially the visually impaired)  would  
not like that very much.

There's also an IPR consideration. CAPTCHA is, IIRC, patented.

--
Dean

---

From: Rubén Cuevas Rumín <[email-masked]>
Date: Wed, 14 Nov 2007 18:39:59 +0100

> recommend a particular Turing test, audio, video or otherwise.
 From my point of view we are discussing how to provide a secure 
assignment of Peer-IDs which I think is something basic for P2PSIP. 
Since with the existing solutions it is impossible to avoid that one 
malicious user obtains as many Peer-IDs as he desires, then we have to 
make the obtention of Peer-IDs costly in somehow (time, CPU...).
I agree the WG (probably) will not recomend the proof-of-work to be 
used. However, we must know if the different proof-of-work defined so 
far are enough to guarantee a high security level or not.
If we find that this is true, then P2PSIP could adopt the scheme with a 
central entity providing the Peer-IDs. However, if we cannot assure a 
given security level, we should move to another Peer-ID assignment scheme.

As basis to evaluate the difficulty of this attack in DHTs (if someone 
is interested) you can have a look on [1] which analyzes mathematically 
this problem.

Thanks,
Rubén.

[1] R.Cuevas, A.Cuevas, M.Urueña, A.Banchs, C.Guerrero. "Evaluation of 
the p2p Structured Systems’ Resistance against the Starvation Attack". 
Tech.Report. Department of Telematic Engineering, Universidad Carlos III 
de Madrid.
Available at: 
http://www.it.uc3m.es/~rcuevas/tech_report/tech_report_starvation_attack.pdf

---

From: "David A. Bryan" <[email-masked]>
Date: Wed, 14 Nov 2007 14:17:20 -0500

I think this is a bit of a red herring.

It is true that if we just have a central authority that gives anyone
who asks as many certificates and peer ids as they wish, we have the
problem you mention.

One could similarly argue that in any account-based architecture where
an admin gives you an ID is flawed, since you can ask for as many as
you want and get them all. The point is that that central authority
has an interest in preventing these sorts of things and can (and does)
use policies to enforce them. A similar mechanism can be used here.

The charter is rather clear that we aren't going to develop
decentralized identity schemes, and we will use a central authority,
with a mechanism to ensure identities, and that defining that
mechanism is outside of the scope of the WG. This decision was made to
ensure that this group would be able to produce a protocol draft in a
reasonable length of time and didn't get into a rat hole of a
"research problem" on making fully distributed identity or
no-intervention identity system. (charter text is here:
http://www.ietf.org/html.charters/p2psip-charter.html)

I think this discussion is interesting, but we are explicitly
discussing the mechanism to assure identities here, something that is
out of our scope. The person running that central authority can use
any mechanism they want. We can discuss this sort of thing of course,
but as I see it, this isn't something that will be addressed within
the context of the WG, as it falls outside our charter.

David

On Nov 14, 2007 12:39 PM, Rubén Cuevas Rumín <[email-masked]> wrote:
> the p2p Structured Systems' Resistance against the Starvation Attack".

-- 
David A. Bryan
[email-masked]
+1.757.565.0101 x101
+1.757.565.0088 (fax)
www.SIPeerior.com

---

From: Philip Matthews <[email-masked]>
Date: Wed, 14 Nov 2007 16:10:30 -0500

I disagree. I think this discussion is very relevant.

First of all, I will note that the charter says:
    The initial work will assume the existence of some enrollment  
process
    that provides a unique user name, credentials, and an initial set of
    bootstrap nodes if that is required by the protocols. Developing a
    non-centralized enrollment process is not in scope.
There is nothing in there that talks about Peer IDs.

Then, in Chicago, EKR commented that the system used by HIP-HOP
to assign Peer IDs was not secure. Furthermore, he claims that the
scheme used by ASP (a central enrollment server) IS secure.
As I recall, there was quite a bit of discussion about this at the  
Monday night
meeting.

The counter-argument that Marcus is making is that the central  
enrollment server
as envisioned by ASP is NOT secure, and thus HIP-HOP is no worse that  
ASP.
Moreover, I would claim that the scheme used by HIP-HOP is more  
practical,
because it does not depend on a centralized enrollment server.

So how do we resolve this debate?
Are you saying that the debate is irrelevant and out-of-scope?

- Philip

---

From: Henning Schulzrinne <[email-masked]>
Date: Wed, 14 Nov 2007 16:35:34 -0500

The problem is that we don't define the assumptions. At one extreme,  
we have "fully anonymous node about which nothing is known and which  
has a billion brethren that look exactly like it". You can also have  
"Node that has obtained a Top Secret security clearance and has made a  
$1M bond deposit." Depending on the assumptions, the problem is either  
unsolvable or fairly easy. However, there isn't a single set of  
assumptions that we can all agree on, as they restrict the  
applicability in various ways. Thus, I think this discussion isn't  
likely to get very far until we have at least a set of assumptions  
that are usefully measurable and we have agreed on.

As a random example, if you can limit the set of participating nodes  
to "good" nodes by the effort of some certification node, possibly in  
some time in the reasonably distant past, you can then likely use a  
distributed mechanism at some other point in time. Thus, you now have  
both a centralized and a distributed mechanisms in one system.

If somebody can solve the problem by making absolutely no assumptions,  
I suspect that person should be writing a paper for a major conference  
pronto, not hang out in this mailing list.

Henning

On Nov 14, 2007, at 4:10 PM, Philip Matthews wrote:

> as envisioned by ASP is NOT secure, and thus HIP-HOP is no worse  
> that ASP.

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 14 Nov 2007 13:52:12 -0800

At Wed, 14 Nov 2007 16:10:30 -0500,
> as envisioned by ASP is NOT secure, and thus HIP-HOP is no worse that  

I don't think the term "secure" is very useful here. Let's rather
talk about how hard it is to mount various attacks.

In a centralized system, where the peer-ids are centrally assigned, in
order to get a peer-id in a portion of the overlay 1/N the size of the
overlay requires N queries to the central enrollment server. In a
decentralized system where you get to generate your own peer-ids--even
if you have no control over the peer-ids you generate other than being
able to generate a new random one, it requires one query. That's just
the basic math of the situation.

The implication here is that:
1. Decentralized systems and centralized systems with no rate
   limiting are vulnerable to both chosen peer ID and Sybil attacks,
   but decentralized systems are moreso.

2. Centralized systems with even moderate rate limiting are
   vulnerable to Sybil but not chosen peer ID attacks.

3. Centralized systems with good rate limiting are not vulnerable
   to either attack.
   
-Ekr

---

From: Philip Matthews <[email-masked]>
Date: Thu, 15 Nov 2007 15:00:11 -0500

> 3. Centralized systems with good rate limiting are not vulnerable

What about a system where a node:
* Creates a public/private key pair and generates an associated  
identifier, say a HIT,
* Makes a one-time call to a central system to get a certificate for  
that HIT
   providing some sort of proof of identity,
* Uses the certificate to join various overlays,
* Uses the HIT as its peer id in each overlay.

In this way, the node demonstrates that it has this identity (the  
HIT) which it
is consistently using as its peer id in all overlays that it joins.
However, we don't need a central enrollment server for each overlay.
In fact, the central server doesn't even need to be accessible
when the node joins the overlay.

- Philip

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 15 Nov 2007 12:10:11 -0800

At Thu, 15 Nov 2007 15:00:11 -0500,
> when the node joins the overlay.

Unfortunately, this doesn't change the parameters of the attack: i.e.,
you can still offline compute any HIT you want and then make a
one-time call to the central system.

In order to stop that, you need the peer-id to be unpredictable
from the perspective of the attacker. That turns it into an n-query
problem.

-Ekr

---

From: Philip Matthews <[email-masked]>
Date: Thu, 15 Nov 2007 15:41:09 -0500

> from the perspective of the attacker. That turns it into an n-query

The point is that the node has _one_ HIT which it uses in multiple  
overlays.
So this HIT might be in a sensitive position for some time in one  
overlay,
but in a non-sensitive position in the next overlay (or later on in  
the first).

Say "A" is the attacker. He has his HIT (also "A"), and can join  
various overlays.
He can join with B and C, or he can join with C,D,E and F.
But in both overlays he has to use his HIT "A". (Enforced by the  
certificate,
which has the HIT inside it).

- Philip

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 15 Nov 2007 13:08:37 -0800

At Thu, 15 Nov 2007 15:41:09 -0500,
> which has the HIT inside it).

Yes, I understand this point, but it doesn't really help, since
there's nothing stopping the node from getting multiple HITs,
one for each overlay. It still only requires one query per
overlay the node wishes to attack.

-Ekr

---

From: "Palanisamy, Kandasamy (Kandasamy)" <[email-masked]>
Date: Thu, 15 Nov 2007 15:07:01 -0700

The central enrollment server that verifies the identity of the node and
issues the certificate should prevent it from getting multiple HITs
(should that
be the policy).

If chain of trust of the joiner's certificate is verified to the root
certificate of the central enrollment at the time of joining, it would
make sure
the joiner is authentic.

Kand

-----Original Message-----
From: Eric Rescorla [mailto:[email-masked]] 
Sent: Thursday, November 15, 2007 1:09 PM
To: Philip Matthews
Cc: P2PSIP Mailing List
Subject: Re: [P2PSIP] Chosen-location attacks,HIP-HOP and central
authorities

Philip Matthews wrote:
> >> * Makes a one-time call to a central system to get a certificate 
> >> for that HIT
> >> In fact, the central server doesn't even need to be accessible when

> >> the node joins the overlay.
> >
> > Unfortunately, this doesn't change the parameters of the attack: 
> > i.e., you can still offline compute any HIT you want and then make a

> > In order to stop that, you need the peer-id to be unpredictable from

> > the perspective of the attacker. That turns it into an n-query 
> > problem.
> 
> overlay, but in a non-sensitive position in the next overlay (or later

> on in the first).
> certificate, which has the HIT inside it).

Yes, I understand this point, but it doesn't really help, since there's
nothing stopping the node from getting multiple HITs, one for each
overlay. It still only requires one query per overlay the node wishes to
attack.

-Ekr

---

From: RUBEN CUEVAS RUMIN <[email-masked]>
Date: Thu, 15 Nov 2007 23:08:56 +0100

> overlay the node wishes to attack.

I agree. The use of HITs (or other autogenerated Peer-ID) makes the 
attack easier (than in the case of central entity) since the attacker 
can calculate the HITs offline (which is something really fast with the 
current CPU capacity) until get the neccesary HIT to perform the 
attack. Then, it asks for the certificate and the attack is succesfull.

On the other hand, in the central solution the attacker needs to obtain 
multiples (lets say N) Peer-IDs from the CA until get the valid one. If 
the process to obtain the Peer-ID takes s second. The attacker needs 
N*s seconds to perform the attack. In the case of the HITs, the 
calculation of N pairs Public/Private case would be a matter of one 
second or few seconds and just one s second to obtain the certificate 
from the CA.

I can just identify one scheme where the autogenerated Peer-IDs can be 
useful. This is if the Peer-ID is related to some verifiable and unique 
external data as could be the user-name. I mean, if you have a 
user-name and your Peer-ID is the hash(user-name) you cannot obtain 
more Peer-IDs with this user-name, since you cannot match a different 
user name with this Peer-ID and any other node can discover you if try 
to use a different Peer-ID than the one assigned to your user-name. 
However this have many implications depending on the proposed 
scenarios. If user-names are obtained after paying some amount of 
money, then this scheme could be considered. But if the user-name can 
be freely obtained, then we are in the same case as before.

Rubén.

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Fri, 16 Nov 2007 09:44:53 -0800

> From: Palanisamy, Kandasamy (Kandasamy) [mailto:[email-masked]] 
> Sent: Thursday, November 15, 2007 2:07 PM
> To: P2PSIP Mailing List
> Subject: RE: [P2PSIP] Chosen-location attacks,HIP-HOP and 
> central authorities
> 

Another possibility would be to allow, during registration with the
central authority, the option of the central authority assigning a
different Peer-ID than the HIT.  It could then bind this alternate
Peer-ID to the HIT in the certificate, providing proof-of-ownership for
the joiner.  In the deployments where central authority doesn't care or
there is no central authority, the HIT could be used as the Peer-ID.

Tom