Preventing Active Timing Attacks in Low-Latency Anonymous Communication

 
Preventing Active Timing Attacks in Low-
Latency Anonymous Communication
 
The 10
th
 Privacy Enhancing Technologies Symposium
July 2010
 
Joan Feigenbaum
Yale University
 
Aaron Johnson
University of Texas
at Austin
 
Paul Syverson
Naval Research
Laboratory
 
1
 
Problem
 
2
 
Problem
 
Users
 
Onion
Routers
 
Destinations
 
Onion routing suffers from timing attacks.
 
Adversary
 
3
 
Problem
 
Users
 
Onion
Routers
 
Destinations
 
Onion routing suffers from timing attacks.
 
Adversary
 
4
Encrypted
Unencrypted
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Adversary
 
Users
 
Destinations
 
5
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Adversary
 
Users
 
Destinations
 
6
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Adversary
 
Users
 
Destinations
 
7
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Adversary
 
Users
 
Destinations
 
8
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Passive timing attack
 
Adversary
 
Users
 
Destinations
 
9
 
Problem
 
Padding Schemes
 
1.
Constant-rate padding
 
2.
Variable-rate padding
1
 
1. 
Timing analysis in low-latency mix
networks: Attacks and defenses. 
Shmatikov &
Wang, ESORICS 06
.
 
2. 
Dependent link padding algorithms for low
latency anonymity systems
. Wang and Srinivasan,
CCS 08
.
 
3.
Minimal padding
2
 
10
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Passive timing attack
 
Adversary
 
Users
 
Destinations
 
11
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Passive timing attack
 
Adversary
 
Users
 
Destinations
 
12
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Passive timing attack
 
Adversary
 
Users
 
Destinations
 
13
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Passive timing attack
 
Adversary
 
Users
 
Destinations
 
14
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Passive timing attack
 
Active timing attack
 
 
Adversary
 
Users
 
Destinations
 
15
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Passive timing attack
 
Active timing attack
 
 
Adversary
 
Users
 
Destinations
 
16
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Passive timing attack
 
Active timing attack
 
 
Adversary
 
Users
 
Destinations
 
17
 
Problem
 
Onion
Routers
 
Onion routing suffers from timing attacks.
 
Passive timing attack
 
Active timing attack
 
 
Adversary
 
Users
 
Destinations
 
18
 
Problem
 
Onion routing suffers from timing attacks.
 
How bad is it?
 
Tor
: 
 
250 
guard
 routers
 
500 
exit
 routers
 
7571 unique users daily per guard
1
 
Top 2% contribute 50% bandwidth
1
 
1. McCoy, Bauer, Grunwald, Kohno, and Sicker. 
Shining light in dark places:
Understanding the Tor network
. PETS 2008.
 
Case 1
: Adversary runs one
guard and one exit.
# comp. = 7571/500
 
    
 15
 
Case 2
: Adversary’s guard and
exit are in top 2% of bandwidth.
# users = 7571*.5/.02
 
  
 189275
# comp. = 189275*.5/(500*.02)
 
    
 9464
 
19
 
Results
 
20
 
Results
 
1.
Protocol for defeating active timing attacks 
given
a padding scheme
Reduces active timing attacks to passive timing
attacks
Uses redundancy and timestamps
2.
Provides a tradeoff between anonymity and
performance
3.
Protects against adversaries smaller than half of
the network.  This is optimal.
4.
Measurements on Tor suggest it may be usable
in practice.
 
21
 
Model
 
22
 
Model
 
Users: 
U
Routers: 
R
Destinations: 
D
Adversary: 
A
R, b 
=
 
|
A
|
/
|
R
|
Probabilistic delays
Random link delay: 
d
(
r
,
s
), 
r
,
s
R
Random processing delay: 
d
(
r
), 
r
R
Synchronized clocks with tolerance 
Padding scheme 
P
(
x
)
Input: New connection information, 
x
Output: Timing patterns in both directions, 
0
,
 
1
Provides 
S
u
 
U
, users with the same timing as 
u
 
 
23
 
Protocol
 
24
 
Protocol
 
To the destination
 Multiple entry points
 One exit point
 Entering data encrypted
 Exiting data
unencrypted
 
From the destination
Multiple exit points
 One entrance point
 Exiting data encrypted
 Entering data
unencrypted
 
25
 
Protocol
 
To the destination
 
26
 
Protocol
 
To the destination
 
27
 
Protocol
 
