Remote physical device fingerprinting
`
`Tadayoshi Kohno
`CSE Department, UC San Diego
`tkohno@cs.ucsd.edu
`
`Andre Broido
`CAIDA, UC San Diego
`broido@caida.org
`
`kc claffy
`CAIDA, UC San Diego
`kc@caida.org
`
`Abstract
`
`We introduce the area of remote physical device finger-
`printing, or fingerprinting a physical device, as opposed to
`an operating system or class of devices, remotely, and with-
`out the fingerprinted device’s known cooperation. We ac-
`complish this goal by exploiting small, microscopic devia-
`tions in device hardware: clock skews. Our techniques do
`not require any modification to the fingerprinted devices.
`Our techniques report consistent measurements when the
`measurer is thousands of miles, multiple hops, and tens of
`milliseconds away from the fingerprinted device, and when
`the fingerprinted device is connected to the Internet from
`different locations and via different access technologies.
`Further, one can apply our passive and semi-passive tech-
`niques when the fingerprinted device is behind a NAT or
`firewall, and also when the device’s system time is main-
`tained via NTP or SNTP. One can use our techniques to
`obtain information about whether two devices on the Inter-
`net, possibly shifted in time or IP addresses, are actually the
`same physical device. Example applications include: com-
`puter forensics; tracking, with some probability, a physical
`device as it connects to the Internet from different public ac-
`cess points; counting the number of devices behind a NAT
`even when the devices use constant or random IP IDs; re-
`motely probing a block of addresses to determine if the ad-
`dresses correspond to virtual hosts, e.g., as part of a virtual
`honeynet; and unanonymizing anonymized network traces.
`
`1 Introduction
`
`There are now a number of powerful techniques for re-
`mote operating system fingerprinting, i.e., techniques for
`remotely determining the operating systems of devices on
`the Internet [2, 3, 5, 27]. We push this idea further and in-
`troduce the notion of remote physical device fingerprinting,
`or remotely fingerprinting a physical device, as opposed to
`an operating system or class of devices, without the finger-
`printed device’s known cooperation. We accomplish this
`
`goal to varying degrees of precision by exploiting micro-
`scopic deviations in device hardware: clock skews.
`
`CLASSES OF FINGERPRINTING TECHNIQUES. We con-
`sider three main classes of remote physical device finger-
`printing techniques: passive, active, and semi-passive. The
`first two have standard definitions — to apply a passive
`fingerprinting technique, the fingerprinter (measurer, at-
`tacker, adversary) must be able to observe traffic from the
`device (the fingerprintee) that the attacker wishes to finger-
`print, whereas to apply an active fingerprinting technique,
`the fingerprinter must have the ability to initiate connec-
`tions to the fingerprintee. Our third class of techniques,
`which we refer to as semi-passive fingerprinting techniques,
`assumes that after the fingerprintee initiates a connection,
`the fingerprinter has the ability to interact with the finger-
`printee over that connection; e.g., the fingerprinter is a web-
`site with which the device is communicating, or is an ISP
`in the middle capable of modifying packets en route. Each
`class of techniques has its own advantages and disadvan-
`tages. For example, passive techniques will be completely
`undetectable to the fingerprinted device, passive and semi-
`passive techniques can be applied even if the fingerprinted
`device is behind a NAT or firewall, and semi-passive and
`active techniques can potentially be applied over longer pe-
`riods of time; e.g., after a laptop connects to a website and
`the connection terminates, the website can still continue to
`run active measurements.
`
`METHODOLOGY. For all our methods, we stress that the
`fingerprinter does not require any modification to or co-
`operation from the fingerprintee; e.g., we tested our tech-
`niques with default Red Hat 9.0, Debian 3.0, FreeBSD
`5.2.1, OpenBSD 3.5, OS X 10.3.5 Panther, Windows XP
`SP2, and Windows for Pocket PC 2002 installations.1 In Ta-
`ble 1 we summarize our preferred methods for fingerprint-
`ing the most popular operating systems.
`Our preferred passive and semi-passive techniques ex-
`ploit the fact that most modern TCP stacks implement the
`
`1Our techniques work for the default installs of other versions of these
`operating systems; here we just mention the most recent stable versions of
`the operating systems that we analyzed.
`
`IA1017
`
`Page 1 of 15
`
`

