Transcript Mark - Computer Science and Engineering

Invisible Traceback in
the Internet
Dong Xuan
Department of Computer Science and Engineering
The Ohio-State University
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
Traceback in the Real World
李世民
李立峰
李亚南
李勇
李强
Animal traceback
Wuhan Univ., 9/17/2008
Mail traceback
Dong Xuan/The Ohio-State Univ.
李文
李飞
Family traceback
2/32
Traceback in the Internet
 Trace the origin of a packet (or a message)
 Trace illegal file distributor and downloader
 Trace two cyberspace criminals communicating
with each other
Investigator
Evil
Wuhan Univ., 9/17/2008
Evil
Dong Xuan/The Ohio-State Univ.
3/32
Invisible Traceback in the Internet
 Investigator’s activity of traceback is
unaware to suspects (e.g. illegal file downloaders and cyberspace criminals.)
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
4/32
Significance of Invisible Traceback
 The Internet has become a breeding ground for
a variety of crimes
Credit Card Fraud
Illegal Downloading
Cyber-Terrorism
Virus Distribution
 Traceback makes the above crimes accountable
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
5/32
Significance of Invisible Traceback
(Cont’d)
 Invisibility is critical, otherwise,
 The criminals will simply stop communicating with
each other, thereby evading further detection.
 They may even develop countermeasures to fool
or mislead investigators etc.
 Invisible traceback is an important network
forensic technique for legal surveillance
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
6/32
Challenges in Invisible Traceback
 The nature of the Internet
 Large scale and loose control
 Destination oriented routing and forwarding –
easily spoofing source IP address
 No intimidate node traffic recording
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
7/32
Challenges in Invisible Traceback
 The availability of anonymous systems
Receiver
Sender
B to R
B
S to A
A
Human Spy Network
Wuhan Univ., 9/17/2008
A to B
Anonymous Communication
Dong Xuan/The Ohio-State Univ.
8/32
Our Focus
Sender
Receiver
Anonymous
Channel
 Suspect Sender is sending traffic through an
encrypted and anonymous channel, how can
Investigator trace and confirm who receiver is?

Wei Yu, Xinwen Fu, Steve Graham, Dong Xuan and Wei Zhao, DSSS-Based Flow
Marking Technique for Invisible Traceback, in Proc. of IEEE Symposium on Security
and Privacy (oakland), May 2007, pp. 18-32.
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
9/32
Outline
 Flow marking-based traceback technique
 Prototyping
 Turning into a real-world tool
 Related work
 Final remarks
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
10/32
Intuitive Solution
 Packet marking
 Put some marks into packets,
Sender
Receiver
Anonymous
Network
 However,
 Packets are encrypted in anonymous systems,
careless mark will fail decryption
 Visible to the attacker
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
11/32
Our Solution
 Flow marking
Change traffic flow rates
 Traffic rate changes represent a “mark”, i.e. a
special secret code

Sender
Anonymous
Network
Anonymous
Channel
Interferer
Investigator
Receiver
Sniffer
Investigator knows that Sender communicates with Receiver!
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
12/32
Key Differences between Packet
Marking and Flow Marking
 Packet Marking
 Mark is embedded in packets
 Packet content is changed
 It is very difficult, if impossible, to hide such
changes when packets are encrypted
 Flow Marking
 Mark is embedded in flow rate changes
 No packet content is changed
 It is feasible to hide flow rate changes in the
Internet, typically with dynamic traffic
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
13/32
Questions to Flow Marking
 A “small” question

How is a mark embedded into flow rate changes?
 Two “big” questions
 How to make the traffic rate changes “invisible”?
 How to make the traffic changes “robust” to burst
traffic interference in the Internet?
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
14/32
Embedding A Mark into Flow Rate
Changes
Flow
Mark
1
1
1 -1 1 -1 -1
 Mark decides flow rate changes


The key to make flow rate changes “invisible” and
“robust” is selecting an appropriate mark
Direct Sequence Spread Spectrum (DSSS)
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
15/32
Basic Direct Sequence Spread
Spectrum (DSSS)
 A pseudo-noise code is used for spreading
a signal and despreading the spread signal
Interferer
Original
Signal
dt
Sniffer
rb
tb
ct
PN Code
Spreading
Wuhan Univ., 9/17/2008
noisy
channel
dr
Recovered
Signal
cr
PN Code
Despreading
Dong Xuan/The Ohio-State Univ.
16/32
Example – Spreading and Despreading
 Signal dt: 1 -1
 PN code (i.e. DSSS code ) ct: 1 1 1 -1 1 -1 -1
 Spread signal tb=dt.ct=1 1 1 -1 1 -1 -1 -1 -1 -1 1 -1 1 1
One symbol is “represented” by 7 chips
 PN code is random and not visible in time and frequency domains
 tb is the mark!
 Despreading is the reverse process of spreading

+1
dt
t
-1
tb
Tc (chip)
t
+1
ct
t
-1
Mark
NcTc
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
17/32
Invisibility of Flow Marking
 Marks show a white noise-like pattern in
both time and frequency domains
 Mark amplitude can be very small
 Suspects don’t know the code, it is very