To the destination
 
Take 0 (onion routing):
 
Pr[compromised] = 
b
2
 
28
 
Protocol
 
To the destination
 
Take 0 (onion routing):
 
Pr[compromised] = 
b
2
 
29
 
Protocol
 
To the destination
 
Take 0 (onion routing):
 
Pr[compromised] = 
b
2
Take 1 (two entry points):
 
Pr[compromised] = 
b
3 
(3-2
b
)
 
30
 
Protocol
 
To the destination
 
Take 0 (onion routing):
 
Pr[compromised] = 
b
2
Take 1 (two entry points):
 
Pr[compromised] = 
b
3 
(3-2
b
)
 
31
 
Protocol
 
To the destination
 
Take 0 (onion routing):
 
Pr[compromised] = 
b
2
Take 1 (two entry points):
 
Pr[compromised] = 
b
3 
(3-2
b
)
 
32
 
Protocol
 
To the destination
 
Take 0 (onion routing):
 
Pr[compromised] = 
b
2
Take 1 (two entry points):
 
Pr[compromised] = 
b
3 
(3-2
b
)
Take 2 (
k
 entry points):
 
Pr[compromised] = 
b
2 
(1-(1-
b
)
k
+(1-
b
)
b
k
-1
)
 b
2
 
k
 
33
 
Protocol
 
To the destination
 
Take 0 (onion routing):
 
Pr[compromised] = 
b
2
Take 1 (two entry points):
 
Pr[compromised] = 
b
3 
(3-2
b
)
Take 2 (
k
 entry points):
 
Pr[compromised] = 
b
2 
(1-(1-
b
)
k
+(1-
b
)
b
k
-1
)
 b
2
Take 3 (layered mesh)
 
log
l
 
l
 
34
 
Protocol
 
To the destination
 
Take 0 (onion routing):
 
Pr[compromised] = 
b
2
Take 1 (two entry points):
 
Pr[compromised] = 
b
3 
(3-2
b
)
Take 2 (
k
 entry points):
 
Pr[compromised] = 
b
2 
(1-(1-
b
)
k
+(1-
b
)
b
k
-1
)
 b
2
Take 3 (layered mesh)
 
log
l
 
l
 
35
 
Protocol
 
To the destination
 
Take 0 (onion routing):
 
Pr[compromised] = 
b
2
Take 1 (two entry points):
 
Pr[compromised] = 
b
3 
(3-2
b
)
Take 2 (
k
 entry points):
 
Pr[compromised] = 
b
2 
(1-(1-
b
)
k
+(1-
b
)
b
k
-1
)
 b
2
Take 3 (layered mesh)
 
log
l
 
l
 
36
 
Protocol
 
To the destination
 
Problem
: Adversary can make delays more likely
even if not certain.
 
Solution
: Use timestamps.
 
Arrival prob
.: .95 = Pr[
d
(
r
,
s
) + 
d
(
s
)
 
d
*(
r
,
s
)]
 
i
th send time: t
i
 = 
t
i
-1
+max
j
,
k
 
d
*(
r
(
i
-1)
j
,
r
i
,
k
)+
 
37
 
Protocol
 
From the destination
 
38
 
Protocol
 
From the destination
 
 Path of length 
k
 Each router has and enforces
timing pattern.
 
39
 
Protocol
 
From the destination
 
 Path of length 
k
 Each router has and enforces timing pattern.
 
40
 
Protocol
 
Setup 
(
l
,
k
,
p
,
c
)
 
1.
Randomly select the routers for 
c
 fixed
l
log
l
 meshes with 
k
-length return paths.
2.
Determine delays 
d
*(
r
,
s
) such that
p
 = Pr[
d
(
r
,
s
) + 
d
(
r
)
 
d
*(
r
,
s
)]
 
User
 
1.
Choose (mesh,path) pair (
M
,
P
).
2.
Obtain padding (
0
, 
1
) = 
P
(
x
).
3.
Randomly select identifiers 
n
s
i
.
4.
Generate private keys 
k
s
i
.
5.
Send O(
1
),
n
si
, 
n
si
, 
k
s
i
 through 
M 
to 
s
i
P.
 
Network
 
41
 
Analysis
 
42
 
Analysis
 
Theorem 1
:
  lim
l
,
k

 Pr[compromise] =
 
0
 
b
 < ½
¼
 
b
 = ½
b
 
b
 > ½
 
43
 
Analysis
 
