Transcript A distributed Search Service for Peer-to

A distributed Search Service
for Peer-to-Peer File Sharing in
Mobile Applications
From U. of Dortmund, Germany
Motivation:
Mobile devices become more powerful
(computation, resources)
They form spontaneous self-organizing
communication structure: Mobile Ad-Hoc
Network. (all of them are peers)
People shares files among those mobile
devices to satisfy more requirements.
Challenge:

Efficiently locating the sharing files
Passive Distributed Indexing
PDI: provide a general-purpose file search
service.
Each mobile device maintains:

Repository: a set of sharing files, PDI provides
local search services
 Doc ID: IP/MAC + local path

Index cache: a set of (keyword, doc ID)
 Used to answer query for non-local doc
PDI: Query
Query model:


A query string contains several keywords
“AND” operation on all keywords
Broadcast: query/response messages
(nature of wireless network)
Forward: for a predefined number of
hops (using broadcast)
By experiments: 2 hops are enough
PDI : Cache
Cache: all received query results in the
local cache index (all nodes which
receives a message)
Local cache indexing replacement:


Least-recently-used algorithm
Timeout
Exploit locality and erase hotspots
PDI: Messages
QUE:


Query string, SRC, SEQ, TTL
Each node stores the highest SEQ for each
SRC and prevents retransmission.
REP:


contains local search results (set of Doc Ids)
Selectively forwarding: only forward the doc
Ids which are not in the local cache index
PDI: Example
Experiment Parameters:
Experiment results:
Tarzan: A Peer-to-Peer
Anonymizing Network Layer
from NYU & MIT
Motivation
People want anonymity for all kinds of
reasons
There are some entities which are
interested in exposing the host’s identity
The goal of Internet anonymization:

A host can communicate with an arbitrary
server in such a manner that nobody can
determine the host’s identity.
Previous work:
Proxy:

Trust the proxy, can be blocked by servers, DOS
A set of mix relays:


Onion routing, Zero-knowledge’s freedom
Relay may be corrupted, timing analysis, some
other same problems with proxy
The above two:


Ignore the attack by observing all network traffic
There are some other solutions, but still not good
Tarzan: P2P Technique armed
Extend mix-net design to a peer-to-peer
environment
communicate over sequences of mix
relays chosen from a pool of volunteer
nodes, without centralized component.
All peers are potential originators and
relays
Nobody can tell who is the first hop in a
mix path (except the originator itself)
Tarzan: resistant to adversary nodes
A new concept: domain
Used to remove potential adversarial bias
Based on the observation:

An adversary may run hundreds of virtual
machines, yet is unlikely to control hundreds
of different IP subnets.
Tarzan: more…
Cover traffic for packet routing
Packets can be routed only between mimics
Applications (with Tarzan support) can talk
to Applications (without Tarzan support)
through special IP tunnels
Tarzan is transparent to Applications.
Tarzan don’t provide authentication and
congestion control functionalities.
Tarzan: Architecture Overview
Tarzan: Packet relay
Two types of messages: data & control
A flow tag uniquely identifies each link of
each tunnel. (used for forwarding)
Symmetric encryption hides data, MAC
protects integrity.
Separate keys are used in each direction
of each relay
Tarzan: Packet relay (cont.)
Clear IP packet’s src filed, encrypt and
encapsulate in a UDP packet
T = (h1, h2,…, hl, hpnat)
For each relay: ekhi, ikhi
c(i) = ENC(ekhi, {B(I+1)})
a(i) = MAC(ikhi, {seq, c(i)})
B(i) = {seq, c(I), a(i)}
Tarzan: packet relay (cont.)
The initiator does all the encryption
Each relay just decrypts the block,
retags it, encapsulates in a new UDP
packet and forwards it.
On the reverse path, the relays encrypt
the packet and the initiator decrypts the
final packets
Tarzan: Tunnel Setup
Initiator is responsible for that work
Includes:


Generate/distribute symmetric keys
Iteratively setup the tunnel one by one
an establish request (forward session key are
encrypted by the public key of node hi )
Using the existing tunnel to setup next step,
so the relays on current tunnel don’t know it’s
a data message or control message (for
setting up another relay)
Tarzan: IP packet forwarding
The last node on the tunnel (PNAT) will
send the packet to the server with its
own address.
Upon receiving the replay, it will send it
back along the tunnel.
Tunnel failure & reconstruction:


Periodically ping message
Start reconstruction from the failed relay
Tarzan: Peer discovery
Gossip Algorithm
Each node has a public key

two handshake authentication
From weakly connected to fully connected
Three different/related operations:



Initialization: send entire neighbor set
(for fast propagation)
Redirection: redirect new nodes to random
neighbors (for shed load)
Maintenance: an incremental update
Tarzan: peer selection
Tarzan: cover traffic
Mimics: node pairs


Calculated, not randomly selected
!! Mimic relationship is symmetric !!
Tunnels must be built through mimics
Cover traffic is transferred between
mimics (adjust according to all incoming
traffic and outgoing traffic)
So nobody can observe the real user
data
Tarzan: Mimic Topology
Experiment result:
Tarzan: conclusion
Resistant to attack (a lot of security analysis)
Achieve anonymity for end users
Overhead:



Each node needs to keep some info for all other
nodes in the network
Packet transfer latency
Considerable computation workload (especially on
the initiator of the traffic)