Transcript slides - Ravi Jain

Cryptographically Protected Prefixes
for Location Privacy in IPv6
Jonathan Trostle, Hosei Matsuoka*,
Muhammad Mukarram Bin Tariq, James Kempf,
Toshiro Kawahara and Ravi Jain
DoCoMo Communications Laboratories USA, Inc.
* Multimedia Laboratories, NTT DoCoMo, Inc.
Outline



Location Privacy Problem in IP networks
Related Works
Proposal of Cryptographically Protected Prefixes (CPP)





Simple Architecture (easily understandable)
Secure Architecture
Security Considerations
Implementation and Performance Measurements
Conclusions
Location Privacy Problems in IP Networks
IP networks use prefix based routing
Subnets often
have
geographical
correspondence
All hosts in a
subnet have
same subnet
prefix
IP address
shows your
geographical
location
IP address
shows whom
you are
together with
Just as our postal addresses are
hierarchically arranged with country,
state, city, …, the IP addresses are
also structured for routing efficiency.
Prefix (es)
Suffix
Related Works

Network Layer Solutions



Mobile IPv6
Hierarchical Mobile IPv6 (HMIPv6)
Application Layer (Overlay) Solutions



Onion Routing
Freedom Network
Crowds, Tarzan, etc.
How do they provide Location Privacy
Overlay Approaches
Mobile IP with Home Agent
Mobile IP with
Route Optimization
Care-of-Address
Foreign Network
This user does not know
the correspondent’s
care-of-address which shows
the user’s actual location.
(Onion routing, Freedom)
Internet
Home Address
HA
Home Network
Onion/Freedom
Overlay Routers
Both approaches cannot provide communications with the
optimal route between two endpoints
Qualitative Comparison of Related Works
Quality of Service
Goal of our project
Desired Location Privacy,
Comparable with today’s CS Telecom
No Additional Routing
Delay
Optimal
Limited
Triangular
Routing
Mobile IPv6 Route
Optimization
HMIPv6
Triangular
Mobile IP Home Agent
Huge Routing/
Performance
Overhead
App Overlay (Onion, Freedom)
Subnet
Level
Several
Subnets
Visited Home
Domain Domain
Global
Degree of Location Privacy
Design Policies of Our Approach (CPP)
 Provide Location Privacy within a domain
 Optimal Routing (No additional Routing Delay)
It is important for some real-time applications.
 Full Compatibility with other Internet Protocols
(Mobile IP, IPsec, Diffserv, etc.)
 No Single Point of Failure
Structure of IP address
IPv4 Address
Network Prefix
32bits
Host Suffix
IPv6 Address
Network Prefix
typically 64bits
Both IPv4 and IPv6 addresses have
the similar structure consisting of
Network Prefix and Host Suffix,
and the Network Prefix is related to
the geographical location.
128bits
Host Suffix
typically 64bits
Advantages of applying to IPv6
 Large space of network prefix provides strong anonymity of the location.
 The fixed boundary between prefix and suffix can simplify the system.
Basic Concept
Replacing the actual prefix with a host-specific encrypted prefix
Routable IPv6 address
P0
PR
Mi
Prefix-encrypted IPv6 address P' ( R , i )  PR  Encrypt ( Key, Mi )
P0
P`(R,i)
Routable IPv6 address
P0


PR
Prefix
Encryption
Mi
PR  P' ( R , i )  Encrypt ( Key, Mi )
Mi
Prefix
Decryption
End-hosts use prefix-encrypted IPv6 address for their communications.
Routers obtain the routable IPv6 address through the decryption of the
encrypted prefix. (Routers have the key for decryption.)
Simple Architecture (easily understandable)
Routers inside Privacy Domain share the secret key and obtain
the routable prefix prior to routing table searches.
P0 P’(R,i)
Mi
0
P0 P’(R,i)
P0 P’(R,i)
Mi
P0 P’(R,i)
Mi
P0 P’(R,i)
4
Mi
Mi
PR
3
PR
5
1
2
PR
P0 P’(R,i)
Mi
Privacy Domain
PR
Routers inside Privacy Domain
decrypt the secondary prefix P`(R, i)
to find the actual routing prefix and
route the packet accordingly until
the packet reaches the desired
destination
Routers outside Privacy Domain
look at the prefix P0 and route the
packet to the privacy domain, there
are no longer matches than P0
outside privacy domain
What changes in the Routers
Prefix Of Destination
Destination
Route
Destination
Address
Packet
Prefix of
Destination
Destination Route
Longest
Prefix
Match
Packet
Dispatcher
Key
Packet
Dispatcher
Destination
Address
Decrypt
Small change, can be
implemented in hardware
for acceleration
Longest
Prefix
Match
Packet
Pre
Processing
Routers Modified
for Location Privacy
Extract
Prefix
Packet
Pre
Processing
Conventional
Routers
Packet
There is no change in conventional routing protocols (RIP, OSPF, etc.)
Secure Architecture
Border Gateway
Level 1
R1
Router
R7
R2
Level 2
Level 3
R8
R3
R4
Level 4
R5
Host
R6
Routers are assigned levels
based on their “hop-count”
from the border router.
Routers at different level use
different key and decrypt
different part of prefix which
is necessary and sufficient for
routing table searches.
A compromised router cannot get
all user’s location.
Structure of IP addresses with CPP
Common Prefix for
Global Routing
Key version bit for
key rotation
The Prefix consists of several small
encrypted components – one corresponding
to each level
P0 V X1 X2 X3 …… Xn
M (the suffix)
128 Bits
P1

