Transcript S12

peer-to-peer system
1
client-server
server
client
client
client/server
client/server
server
client
client
client
client
client
client
2
peer-to-peer
 A peer’s resources are similar to the
resources of the other participants.
peer
peer
peer
peer
peer
peer
peer
peer
3
Looking up Data in P2P Systems
 Centralized directory model
 Advantages : efficiency, low bandwidth usage and low
storage requirement on the peers.
 Drawbacks : single point of failure and limited
scalability.
44
 Flooded requests model
 Advantages : no single point of failure, peers only need to know
their immediate neighbours
 Drawbacks : inefficient in searching, generating a lot of traffic,
limited scalability
5
 Document routing model
 Advantages of the model : the searching is efficient, each node
only needs to maintain a limited amount of information for
routing queries and it provides a certain degree of fault
tolerance.
 Drawback of the model is that it is more complicated than the
other two models.
6
Problems
 How to name nodes and objects
 How to find other nodes efficiently
 How to split data between nodes
 How to prevent data from being lost
7
Content-Addressable Network (CAN)
 The system is made up
of a d-dimensional
Cartesian coordinate
space
 Space divided between
nodes
 All nodes cover the
entire space
n1
8
 When a node, say N2,
joins the system, N2 is
first mapped to a point,
say R, in the system.
 When N2 reaches
point R, the owner of
the zone within which
R lies splits the zone
into half and assigns
one half to node N.
n2
n1
9
n2
n1
n3
10
n2
n4
n1
n3
11
o
In
a
d-dimensional
coordinate space, two
nodes are neighbours if
their coordinate spans
overlap
along
d-1
dimensions and abut
along one dimension
n2
n4
n1
n3
12
 a node is responsible
for the items in its
zone
i1
i2
n2
n4
i3
n1
n3
i4
13
 User at n1 wants to
look up for file i2
 A node routes a
message towards its
destination by simple
greedy forwarding to
the neighbor with
coordinates closest to
the destination
coordinates.
i1
i2
n2
n4
i3
n1
n3
i4
14
node departure
i1
i2
i1
n2
i2
n2
n4
i3
i3
n1
n1
n3
n3
i4
i4
15
node failure
 A node sends periodic
update messages to
each of its neighbors
giving its zone
coordinates and a list
of its neighbors and
their zone coordinates.
i1
i2
n2
n4
i3
n1
n3
i4
16
 The prolonged absence of
an update message from a
neighbor signals its failure.
 Once a node has decided
that its neighbor has died
it initiates the takeover
mechanism by contacting all
the neighbours of the
failed node.
i1
i2
n2
n4
i3
n1
n3
i4
17
coping with failure
n1
i2
n2
i4
n4
i3
n3
i3
n3
i1
n1
i2
i4
n4
n2
i1
18
Chord
 Each
data item is
represented by a key.
 Keys and nodes’ IDs are
mapped to m-bit
identifiers using hash
functions.
 Identifiers are ordered
in an identifier circle
modulo 2m.
0
1
7
2
6
3
5
4
19
 Identifiers are ordered
in an identifier circle
modulo 2m.
 Key k is assigned to the
first node whose
identifier is equal to or
follows the identifier
of k in the identifier
space.
 This node is called the
successor node of key k,
denoted by
successor(k).
20
 When a node n joins the network, certain keys previously
assigned to n’s successor now become assigned to n.
 When node n leaves the network, all of its assigned keys are
reassigned to n’s successor. No other changes in assignment of
keys to nodes need occur.
{0,7}
{0,4,5,6,7}
1
7
3
5
4
1
7
2
6
{1}
0
{1}
0
2
6 {4,5,6}
{2,3}
3
5
4
{2,3}
21
Looking for objects
 Each node needs only be aware of its
successor node on the circle.
query 5
0
1
7
2
6
3
5
4
22
improve the efficiency of the query routing
 Each node, n, maintains a routing table with at
most m entries, called the finger table
 The ith entry in the table at node n contains the
identity of the first node, s, that succeeds n by at
least 2i-1 on the identifier circle. That is, s =
successor((n+2i-1) mod 2m).
 n.finger(i).start is (n+2i-1) mod 2m in the identifier
circle.
 n.finger(i).interval = [n.finger(i).start,
n.finger(i+1).start)
23
24
 A new node n first finds the identity of an existing
Chord node n’.
 n learns it predecessor and finger table from n’.
 updating the finger tables of the other nodes is
based on the following observations


n becomes the ith finger of a node p if and only if p precedes
n by at least 2i-1
the ith finger of p succeeds n
25
26
27
Preserving the Identity of
Message Sender and Receiver
 Sometimes, it is important to preserve the