Theorem 1
:
  lim
l
,
k

 Pr[compromise] =
 
0
 
b
 < ½
¼
 
b
 = ½
b
 
b
 > ½
 
Theorem 2
:  Pr[compromise] = 
(
l 
log(
b
)-log(1-
b
)
)
 
44
 
Analysis
 
Theorem 1
:
  lim
l
,
k

 Pr[compromise] =
 
0
 
b
 < ½
¼
 
b
 = ½
b
 
b
 > ½
 
Theorem 2
:  Pr[compromise] = 
(
l 
log(
b
)-log(1-
b
)
)
 
Theorem 3
:  Let 
c
(
b
) be the probability of
compromise in some forwarding topology.
If b < ½, then  
c
(
b
) < 
 
 
c
(1-
b
) > 1-
b- 
(1-
b
)/
b
.
 
45
 
Analysis
 
Theorem 1
:
  lim
l
,
k

 Pr[compromise] =
 
0
 
b
 < ½
¼
 
b
 = ½
b
 
b
 > ½
 
Theorem 2
:  Pr[compromise] = 
(
l 
log(
b
)-log(1-
b
)
)
 
Theorem 3
:  Let 
c
(
b
) be the probability of
compromise in some forwarding topology.
If b < ½, then  
c
(
b
) < 
 
 
c
(1-
b
) > 1-
b- 
(1-
b
)/
b
.
 
Theorem 4
:
1.
 
Latency is (
l
+
k
+
2
).
2.
 
# of messages is 
2
log
l
+(
I
-
1)
(log
l
)
2
 +
k+2.
 
46
 
Analysis
 
Mesh routing vs. Onion routing
 
47
 
Tor Measurements
 
Measured delays in Tor for a month (3/09).
Delays for new connections and 400-byte packets.
Used empirical measurements for delay distributions
per router per 6hr. Period.
 
Analysis
 
48
 
Relative added connection
delays  (p=.95)
 
Relative added packet
delays (p=.95)
 
p(50) 
 1.48
 
p(50) 
 2.95
 
Conclusion
 
Reduced active timing attacks to designing
padding schemes.
Protocol allows system to trade off anonymity
and performance.
Future work
Usable padding scheme
Free routes
Protection from DOS attacks
 
49
 
Protocol
 
To the destination
 
Message Onion
 
Message 
M
Random numbers 
n
r
i
, 
n
s
i
Private key 
k
r
{
M
}
r
 
denotes encryption with 
r
’s public key
Destination 
d
 
O(
M
) = {
n
r
1
, 
t
1
, {
n
r
2
, 
t
2
, 
{
n
r
, 
d
, 
n
s
1
, 
k
r
, 
M
}
r
 
}
r
2
}
r
1
 
50
 
Protocol
 
To the destination
 
User
 
Router r
i
 
1.
Let 
M
 be waiting message or dummy if none.
2.
When pattern 
0 
instructs, send O(
M
) to each
router in first mesh layer.
 
1.
On incoming
 {
n
r
i
, 
t
, 
M
}
r
i
,
  if 
n
r
i 
is previously unseen,
    send 
M 
at time 
t 
to each router in next layer.
 
51
 
Protocol
 
From the destination
 
{
M
}
k
 
denotes encryption with private key 
k
.
n
s
i,
 n
s
i
+1
 
are identifiers given to 
s
i 
by user
k
s
i 
is private key given to 
s
i
 by user
1  
i
s return pattern given by user
 
Router s
i
 
1.
On incoming
 <
n
s
i
,
M
>,
  place 
<
n
s
i
+1
, 
{
n
s
i
,
M
}
k
s
i
> into queue.
2.
When pattern 
1 
instructs,
  take <
n
s
i
+1
, 
M’
> 
from queue (or dummy)
    send 
to 
s
i
+1
.
 
52
Slide Note
Embed
Share

This research addresses the vulnerabilities of onion routing to timing attacks and proposes solutions to prevent active timing attacks, focusing on low-latency anonymous communication systems. Various problems related to timing attacks in onion routing are analyzed, including the role of adversaries, users, onion routers, and destinations. The study discusses different padding schemes and timing analysis techniques to defend against these attacks effectively.