H(L1, M)
Pk  H(Ln, M)
H( ) is a encryption or
hash function
Any router at level “k” can use its level key Lk to decrypt Pk and given
P1,…Pk-1 from the upper level router with hop-by-hop option, it
obtains routable prefix and forward packets correctly to next hop.
Security Considerations

Eavesdropping on the same link
Eavesdroppers can realize the location of the other hosts
on the same network link by snooping the traffic of the link.
CPP should use some other techniques to prevent traffic analysis.

Guessing Attack
Attackers use connection trials in various subnets and guess H(Li, M)
using plain prefixes of the location where the response is received.
Privacy Domain changes the secret key for some interval.
CPP Extended Address (to be explained next)

ICMP packets
ICMP packets from a router in the middle of the connection
give the sender the hints of the receiver’s location.
Router must not use the real source address for ICMP packets.
No Traceroute
Guessing Attacks and CPP Extended Address
Guessing Attacks
Attackers try to obtain H(Li, Mv) for tracking the victim who has the suffix Mv,
because once they obtain H(Li, Mv), they can easily track the victim.
Reason behind this attack is that H(Li, Mv) is a constant value regardless of its location.
CPP Extended Address
Using H(Li, <Mv, P1, … , Pi-1, Xi+1, … Xk>) instead of H(Li, Mv)
provides more robust security against Guessing Attacks.
Probability that the adversary obtains the prefix components P1 … Pj of the victim’s address is
j
1
 ( x( s  2) p s  2  x(0)) where
2
p  max{ p1 , p2 ,... p j } ,    (1  pi )
s is the number of subnets searched
i 1
x(a)  x2 a 2  x1a  x0 with
x2  1 /( p  1), x1  (3  2 px2 ) /( p  1), x0  (2  px2  px1 ) /( p  1)
Implementation
FreeBSD 4.8 Kernel Structure
Modified ip6_input() function
Transport
Protocol
Cryptographic Functions used:
ip6_input
ip6_forward
AES, SHA-1
ip6_output
decrypt & lookup
ip6intr
nd6_output
routing
table
start of
measure
Time measurement of
one packet forwarding
input queue
end of
measure
output queue
Network
Interfaces
Performance Results
Software Router Specification:
OS:
FreeBSD 4.8
CPU:
1GHz
Memory:
512MB
Type of Router 
Unmodified
Using SHA-1
Using AES
One Packet Forwarding Time
6 micro sec
11 micro sec
9 micro sec
Packet Rate
166,666 pps
90,909 pps
111, 111 pps
Data Rate
(1Kbyte per packet)
1300 Mbps
727 Mbps
888 Mbps
Conclusions
CPP alleviates IPv6 location privacy problem
Traditional Approaches
CPP
Routing Overhead
No Routing Overhead
Poor Compatibility with other
Internet protocols
Full Compatibility with other
Internet protocols
Stateful and Per-packet
processing
No state, Good Performance
Require Small Changes in
Routers
Rekey (Backup slides)
Routers change the key(A) and the key(B) alternately, and encrypt prefixes
with the newer key. The duration from finishing changing the key to starting
changing the other key must be more then the lifetime of prefixes.
more than
prefix lifetime
Key(A)
more than
prefix lifetime
more than
prefix lifetime
Key(B)
rekey
Key(B)
rekey
Key(A)
rekey
Key(A)
Advertised Addresses (encrypted with the newer key)
Scambled
address (A)
Scambled
address (B)
Scambled
address (A)
Scambled
address (B)
Scambled
address (A)
Timeline
rekey
is long enough to rekey on all routers even if it is done manually.
Implementation (backup slide)
P0(48 bits)
Q(16 bits)
offset
M(64 bits)
128 bits input message adding
zero-padding of 64 bits to M
target
prefix
AES or SHA-1
(block cipher or Hash)
router’s secret key
(128 bits)
128 bits output message
prefix components
of higher routers
Exclusive-OR
hop-by-hop
option
concatenation
real prefix components
needed for routing
table searches
Inter-domain Extension (Backup slide)
 All domains use the same P0 (2001:1234:). P0 does not reveal the user’s domain.
 All domains use the different global AS numbers.
BGP message
BGP message
Prefix: 2001:1234
AS number: 2
Prefix: 2001:1234
AS number: 1
Domain B
Domain A
P0 prefix: 2001:1234::
AS number: 2
P0 prefix: 2001:1234::
AS number: 1
Europe
USA
Asia
BGP message
Prefix: 2001:1234
AS number: 3
Domain C
P0 prefix: 2001:1234::
AS number: 3
Given the multiple BGP messages of the
same set of destinations, the one with the
highest degree of preference is selected.
Packets destined to P0 would be
delivered to the nearest CPP domain
Inter-Domain Extension (Backup slide)
CPP address
X1 H (key, Mi )
Nearest
border gateway
Domain B
shows which domain
the host(i) resides in.
tunneling
Europe USA
Asia
Domain C
P0 X1 X2 X3 X4 M (Host Suffix)
P1 P2 P3 P4
Domain A
host(i)
International traffic is
slightly triangle route
Domestic traffic is
always optimal route
A little more about CPP (Backup slide)
 For optimal routing, the suffix is computed such that any router can
determine if it is a cross over router
We use it for optimal routing, but can also be used for other techniques.
 How do we do this
Each router R in Privacy Domain has a unique key KR
M is chosen for subnet of router “r” such that:
H(KR, M) equals ZERO if R
C
Set of all cross over
routers:
C={R1, R2, R3, R4}
R1
C
R2
H(KR, M) not equals ZERO if R
Where C is set of all cross over routers for router “r”
Fine Detail: No two cross over routers can have same level,
if they are directly connected
R9
R8
R5
R3
R4
R6
R7
“r”