identities of the senders and the receivers
of the messages
for privacy
 avoid persecution

 It is possible to construct a peer-to-peer
network that conceal the identity of the
senders and the receivers of messages
transmitted over the network.
28
Tor: The Second-Generation Onion Router
 Tor seeks to frustrate attackers from linking





communication partners
An overlay network formed by peers
To communicate, a user constructs a circuit (i.e. a
route for transmitting data) using some of the
peers in the overlay network
Each peer (called a router) in a circuit only knows
its two neighbours in the circuit
The router at the entry point of the circuit knows
the IP of the user, but not the IP of the party
that the user wants to communicate
The router at the exit point of the router knows
the IP of the party that the user wants to
communicate, but not the IP of the user
29
Onion Routing
 During the circuit creation, the user sets up a
session key with each of the routers in the circuit.
 The user encrypts the data with the session keys
repeatedly, starting with the exiting router and
ending with entry router
 In order to find out the transmitted data, the
routers in the circuit need to decrypt the data
using their session keys
30
How to set up a shared secrete key
 An important issue in shared secret key protocol
is how to set up the shared key between two
parties


If the two parties know each other in advance, they can
set up the keys before the communication.
What if the two parties do not know each other?
 The Diffie–Hellman key agreement method allows
two parties to establish a shared secret key over
an insecure communication channel.


The two parties do not need to know each other in
advance.
The communication channel does not need to be secure.
31
Diffie–Hellman key agreement
 Alice and Bob want to agree on a secret key
 Alice and Bob need to choose two numbers p and g
 p is a large prime on the order of 1024 bits
 The two numbers do not need to be confidential, i.e. they can be
sent over the Internet
 Alice and Bob choose a large random number respectively
 Alice and Bob must keep their random number secret
 Alice and Bob compute a value using p, g and their chosen
random numbers respectively

The computed values do not need to be secret
 Alice and Bob exchange their computed value
 Alice and Bob use their received value and their chosen
random value to form the shared key
32
http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

33
Security of Diffie–Hellman (1)

34
Security of Diffie–Hellman (2)
 Man-in-the-middle attack
The attacker intercepts Alice’s and Bob’s
message and relay their messages
 The attacker sets a key with Alice and Bob
respectively
 The attackers use the keys to decrypt/encrypt
Alice’s and Bob’s messages

35
Constructing a circuit (1)
 TOR client obtains a list of TOR nodes from a
directory server
 Directory servers maintain list of which onion
routers are up, their locations, current keys, exit
policies, etc.
36
Constructing a circuit (2)
 User establishes key and circuit with Onion Router
1 using a Diffie–Hellman variation
 User sends “ Create c1, E(gx1) ” where E is a PKI
encryption function that uses router 1’s key
 Router 1 replies with “Created c1, gy1, H(K1)”
where K1 = gx1y1 and H is a hash function
 The user computes the session key with router 1
from the reply
37
Constructing a circuit (3)
 User tunnels through that circuit to extend to
Onion Router 2

Relay c1 {Extend, OR2, E(gx2)}
 Router 1 extends the circuit by sending “Create
c2, E(gx2)” to router 2
 Router 2 replies “Created c2, gy2, H(K2)”
 Router 1 sends “Relay c1 {Extended, gy2, H(K2)}”
38
Constructing a circuit (4)
 User tunnels through that circuit to
extend to Onion Router 3
39
Communicate over the circuit
 Client applications connect and
communicate over TOR circuit
40
Create data
 User encrypts the data using the session
keys
 User sends the encrypted data to the
circuit
41
Relay data
 Router 1 decrypts the data, and relays it to
router 2
42
 Router 2 decrypts the data, and relays it
to router 3
43
 Router 3 decrypts the data, find the real
receiver, and relay the data to the
receiver
44
45
Send reply to a user
 When a router later replies to a user with
a relay cell, it encrypts the cell’s relay
header and payload with the session key it
shares with the user, and sends the cell
back toward the user along the circuit.
 Subsequent routers add further layers of
encryption as they relay the cell back to
the user.
46
location-hidden services
 Bob wants to offer a service, such as a
webserver, without revealing his IP
address

protects against distributed DoS attacks
 The scheme should allow Bob to control
who can access his service
 Tor supports this type of service through
rendezvous points
47
Message Digest (hash)
 Used to represent a message with a given number
of bits.

produced by condensing the information in the message
 Used to guarantee that a message has not been
altered in transit


Like a cryptographic checksum
The function for computing the digest (hash) of a
message must be secure.
• Given a message M and its hash H(M), it must be very hard
to find a message M’ that has the same digest; i.e., for
which H(M) = H(M’).
• One-way function