`

`Technique and section
`TCP timestamps, Section 3
`TCP timestamps, Section 3
`ICMP tstamp requests, Section 4
`
`NTP Red Hat 9.0 OS X Panther Windows XP
`Class
`Yes
`Yes
`Yes
`No
`passive
`semi-passive Yes
`Yes
`Yes
`Yes
`active
`No
`Yes
`No
`Yes
`
`Table 1. This table summarizes our main clock skew-based physical device fingerprinting techniques.
`A “Yes” in the NTP column means that one can use the attack regardless of whether the fingerprintee
`maintains its system time with NTP [19]. One can use passive and semi-passive techniques when
`the fingerprintee is behind a NAT or current generation firewall.
`
`TCP timestamps option from RFC 1323 [13] whereby, for
`performance purposes, each party in a TCP flow includes
`information about its perception of time in each outgoing
`packet. A fingerprinter can use the information contained
`within the TCP headers to estimate a device’s clock skew
`and thereby fingerprint a physical device. We stress that
`one can use our TCP timestamps-based method even when
`the fingerprintee’s system time is maintained via NTP [19].
`While most modern operating systems enable the TCP
`timestamps option by default, Windows 2000 and XP ma-
`chines do not. Therefore, we developed a trick, which in-
`volves an intentional violation of RFC 1323 on the part of
`a semi-passive or active adversary, to convince Microsoft
`Windows 2000 and XP machines to use the TCP times-
`tamps option in Windows-initiated flows.
`In addition to
`our TCP timestamps-based approach, we consider passive
`fingerprinting techniques that exploit the difference in time
`between how often other periodic activities are supposed to
`occur and how often they actually occur, and we show how
`one might use a Fourier transform on packet arrival times
`to infer a device’s clock skew. Since we believe that our
`TCP timestamps-based approach is currently our most gen-
`eral passive technique, we focus on the TCP timestamps
`approach in this paper.
`An active adversary could also exploit the ICMP proto-
`col to fingerprint a physical device. Namely, an active ad-
`versary could issue ICMP Timestamp Request messages to
`the fingerprintee and record a trace of the resulting ICMP
`Timestamp Reply messages. If the fingerprintee does not
`maintain its system time via NTP or does so only infre-
`quently and if the fingerprintee replies to ICMP Timestamp
`Requests, then an adversary analyzing the resulting ICMP
`Timestamp Reply messages will be able to estimate the fin-
`gerprintee’s system time clock skew. Default Red Hat 9.0,
`Debian 3.0, FreeBSD 5.2.1, OpenBSD 3.5, and Windows
`2000 and XP and Pocket PC 2002 installations all satisfy
`the above preconditions.
`
`PARAMETERS OF INVESTIGATION. Toward developing the
`area of remote physical device fingerprinting via remote
`clock skew estimation, we must address the following set
`of interrelated questions:
`
`(1) For what operating systems are our remote clock skew
`estimation techniques applicable?
`(2) What is the distribution of clock skews across multiple
`fingerprintees? And what is the resolution of our clock
`skew estimation techniques? (I.e., can one expect two
`machines to have measurably different clock skews?)
`(3) For a single fingerprintee, can one expect the clock
`skew estimate of that fingerprintee to be relatively
`constant over long periods of time, and through re-
`boots, power cycles, and periods of down time?
`(4) What are the effects of a fingerprintee’s access tech-
`nology (e.g., wireless, wired, dialup, cable modem)
`on the clock skew estimates for the device?
`(5) How are the clock skew estimates affected by the dis-
`tance between the fingerprinter and the fingerprintee?
`(6) Are the clock skew estimates independent of the fin-
`gerprinter? I.e., when multiple fingerprinters are mea-
`suring a single fingerprintee at the same time, will they
`all output (approximately) the same skew estimates?
`(7) How much data do we need to be able to remotely
`make accurate clock skew estimates?
`Question (6) is applicable because common fingerprinters
`will probably use NTP-based time synchronization when
`capturing packets, as opposed to more precise CDMA- or
`GPS-synchronized timestamps. Answers to the above ques-
`tions will help determine the efficacy of our physical device
`fingerprinting techniques.
`
`EXPERIMENTS AND HIGH-LEVEL RESULTS. To under-
`stand and refine our techniques, we conducted experiments
`with machines that we controlled and that ran a variety of
`operating systems, including popular Linux, BSD, and Mi-
`crosoft distributions. In all cases we found that we could
`use at least one of our techniques to estimate clock skews
`of the machines, and that we required only a small amount
`of data, though the exact data requirements depended on the
`operating system in question. For the most popular operat-
`ing systems, we observed that when the system did not use
`NTP- or SNTP-based time synchronization, then the TCP
`timestamps-based and the ICMP-based techniques yielded
`
`IA1017
`
`Page 2 of 15
`
`

