Transcript Document

Anonymous Communications
CSE 5473: Network Security
Lecture due to Prof. Dong Xuan
Some material from Prof. Joan Feigenbaum
1
Outline
 Overview and Concepts
 Anonymous Schemes
 Onion Routing
 Crowd
 Hordes
 Incomparable Public Keys
2
Motivation
 Is Internet communication private?
 No! ... Why?
 Routing information is completely ‘open’ (visible)
to the network and its users.
• e.g. IP Source, IP destination addresses.

Traffic Analysis can result in loss of privacy
throwing up patterns showing communication
propensities of internet users.
3
Motivation...
 Do we need private communication?
 Yes…

Existence of inter-company collaboration may be confidential

E-mail users may not wish to reveal who they are communicating
with, to the rest of the world

Anonymity may also be desirable: anonymous e-cash is not very
anonymous if delivered with a return address

Web based shopping or browsing of public databases should not
require revealing one’s identity
4
Anonymity Properties
 Types of Anonymity
• Sender Anonymity
• Receiver Anonymity
• Unlinkability of sender and receiver
 Model of the Attacker
• Eavesdropper
• Collaboration of parties
 Anonymity Degree
5
Concept: Mix Networks
 First outlined by Chaum in 1981
 Provide anonymous communication
 High latency
 Message-based (“message-oriented”)
 One-way or two-way
6
Mix Networks
Users
Mixes
Destinations
7
Mix Networks
Adversary
{{{,d}M3,M3}M2,M2}M1
u
M1
d
M2
M3
Users
Mixes
Protocol
1. User selects a sequence of mixes
and a destination.
2. Onion-encrypt the message.
Destinations
Onion Encrypt
1. Proceed in reverse order
of the user’s path.
2. Encrypt (message,
next hop) with the public
key of the mix. 8
Mix Networks
Adversary
{{{,d}M3,M3}M2,M2}M1
u
M1
d
M2
M3
Users
Mixes
Protocol
1. User selects a sequence of mixes
and a destination.
2. Onion-encrypt the message.
3. Send the message, removing a
layer of encryption at each mix.
Destinations
Onion Encrypt
1. Proceed in reverse order
of the user’s path.
2. Encrypt (message,
next hop) with the public
key of the mix. 9
Mix Networks
Adversary
u
M1 {{,d}M3,M3}M2
M2
d
M3
Users
Mixes
Protocol
1. User selects a sequence of mixes
and a destination.
2. Onion-encrypt the message.
3. Send the message, removing a
layer of encryption at each mix.
Destinations
Onion Encrypt
1. Proceed in reverse order
of the user’s path.
2. Encrypt (message,
next hop) with the public
key of the mix. 10
Mix Networks
Adversary
u
d
M1
M2 {,d}M3
M3
Users
Mixes
Protocol
1. User selects a sequence of mixes
and a destination.
2. Onion-encrypt the message.
3. Send the message, removing a
layer of encryption at each mix.
Destinations
Onion Encrypt
1. Proceed in reverse order
of the user’s path.
2. Encrypt (message,
next hop) with the public
key of the mix. 11
Mix Networks
Adversary
u
M1

M2
d
M3
Users
Mixes
Protocol
1. User selects a sequence of mixes
and a destination.
2. Onion-encrypt the message.
3. Send the message, removing a
layer of encryption at each mix.
Destinations
Onion Encrypt
1. Proceed in reverse order
of the user’s path.
2. Encrypt (message,
next hop) with the public
key of the mix. 12
Mix Networks
Adversary
u
d
v
e
w
f
Users
Mixes
Destinations
Anonymity?
1. No one mix knows both source and destination.
2. Adversary cannot follow multiple messages through the
same mix.
3. More users provides more anonymity.
13
How Onion Routing Works
1
2
u
3
5
User u running client
d
4
Internet destination d
Routers running servers
14
How Onion Routing Works
1
2
u
3
5
d
4
1. u creates 3-hop circuit through routers (u.a.r.).
2. u opens a stream in the circuit to d.
15
How Onion Routing Works
{{{}3}4}1
1
2
u
3
5
d
4
1. u creates 3-hop circuit through routers (u.a.r.).
2. u opens a stream in the circuit to d.
3. Data are exchanged.
16
How Onion Routing Works
1
u
5
2
3
d
{{}3}4
4
1. u creates 3-hop circuit through routers (u.a.r.).
2. u opens a stream in the circuit to d.
3. Data are exchanged.
17
How Onion Routing Works
1
2
u
3
5
4
d
{}3
1. u creates 3-hop circuit through routers (u.a.r.).
2. u opens a stream in the circuit to d.
3. Data are exchanged.
18
How Onion Routing Works
1
2
u
3
5

