Transcript ppt

15-446 Networked Systems
Practicum
Lecture 16 – Trust/Reputation
1
Trust
• Trust involves human activities
• We share the same interests.
• We had a satisfactory transaction.
• We are friends.
• After trust is established
• Can bootstrap other forms of security using
crypto
2
Overview
• SybilGuard: trust in people
• Credence: trust in objects based on people
• Wi-Fi reports: trust in objects based on people
with privacy
• Perspectives: trust in objects based on
independent views
3
Overview
• SybilGuard: trust in people
• Credence
• Wi-Fi reports
• Perspectives
4
Impact of Sybil
• Power of the adversary:
• Unlimited number of
colluding sybil nodes
• Sybil nodes may not
follow SybilGuard
protocol
• W.h.p., honest node
accepts ≤ g*w sybil
nodes
• g: # of attack edges
• w: Length of random
route
If SybilGuard
bounds #
accepted sybil
nodes within
n/2
n
Then apps
can do
byzantine
consensus
majority
voting
not much larger effective
than n
replication
5
Background: Sybil Attack
• Sybil attack: Single user
pretends many fake/sybil
identities
honest
• Creating multiple accounts malicious
from different IP addresses
• Sybil identities can become
a large fraction of all
identities
launch
sybil
attack
• Out-vote honest users in
collaborative tasks
6
Background: Defending Against
Sybil Attack
• Using a trusted central authority
• Tie identities to actual human beings
• Not always desirable
• Can be hard to find such authority
• Sensitive info may scare away users
• Potential bottleneck and target of attack
• Without a trusted central authority
• Impossible unless using special assumptions
[Douceur’02]
• Resource challenges not sufficient -- adversary can
have much more resources than typical user
7
SybilGuard Basic Insight:
Leveraging Social Networks
Our Social Network Definition
• Undirected graph
• Nodes = identities
• Edges = strong trust
• E.g., colleagues,
relatives
8
SybilGuard Basic Insight
• n honest users: One identity/node each
• Malicious users: Multiple identities each (sybil
nodes)
honest
nodes
attack
edges
sybil
nodes
Sybil nodes
may collude –
the adversary
malicious
user
Observation: Adversary cannot create extra
edges between honest nodes and sybil nodes
9
SybilGuard Basic Insight
honest
nodes
sybil
nodes
Dis-proportionally
small cut
disconnecting a large
number of identities
But cannot search for
such cut bruteforce…
10
Goal of Sybil Defense
• Goal: Enable a verifier node to decide whether
to accept another suspect node
• Accept: Provide service to / receive service from
• Idealized guarantee: An honest node accepts and
only accepts other honest nodes
• SybilGuard:
• Bounds the number of sybil nodes accepted
• Guarantees are with high probability
• Approach: Acceptance based on random route
intersection between verifier and suspect
11
Random Walk Review
f
a
b
c
pick random edge d
d
e
pick random edge e
pick random edge c
12
Random Route: Convergence
f
a
b
randomized
routing table
ad
ba
cb
dc
d
c
e
de
ed
f f
Random 1 to 1 mapping between
incoming edge and outgoing edge
• Using routing table gives Convergence Property
• Routes merge if crossing the same edge
13
Random Route: Back-traceable
f
a
b
ad
ba
cb
d
c
e
de
ed
f f
dc
If we know the
route traverses
edge e, then we
know the whole
route
• Using 1-1 mapping gives Back-traceable Property
• Routes may be back-traced
14
Random Route Intersection:
Honest Nodes
• Verifier accepts a
suspect if the two
routes intersect
Verifier
• Route length w:
Suspect
~ n log n

honest nodes
sybil nodes
• W.h.p., verifier’s
route stays within
honest region
• W.h.p., routes
from two honest
nodes intersect
15
Random Route Intersection:
Sybil Nodes
• SybilGuard bounds the number of accepted
sybil nodes within g*w
• g: Number of attack edges
• w: Length of random routes
• Next …
• Convergence property to bound the number of
intersections within g
• Back-traceable property to bound the number
of accepted sybil nodes per intersection within
w
16
Bound # Intersections Within g
must cross attack edge to intersect even if
sybil nodes do not follow the protocol
Verifier
Suspect
same
intersection
honest nodes
sybil nodes
• Convergence: Each
attack edge gives
one intersection
 at most g