Uploaded on Sep 06, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Preventing Active Timing Attacks in Low- Latency Anonymous Communication Joan Feigenbaum Yale University Aaron Johnson University of Texas at Austin Paul Syverson Naval Research Laboratory The 10thPrivacy Enhancing Technologies Symposium July 2010 1

  2. Problem 2

  3. Problem Onion routing suffers from timing attacks. Adversary Users Onion Routers Destinations 3

  4. Problem Onion routing suffers from timing attacks. Adversary Unencrypted Encrypted Users Onion Routers Destinations 4

  5. Problem Onion routing suffers from timing attacks. Adversary Users Onion Routers Destinations 5

  6. Problem Onion routing suffers from timing attacks. Adversary Users Onion Routers Destinations 6

  7. Problem Onion routing suffers from timing attacks. Adversary Users Onion Routers Destinations 7

  8. Problem Onion routing suffers from timing attacks. Adversary Users Onion Routers Destinations 8

  9. Problem Onion routing suffers from timing attacks. Passive timing attack Adversary Users Onion Routers Destinations 9

  10. Problem Padding Schemes 1. Constant-rate padding 2. Variable-rate padding1 3. Minimal padding2 2. Dependent link padding algorithms for low latency anonymity systems. Wang and Srinivasan, CCS 08. 1. Timing analysis in low-latency mix networks: Attacks and defenses. Shmatikov & Wang, ESORICS 06. 10

  11. Problem Onion routing suffers from timing attacks. Passive timing attack Adversary Users Onion Routers Destinations 11

  12. Problem Onion routing suffers from timing attacks. Passive timing attack Adversary Users Onion Routers Destinations 12

  13. Problem Onion routing suffers from timing attacks. Passive timing attack Adversary Users Onion Routers Destinations 13

  14. Problem Onion routing suffers from timing attacks. Passive timing attack Adversary Users Onion Routers Destinations 14

  15. Problem Onion routing suffers from timing attacks. Passive timing attack Active timing attack Adversary Users Onion Routers Destinations 15

  16. Problem Onion routing suffers from timing attacks. Passive timing attack Active timing attack Adversary Users Onion Routers Destinations 16

  17. Problem Onion routing suffers from timing attacks. Passive timing attack Active timing attack Adversary Users Onion Routers Destinations 17

  18. Problem Onion routing suffers from timing attacks. Passive timing attack Active timing attack Adversary Users Onion Routers Destinations 18

  19. Problem Onion routing suffers from timing attacks. How bad is it? Tor: 250 guard routers 500 exit routers 7571 unique users daily per guard1 Top 2% contribute 50% bandwidth1 Case 1: Adversary runs one guard and one exit. # comp. = 7571/500 15 Case 2: Adversary s guard and exit are in top 2% of bandwidth. # users = 7571*.5/.02 189275 # comp. = 189275*.5/(500*.02) 9464 1. McCoy, Bauer, Grunwald, Kohno, and Sicker. Shining light in dark places: Understanding the Tor network. PETS 2008. 19

  20. Results 20

  21. Results 1. Protocol for defeating active timing attacks given a padding scheme Reduces active timing attacks to passive timing attacks Uses redundancy and timestamps 2. Provides a tradeoff between anonymity and performance 3. Protects against adversaries smaller than half of the network. This is optimal. 4. Measurements on Tor suggest it may be usable in practice. 21

  22. Model 22

  23. Model Users: U Routers: R Destinations: D Adversary: A R, b =|A|/|R| Probabilistic delays Random link delay: d(r,s), r,s R Random processing delay: d(r), r R Synchronized clocks with tolerance Padding scheme P(x) Input: New connection information, x Output: Timing patterns in both directions, 0, 1 Provides Su U, users with the same timing as u 23

  24. Protocol 24

  25. Protocol To the destination Multiple entry points One exit point Entering data encrypted Exiting data unencrypted From the destination Multiple exit points One entrance point Exiting data encrypted Entering data unencrypted 25

  26. Protocol To the destination 26

  27. Protocol To the destination 27

  28. Protocol To the destination Take 0 (onion routing): Pr[compromised] = b2 28

  29. Protocol To the destination Take 0 (onion routing): Pr[compromised] = b2 29

  30. Protocol To the destination Take 0 (onion routing): Pr[compromised] = b2 Take 1 (two entry points): Pr[compromised] = b3 (3-2b) 30

  31. Protocol To the destination Take 0 (onion routing): Pr[compromised] = b2 Take 1 (two entry points): Pr[compromised] = b3 (3-2b) 31

  32. Protocol To the destination Take 0 (onion routing): Pr[compromised] = b2 Take 1 (two entry points): Pr[compromised] = b3 (3-2b) 32

  33. Protocol To the destination k Take 0 (onion routing): Pr[compromised] = b2 Take 1 (two entry points): Pr[compromised] = b3 (3-2b) Take 2 (k entry points): Pr[compromised] = b2 (1-(1-b)k+(1-b)bk-1) b2 33

  34. Protocol To the destination logl l Take 0 (onion routing): Pr[compromised] = b2 Take 1 (two entry points): Pr[compromised] = b3 (3-2b) Take 2 (k entry points): Pr[compromised] = b2 (1-(1-b)k+(1-b)bk-1) b2 Take 3 (layered mesh) 34

  35. Protocol To the destination logl l Take 0 (onion routing): Pr[compromised] = b2 Take 1 (two entry points): Pr[compromised] = b3 (3-2b) Take 2 (k entry points): Pr[compromised] = b2 (1-(1-b)k+(1-b)bk-1) b2 Take 3 (layered mesh) 35

  36. Protocol To the destination logl l Take 0 (onion routing): Pr[compromised] = b2 Take 1 (two entry points): Pr[compromised] = b3 (3-2b) Take 2 (k entry points): Pr[compromised] = b2 (1-(1-b)k+(1-b)bk-1) b2 Take 3 (layered mesh) 36

  37. Protocol To the destination Problem: Adversary can make delays more likely even if not certain. Solution: Use timestamps. Arrival prob.: .95 = Pr[d(r,s) + d(s) d*(r,s)] ith send time: ti = ti-1+maxj,kd*(r(i-1)j,ri,k)+ 37

  38. Protocol From the destination 38

  39. Protocol From the destination Path of length k Each router has and enforces timing pattern. 39

  40. Protocol From the destination Path of length k Each router has and enforces timing pattern. 40

  41. Protocol Setup (l,k,p,c) Network 1. Randomly select the routers for c fixed l logl meshes with k-length return paths. 2. Determine delays d*(r,s) such that p = Pr[d(r,s) + d(r) d*(r,s)] User 1. Choose (mesh,path) pair (M,P). 2. Obtain padding ( 0, 1) = P(x). 3. Randomly select identifiers nsi. 4. Generate private keys ksi. 5. Send O( 1),nsi, nsi, ksi through M to si P. 41

  42. Analysis 42

  43. Analysis 0 b b < b = b > Theorem 1: liml,k Pr[compromise] = 43

  44. Analysis 0 b b < b = b > Theorem 1: liml,k Pr[compromise] = Theorem 2: Pr[compromise] = (l log(b)-log(1-b)) 44

  45. Analysis 0 b b < b = b > Theorem 1: liml,k Pr[compromise] = Theorem 2: Pr[compromise] = (l log(b)-log(1-b)) Theorem 3: Let c(b) be the probability of compromise in some forwarding topology. If b < , then c(b) < c(1-b) > 1-b- (1-b)/b. 45

  46. Analysis 0 b b < b = b > Theorem 1: liml,k Pr[compromise] = Theorem 2: Pr[compromise] = (l log(b)-log(1-b)) Theorem 3: Let c(b) be the probability of compromise in some forwarding topology. If b < , then c(b) < c(1-b) > 1-b- (1-b)/b. Theorem 4: 1. Latency is (l+k+2). 2. # of messages is 2logl+(I-1)(logl)2+k+2. 46

  47. Analysis Mesh Onion Routing b l w Pr[comp.] Messages Pr[comp.] Messages .05 .05 3 4 3 3 .0002 .00003 29 39 .0025 .0025 8 10 .1 4 3 .0007 39 .01 10 .25 4 2 .0303 22 .0625 10 Mesh routing vs. Onion routing 47

  48. Analysis Tor Measurements Measured delays in Tor for a month (3/09). Delays for new connections and 400-byte packets. Used empirical measurements for delay distributions per router per 6hr. Period. Relative added connection delays (p=.95) p(50) 1.48 Relative added packet delays (p=.95) p(50) 2.95 48

  49. Conclusion Reduced active timing attacks to designing padding schemes. Protocol allows system to trade off anonymity and performance. Future work Usable padding scheme Free routes Protection from DOS attacks 49

  50. Protocol To the destination Message M Random numbers nri, nsi Private key kr {M}rdenotes encryption with r s public key Destination d Message Onion O(M) = {nr1, t1, {nr2, t2, {nr, d, ns1, kr, M}r }r2}r1 50

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#