difficult for them to recognize marks
+1
dt
t
-1
tb
Tc (chip)
+1
ct
t
-1
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
Mark
18/32
Accuracy of Flow Marking Recognition
 Spread/despread processes make the mark
immune to burst interference introduced by
internet background traffic
+1
dt
t
-1
tb
Tc (chip)
+1
ct
t
-1
Mark
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
19/32
A Prototype System
Sender
Receiver
Anonymous
Network
Flow Modulator
Flow Demodulator
Signal Modulator
Signal Modulator
Signal (e.g., 1 -1)
Recovered Signal
Interferer
Wuhan Univ., 9/17/2008
Sniffer
Dong Xuan/The Ohio-State Univ.
20/32
Embedding Signal into Traffic at
Interferer
Choose a random signal
of length n: (1 -1)
2. Signal modulator: obtain
the spread signal
Signal
1.
Signal
Modulator
PN
Code
(1 1 1 -1 1 -1 -1 -1 -1 -1 1 -1 1 1)
Flow
Modulator
3. Flow modulator: modulate a
target traffic flow by
appropriate interference


Bit 1: without interference
Bit -1: with interference
Internet
spread signal + noise
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
21/32
Recovering Signal at Sniffer
1.
Flow demodulator:



Sniff the target traffic
Sample target traffic to derive
traffic rate time series
Use high-pass filter to remove
direct component by Fast
Fourier Transform (FFT)
spread signal + noise
Flow Demodulator
High-pass
Filter
PN
Code
2. Signal demodulator:


Despreading by the PN code
Use low-pass filter to remove
high-frequency noise
(1 -1)
3. Decision rule:

Recovered signal == Original
signal?
Wuhan Univ., 9/17/2008
Low-pass
Filter
Signal Demodulator
Decision
Rule
Dong Xuan/The Ohio-State Univ.
22/32
Analytical Results
 1 bit signal detection rate: the probability that we
recognize one signal bit if we know when the signal
appears
where erfc(.) is complementary error function, and
Nc is the PN code length
 n bit signal detection rate
Signal to Noise
Ratio (SNR)
(1)
A (2)
(3)
 SNR influences accuracy as well as invisibility
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
23/32
Real World Experiment Setup
 The flow modulator at the interferer uses denial of service
attack in wired networks
 Tor: a popular anonymous network on the Internet
(http://www.torproject.org/)
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
24/32
Evaluation Setup
Sender
Receiver
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
25/32
Traceback Invisibility
 Overlapping Traffic Rate Curves for Traffic without Marks
and with Marks in Time and Frequency Domains
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
26/32
Traceback Accuracy
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
27/32
Turning into A Real World Tool
 Remaining issues
Not totally invisible
 Not accurate to low rate traffic
 Robustness

 Applied to different scenarios
 One-to-one => group
• Orthogonal codes => parallel flow marking

Wireless/wired networks
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
28/32
Related Work
 IP packet marking based traceback (UC Berkeley, Purdue Univ.) [1,
2]


Have routers on the path add its IP address to packet; victim will read
path from the packet
Disadvantage: require extra space in the packet; need network
infrastructure involve
 Packet interval arrival time based traceback (North Carolina State
Univ., George Mason Univ.) [3, 4]



Adjust the packet interval time conveying information
Advantage: fewer packets
Disadvantage: sensitive to interference; need of more controlled
network segments
 Correlation based traceback (UT-Arlington, Univ. of Cambridge) [5,
6]



Correlate traffic at different locations (passively or actively)
Advantage: passive and no interference of target traffic (good
secrecy)
Disadvantage: need of a threshold to determine whether traffic at at
different locations is related
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
29/32
Final Remarks
 Invisible traceback is important but hard
 We develop a novel traceback technique
based on flow marking with Spread
Spectrum
 We prototype a system based on the above
technique
 Our technique possesses a high potential to
be further developed into a real-world tool
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
30/32
References
[1] D. X. Song and A. Perrig, “Advanced and authenticated marking schemes
for IP traceback”, in Proc. of IEEE Infocom, 2001
[2] K. Park and H. Lee, “On the Effectiveness of Probabilistic Packet
Marking for IP Traceback under Denial of Service Attack”, in proc. of
IEEE Infocom 2001.
[3] X. Wang, S. Chen, , and S. Jajodia, “Tracking anonymous peer-to-peer
voip calls on the internet,” in Proc. of the 12th ACM Conference on
Computer Communications Security (CCS), 2005.
[4] P. Peng, P. Ning, and D. S. Reeves, “On the secrecy of timing-based
active watermarking trace-back techniques,” in Proc. of the IEEE
Security and Privacy Symposium (S&P), 2006.
[5] Y. Zhu, X. Fu, B. Graham, R. Bettati, and W. Zhao, “On flow correlation
attacks and countermeasures in mix networks,” in Proc. of Workshop on
Privacy Enhancing Technologies (PET), 2004.
[6] B. N. Levine, M. Reiter, C. Wang, and M. Wright, “Timing analysis in lowlatency mix systems,” in Proc. of the 8th International Conference on
Financial Cryptography, 2004.
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
31/32
Thank You !
Questions?
Wuhan Univ., 9/17/2008
Dong Xuan/The Ohio-State Univ.
32/32