intersections with g
attack edges
Intersection =
(node, incoming edge
17
Bound # Sybil Nodes Accepted per
Intersection within w
Verifier
• Back-traceable:
Each intersection
should correspond
to routes from at
most w honest
nodes
• Verifier accepts at
most w nodes per
intersection
for a given intersection
• Will not hurt honest
nodes
18
Summary of SybilGuard Guarantees
• Power of the adversary:
• Unlimited number of
colluding sybil nodes
• Sybil nodes may not
follow SybilGuard
protocol
• W.h.p., honest node
accepts ≤ g*w sybil
nodes
• g: # of attack edges
• w: Length of random
route
If SybilGuard
bounds #
accepted sybil
nodes within
n/2
n
Then apps
can do
byzantine
consensus
majority
voting
not much larger effective
than n
replication
19
Overview
• SybilGuard
• Credence: trust in objects based on people
• Wi-Fi reports
• Perspectives
20
Problem: Pollution
• P2P pollution
• Non-authentic content
• Corrupted or missing contents
• Viruses
• What are the solutions?
• Ranked by popularity
• Ranked by submitter (how many filed
submitted)
21
Credence: Reputation based on Voting
Is the file authentic?
22
Credence: Reputation based on Voting
Randomly choose
peers to collect votes
Is the file
authentic?
Is the file
authentic?
Is the file
authentic?
23
Credence: Reputation based on Voting
Randomly choose
peers to collect votes
Yes!
No
Yes!
24
Credence: Reputation based on Voting
What is the reputation
of each response?
(correlation coefficient)
Yes!
No
Yes!
25
Credence: Reputation based on Voting
Probably not authentic…
Yes!
No
Yes!
26
Credence Reputation Graph
27
Overview
• SybilGuard
• Credence
• Wi-Fi reports: trust in objects based on
people with privacy
• Perspectives
28
Problem: Commercial AP Selection
Jiwire.com
Hotspot database
tmobile
attwifi (ap 1)
attwifi (ap 2)
linksys
seattlewifi
Free Public Wifi
$9.9
9
$3.9
9
Quality =
???
Free!
Free!
Which networks will run my applications?
Which ones have good performance?
We often have many choices of wireless
access points (APs), but little information about each
29
Goal: Provide More Information
Improved
Hotspot database
Bandwidth: 300 kbps
Blocked ports: None
Bandwidth: 30 kbps
Blocked ports: Email
Bandwidth: 100 kbps
Blocked ports: None
Doesn’t work!
Doesn’t work!
Bandwidth: 5 Mbps
Blocked ports: None
Bandwidth: 300 kbps
Blocked ports: None
tmobile
Bandwidth: 300 kbps
Blocked ports: None
attwifi (ap 1)
Bandwidth: 100 kbps
Blocked ports: None
attwifi (ap 2)
Bandwidth: 300 kbps
Blocked ports: None
linksys
Doesn’t work!
Bandwidth: 100 kbps
Blocked ports: Email,
Skype
Doesn’t work!
Free Public Wifi
seattlewifi
Doesn’t work!
Bandwidth: 300 kbps
Blocked ports: None
Doesn’t work!
I need to use VoIP so this is the
best network for me
Provide information about AP performance
and application support
30
Goal: Wifi-Reports
Users automatically report on APs that they use
31
Strawmen Protocols
Alice’s locations:
authenticate Alice
submit: R
cafe1
tmobile #3
Bob’s Network
Alcohol Anon Net
CMU
…
Location Privacy
If Alice has already submitted
a report on cafe1 then abort,
else save the report
measure cafe1
Anonymous
Report on cafe1
Bandwidth: 5
100
MbMb
R

report on cafe1
submit: R
mix network
Limited Influence
32
starbucks2
cafe1
Report Protocol
…
{kcafe1, k-1cafe1}

authenticate and
download list of APs
List of all APs
cafe1
cafesolstice
tmobile #4
AT&T #54

new key pair
{kcafe2, k-1cafe2}  new key pair
Blind the token kcafe1  Tblind
…
request: cafe1, Tblind
reply: Sblind
If Alice requested cafe1 before
then abort
else sign the token  Sblind
Unblind the signature  Scafe1
measure cafe1
Report on cafe1
Bandwidth: 5 Mbps
submit:
cafe1, Scafe1, kcafe1, R, SR
mix network
R

report on cafe1
Verify the signatures
Delete old reports signed with
kcafe1
Sign the report  SR
33
Report Protocol
authenticate and
download list of APs
{kcafe1, k-1cafe1}

new key pair
Blind the token kcafe1  Tblind
cafe2
cafe1
request: cafe1, Tblind
reply: Sblind
If Alice requested cafe1 before
then abort
else sign the token  Sblind
Unblind the signature  Scafe1
Location Privacy
measure cafe1
Report on cafe1
Bandwidth: 5 Mbps
submit:
cafe1, Scafe1, kcafe1, R, SR
mix network
R

report on cafe1
Limited Influence
Report on cafe2
Bandwidth: 5 Mbps
Verify the signatures
Delete old reports signed with
kcafe1
Sign the report  SR
34
Overview
• SybilGuard
• Credence
• Wi-Fi reports
• Perspectives: trust in objects based on
independent semi-trusted views
35
“Man in the Middle” (MitM) Attacks
•
Alice needs Bob’s public key to
establish a secure channel (e.g., SSL/SSH)
to him.
Hello,Bob
Alice
secure channel
KA
Bob
36
“Man in the Middle” (MitM) Attacks
Is KB really
Bob’s key?
Hello,Bob
“secure”
channel
Alice
KB
Mallory
Bob
If Alice accepts KB Mallory
can snoop and modify all
traffic!
37
Obtaining Authentic Public Keys
• Two standard approaches to handling MitM
attacks:
• Public Key Infrastructure (e.g., Verisign certs)
• Prayer
38
Perspectives Overview
KA
Bob’s Key?
Bob’s Key?
Offered
Key
KA
N
Hello,Bob
Alice
KA
N
KA
Bob
Key?
KA KA Bob’s
KA
Observations
Client Consistent
Policy Inconsistent
KA
N
Accept Key,
Continue
Reject Key, Abort
Connection
39