`

`approximately the same skew estimates. This result, cou-
`pled with details that we describe in the body, motivated
`us to use the TCP timestamps-based method in most of our
`experiments. We survey some of our experiments here.
`To understand the effects of topology and access tech-
`nology on our skew estimates, we fixed the location of the
`fingerprinter and applied our TCP timestamps-based tech-
`nique to a single laptop in multiple locations, on both North
`American coasts, from wired, wireless, and dialup loca-
`tions, and from home, business, and campus environments
`(Table 3). All clock skew estimates for the laptop were
`close — the difference between the maximum and the min-
`imum skew estimate was only 0.67 ppm. We also simul-
`taneously measured the clock skew of the laptop and an-
`other machine from multiple PlanetLab nodes throughout
`the world, as well as from a machine of our own with a
`CDMA-synchronized Dag card [1, 9, 11, 17] for taking net-
`work traces with precise timestamps (Table 4). With the ex-
`ception of the measurements taken by a PlanetLab machine
`in India (over 300 ms round trip time away), for each exper-
`iment, all the fingerprinters (in North America, Europe, and
`Asia) reported skew estimates within only 0.56 ppm of each
`other. These experiments suggest that, except for extreme
`cases, the results of our clock skew estimation techniques
`are independent of access technology and topology.
`Toward understanding the distribution of clock skews
`across machines, we applied the TCP timestamps technique
`to the devices in a trace collected on one of the U.S.’s Tier 1
`OC-48 links (Figure 2). We also measured the clock skews
`of 69 (seemingly) identical Windows XP SP1 machines in
`one of our institution’s undergraduate computing facilities
`(Figure 3). The latter experiment, which ran for 38 days,
`as well as other experiments, show that the clock skew es-
`timates for any given machine are approximately constant
`over time, but that different machines have detectably dif-
`ferent clock skews. Lastly, we use the results of these and
`other experiments to argue that the amount of data (packets
`and duration of data) necessary to perform our skew estima-
`tion techniques is low, though we do not perform a rigorous
`analysis of exactly what “low” means.
`
`APPLICATIONS AND ADDITIONAL EXPERIMENTS. To test
`the applicability of our techniques, we applied our tech-
`niques to a honeyd [24] virtual honeynet consisting of 100
`virtual Linux 2.4.18 hosts and 100 virtual Windows XP SP1
`hosts. Our experiments showed with overwhelming proba-
`bility that the TCP flows and ICMP timestamp responses
`were all handled by a single machine as opposed to 200
`different machines. We also applied our techniques to a
`network of five virtual machines running under VMware
`Workstation [4] on a single machine. In this case, the clock
`skew estimates of the virtual machines are significantly dif-
`ferent from what one would expect from real machines (the
`skews were large and not constant over time; Figure 5). An
`
`application of our techniques, or natural extensions, might
`therefore be to remotely detect virtual honeynets.
`Another applications of our techniques is to count the
`number of hosts behind a NAT, even if those hosts use ran-
`dom or constant IP IDs to counter Bellovin’s attack [7],
`even if all the hosts run the same operating system, and even
`if not all of the hosts are up at the same time. Furthermore,
`when both our techniques and Bellovin’s techniques are ap-
`plicable, we expect our approach to provide a much higher
`degree of resolution. One could also use our techniques for
`forensics purposes, e.g., to argue whether or not a given lap-
`top was connected to the Internet from a given access loca-
`tion. One could also use our techniques to help track laptops
`as they move, perhaps as part of a Carnivore-like project
`(here we envision our skew estimates as one important com-
`ponent of the tracking; other components could be informa-
`tion gleaned from existing operating system fingerprinting
`techniques, usage characteristics, and other heuristics). One
`can also use our techniques to catalyze the unanonymization
`of prefix-preserving anonymized network traces [28, 29].
`
`It has long been
`BACKGROUND AND RELATED WORK.
`known that seemingly identical computers can have dis-
`parate clock skews. The NTP [19] specification describes
`a method for reducing the clock skews of devices’ sys-
`tem clocks, though over short periods of time an NTP-
`synchronized machine may still have slight clock skew. In
`1998 Paxson [22] initiated a line of research geared toward
`eliminating clock skew from network measurements, and
`one of the algorithms we use is based on a descendent of
`the Paxson paper by Moon, Skelly, and Towsley [20]. Fur-
`ther afield, though still related to clock skews, P´asztor and
`Veitch [21] have created a software clock on a commod-
`ity PC with high accuracy and small clock skew. One fun-
`damental difference between our work and previous work
`is our goal: whereas all previous works focus on creat-
`ing methods for eliminating the effects of clock skews, our
`work exploits and capitalizes on the effects of clock skews.
`Anagnostakis et. al. [6] use ICMP Timestamp Requests
`to study router queuing delays. It is well known that a net-
`work card’s MAC address is supposed to be unique and
`therefore could serve as a fingerprint of a device assum-
`ing that the adversary can observe the device’s MAC ad-
`dress and that the owner of the card has not changed the
`MAC address. The main advantage of our techniques over
`a MAC address-based approach is that our techniques are
`mountable by adversaries thousands of miles and multiple
`hops away. One could also use cookies or any other per-
`sistent data to track a physical device, but such persistent
`data may not always be available to an adversary, perhaps
`because the user is privacy-conscious and tries to minimize
`storage and transmission of such data, or because the user
`never communicates that data unencrypted.
`See [15] for the full version of this paper.
`
`IA1017
`
`Page 3 of 15
`
`

`

`2 Clocks and clock skews
`
`When discussing clocks and clock skews, we build on
`the nomenclature from the NTP specification [19] and from
`Paxson [22]. A clock C is designed to represent the amount
`of time that has passed since some initial time i[C]. Clock
`C’s resolution, r[C], is the smallest unit by which the clock
`can be incremented, and we refer to each such increment
`as a tick. A resolution of 10 ms means that the clock is de-
`signed to have 10 ms granularity, not that the clock is always
`incremented exactly every 10 ms. Clock C’s intended fre-
`quency, Hz[C], is the inverse of its resolution; e.g., a clock
`with 10 ms granularity is designed to run at 100 Hz. For
`all t ≥ i[C], let R[C](t) denote the time reported by clock
`C at time t, where t denotes the true time as defined by
`national standards. The offset of clock C, off[C], is the dif-
`ference between the time reported by C and the true time,
`i.e., off[C](t) = R[C](t) − t for all t ≥ i[C]. A clock’s
`skew, s[C], is the first derivative of its offset with respect to
`time, where we assume for simplicity of notation that R[C]
`is a differentiable function in t. We report skew estimates in
`microseconds per second (µs/s) or, equivalently, parts per
`million (ppm). As we shall show, and as others have also
`concluded [22, 20, 26], it is often reasonable to assume that
`a clock’s skew is constant. When the clock in question is
`clear from context, we shall remove the parameter C from
`our notation; e.g., s[C] becomes s.
`A given device can have multiple, possibly independent,
`clocks. For remote physical device fingerprinting, we ex-
`ploit two different clocks: the clock corresponding to a de-
`vice’s system time, and a clock internal to a device’s TCP
`network stack, which we call the device’s TCP timestamps
`option clock or TSopt clock. We do not consider the hard-
`ware bases for these clocks here since our focus is not on
`understanding why these clocks have skews, but on exploit-
`ing the fact these clocks can have measurable skews on pop-
`ular current-generation systems.
`
`THE SYSTEM CLOCK. To most users of a computer sys-
`tem, the most visible clock is the device’s system clock,
`Csys, which is designed to record the amount of time since
`00:00:00 UTC, January 1, 1970. Although the system
`clocks on professionally administered machines are often
`approximately synchronized with true time via NTP [19]
`or, less accurately, via SNTP [18], we stress that it is much
`less likely for the system clocks on non-professionally man-
`aged machines to be externally synchronized. This lack of
`synchronization is because the default installations of most
`of the popular operating systems that we tested do not syn-
`chronize the hosts’ system clocks with true time or, if they
`do, they do so only infrequently. For example, default Win-
`dows XP Professional installations only synchronize their
`system times with Microsoft’s NTP server when they boot
`and once a week thereafter. Default Red Hat 9.0 Linux
`
`installations do not use NTP by default, though they do
`present the user with the option of entering an NTP server.
`Default Debian 3.0, FreeBSD 5.2.1, and OpenBSD 3.5 sys-
`tems, at least under the configurations that we selected (e.g.,
`“typical user”), do not even present the user with the op-
`tion of installing ntpd. For such a non-professionally-
`administered machine, if an adversary can learn the values
`of the machine’s system clock at multiple points in time,
`the adversary will be able to infer information about the de-
`vice’s system clock skew, s[Csys].
`THE TCP TIMESTAMPS OPTION CLOCK. RFC 1323 [13]
`specifies the TCP timestamps option to the TCP protocol.
`A TCP flow will use the TCP timestamps option if the net-
`work stacks on both ends of the flow implement the option
`and if the initiator of the flow includes the option in the
`initial SYN packet. All modern operating systems that we
`tested implement the TCP timestamps option. Of the sys-
`tems we tested, Microsoft Windows 2000 and XP are the
`only ones that do not include the TCP timestamps option in
`the initial SYN packet (Microsoft Windows Pocket PC 2002
`does include the option when initiating TCP flows). In Sec-
`tion 3 we introduce a trick for making Windows 2000- and
`XP-initiated flows use the TCP timestamps option.
`For physical device fingerprinting, the most important
`property of the TCP timestamps option is that if a flow uses
`the option, then a portion of the header of each TCP packet
`in that flow will contain a 32-bit timestamp generated by
`the creator of that packet. The RFC does not dictate what
`values the timestamps should take, but does say that the
`timestamps should be taken from a “virtual clock” that is “at
`least approximately proportional to real time [13];” the RFC
`1323 PAWS algorithm does stipulate (Section 4.2.2) that the
`resolution of this virtual clock be between 1 ms and 1 sec-
`ond. We refer to this “virtual clock” as the device’s TCP
`timestamps option clock, or its TSopt clock Ctcp. There is no
`requirement that a device’s TSopt clock and its system clock
`be correlated. Moreover, for popular operating systems like
`Windows XP, Linux, and FreeBSD, a device’s TSopt clock
`may be unaffected by adjustments to the device’s system
`clock via NTP. To sample some popular operating systems,
`standard Red Hat 9.0 and Debian 3.0 Linux distributions2
`and FreeBSD 5.2.1 machines have TSopt clocks with 10 ms
`resolution, OS X Panther and OpenBSD 3.5 machines have
`TSopt clocks with 500 ms resolution, and Microsoft Win-
`dows 2000, XP, and Pocket PC 2002 systems have TSopt
`clocks with 100 ms resolution. Most systems reset their
`TSopt clock to zero upon reboot; on these systems i[Ctcp]
`is the time at which the system booted. If an adversary can
`learn the values of a device’s TSopt clock at multiple points
`in time, then the adversary may be able to infer information
`about the device’s TSopt clock skew, s[Ctcp].
`2We do not generalize this to all Linux distributions since Knoppix 3.6,
`with the 2.6.7 experimental kernel, has 1 ms resolution.
`
`IA1017
`
`Page 4 of 15
`
`

