Transcript Pseudo Trust - Department of Computer Science and Engineering

Pseudo Trust: Zero-Knowledge
Based Authentication in Anonymous
Peer-to-Peer Protocols
Li Lu, Lei Hu
State Key Lab of Information Security, Graduate School of
Chinese Academy of Sciences
Jinsong Han, Yunhao Liu, Lionel M. Ni
Dept. of Computer Science and Engineering, Hong Kong University
of Science and Technology
Jinpeng Huai
School of Computer Science,
State Key Lab of Software Developing Environment,
Beihang University
Authentication
To make one person trust another one.
Who is talking to whom must be as valid
as whom he or she claimed.
Is he/she the valid person who is
searching a public database?
Is he/she the valid person who provide
you a movie without virus?
Is the collaborating company legal?
Is a cheater who send you an e-mail?
However…
Your machine may be accessed by a
hacker.
You may receive fraudulent.
advertisement via e-mail.
The goal of authentication: A host will
communicate with a server while he can
determine its identity.
Anonymity or Privacy
the right to be let alone: one of the rights
most cherished by people.
Who is talking to whom should be
confidential or private in the Internet.
Who is searching a public database?
Which movie are you downloading?
Which companies are collaborating?
Who are you talking to via e-mail?
However…
Your machine’s IP uniquely identifies you across web
sites.
Nothing illegal about cross-referencing.
The goal of Internet anonymity: A host can
communicate with a server while nobody can
determine its identity
www.ticket-agency.com
www.insurance-advertisement.com
Previous approaches: Authentication
Authentication in P2P is used to help
evaluating reputations of peers. To know Who
want to download or searching from Whom.
Indeed, current P2P trust designs are
identity-based, where one peer does not trust
another before knowing its identity.
Not trying to protect the identity’s
anonymity of peers.
Previous approaches: Anonymity
Anonymity is the state of being
indistinguishable from other members of
some group. Don’t know Who is Searching or
Downloading What from Whom.
Main goal is to hide initiator’s and responder’s
real identities, such as IP address, post
address, etc.
Not trying to authenticate the validity of
peers.
Anonymity Examples: Mix &
Onion
A
B
C
D
ABCD
Public keys IP
IPC IPD
IPC
IPB
M D IP IPD M D
C
IPC
B
IPD
IPD
IPD M D
C
B
C
M
Anonymity Example: APFS
Server
Client
However, APFS is just for file delivery,
without identity authentication.
Tradeoff
Authentication is Identity-based
– Leaking the real identity of peer, such as
IP address, post address…
Anonymity is to hide the identity.
– Vulnerable to many active attacks,
especially impersonation and man-in-middleattack.
Basic goal: A New Mutual
Anonymity Authentication for P2P
Non ID-based authentication
No need to know real identity of peer before
authentication.
Pseudonym-based authentication.
Invulnerable to many active attacks.
Impersonation
Man-in-Middle-Attack
Replay…
Lightweight: efficient pseudonym generation
and authentication.
Query and Downloading in
Unstructured P2P Systems
Flooding based query
• Reversed path based response
• Direct downloading
Initiator
Query
Responder
Response
Downloading
Pseudonym generation
We use cryptographic hash function to generate
pseudonym PI:
Seed  h( ID, p1 , p2 )
PI  h(Seed, n)
Where moduli n  p1  p2 , and p1 , p2 are two big primes.
These two primes are kept as peer’s secrets. Due to
the one-way and collision-resistant properties of
hash function, a malicious peer cannot impersonate
other peer’s pseudonym.
Our Design: Pseudo Trust
Query Sending
Tail node
TI
Responder R
Query q
Initiator I
Onion Path
Flooding
Response
Tail node TR
Tail node TI
Responder R
Response; prove your
pseudonym.
Query q
Initiator I
Onion Path
between R
and T
R
TCP Link
Onion Path
between I
and TI
Mutual authentication
Tail node TR
Tail node TI
Responder R
Proof verification
Challenge
Request
verification
message
Authentication
Proof generation
request
Initiator I
Onion Path
between R
and T
R
TCP Link
Onion Path
between I
and TI
SimilarResponder
procedureauthenticates
for Initiator authenticating
initiator.
responder
Remarks on mutual authentication
The zero-knowledge identification protocol is
used to implement pseudonym-base
authentication.
Session key exchange is embedded in the
mutual authentication.
After authentication, initiator and responder
can use the session key to protect file
confidentiality and integrity. For example,
using symmetric-key encryption and massage
authentication code.
Several important issues
Security
Anonymity degree
Impersonation
Man-in-Middle-attack
Overhead
Traffic overhead
Cryptographic overhead
Response time of queries
Security Analysis
Completely anonymity
Resistant to impersonation and replay.
Man-in-Middle attacker gets nothing from
authentication
Resistant to inner attacks
Tail nodes are attackers.
Initiator or responder is attack.
Trace Driven Simulation
Physic network: Gnutella
Overlay network: DSS Clip2 trace
In a variety of network sizes ranging
from hundreds to thousands.
For each simulation, we take the
average result from 1,000 runs.
Response Time
Accumulative Percentage
100
80
60
40
Gnutella
APFS
Direct Authentication
PT
20
0
0
5
10
15
Time(seconds)
The response time of APFS is approximately 3 times that of
overt Gnutella, while PT is around 7 times that of overt Gnutella.
The time consumed in anonymous paths of PT constitutes a
major part of the whole latency.
The time consumption of authentication is indeed trivial.
Traffic Overhead
1.25
Traffic stretch
1.2
1.15
1.1
1.05
0
500
1000
1500
Search scope
The figure above plots the extra traffic cost brought
about by authentication procedures.
Traffic stretch is defined as the traffic cost ratio
between PT plus Gnutella, and Gnutella only
Prototype Implementation
We implemented a prototype in our labs at
the Chinese Academy of Sciences, the campus
of Beihang University and Hong Kong
University of Science and Technology.
We test:
The extra computation overhead caused by PT.
Overall latency of pseudo identity authentication
procedures in the Internet environment
Computational Overhead
x 10
3
2.5
Time consumption(ms)
Time consumption(ms)
4
3.5
PIV 2.66G
PIV 1.8G
PM 1.4G
PIII 450M
2
1.5
1
0.5
0
0
20
40
60
80
40
30
PIV 2.66G
PIV 1.8G
PM 1.4G
PIII 450M
20
10
0
0
100
20
Number of quadratic residues
10
8
PIV 2.66G
PIV 1.8G
PM 1.4G
PIII 450M
6
4
2
0
0
20
60
Proof generation
Pseudonym certificate generation
Time consumption(ms)
40
80
Number of quadratic residues
40
60
80
Number of quadratic residues
Verification
100
100
160
Time consumpation(ms)
180
length of moduli n=2048 bits
length of moduli n=1024 bits
140
120
100
80
60
0
20
40
60
80
100
Number of quadratic residues
400
length of moduli n=2048 bits
length of moduli n=1024 bits
350
300
250
200
0
20
40
60
MAN test
680
660
length of moduli n=2048 bits
length of moduli n=1024 bits
640
620
600
580
560
0
80
Number of quadratic residues
CAN test
Time consumpation(ms)
Time consumpation(ms)
Time Consumption in Message
Transmission
20
40
60
80
Number of quadratic residues
WAN test
100
100
Li Lu, Lei Hu
State Key Lab of Information Security, Graduate School of
Chinese Academy of Sciences
Jinsong Han, Yunhao Liu, Lionel M. Ni
Dept. of Computer Science and Engineering, Hong Kong University
of Science and Technology
Jinpeng Huai
School of Computer Science,
State Key Lab of Software Developing Environment,
Beihang University