If you are given the digest for a message and you are
able to compute exactly the same digest for that
message, then it is highly likely this message produced
the digest you were given.
• The message has not been altered.
48
Digital signatures
 If the digest of a message is transmitted
alongside the message, anybody who modifies the
message can also replace the digest by one
matching the modified message.

To prevent the above problem, the digest may be
encrypted by the sender.
 If the sender of a message encrypts the digest of
the message by public key cryptography using a
private key whose matching public key is available
to the receiver, the encrypted digest serves as a
digital signature.

assert the identity of the sender of the message
• guarantee that a message was authorized by a specified
entity
49
Digitally sign a message
 The sender carries out the following operations
 Generates a public/private key pair, Kpub and Kpri
• Distribute the public key Kpub to the receiver



Computes the digest H(m) of message m
Encrypts the digest with the private key to obtain
{H(m)}Kpri
Send (m, {H(m)}Kpri) to the receiver
 The receiver carries out the following operations
 Computes the digest H(m) of message m
 Decrypts {H(m)}K
using the sender’s public key to
pri
obtain H(m)’
 Check whether H(m) = H(m)’
• If they are equal, m has not been tampered with, since it is
infeasible to find a message that has the same digest as m
• Can also be assured that the message comes from the
specified sender, since only the sender has Kpri
50
Advertising service
 Bob generates a long-term public key pair
to identify his service.

Not issued by CA
 Bob chooses some introduction points, and
advertises them on the lookup service,
signing the advertisement with his private
key.
 Bob builds a circuit to each of his
introduction points, and tells them to wait
for requests.
51
52
Contacting the server
 Alice learns about Bob’s service out of band
 Bob told her, or she found it on a website
 Alice retrieves the details of Bob’s service from
the lookup service.

If Alice wants to access Bob’s service anonymously, she
must connect to the lookup service via Tor.
 Alice chooses a router as the rendezvous point
(RP) for her connection to Bob’s service.

She builds a circuit to the RP, and gives it a randomly
chosen “rendezvous cookie” to recognize Bob.
 Alice connects anonymously to one of Bob’s
introduction points, and gives it a message
(encrypted with Bob’s public key) telling it about
herself, her RP and rendezvous cookie, and the
start of a DH handshake.
53
54
Connecting clients and services
 The introduction point sends the message
to Bob.
 If Bob wants to talk to Alice, he builds a
circuit to Alice’s RP and sends the
rendezvous cookie, the second half of the
DH handshake, and a hash of the session
key they now share.

The RP relays this information to Alice.
 The RP connects Alice’s circuit to Bob’s.
 The RP can’t recognize Alice, Bob, or the data
they transmit.
55
56
Some analysis of Tor
 Tor assumes that the directory servers
control who can join the peer network to
become routers

Filter out most malicious peers
 Tor has many directory servers, if a few
directory servers disappear, Tor still
works by using the others that are still
available.
 A hostile entity must have control of the
first and the last router in order to know
the communicating parties
57
reviews
 What are the three techniques for looking resources in a




P2P system? Compare and contrast them in terms of
efficiency, reliability and scalability.
In the CAN protocol, how do we determine which node store
a document and how to look up a document stored in the
system?
In the CAN protocol, how do the peers determine whether a
peer has left the system or has failed? How can we make
sure that files stored in a system can survive failures of the
peers in the system?
In the CHORD protocol, how do we determine which node
store a document?
Understand how to construct the finger table for each of
the node in the CHORD protocol.
58
reviews
 How does the Diffie–Hellman key agreement scheme work?
 What attacks can be used against the Diffie–Hellman





scheme? What measures can be used to counter these
attacks?
Understand how to create a circuit in Tor.
Understand how a user uses a rendezvous point to connect
to a anonymous service.
In Tor, how does a user know that the session key being
created belong to the router that the user want to extend
the circuit to?
In Tor, when a router sets up a session key with a user, what
prevents the router from knowing the identity of the user?
In Tor, why do we need to encrypt the data transmitted
over the circuit?
59
Readings
 D.S. Milojicic et. al., Peer-to-Peer Computing, HP Laboratories,




HPL-2002-57
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and
Scott Shenker. A scalable content-addressable network. In Proc.
ACM SIGCOMM 2001
I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan.
Chord: A scalable peer-to-peer lookup service for Internet
applications. Technical Report TR-819, MIT, March 2001
Roger Dingledine, Nick Mathewson, and Paul Syverson. 2004. Tor:
the second-generation onion router. In Proceedings of the 13th
conference on USENIX Security Symposium - Volume
13 (SSYM'04), Vol. 13. USENIX Association, Berkeley, CA, USA,
21-21.
An interesting talk about Tor
http://www.youtube.com/watch?v=GwMr8Xl7JMQ
60