`

`3 Exploiting the TCP Timestamps Option
`
`In this section we consider (1) how an adversary might
`obtain samples of a device’s TSopt clock at multiple points
`in time and (2) how an adversary could use those samples
`to fingerprint a physical device. We assume for now that
`there is a one-to-one correspondence between physical de-
`vices and IP addresses, and defer to Section 8 a discussion
`of how to deal with multiple active hosts behind a NAT; in
`this section we do consider NATs with a single active device
`behind them.
`
`THE MEASURER. The measurer can be any entity capable
`of observing TCP packets from the fingerprintee, assum-
`ing that those packets have the TCP timestamps option en-
`abled. The measurer could therefore be the fingerprintee’s
`ISP, or any tap in the middle of the network over which
`packets from the device travel; e.g., we apply our techniques
`to a trace taken on a major Tier 1 ISP’s backbone OC-48
`links. The measurer could also be any system with which
`the fingerprintee frequently communicates; prime examples
`of such systems include a search engine like Google, a news
`website, and a click-through ads service that displays con-
`tent on a large number of websites. If the measurer is ac-
`tive, then the measurer could also be the one to initiate a
`TCP flow with the fingerprintee, assuming that the device
`is reachable and has an open port. If the measurer is semi-
`passive or active, then it could make the flows that it ob-
`serves last abnormally long, thereby giving the measurer
`samples of the fingerprintee’s clock over extended periods
`of time.
`
`A TRICK FOR MEASURING WINDOWS 2000 AND XP MA-
`CHINES. We seek the ability to measure TSopt clock skews
`of Windows 2000 and XP machines even if those machines
`are behind NATs and firewalls. But, because of the nature of
`NATs and firewalls, in these cases we will typically be lim-
`ited to analyzing flows initiated by the Windows machines.
`Unfortunately, because Windows 2000 and XP machines do
`not include the TCP timestamps option in their initial SYN
`packets, the TCP timestamps RFC [13] mandates that none
`of the subsequent packets in Windows-initiated flows can
`include the TCP timestamps option. Thus, assuming that all
`parties correctly implement the TCP RFCs, a passive adver-
`sary will not be able to exploit the TCP timestamps option
`with Windows 2000/XP-initiated flows.
`If the adversary is semi-passive, we observe the follow-
`ing trick. Assume for simplicity that the adversary is the de-
`vice to whom the Windows machine is connecting. After re-
`ceiving the initial SYN packet from the Windows machine,
`the adversary will reply with a SYN/ACK, but the adversary
`will break the RFC 1323 specification and include the TCP
`timestamps option in its reply. After receiving such a reply,
`our Windows 2000 and XP machines ignored the fact that
`
`they did not include the TCP timestamps option in their ini-
`tial SYN packets, and included the TCP timestamps option
`in all of their subsequent packets. As an extension, we note
`that the adversary does not have to be the device to whom
`the Windows machine is connecting. Rather, the adversary
`simply needs to be able to mount a “device-in-the-middle”
`attack and modify packets such that the Windows machine
`receives one with the TCP timestamps option turned on. If
`the adversary is the device’s ISP, then the ISP could rewrite
`the Windows machine’s initial SYN packets so that they in-
`clude the TCP timestamps option. The SYN/ACKs from
`the legitimate recipients will therefore have the TCP times-
`tamps option enabled and, from that point forward, the Win-
`dows machine will include the TCP timestamps option in all
`subsequent packets in the flows.
`We applied this technique to Windows XP machines on
`a residential cable system with a LinkSys Wireless Access
`Point and a NAT, as well as to Windows XP SP2 machines
`using the default XP SP2 firewall, and to Windows XP SP1
`machines with the Windows ZoneAlarm firewall. (While
`current firewalls do not detect this trick, it is quite possible
`that future firewalls might.)
`ESTIMATING THE TSOPT CLOCK SKEW. Let us now as-
`sume that an adversary has obtained a trace T of TCP pack-
`ets from the fingerprintee, and let us assume for simplicity
`that all |T | packets in the trace have the TCP timestamps
`option enabled. Toward estimating a device’s TSopt clock
`skew s[Ctcp] we adopt the following additional notation. Let
`ti be the time in seconds at which the measurer observed the
`i-th packet in T and let Ti be the Ctcp timestamp contained
`within the i-th packet. Define
`xi = ti − t1
`vi = Ti − T1
`wi = vi/Hz
`yi = wi − xi
`OT = { (xi, yi) : i ∈ {1, . . . , |T |} } .
`The unit for wi is seconds; yi is the observed offset of the i-
`th packet; OT is the the offset-set corresponding to the trace
`T . We discuss below how to compute Hz if it is not known
`to the measurer in advance. As an example, Figure 1 shows
`the offset-sets for two devices in a two-hour trace of traffic
`from an Internet backbone OC-48 link on 2004-04-28 (we
`omit IP addresses for privacy reasons). Shifting the clocks
`by t1 and T1 for xi and vi is not necessary for our analysis
`but makes plots like in Figure 1 cleaner.
`If we could assume that the measurer’s clock is accurate
`and that the t values represent true time, and if we could as-
`sume that there is no delay between when the fingerprintee
`generates the i-th packet and when the measurer records
`the i-th packet, then yi = off(xi + t1). Under these as-
`sumptions, and if we make the additional assumption that
`
`IA1017
`
`Page 5 of 15
`
`

`

`mizes the average vertical distance of all the points in OT
`from the line; i.e., the linear programming solution is one
`that minimizes the objective function
`|T |(cid:1)
`(cid:2)
`1
`α · xi + β − yi
`|T | ·
`
`(cid:3)
`
`.
`
`i=1
`Although one can solve the above using standard linear pro-
`gramming techniques, as Moon, Skelly, and Towsley [20]
`note, there exist techniques to solve linear programming
`problems in two variables in linear time [10, 16]. We use
`a linear time algorithm in all our computations.
`It remains to discuss how to infer Hz if the measurer does
`not know it in advance. One solution involves computing
`the slope of the points
`I = { (xi, vi) : i ∈ {1, . . . , |T | }
`and rounding to the nearest integer. One can compute the
`slope of this set by adapting the above linear programming
`problem to this set.
`AN EQUIVALENT VIEW. If A is the slope of the points in
`the above set I, derived using the linear programming al-
`gorithm, then one could also approximate the skew of Ctcp
`as A/Hz − 1. This approach is simply a different way of
`arriving at the same solution since we can prove that, when
`using the linear programming method for slope estimation,
`both approaches produce the same skew estimate. We use
`the offset-set approach since these sets naturally yield fig-
`ures where the skews are clearly visible; e.g., Figure 1.
`
`4 Exploiting ICMP Timestamp Requests
`
`THE MEASURER. To exploit a device’s system time clock
`skew, the measurer could be any website with which the fin-
`gerprintee communicates, or any other device on the Inter-
`net provided that the measurer is capable of issuing ICMP
`Timestamp Requests (ICMP message type 13) to the fin-
`gerprintee. The measurer must also be capable of record-
`ing the fingerprintee’s subsequent ICMP Timestamp Reply
`messages (ICMP message type 14). In order for this tech-
`nique to be mountable, the primary limitation is that the de-
`vice must not be behind a NAT or firewall that filters ICMP.
`
`ESTIMATING THE SYSTEM CLOCK SKEW. Let us now as-
`sume that an adversary has obtained a trace T of ICMP
`Timestamp Reply messages from the fingerprintee. The
`ICMP Timestamp Reply messages will contain two 32-bit
`values generated by the fingerprintee. The first value is
`the time at which the corresponding ICMP Timestamp Re-
`quest packet was received, and the second value is the time
`at which the ICMP Timestamp Reply was generated; here
`time is according to the fingerprintee’s system clock, Csys,
`and is reported in milliseconds since midnight UTC. Win-
`dows machines report the timestamp in little endian for-
`
`Source 1: 10Hz TSopt clock, 37526 packets, ttl=113
`Source 2: 100Hz TSopt clock, 20974 packets, ttl=55
`linear programming-based upper bound
`
`900
`
`2700
`1800
`5400
`4500
`3600
`time since start of measurement (seconds)
`
`6300
`
`7200
`
`400
`
`200
`
`0
`
`-200
`
`-400
`
`observed offset (ms)
`
`-600
`
`0
`
`Figure 1. TSopt clock offset-sets for two
`sources in BBN. Trace recorded on an OC-
`48 link of a U.S. Tier 1 ISP, 2004-04-28 19:30–
`21:30PDT. The source with the wide band has
`a 10 Hz TSopt clock, the source with the nar-
`row band has a 100 Hz TSopt clock. A source
`with no clock skew would have a horizontal
`band.
`
`R is differentiable, then the first derivative of y, which is
`the slope of the points in OT , is the skew s of Ctcp. Since
`we cannot generally make these assumptions, we are left to
`approximate s from the data.
`Let us consider plots like those in Figure 1 more closely.
`We first observe that the large band corresponds to a device
`where the TSopt clock has low resolution (r = 100 ms) and
`that the narrow band corresponds to a device with a higher
`resolution (r = 10 ms). The width of these bands, and in
`particular the wide band, means that if the duration of our
`trace is short, we cannot always approximate the slope of
`the points in OT by computing the slope between any two
`points in the set. Moreover, as Paxson and others have noted
`in similar contexts [22, 20], variable network delay renders
`simple linear regression insufficient. Consequently, to ap-
`proximate the the skew s from OT , we borrow a linear pro-
`gramming solution from Moon, Skelly, and Towsley [20],
`which has as its core Graham’s convex hull algorithm on
`sorted data [12].
`The linear programming solution outputs the equation of
`a line αx + β that upper-bounds the set of points OT . We
`use an upper bound because network and host delays are all
`positive. The slope of the line, α, is our estimate of the clock
`skew of Ctcp. In detail, the linear programming constraints
`for this line are that, for all i ∈ {1, . . . , |T |},
`α · xi + β ≥ yi ,
`which means that the solution must upper-bound all the
`points in OT . The linear programming solution then mini-
`
`IA1017
`
`Page 6 of 15
`
`

`

`mat, whereas all the other machines that we tested report
`the timestamp in big endian notation. The remaining nota-
`tion and the method for skew estimation is now identical to
`what we presented in Section 3, with two minor exceptions.
`First, the adversary does not have to compute Hz since RFC
`792 [23] requires that Hz be 1000 (or, if not, that a spe-
`cial bit be set to indicate non-compliance). Second, since
`the time reported in the ICMP Timestamp Reply is in mil-
`liseconds since midnight UTC, we expect the timestamps
`reported in the ICMP Timestamp Reply messages to reset
`approximately once a day; we adjust the v values accord-
`ingly. (The only thing special that our attack exploits about
`ICMP is the fact that ICMP has a message type that will
`reveal a device’s system time; our techniques would work
`equally well with any other protocol that leaks information
`about a device’s system or other clock.)
`
`BRIEF COMPARISON WITH TCP TIMESTAMPS. For much
`of the rest of this paper, we focus on our TCP timestamps-
`based appro