d
4
1. u creates 3-hop circuit through routers (u.a.r.).
2. u opens a stream in the circuit to d.
3. Data are exchanged.
19
How Onion Routing Works
1
2
u
3
5
’
d
4
1. u creates 3-hop circuit through routers (u.a.r.).
2. u opens a stream in the circuit to d.
3. Data are exchanged.
20
How Onion Routing Works
1
2
u
3
5
4
d
{’}3
1. u creates 3-hop circuit through routers (u.a.r.).
2. u opens a stream in the circuit to d.
3. Data are exchanged.
21
How Onion Routing Works
1
u
2
{{’}3}4
3
5
d
4
1. u creates 3-hop circuit through routers (u.a.r.).
2. u opens a stream in the circuit to d.
3. Data are exchanged.
22
How Onion Routing Works
{{{’}3}4}1
1
2
u
3
5
d
4
1. u creates 3-hop circuit through routers (u.a.r.).
2. u opens a stream in the circuit to d.
3. Data are exchanged.
23
How Onion Routing Works
1
2
u
3
5
d
4
1. u creates 3-hop circuit through routers (u.a.r.).
2. u opens a stream in the circuit to d.
3. Data are exchanged.
4. Stream is closed.
24
How Onion Routing Works
1
2
u
3
5
d
4
1. u creates 3-hop circuit through routers (u.a.r.).
2. u opens a stream in the circuit to d.
3. Data are exchanged.
4. Stream is closed.
5. Circuit is changed every few minutes.
25
Onion Routing
 Provides

An infrastructure for Private Communication over a
Public Network

Anonymity of endpoints of communication

Bi-directional and near real-time communication

Resistance to eavesdropping from
• Network
• Outside Observers of the network
 Can be substituted for sockets
26
Protocol Operation
 Establish Anonymous connection through a series of ORs (Onion Router)
instead of a direct socket connection to the destination.
 “Initiator” makes a socket connection to an Application Specific Proxy on
first OR.
 Onion Proxy defines the route



Constructs a layered structure (Onion) and sends it through the network
to establish the Virtual Circuit (same as ATM Virtual Circuit
Establishment with VPI/VCI).
Onion passes through the entire path to the responder proxy => all
involved ORs are initialized with relevant information to encrypt/
decrypt forward/backward data.
Now, initiator’s proxy starts sending data through the anonymous
connection.
28
Protocol Operation (contd...)
 Each layer of the onion defines a next hop in the route.
 An OR, on receiving an onion




peels off its layer
chooses new values for incoming/outgoing VCIs.
identifies next hop
sends the embedded onion to that next hop OR.
 Each Onion Layer also contains Keys


Keys are used for crypting data sent forward/backward.
When the onion bounces along, they are stored at each intermediate
hop (i.e., OR).
 Last OR forwards data to Responder’s Proxy that


Sits on the firewall of the responder’s sensitive site.
Passes data between ORN and the responder.
29
The Onion (contd...)
 What happens to the onion at each hop?




It shrinks in size
Compromised nodes can infer route information from this
monotonically diminishing size.
So, a random bit string is appended to the end of the
payload before forwarding.
Even ‘constant’ size onion might be traced unless all onions
have the same size, so the size of the onion is (universally)
standardized (fixed).
31
Reply Onion
 How to reply anonymously?



Send a reply onion embedded as payload in the forward onion
Responder proxy sends this Reply Onion on the reverse path till
the Initiator’s Proxy
VC set-up by Forward Onion, so data path is already established.
 The Reply Onion is



Exactly the same as the Forward onion except that the innermost
payload has
• Enough information to enable the initiator’s proxy to reach
the initiator
• All cryptographic function/key pairs that are to crypt data
along the Virtual Circuit
Processing it is same as processing a Forward Onion
Usable only once
• So multiple reply onions need to be sent if multiple replies are
required.
33
Crowd
“blending into a crowd”
i.e. hiding one’s actions within the actions of many others
How does it work?
jondo
Request admittance
Information to enable
jondo to participate
blender
34
Crowd (contd...)
Request
from browser
Crowd
Geographically diverse group
35
Crowd (features)
 Data may be in the clear: no protection wrt
global eavesdropper
 No attempt to pad to avoid flow analysis, no
attempt to prevent sender-receiver unlinkability
 Used for web transactions: browser uses local
johndo as proxy for itself, blender sends data
of remote johndo’s to this johndo
 Paths are selected randomly and hop-by-hop
(not a priori circuit selection as in tor)
36
Hordes
 Take advantage of multicast communication
Destination address is a multicast group
address, which provides receiver anonymity.
 It is difficult to determine the membership of
a multicast group.
 Even if some group memberships are
discovered, anonymity can still be provided.

37
Hordes (contd...)
 Simple protocol
Join a multicast group.
 Initiator sends request using group address.

• can use either crowds or onion routing for forward path
 Server
sends reply to the group address.
 Initiator receives the reply.
 Non-initiators just ignore the reply.
38
Incomparable Public Keys
 Take advantage of a novel public key
scheme
Traditional scheme: one private key, one public
key
 The new scheme: one private key, but multiple
public keys
 Feature: one cannot tell whether two public
keys map to the same or different private keys

39
Incomparable Public Keys (contd…)
 Plus multicast to provide encryption and
anonymity
Join a multicast group.
 Initiator sends request using group address
with a public key.
 Server sends reply, encrypted with the public
key, to the group address.
 Initiator receives the reply and decrypt it.
 Non-initiators just ignore the reply.
 Initiator sends request to the same/another
server using another public key

40
Conclusion
 What are anonymous communications?
Why?
 Four representative schemes
Onion Routing
 Crowd
 Hordes
 Incomparable Public Keys

41