# Identifying and characterizing ZMap scans:
a cryptanalytic approach

Johan Mazel<EMAIL_ADDRESS><EMAIL_ADDRESS>Rémi Strullu
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Network scanning tools play a major role in Internet security. They are used
by both network security researchers and malicious actors to identify
vulnerable machines exposed on the Internet. ZMap is one of the most common
probing tools for high-speed Internet-wide scanning. We present novel
identification methods based on the IPv4 iteration process of ZMap. These
methods can be used to identify ZMap scans with a small number of addresses
extracted from the scan. We conduct an experimental evaluation of these
detection methods on synthetic, network telescope, and backbone traffic. We
manage to identify 28.5% of the ZMap scans in real-world traffic. We then
perform an in-depth characterization of these scans regarding, for example,
targeted prefix and probing speed.

##  1 Introduction

Internet wide scanning tools are commonly used by privacy and security
researchers and malicious actors. Use cases range from anti-censorship
techniques [25, 37] or computer security [19] research, to commercial services
[15, 4] and malicious mass-exploitation [18]. Leonard et al. [27] proposed the
seminal work regarding high-speed uniformly spread Internet-wide scanning.
Durumeric et al. and Robert Graham then published two tools, ZMap [17, 9] and
Masscan [22], that considerably eased Internet-wide scanning. This lead to a
constant use increase [29]. Security administrators monitor their networks to
detect attacks at several stages such as reconnaissance, exploitation or
command and control. Incident response teams analyze network traffic logs to
determine root causes of compromise. Network scans are reconnaissance events,
and thus interest security administrators (as occurring events) and incident
response team (as security incident root cause). These actors, however, often
have trouble understanding probing scope and purpose.

Previous work [16, 14, 29] analyzed ZMap usage in the wild. These works use
heuristics [16, 14], signatures [29], and the fact that ZMap sets the IP ID
field to 54321, to identify ZMap traffic. They also rely on privileged points
of view on traffic: a network telescope slightly smaller than a /9 prefix for
[16], and backbone traffic containing prefixes adding up to a /13 prefix in
[29]. Security administrators usually operate smaller networks. It is thus
more difficult for them to detect incoming probing traffic [28], and to assess
its nature.

Our goal is to identify ZMap scans and associated internal characteristics
from short sequences of observed packets. We propose new methods to identify
ZMap scans with or without the IP ID fingerprint. These identification methods
also recover targeted prefix which can be used by administrators and incident
response teams to determine probing purpose. For example, administrators can
quickly discard indiscriminate Internet-wide probing, and focus on scans that
specifically target their network. By recovering the internal state of ZMap,
we can also predict future probed addresses, and block related scanning
traffic. Similarly, incident response teams can use our identification methods
to investigate scanning that targeted a compromised host. Our methods are thus
useful for both _real-time_ use cases (e.g. scan detection and probed IP
address prediction and blocking), and _a posteriori_ ones (e.g. network
traffic forensics). Finally, we provide an in-depth characterization of ZMap
scans that goes beyond existing work [16, 14, 29], for example regarding scan
progress, packet rates and unnecessary probing.

Our contribution is threefold. First, we propose two crypto-analysis methods
to identify ZMap scanning. Second, we evaluate efficiency and computing cost
using synthetic data and real-world traffic captured from both network
telescope and backbone traffic. Third, we provide an in-depth analysis of ZMap
usage in the wild. We thus identify misuses, such as private IP address
probing and packet rate above upstream capacity, that waste network resources.

Our paper is structured as follows. Section 2 present existing work on probing
and ZMap scan analysis. Section 3 details relevant aspects of ZMap design and
implementation. Section 4 describes our identification methods. Section 5
presents our identification and characterization results.

##  2 Related work

Several works analyze scans in real-world traffic [10, 21, 12]. ZMap usage has
been documented in network telescope [16] and backbone data [29]. In [16],
Durumeric et al. characterize ZMap usage, packet rate, source IP location,
targeted ports and scan coverage. In [29], Mazel et al. describe the rise of
ZMap usage from 2013 to 2016.

Doerr et al. [14] follow an approach similar to ours. They extract the
internal state of ZMap to predict future probed IP addresses and block
forecasted traffic. To this end, they brute force the sequence of observed IP
addresses collected in a /16 network telescope using GPUs. Their work,
however, exhibit several limitations. First, they do not describe the
blacklist and offset mechanisms in ZMap. Second, they do not take into account
packet reordering which is an exteremely common phenomenom in networks [11,
32, 36, 23, 31]. Third, they do not provide any characteristics regarding
observed scans.

We improve the work of Doerr et al. [14] by taking into acount ZMap’s
blacklist and offset mechanisms (see Section 3). We also consider the impact
of packet reordering on our methods and provide a sampling methodology that
alleviates its impact (see Section 5.2.5). By leveraging ZMap’s internal
state, we detail ZMap scans characteristics that were not addressed in [16,
29], such as blacklist usage, targeted prefix, packet rate, evidence of
cooperation among sources, scan progress and probe visibility (see Section
5.2.6 to Section 5.2.9).

##  3 ZMap overview

We describe the process used by ZMap to iterate over the IPv4 address space.
This process relies on modular arithmetic in a finite field $\mathbb{F}_{p}$
defined by a prime number $p$. Mathematical background can be found in [13].

The structure of the iterator can be decomposed into two parts: the internal
state $s$ that is updated over the integers of $\mathbb{F}_{p}$ and the
function $f$ that maps the internal state into an IPv4 address.

(a) Original sharding [9]

(b) New pizza-like sharding [5]

Figure 1: Sharding mechanisms used in ZMap.

###  3.1 Internal state

At the initialization of the scan, a prime number $p$ is selected according to
the number of IPv4 addresses to scan. If we denote $n$ this number of
addresses, then $p$ is the smallest prime number among the integers
$\\{p_{0},...,p_{4}\\}$ to be be greater or equal to $n$. The prime numbers
$p_{0},...,p_{4}$ are predefined by the ZMap implementation: $p_{0}=2^{8}+1$,
$p_{1}=2^{16}+1$, $p_{2}=2^{24}+43$, $p_{3}=2^{28}+3$ and $p_{4}=2^{32}+15$.

A primitive root $g$ of $\mathbb{F}_{p}$ and the initial internal state
$s_{0}$ are also randomly generated at the beginning of each scan. If the
random generator has good randomness properties, we can suppose that these
values are unique and characterize each scan. Then, at each step $i$ in
$\\{1,...,p-2\\}$, the state $s_{i}$ is updated according to the formula:

$s_{i}=g\cdot s_{i-1}\mod p$ (1)

ZMap supports distributed scans over several instances. If this option is
activated, the address generation process is parallelized between the
instances by splitting the sequence of states into shards of equal length. To
perform this task, ZMap implements two types of sharding techniques that
depend on the software version.

Prior to a ZMap commit [5] on September 15, 2017, the sharding technique was
realized as follow : let $d$ be the number of instances that perform the
distributed scan. At the initialization step, a primitive root $g$ and a
random number $s_{0}$ in $\mathbb{F}_{p}$ are shared between all the
instances. Then, each instance indexed by $k$ in $\\{0,...,d-1\\}$ generates
its own initial internal state $s_{0,k}=s_{0}\cdot g^{k}$ and the internal
state $s_{i,k}$ is updated according to the formula:

$s_{i,k}=g^{d}\cdot s_{i-1,k}\mod p$ (2)

If we denote $Shard_{k}$ the set of internal states generated by the instance
$k$, then

$Shard_{k}=\left\\{s_{i,k}\mid
i\in\left\\{0,...,\Bigl{\lfloor}\dfrac{p-2}{d}\Bigr{\rfloor}\right\\}\right\\}$

where $\Bigl{\lfloor}\dfrac{p-2}{d}\Bigr{\rfloor}$ is the integer division of
$p-2$ by $d$.

It is easy to notice that

$\bigcup_{0\leq k<d}Shard_{k}=\\{s_{i}\mid
i\in\\{0,...,p-2\\}\\}=\mathbb{F}_{p}\setminus\\{0\\}$

and the sets $Shard_{k}$ are disjoint. This allows to cover the whole address
space to scan without repetition of an address into different shards. This
method is depicted in Figure 1a.

Since the ZMap version of September 15, 2017 [5], the sharding technique has
been modified. Each $Shard_{k}$ contains the consecutive states $s_{i}$ ($i$
in $\\{k\cdot\lfloor p-2/d\rfloor,...,(k+1)\cdot\lfloor p-2/d\rfloor-1\\}$)
that would have been obtained with a non distributed scan . This is depicted
in Figure 1b. With our previous notations, the internal state of the instance
$k$ is initialized with $s_{0,k}=s_{0}\cdot g^{k\cdot\lfloor p-2/d\rfloor}$
and is updated according to:

$s_{i,k}=g\cdot s_{i-1,k}\mod p$ (3)

In all these three settings, the choice of the values ($g$, $s_{0}$) is
important as these values can be used to characterize the scan. Two scans with
the same couple of values $(g,s_{0})$ will generate the same IPv4 sequence of
addresses. In the case of distributed scans, it can also be used to identify
the machines that cooperate to the same scan. ZMap generates these values
pseudo-randomly by applying the block cipher AES to a selected seed. By
default, ZMap obtains the seed randomly from the Unix /dev/random device. The
user can, however, specify a seed as an option (-e) or in the configuration
file. Hence, when the user repeatedly launches ZMap with a specific seed, the
same values ($g$, $s_{0}$) are generated and the same sequence of addresses
will be probed.

###  3.2 Mapping function

The sequence of scanned IPv4 addresses is obtained by applying a mapping
function $f$ to the current internal state at each step of the ZMap generation
process.

The function $f$ is built at the initialization of the scan and depends on two
parameters: a whitelist of IPv4 addresses $\mathcal{W}$ and a blacklist
$\mathcal{B}$. The whitelist $\mathcal{W}$ contains the addresses that the
user has specified to scan and the blacklist $\mathcal{B}$ contains the
addresses to skip. Hence, if $\mathcal{S}$ is the set of IPv4 addresses that
will eventually be scanned, we have the relation
$\mathcal{S}=\mathcal{W}\setminus\mathcal{B}$.

The function $f$ is a one-to-one mapping from the integers $\\{1,...,n\\}$ to
the address set $\mathcal{S}$. The address sequence $(ip_{1},...,ip_{n})$ is
then obtained by applying $f$ to the internal states $s_{i}$ when $s_{i}\leq
n$, as described in Algorithm 1.

Algorithm 1 IPv4 sequence generation $(ip_{j})_{j\in\\{1,...,n\\}}$

$j\leftarrow 0$

for $i\in\\{1,...,p\\}$ do

Update $s_{i}$ using Eq. 1 (or Eq. 2,3 in case of sharding)

if $s_{i}\leq n$ then

$ip_{j}\leftarrow f(s_{i})$

$j\leftarrow j+1$

end if

end for

The construction of $f$ relies on a tree structure $T$ that speeds up the
computation of the addresses. $T$ is a binary tree that is built at the
initialization of the scan, when the address lists $\mathcal{W}$ and
$\mathcal{B}$ are provided. The leaves of $T$ represent disjoint subnets of
$\mathcal{S}$ and the union of the leaves covers $\mathcal{S}$. The network
representation $t_{l}$ of a leaf $l$ in $T$ is the following: for each node,
we assign the label $0$ to the left part of the tree under the node and $1$ to
the right part. With this coding, a leaf $l$ of $T$ can be represented as a
finite sequence $(x_{1},...,x_{q})$ of node selections where
$x_{i}\in\\{0,1\\}$. Using the CIDR notation, we associate to $l$, the subnet
$t_{l}\subseteq\mathcal{S}$ whose prefix address is the bits
$(x_{1},...,x_{q})$ and the prefix length is $q$. Furthermore, by construction
of $T$, we enforce that, for each leaf $l$, $t_{l}$ is maximal in
$\mathcal{S}$ in the sense that there is no subnet
$t^{\prime}\subseteq\mathcal{S}$ with $t_{l}\subseteq t^{\prime}$ and prefix
length smaller than $q$.

At each level $i$, the nodes of $T$ are labeled with the number of addresses
in $\mathcal{S}$ that fall in the subnet of prefix length $i$ defined by the
node. When the building process of $T$ is finished, the mapping of an index
$x\leq n$ to an address is performed by efficiently computing $f_{0}(x)=ip$
where $ip$ is the $x$th address in the list $\mathcal{S}$ ordered by the
integer comparison of the host byte representation of the IPv4 addresses. This
computation is performed by applying recursively Algorithm 2 to the tree $T$.

Algorithm 2 Index to address function $f_{0}(T,x)$

if $T$ is a leaf $l$ then

$ip\leftarrow x_{1}\cdot 2^{31}+x_{2}\cdot 2^{30}+...+x_{q}+x$ where
$(x_{1},...,x_{q})$ is the sequence that codes the leaf

return the IPv4 address corresponding to $ip$

else

Let $T_{0}$ the left subtree of $T$

Let $T_{1}$ the right subtree

Let $n_{0}$ the label of the left node of $T$ (number of addresses in the left
subtree)

if $x\leq n_{0}$ then

return $f_{0}(T_{0},x)$

else

return $f_{0}(T_{1},x-n_{0})$

end if

end if

###  3.3 Radix table

In the last versions of ZMap (starting from v1.1.0 which was released on
November 18th 2013), a lookup table called the radix table is used for
speeding up the computation of the addresses in addition to the tree $T$. The
radix table $R$ contains the CIDR addresses of all the subnets of prefix
length 20 included in $\mathcal{S}$. For these versions of ZMap, the mapping
function $f$ can be decomposed into two subfunctions $f_{0}$ and $f_{1}$. If
the index $x\in\\{1,...,n\\}$ is less than $n_{R}\cdot 2^{12}$, where $n_{R}$
is the length of the radix table, then the radix table $R$ is used for the
computation and $f(x)=f_{1}(R,x)$. On the other hand, if $x>n_{R}\cdot
2^{12}$, then the tree $T$ built on the remaining addresses of $\mathcal{S}$
is used and $f(x)=f_{0}(T,x-n_{R}\cdot 2^{12})$.

The radix table $R$ contains the CIDR addresses of all the subnets of prefix
length 20 included in $\mathcal{S}$ and is ordered by the integer comparison
of the prefix in their host byte representation. If $i$ is an integer smaller
than $n_{R}$, $R[i]$ is the $i$th subnet of prefix length 20 included in
$\mathcal{S}$. Then $f_{1}(R,x)$ is defined as the $j$th address of the subnet
$R[i]$ with $i$ the integer division of $x$ by $2^{12}$ and $j=x\mod 2^{12}$
(see Algorithm 3).

Algorithm 3 Index to address function $f_{1}(R,x)$

$i\leftarrow\Bigl{\lfloor}\dfrac{x}{2^{12}}\Bigr{\rfloor}$

$j\leftarrow x-i\cdot 2^{12}$

$ip\leftarrow R[i]\cdot 2^{12}+j$

return the IPv4 address corresponding to $ip$

##  4 ZMap detection methods

We present two detection methods of ZMap scans based on the cryptanalysis of
the IPv4 address generation. These methods find the generator of the scan $g$
given a few samples of IPv4 addresses extracted from the scan.

###  4.1 Observation network

We denote by $\mathcal{O}$ the set of IPv4 addresses that are monitored by the
administrator of a network. In the case of an Internet-wide scan, some of the
scanned addresses of $\mathcal{S}$ will reach the observed network
$\mathcal{O}$. We then make several hypotheses.

First, the administrator can retrieve a significant part of these addresses,
and determine their arrival order. Notice that we do not assume that all the
scanned addresses that lay in the set $\mathcal{O}$ are observed by the
administrator: some loss can occur during the capture of the packets. However,
the capture quality (packet loss rate and packet reordering) and the monitored
network size both affect the performance (speed and success) of our detection
methods.

Second, we also suppose that the observation network is completely included in
a subnet of the scanned addresses. Formally, if we order the monitored
addresses by their host byte representation, we suppose that there is no IPv4
address $ip\not\in\mathcal{S}$ such that $o_{1}<ip<o_{2}$ with $o_{1},o_{2}$
in $\mathcal{O}$. This occurs when $\mathcal{O}$ is a single subnet and there
is no blacklisted address in $\mathcal{O}$. Durumeric et al. [16] reported
that they received exclusion requests for 5.4 millions IP addresses. They thus
added 21,094 subnets of prefix length 24 to the default blacklist [7]. This
represents 0.1% of all subnets of prefix length 24. It means that if
$\mathcal{O}$ is a subnet of prefix length 16 (resp. 20), and we consider the
worst case where the blacklisted subnets are uniformly distributed among the
remaining subnetworks of prefix length 24, then, the probability that
$\mathcal{O}$ fulfill our hypothesis is 72% (resp. 98%). This hypothesis on
the observation network can greatly simplify the computation of the mapping
function described in Section 3 as we show in the following Theorem.

######  Theorem 1.

Suppose that there is a subnet $\mathcal{I}$ such that
$\mathcal{O}\subseteq\mathcal{I}\subseteq\mathcal{S}$. Then there is an
integer that we denote offset such that for all $x\in\\{1,...,n\\}$ with
$f(x)\in\mathcal{O}$

$f(x)=hton(x+\mathit{offset})$

where $hton$ is the function that converts host bytes to IPv4 addresses.

###### Proof.

Let first assume that there exists a subnet $\mathcal{I^{\prime}}$ of size
$2^{12}$ with $\mathcal{O}\subseteq\mathcal{I^{\prime}}\subseteq\mathcal{S}$.
If ZMap supports radix table then $f(x)=f_{1}(R,x)$. Since $f(x)$ is in
$\mathcal{O}$, then $f_{1}(R,x)$ is in $\mathcal{I^{\prime}}$. We deduce that
there is a $i_{0}$ such that $R[i_{0}]=\mathcal{I^{\prime}}$ and $\lfloor
x/2^{12}\rfloor=i_{0}$. From the definition of $f_{1}$, $f_{1}(R,x)$ is the
$j$th address of the subnet $R[i_{0}]$. Hence we have $f(x)=hton(N+j)$ with
$N$ the host byte representation of the subnet
$R[i_{0}]=\mathcal{I^{\prime}}$. Then $f(x)=hton((N-i_{0}\cdot
2^{12})+(i_{0}\cdot 2^{12}+j))=hton(\mathit{offset}+x)$ with
$\mathit{offset}=N-i_{0}\cdot 2^{12}$.

Now assume that ZMap still supports radix table, but the minimal size of the
subnets $\mathcal{I^{\prime}}\supseteq\mathcal{O}$ is greater than $2^{12}$.
Let $\mathcal{I^{\prime\prime}}$ such a minimal network. Then
$\mathcal{I^{\prime\prime}}=\mathcal{I}_{0}\cup...\cup\mathcal{I}_{k}$ where
$\mathcal{I}_{0},...,\mathcal{I}_{k}$ are the subnets of
$\mathcal{I^{\prime\prime}}$ of size $2^{12}$ ordered by their prefix. From
the previous part of the proof, there exist
$\mathit{offset}_{0}$,…,$\mathit{offset}_{k}$ such that
$f(x)=hton(\mathit{offset}_{j}+x)$ when $f(x)$ is in $\mathcal{I}_{j}$.
However, it is easy to notice that if we write
$\mathit{offset}_{j}=N_{j}-i_{j}\cdot 2^{12}$, then $N_{j}=N_{0}+j\cdot
2^{12}$ and $i_{j}=i_{0}+j$. Therefore
$\mathit{offset}_{j}=\mathit{offset}_{0}$ for all $j\in\\{1,...,k\\}$.

Finally, assume that ZMap does not support radix computation or that the
maximal size of the subnet $\mathcal{I^{\prime}}\supseteq\mathcal{O}$ is less
than $2^{12}$. Then we have $f(x)=f_{0}(T,x)$. Since $\mathcal{I}$ is a subnet
of $\mathcal{S}$, $\mathcal{I}$ is included in a subnet $\mathcal{I^{\prime}}$
represented by a leaf $l$ of $T$. By definition $f_{0}(T,x)$ is the $j$th
address of the subnet $\mathcal{I^{\prime}}$, with $j=x-x_{0}$, and $x_{0}$ is
the index of the first address of $\mathcal{I^{\prime}}$. Hence we have
$f_{0}(T,x)=hton(N+j)$ with $N$ the host byte representation of the prefix
$\mathcal{I^{\prime}}$. Therefore
$f(x)=hton((N-x_{0})+x)=hton(\mathit{offset}+x)$ with
$\mathit{offset}=N-x_{0}$. ∎

At first glance, the second and the last hypotheses of the proof lead to the
same result and it seems useless to fulfill the strongest hypothesis that
$\mathcal{I}$ has size $\geq 2^{12}$. There is, however, a difference that has
an impact on the detection: when the monitored network is included in a subnet
of size $\geq 2^{12}$ with no blacklisted address and ZMap supports radix
table, then there are only $2^{20}$ possible values of offset. If the
detection method requires to compute the list of indices from the observed
addresses, then we may have to test $2^{20}$ offsets, instead of $2^{32}$
values in the last hypothesis of the proof.

###  4.2 Detecting local scans

The first detection method that we present can be applied to the scans for
which $\mathcal{S}\subseteq\mathcal{O}$. This case occurs when the observation
network $\mathcal{O}$ is a large subnet of Internet (e.g. with prefix length
16), or if we want to detect small scans that are local to the observation
network (e.g. scans of prefix length 24 in an observation network of prefix
length 22).

We also assume that the size of the scan $n$ is close to the prime number $p$
used at the initialization of the scan. This means that the subnet specified
by the user (i.e. the whitelist $\mathcal{W}$) is a subnet of prefix length
$8,16,24,28$ or $32$ and the blacklist $\mathcal{B}$ is disproportionately
small compared to the size of the whitelist.

Let $o_{1},o_{2}$, and $o_{3}$ be three consecutively observed IPv4 addresses.
As described in Section 3, there is a sequence of internal states
$s_{i_{1}},s_{i_{2}},s_{i_{3}}$ such that $f(s_{i_{1}})=o_{1}$,
$f(s_{i_{2}})=o_{2}$, $f(s_{i_{3}})=o_{3}$. From the hypothesis on the small
difference between $n$ and $p$, there is a high probability that $s_{i_{1}+1}$
and $s_{i_{1}+2}$ are less than $n$. Since $\mathcal{S}\subseteq\mathcal{O}$,
we deduce that $f(s_{i_{1}+1})$, $f(s_{i_{1}+2})$ are in $\mathcal{O}$ and
$i_{2}=i_{1}+1$, $i_{3}=i_{1}+2$, i.e. the internal states of consecutively
observed addresses are also consecutive. We can apply the following theorem to
retrieve $g$.

######  Theorem 2.

Let $o_{1},o_{2},o_{3}$ three IPv4 addresses such that there exists an integer
$i$ with $f(s_{i})=o_{1}$, $f(s_{i+1})=o_{2}$, $f(s_{i+2})=o_{3}$. Then we
have

$g=\frac{h_{3}-h_{1}}{h_{2}-h_{1}}-1\mod p$

where $h_{1}$, $h_{2}$, $h_{3}$ are the host byte representations of $o_{1}$,
$o_{2}$, $o_{3}$.

###### Proof.

From Theorem 1, $h_{j}=s_{j}+\mathit{offset}$ for $j$ in $\\{1,2,3\\}$. By
definition of the ZMap iteration process, we have $h_{i}\equiv s_{1}\cdot
g^{i-1}+\mathit{offset}\pmod{p}$ where the symbol $\equiv$ denotes the
congruence relation in the modular arithmetic. We deduce that
$h_{2}-h_{1}\equiv s_{1}\cdot(g-1)\pmod{p}$ and $h_{3}-h_{1}\equiv
s_{1}\cdot(g^{2}-1)\pmod{p}\equiv s_{1}\cdot(g+1)\cdot(g-1)\pmod{p}$. Since
$g$ is a primitive root, $g\neq 1$ and we have the result. ∎

The description of the detection method is given in Algorithm 4. Note that it
does not require any hypothesis on the offset value of the mapping function
$f$. Once $g$ is known, it is possible to retrieve this value by computing
$s_{i}=(h2-h_{1})/(g-1)\mod p$ and $\mathit{offset}=h_{1}-s_{i}$. This gives
additional information on the scanned addresses set $\mathcal{S}$ by using
Theorem 1.

Algorithm 4 Detection method $Det1(p,(o_{j})_{j\in\\{1,...,m\\}})$

Let $h_{j}$ the host byte representation of $o_{j}$ for $j\in\\{1,...,m\\}$

$g\leftarrow\frac{h_{3}-h_{1}}{h_{2}-h_{1}}-1$

$s\leftarrow\frac{(h2-h_{1})}{(g-1)}\mod p$

$\mathit{offset}\leftarrow h_{1}-s$

for $j\in\\{4,..,m\\}$ do

if $h_{j}\neq((s\cdot g^{j})\mod p+\mathit{offset})$ then

return "not a ZMap scan"

end if

end for

return $g,\mathit{offset}$

###  4.3 Detecting Internet-wide scans

We propose a second detection method that can be applied on scans whose scope
is much wider than the observation network. Even if the monitored network size
has an impact on the computation time of the detection algorithm (see Section
4.5 and Section 5.1), it is possible to detect internet-wide scans by using
small monitored networks. The method requires at least 20 packets for a high
probability of success (see below). Contrary to the previous method, it does
not require consecutive packets. In other words, packet loss does not impact
the success of this method.

This detection method relies on the following Theorem:

######  Theorem 3.

Let ($o_{1},...,o_{m}$) a sequence of scanned IPv4 addresses ordered according
to their packet arrival times, and ($h_{1},...,h_{m}$) their host byte
representations. For $b$ in $\mathbb{F}_{p}$, let $log_{a}(b)$ (or $log(b)$
for simplicity) the integer $x<p$ such that $b=a^{x}\mod p$ where $a$ denotes
a predefined primitive root of $\mathbb{F}_{p}$ (i.e. $a=2$ or $a=3$ according
to the value of $p\in\\{p_{0},...,p_{4}\\}$). If ($o_{1},...,o_{m}$) is
extracted from a ZMap scan, then there is an integer $k<p-1$ coprime with
$p-1$ such that sequence ($e_{2},...,e_{m}$) defined by

$e_{j}=log\left(\frac{h_{j}-\mathit{offset}}{h_{1}-\mathit{offset}}\mod
p\right)\cdot k^{-1}\mod p-1$

is strictly increasing.

Furthermore, suppose that $k$ satisfies the property above, and let
$r=gcd(e_{2},...,e_{m})$ and $k^{\prime}=k\cdot r$. Then, with some additional
assumptions on the discrete log distribution, we have

$\Pr[(o_{1},...,o_{m})\;is\;a\;ZMap\;scan\;and\;k^{\prime}=log(g)]\\\
\geq\left(1-\frac{1}{(m-1)!}\right)^{\phi(p-1)}$

where $\Pr$ is the probability measure and $\phi$ is the Euler’s totient
function.

###### Proof.

Let ($i_{1},...,i_{m}$) the sequence of state indexes such that
$h_{j}=s_{i_{j}}+\mathit{offset}=((s_{0}\cdot g^{i_{j}})\mod
p)+\mathit{offset}$ for $j$ in $\\{1,...,m\\}$. Let $\delta i_{j}=i_{j}-i_{1}$
for $j$ in $\\{2,...,m\\}$. $\delta i_{2},...,\delta i_{m}$ is an increasing
sequence and if $k=log(g)$, then $\delta i_{j}=e_{j}$. This proves the
existence of $k$.

Notice that if $\delta i_{m}\ll p$ and if $r$ is an integer with
$r<\frac{p}{\delta i_{m}}$ and $r$ coprime with $p-1$, then the sequence
$r\cdot\delta i_{2},...,r\cdot\delta i_{m}$ is also increasing and
$r\cdot\delta i_{j}=e_{j}$ for $k=log(g)\cdot r^{-1}\mod(p-1)$.

Let

$A=\\{log(g)\cdot r^{-1}mod(p-1)\mid r<\frac{p}{\delta i_{m}}\;\\\
and\;r\;coprime\;with\;p-1\\}.$

If $k\in A$, by assuming that $gcd(\delta i_{2},...,\delta i_{m})=1$ then we
have $r=gcd(e_{2},...,e_{m})$ and therefore $log(g)=gcd(e_{2},...,e_{m})\cdot
k$.

Now suppose that $k\not\in A$ and we want to estimate the probability that $k$
satisfies the property of the theorem ($A$ is the empty set if
$o_{1},...,o_{m}$ are not generated by a ZMap scan). We assume that for any
$k$, the sequence $(e_{j})_{j\in\\{2,...,m\\}}$ defined by $k$ is
equidistributed. This assumption stems from the fact that discrete logarithm
has an uniform distribution on arithmetic subsets of $\mathbb{F}_{p}$ when
$p\rightarrow\infty$ as stated in [20]. Let $\Pr_{k}(e_{2}<...<e_{m})$ the
probality that the sequence ($e_{2}$,…,$e_{m}$) defined for a fixed $k$ is
increasing. Then for $k\not\in A,\Pr_{k}(e_{2}<...<e_{m})=\frac{1}{(m-1)!}$ as
there are $(m-1)!$ permutations of $\\{2,...,m\\}$ and each ordering of
$(e_{j})_{j\in\\{2,...,m\\}}$ can be defined by one of these permutations. We
also assume that the probabilities that $(e_{j})_{j\in\\{2,...,m\\}}$ is not
increasing are independent for (almost) all $k$. Hence, the probability that
for all $k\not\in A$, $(e_{j})_{j\in\\{2,...,m\\}}$ is not increasing can be
bounded from below by

$\prod_{k\;coprime\;with\;(p-1)}Pr_{k}[(e_{j})_{j\in\\{2,...,m\\}}\;is\;not\;\\\
increasing]=\left(1-\frac{1}{(m-1)!}\right)^{\phi(p-1)}.$

Therefore, if $k$ defines an increasing sequence
$(e_{j})_{j\in\\{2,...,m\\}}$, then

$Pr[k\in A]\geq\left(1-\frac{1}{(m-1)!}\right)^{\phi(p-1)}.$

∎

The description of the ZMap detection algorithm is given in Algorithm 5.

Algorithm 5 Detection method
$Det2(p,\mathit{offset},(o_{j})_{j\in\\{1,...,m\\}})$

for $j\in\\{2,...,m\\}$ do

$f_{j}\leftarrow
log_{a}\left(\frac{h_{j}-\mathit{offset}}{h_{1}-\mathit{offset}}\mod p\right)$
with $h_{j}$ the host byte representation of $o_{j}$

end for

for $k\in\\{1,...,p-1\\}$ and $k$ coprime with $p-1$ do

for $j\in\\{2,..,m\\}$ do

$e_{j}\leftarrow f_{j}\cdot k$

if $e_{j}\leq e_{j-1}$ then

break

end if

if $j=m$ then

$r\leftarrow gcd(e_{2},...,e_{m})$

return $g=a^{k\cdot r}$

end if

end for

end for

return "not a ZMap scan"

The discrete logarithm $log_{a}$ can be efficiently computed by using baby-
step giant-step algorithm [35] or Pohlig-Hellman algorithm [33]. The
computation complexity of the discrete logarithm is $\mathcal{O}(\sqrt{p})$
for baby-step giant-step and $\mathcal{O}\left(\sum_{i}{y_{i}(\log
n+\sqrt{x}_{i})}\right)$ with $n=p-1=\prod_{i}x_{i}^{y_{i}}$ for Pohlig-
Hellman. Since the value of $p$ is at most $p_{4}=2^{32}+15$, we can expect to
perform the computation respectively in $2^{16}$ or $2^{10}$ operations. The
iteration of $k$ amongst the numbers coprime with $p-1$ can also be
efficiently performed by precomputing the list of such coprime numbers and
storing them into a file. During the main iteration loop of Algorithm 5, the
file takes at most $4\cdot\phi(p_{4}-1)=4,5$ GB in memory. Actually, the
critical part of the algorithm is the multiplication of the $f_{j}$ by $k$
which is performed $j_{m}\cdot\phi(p-1)$ times in the worst case of a full
iteration over the coprime integers ($j_{m}$ is the mean value of the least
$j\leq m$ such that $e_{j}\leq e_{j-1}$, with the assumptions on the discrete
log distribution of Theorem 3 we can show that $j_{m}=e\approx 2.72$). This
results in $j_{m}\cdot\phi(p-1)=2.72\cdot 1136578560\approx 2^{32}$ operations
with $p=p_{4}$.

The number of IPv4 addresses $m$ extracted from the scan has also an impact on
the success of the detection method. Let
$\theta(m,p)=1-\left(1-\frac{1}{(m-1)!}\right)^{\phi(p-1)}$ the upper bound of
the failure probability of Theorem 3 with $m$ addresses. In the context of
ZMap scan detection, this failure probability corresponds to the false
positive rate. For $p_{4}=2^{32}+15$, we have $\theta(14,p_{4})=0.16$,
$\theta(15,p_{4})=0.013$, $\theta(17,p_{4})=5.4\cdot 10^{-5}$, and
$\theta(20,p_{4})=9.3\cdot 10^{-9}$. As we test a high volume of scans in our
experiments, we select $m=20$ for our implementation of the detection tool to
avoid false positives. Also note that, when the $\mathit{offset}$ value is
known, the false negative rate is equal to $0$.

###  4.4 Offset computation

The drawback of the detection method $Det2$ is that it requires to know the
$\mathit{offset}$ value of the generated IPv4 addresses (Section 4.1).
However, this value can be retrieved in two special cases. The first case is
when the scan does not use any blacklist (i.e. $\mathcal{B}=\emptyset$). The
second case is when the scan uses the default ZMap blacklist (i.e
$\mathcal{B}=\mathcal{B}_{ZMap}$ [7]). Let $o_{1},...,o_{m}$ be a sequence of
IPv4 addresses to characterize. For each whitelist $\mathcal{W}_{k}$ that
corresponds to a subnet $t_{k}$ of prefix length $k$ containing
$o_{1},...,o_{m}$, we can compute the two corresponding $\mathit{offset}$
values $\mathit{offset}_{k}^{\mathcal{B}_{ZMap}}$ and
$\mathit{offset}_{k}^{\emptyset}$. Then, for each $k\in\\{0,...,24\\}$, we
apply $Det2$ with the inputs $o_{1},...,o_{m}$, $\mathit{offset}_{k}^{i}$ and
$p_{r(k)}$ where $p_{r(k)}$ is the prime number associated to the size of the
network $t_{k}$. This overall detection method managed to identify and
characterize a large amount of ZMap scans, as we will see later in our
experiments (see Section 5).

###  4.5 Offset brute forcing

When ZMap uses a custom blacklist, the detection and the characterization of
the scan can be performed by brute forcing the $\mathit{offset}$ value. If we
assume that ZMap supports radix table for IPv4 computation as described in
Section 3 and that the observation network $\mathcal{O}$ is included in a
subnet $\mathcal{I}\subseteq\mathcal{S}$ of size $\geq 2^{12}$ (which is the
case when $\mathcal{O}$ is a subnet with no blacklisted IP and $\mathcal{S}$
is an Internet-wide scan), we have shown in Theorem 1 that there are $2^{20}$
potential values for $\mathit{offset}$. Therefore, there are $2^{20}$ calls to
$Det2$ for an exhaustive search of the offset value. For each call of
Algorithm 5, it is also possible to reduce the number of integers $k$ coprime
with $p-1$ that are tested:

######  Theorem 4.

Assume that ($o_{1},...,o_{m}$) is a sequence of ZMap probed IPv4 addresses in
an observation network $\mathcal{O}$ which is included in the total scanned
addresses $\mathcal{S}$. Let $k$ a random number drawn uniformly from the
integers in $\\{1,...,p-1\\}$ coprime with $p-1$ and $\Gamma$ the property on
$k$ defined in Theorem 3. Then

$Pr[k\text{ satisfies
}\Gamma]\approx\frac{|\mathcal{O}|}{(m-1)\cdot|\mathcal{S}|}.$

###### Proof.

Let ($o_{1},...,o_{l}$) a sequence of probed IPv4 addresses in the observation
network and ($i_{1},...,i_{l}$) the corresponding indices of the states, i.e.
$o_{j}=hton(s_{i_{j}}+\mathit{offset})$ for all $j$ in $\\{1,...,l\\}$.

If we denote $\gamma_{j}=i_{j}-i_{j-1}$ and
$\gamma_{mean}=mean\\{\gamma_{j}\mid 2\leq j\leq l\\}$, then we can notice
that for $l$ sufficiently large,
$\gamma_{mean}=\frac{|\mathcal{S}|}{|\mathcal{O}|}$. Since the sequence of
$\gamma_{j}$ can be viewed as a sequence of independent and identically
distributed random variables of mean $\gamma_{mean}$ and $\delta
i_{m}=i_{m}-i_{1}=\gamma_{2}+...+\gamma_{m}$, by the law of large numbers we
can approximate $\delta i_{m}$ by $\hat{\delta}i_{m}=(m-1)\cdot\gamma_{mean}$.
Let

$A=\\{log(g)\cdot r^{-1}\mid r<\frac{p}{\delta
i_{m}}\;and\;r\;coprime\;with\;p-1\\}.$

As we have shown in Theorem 3, if $k$ is in $A$ then $k$ satisfies $\Gamma$,
and the probability that $k$ satisfies $\Gamma$ if $k$ is not in $A$ is very
small. Therefore

$Pr[k\text{ satisfies }\Gamma]\approx Pr[k\in A].$

From our hypothesis on the discrete logarithm distribution, we can assume that
$A$ is equally distributed in the integers coprime with $p-1$. Hence

$Pr[k\in A]=\frac{|A|}{\phi(p-1)}=\frac{1}{\delta
i_{m}}\approx\frac{|\mathcal{O}|}{(m-1)\cdot|\mathcal{S}|}.$

∎

Theorem 4 underlines the fact that the size of the observation network
$\mathcal{O}$ has an impact on the computation time of Algorithm 5. If
($o_{1},...,o_{m}$) is a sequence of ZMap probed IPv4 addresses then the mean
number of modular multiplications $f_{j}\cdot k$ is equal to
$\frac{e\cdot(m-1)\cdot|\mathcal{S}|}{|\mathcal{O}|}$. For example, on an
Internet-wide scan where
$\mathcal{S}=\mathcal{S}_{Internet}=\\{\text{"0.0.0.0"},...,"\text{255.255.255.255"}\\}$,
if the observation network $\mathcal{O}$ is a /24 subnet and the number $m$ of
ZMap probed addresses is equal to $20$, then the mean number of operations of
Algorithm 5 is approximately equal to $19\cdot 2.72\cdot 2^{24}=2^{30}$, and
if $\mathcal{O}$ is a /16 subnet then the mean number of operations is
approximately equal to $2^{22}$.

Theorem 4 also shows that we can improve the computation time of Algorithm 5
by reducing the number of tested integers $k$ accordingly to a confidence
threshold $\alpha$ which will correspond to the false negative rate. Let
$T_{k_{max}}$ the first $k_{max}$ integers coprime with $p-1$. By applying
Theorem 4, if ($o_{1},...,o_{m}$) is a ZMap scan and the integers $k$ tested
in Algorithm 5 are restricted to $T_{k_{max}}$, then

$1-\alpha=Pr[\exists k\in T_{k_{max}}\text{s.t. }k\text{ satisfies }\Gamma]\\\
\geq 1-\left(1-\frac{|\mathcal{O}|}{(m-1)\cdot|\mathcal{S}|}\right)^{k_{max}}$

where $\alpha$ is the false negative rate of the restricted algorithm.

By fixing the false negative rate $\alpha$, the minimum number of integers
$k_{max}$ to test is equal to

$k_{max}\approx\frac{log(\alpha)}{log(1-\frac{|\mathcal{O}|}{(m-1)\cdot|\mathcal{S}|})}.$

If we apply the restricted algorithm $2^{20}$ times for an exhaustive search
of the $\mathit{offset}$ value, then the overall false negative rate is equal
to $1-(1-\alpha)^{2^{20}}$ and the mean number of operations is equal to
$k_{max}\cdot e\cdot 2^{20}$.

Let consider the case of the detection and the characterization of ZMap
Internet-wide scans with a custom blacklist of IP addresses where
$\mathcal{S}=\mathcal{S}_{Internet}$ and $\mathcal{O}$ is a /16 subnet. If we
want to achieve a false negative rate $\alpha=10^{-8}$ for the restricted
version of Algorithm 5, then we can limit the number of integers coprime with
$p-1$ to $k_{max}=2^{25}$. The overall false negative rate is equal to $0.01$
and the overall number of operations for each scan is equal to $2^{46}$. This
takes roughly $15$ days on a single core of a Intel Xeon E7-4820.

###  4.6 Summary

We summarize the detection methods’ usages regarding scan types in Table 1.

Table 1: Scan types and detection methods. Scan types |  Detection method
---|---
/24 scans or large observation network (>/16) |  $Det1$
Scans with default or empty blacklists |  $Det2$ with offset computation
Scans with custom blacklists |  $Det2$ with offset brute forcing

##  5 Results

This section presents our identification and characterization results using
$Det2$ and pre-computed offsets on synthetic and real network traffic. We do
not run the $Det1$ method because the odds of observing three consecutive
packets inside our datasets (see Section 5.2.1) are very low. We also do not
run the offset bruteforcing method because computing costs are too expensive
(see Section 4.5). The method used hereafter in this section is $Det2$ with
pre-computed offsets.

###  5.1 Synthetic data

In this section, we analyze the detection performance of the method $Det2$
using synthetic data. We collect destination IP address sequences using the -d
(or –dryrun) option of ZMap. For each prefix size between $0$ and $24$, we
generate $100$ sequences of ZMap scans with different seeds. Then, we restrict
each of these sequences to the IPv4 addresses that lay into the observation
network of the given prefix size. We also ensure that we generate enough
packets so that each scan contains $20$ packets in the observation network.

####  5.1.1 Size of observed prefix $\mathcal{O}$ vs detection runtime

In order to evaluate $Det2$ runtime, we measure the mean number of coprimes
tested in the main loop of Algorithm 5 for different observation network
sizes. We use a single thread to generate the packets. The detection method
$Det2$ identify all the ZMap scans and retrieve the correct generator $g$.

Figure 2: Mean number of coprimes tested for several sizes of observed prefix
$\mathcal{O}$.

Figure 2 describes the mean number of iterations against the sizes of observed
prefix $\mathcal{O}$. We observe that the empirical results are similar to
those obtained with the formula:
$t(\mathcal{O})=(m-1)\cdot\frac{|\mathcal{S}|}{|\mathcal{O}|}$. This validates
the approximation of the probability in Theorem 4.

####  5.1.2 Number of threads vs detection success

Figure 3: $Det2$ success rate for 2, 4 and 10 threads for several sizes of
observed prefix $\mathcal{O}$.

ZMap uses an option (-T) to control the number threads that send probing
packets. Threads use sharding (see Section 3.1) to share packet sending. Using
several threads may alter the packet sending order and thus impacts detection
success. Before December 6th, 2016 [3], the default number of threads was the
number of cores of the machine. In the current version of ZMap (post [3]), the
default number of thread is one.

Figure 3 depicts the method success rate against the number of threads used
for several sizes of observed prefix $\mathcal{O}$. We here use the first 20
packets observed as input to the $Det2$ method. We observe that smaller
numbers of threads yield higher success rates. This is expected because when
the thread number increases, the odds of observing a sequence from distinct
threads that cannot be identified also increase. Bigger prefix sizes yield a
smaller success rate for all configurations. The first 20 packets are quicker
to obtain with small prefix sizes. We thus hypothesize that, for small prefix
sizes, observed packets are often sent by the first launched thread. As the
prefix size increases, the first 20 packets are increasingly sent by distinct
threads which alter the original order.

###  5.2 Real world traffic

This section presents our identification and characterization results on real-
world data.

####  5.2.1 Datasets

We use two real-world network traffic datasets. The first dataset was
collected using a network telescope from June 2014 to January 2015. The
observed prefix changes along time, from a single /24 to three adjacent /24
prefixes inside a /22. The second dataset is the MAWI repository [2]. This
dataset is collected on a Japanese backbone link. We use the multi-day long
traces captured during the Day In The Life of Internet (DITL) event that took
place on April 11th and 12th in 2017. Unlike the publicly available MAWI
traces where IP addresses are anonymized, we use original IP addresses. We
restrict our observation to a single /16 to fulfill the hypothesis on the
observation network $\mathcal{O}$ from Section 4.1.

####  5.2.2 Pre-processing

We identify scanning IP addresses using two methods. First, we extract source
IP address that have at least a packet with the ZMap fingerprint (IP ID field
equals to 54321). Second, we apply the Threshold Random Walk [24] method using
Zeek/Bro. We then compute the union of source IP addresses extracted by the
methods above, and keep only the IP addresses that send packets to at least 5
distinct destination IPs. Individual scans performed by scanning IPs are then
identified using a burst detection method [26]. Table 2 presents detected
scans. We breakdown scans with more and less than 20 packets because the
$Det2$ method needs at least 20 packets (see Section 4.3). Scan with at least
95% of packets with the ZMap fingerprint (see above) are labelled as ZMap in
IP ID-related column hereafter. Overall, we identify 1,314,804 scans, and
apply the $Det2$ method on 639,599 ones.

Table 2: Scan data breakdown.
# IP | IP ID | Telescope | Backbone
---|---|---|---
|  | TCP | UDP | TCP | UDP
$<$ 20 IP |  | 546,259 | 11,599 | 717,643 | 39,303
$>=$ 20 IP | ZMap | 12,200 | 6,944 | 17,737 | 2,869
| Other | 197,421 | 612 | 391,901 | 9,915
| $\sum$ | 209,621 | 7,556 | 409,638 | 12,784

####  5.2.3 Identification results

Table 3: ZMap identification results. $\mathcal{B}_{ZMap}$ is the default list
used by ZMap described at [7], $\emptyset$ means that the scan does not use
any blacklist and $\mathcal{B}_{ZMap}\land\emptyset$ represents both default
blacklist and lack thereof.
IP ID field | Det2 | Telescope | Backbone
---|---|---|---
Result |  Blacklist used | TCP | UDP | TCP | UDP
# | % | # | % | # | % | # | %
ZMap | ✗ |  | 7,139 | 58.5 | 6,285 | 90.5 | 12,353 | 69.6 | 2,671 | 93.1
✓ | $\mathcal{B}_{ZMap}$ | 4,617 | 37.8 | 519 | 7.5 | 4,281 | 24.1 | 198 | 6.9
$\emptyset$ | 422 | 3.5 | 140 | 2.0 | 972 | 5.5 | - | -
$\mathcal{B}_{ZMap}\land\emptyset$ | 22 | 0.2 | - | - | 131 | 0.7 | - | -
$\sum$ | 5,061 | 41.5 | 659 | 9.5 | 5,384 | 30.4 | 198 | 6.9
$\sum$ |  | 12,200 |  | 6,944 |  | 17,737 |  | 2,869 |
Other | ✗ |  | 197,421 | 100 | 612 | 100 | 391,898 | 100 | 9,915 | 100
✓ | $\mathcal{B}_{ZMap}$ | - | - | - | - | 3 | 0.0 | - | -

Table 3 presents the identification results. For the telescope dataset, our
method is successful on 37.8% ZMap scans using TCP and 7.5% using UDP. For the
backbone dataset, percentages of successful identification are lower: 24.1%
(resp. 6.9%) for TCP (resp. UDP) scans. Overall, the majority of identified
scans use the default ZMap blacklist [7]. Only 3.5% (resp. 1.8%) of ZMap TCP
(resp. UDP) scans in the telescope data and 5.5% of TCP scans in the backbone
data do not use any blacklist. This means that they actually send packets to
IP addresses that are reserved such as private or multicast addresses. They
are thus needlessly increasing the workload of their infrastructure and their
upstream provider. We do not identify 58.5% ZMap scans using TCP and 90.5%
using UDP in the telescope dataset, and 69.2% ZMap scans using TCP and 93.1%
using UDP in the backbone dataset. By analyzing reverse-DNS entries, we
discover probing entities that confirm to us that they use customized
blacklist. In the telescope data, 60% of UDP scans with ZMap’s IPID are from
Rapid7 [1], and that 11% of TCP scans with ZMap’s IPID are from University of
Michigan [6]. We thus hypothesize that, either unidentified scans use custom
blacklists that we could not identify, or use several threads (see Section
5.1.2), or packet reordering occurred and our sampling strategy was not
sufficient to cope with this problem (see Section 5.2.5). A small number of
scans (22 in the telescope and 131 in the backbone) have been identified by
our tool as using both the default ZMap blacklist, and no blacklist at the
same time. This is due to the fact that some of the precomputed offsets
$\mathit{offset}_{k}^{\mathcal{B}_{ZMap}}$ and
$\mathit{offset}_{k}^{\emptyset}$ (as described in Section 4.4) are the same
when the scanned network is small. It is therefore impossible to determine if
these scans use any blacklist. The same generators are, however, returned in
both cases, and it is still possible to infer additional scan characteristics.

We detect 3 scans _without_ the ZMap specific value for IP ID field in the
backbone dataset. These scans are performed by 3 IP in the same /24 prefix.
They have many common characteristics: they start and finish around the same
time, they use the same generator $g$, exhibit low visibility (i.e. we do not
see all their packets, see Section 5.2.7), target the whole Internet and the
destination port is 443. We thus hypothesize that a single entity uses
sharding to decrease detection odds while removing ZMap IP ID field
fingerprint to increase stealthiness.

####  5.2.4 Run time

Table 4: ZMap identification run time (mean $\pm$ standard deviation in
seconds). $\mu$ is the mean. $\sigma$ is the standard deviation.
$\widetilde{x}$ is the median.
Blacklist |  Result | Telescope | Backbone |
---|---|---|---|---
$\mu$ | $\pm$ | $\sigma$ | $\widetilde{x}$ | $\mu$ | $\pm$ | $\sigma$ | $\widetilde{x}$ |
$\emptyset$ | ✗ | 333.3 | $\pm$ | 100.9 | 290.6 | 178.5 | $\pm$ | 22.6 | 183.1 |
✓ | 104.6 | $\pm$ | 93.7 | 59.2 | 56.0 | $\pm$ | 48.6 | 38.4 |
$\mathcal{B}_{ZMap}$ | ✗ | 351.3 | $\pm$ | 101.6 | 300.4 | 177.8 | $\pm$ | 22.6 | 182. |
✓ | 70.7 | $\pm$ | 38.1 | 58.5 | 57.1 | $\pm$ | 48.7 | 38.5 |

We instrument the execution time of our tool. The network telescope dataset is
analyzed using a machine with 4 Intel Xeon E7-4820 (octo core with Hyper-
Threading). The backbone dataset is analyzed using two machines with 2 Intel
Xeon E5-2650 (octo core with Hyper-Threading). In both cases, we restrict the
number of paralellized executions to avoid Hyper-Threading. Each scan is
analyzed by our method using a single core. Table 4 details the measured
execution time. When the identification is successful, duration averages
slightly more than a minute for the telescope dataset and slightly less than a
minute for the backbone data. When our method fails to identify a ZMap scan,
the average run time is around 5 minutes for the telescope data and 3 minutes
for backbone data.

####  5.2.5 Impact of destination IP address sequence sampling

Packet reordering occurs on devices [11] or may be caused by routing events
[30]. Network traffic analysis showed diverse percentage of packet reordering:
0.3 to 2% [32], 3.2% [36], 1 to 1.5% [23] and 0.074% [31]. These percentages
are significant and potentially threaten the result of our identification
method by inverting the order of consecutive observed packets $o_{i}$. In
order to alleviate this problem, we actually analyze both the raw sequence of
the first 20 observed packet $o_{i}$ and a _sampled_ sequence. This sequence
contains 20 packets spread in the raw sequence: the first packet is $o_{1}$,
the last one $o_{c}$ and the 18 other packets are evenly spread between
$o_{1}$ and $o_{c}$. Figure 4 provide an example of the sampling procedure for
a scan with 41 packets. We analyze both the raw sequence $\\{o_{1}\dots
o_{20}\\}$ and the sampled sequence which contain $o_{i}$ with $i={1\dots 41}$
and $i$ an odd positive integer.

Figure 4: Example of raw ($\bullet$) and sampled ($\circ$) sequences for a
scan containing 41 destination IP addresses. Table 5: Identification results
of scans with the ZMap fingerprint regarding the raw ($\bullet$) and sampled
($\circ$) sequences.
Blacklist |  Data type | Telescope | Backbone
---|---|---|---
TCP | UDP | TCP | UDP
# | % | # | % | # | % | # | %
$\mathcal{B}_{ZMap}$ | $\bullet\land\circ$ | 4,513 | 97.7 | 444 | 85.5 | 3,975 | 92.9 | 16 | 8.1
$\bullet\land\lnot\circ$ | 64 | 1.4 | 60 | 11.6 | 8 | 0.2 | 1 | 0.5
$\lnot\bullet\land\circ$ | 40 | 0.9 | 15 | 2.9 | 298 | 7.0 | 181 | 91.4
$\sum$ | 4,617 |  | 519 |  | 4,281 |  | 198 |
$\emptyset$ | $\bullet\land\circ$ | 350 | 82.9 | 105 | 75.0 | 954 | 98.1 | - | -
$\bullet\land\lnot\circ$ | 36 | 8.5 | 20 | 14.3 | 2 | 0.2 | - | -
$\lnot\bullet\land\circ$ | 36 | 8.5 | 15 | 10.7 | 16 | 1.6 | - | -
$\sum$ | 444 |  | 140 |  | 972 |  | - |
$\mathcal{B}_{ZMap}$-$\emptyset$ | $\bullet\land\circ$ | 1 | 4.5 | - | - | 4 | 3.1 | - | -
$\bullet\land\lnot\circ$ | 4 | 18.2 | - | - | 21 | 16.0 | - | -
$\lnot\bullet\land\circ$ | 17 | 77.3 | - | - | 106 | 80.9 | - | -
$\sum$ | 22 |  | - |  | 131 |  | - |
* | $\bullet\land\circ$ | 4,864 | 96.1 | 549 | 83.3 | 4,933 | 91.6 | 16 | 8.1
$\bullet\land\lnot\circ$ | 104 | 2.1 | 80 | 12.1 | 31 | 0.6 | 1 | 0.5
$\lnot\bullet\land\circ$ | 93 | 1.8 | 30 | 4.6 | 420 | 7.8 | 181 | 91.4
$\sum$ | 5,061 |  | 659 |  | 5,384 |  | 198 |
Table 6: Targeted prefixes of scans with the ZMap fingerprint with full
percentages calculations.
Blacklist |  Prefix size | Telescope | Backbone
---|---|---|---
TCP | UDP | TCP | UDP
# | % | # | % | # | % | # | %
$\mathcal{B}_{ZMap}$ | 0 | 4,615 | 91.2 | 518 | 78.6 | 4,284 | 79.6 | 198 | 100.0
1 | 2 | 0.0 | 1 | 0.2 | - | - | - | -
$\emptyset$ | 0 | 414 | 8.2 | 140 | 21.2 | 972 | 18.1 | - | -
1 | 5 | 0.1 | - | - | - | - | - | -
3 | 3 | 0.1 | - | - | - | - | - | -
$\mathcal{B}_{ZMap}$ & $\emptyset$ | 5 | 1 | 0.0 | - | - | - | - | - | -
8 | 4 | 0.1 | - | - | 131 | 2.4 | - | -
16 | 17 | 0.3 | - | - | - | - | - | -
* | 0 | 5,029 | 99.4 | 658 | 99.8 | 5,256 | 97.6 | 198 | 100.0
1 | 7 | 0.1 | 1 | 0.2 | - | - | - | -
3 | 3 | 0.1 | - | - | - | - | - | -
5 | 1 | 0.0 | - | - | - | - | - | -
8 | 4 | 0.1 | - | - | 131 | 2.4 | - | -
16 | 17 | 0.3 | - | - | - | - | - | -

Table 5 presents the breakdown of our results regarding sampling. In the
telescope data, scans that were only successfully identified with sampling
represent a minority of all scans: 1.8% for TCP and 4.6% for UDP. In backbone
data, “sampling only” exhibits a bigger percentage of successfully identified
scans: 7.8% of TCP scans and 91.4% of UDP ones. We hypothesize that the bigger
monitored prefix (65,535 IP addresses in the backbone data and 768 IP
addresses in the telescope data) increases the odds of observing reordered
packets. Another possible explanation is that usual probing speed increased
from 2015 to 2017, and thus caused a packet reordering rise. We also observe
that some scan are identified with raw sequences but not with sampled
sequences. We hypothesize that this is due to time-splitting errors (see
Section 5.2.2). When this error happens, one or several scans using distinct
generators are merged together into a single one. This causes the sampled
sequence to contain observed packets from one or more scans with distinct
generators. In that case, our method is not successful.

####  5.2.6 Targeted prefix

Table 6 details the prefix targeted by the identified ZMap scans. More than
99% of scans found in the telescope data, and more than 97% of scans
identified in the backbone data, target a /0 prefix. This is expected since
ZMap is one of the two main high speed scanning tools (with Masscan [22]) that
aim to perform fast and large scale probing. We however note that some scans
target smaller prefixes (e.g. /16).

Figure 5:  Example of scanned network $\mathcal{S}$ and observed network
$\mathcal{O}$ with missing packet for $rk=4$ due to packet loss.

(a) Telescope

(b) Backbone

Figure 6: Scatter plot, histograms and ECDF of visibility $\mathcal{V}$
(percentage of observed probing packets) vs progress $\mathcal{P}$ of scans
with the ZMap fingerprint.

####  5.2.7 Scan packet visibility and scan progress

Let $o_{1},...,o_{m}$ the observed probed addresses, and $i_{1},...,i_{m}$ the
indices of the associated ZMap states, i.e. $o_{j}=hton(s_{i_{j}}+offset)$ for
all $j\in\\{1,...,m\\}$. $Det2$ using offset computation is able to identify
the generator and the prefix of the scan. Then, it is possible to retrieve the
internal state and the state index of any address $ip$ in $\mathcal{O}$
relatively to the first observed address $o_{1}$. Hence, we can reorder the
visible IP addresses of the observation network $\mathcal{O}$ accordingly to
their state indexes, or in other words in their scan order. If
$ip\in\mathcal{O}$, we define $rk(ip)$ the rank of the address for this order
starting from $o_{1}$ with $rk(o_{1})=1$ (see Figure 5). Formally, for each
$ip\in\mathcal{O}$ let $\delta(ip)=i_{ip}-i_{1}$ where $i_{ip}$ is the index
of the internal state that corresponds to $ip$ (i.e. $ip=f(s_{i_{ip}})$).
Then,
$rk(ip)=|\\{ip^{\prime}\in\mathcal{O}\mid\delta(ip^{\prime})<\delta(ip)\\}|$.

We then compute two metrics. First, we note $\mathcal{P}$, the progress of the
scan. It is the relative position of the index of the last observed probed
address within the observed IP addresses: $\mathcal{P}=\frac{rk(o_{m})}{l}$
where $l$ is the size of $\mathcal{O}$. This value reflects the scan
completion percentage. A $\mathcal{P}$ value lower than one, means the scan
did not reach all IP addresses in the observed prefix $\mathcal{O}$. This may
be caused by sharding [9], ZMap capping options (-n for probe number, -N for
result number, -t for time [8]), early interruption by user or incomplete
data. Second, we note $\mathcal{V}$ the visibility of the scan. It is the
percentage of observed probing packet: $\mathcal{V}=\frac{m}{rk(o_{m})}$. When
this value is lower than one, it means that some packets are missing, either
due to packet loss or sharding [9]. On Figure 5,
$\mathcal{P}=\frac{5}{10}=50\%$ and $\mathcal{V}=\frac{4}{5}=80\%$.

Figure 6 present our results. For the telescope (resp. backbone) dataset, 72%
(resp 85%) of identified scans have a $\mathcal{V}$ greater than 95%. Scans
with visibility smaller than 95% exhibit either progress smaller than 20% (67%
in the telescope dataset and 30% in backbone data), or progress higher than
90% (16% in the telescope dataset and 57% in backbone data). We hypothesize
that scans with low visibility exhibit low progress because they were stopped
as soon as users noticed packet loss or upstream overload. Scans with
visibility higher than 95% exhibit a behavior similar to those with low
visibility regarding progress $\mathcal{P}$. These scans’ progress values are
either smaller than 20% (40.8% in the telescope dataset and 99.7% in backbone
data), or higher than 90% (34.8% in the telescope dataset and 0.04% in
backbone data). We notice some peaks for progress value of 5 and 10% in Figure
6a. We hypothesize that these values are common for users that do not want to
scan the full IPv4 address space and use the -n option in ZMap. Sharding
causes visibility values lower than 50%. It is visible on the lower right part
of Figure 6a and on the lower part of Figure 6b. We observe many scans with
visibility values around 0.4 and 2.5% in Figure 6b. We hypothesize that these
scans uses sharding among 250 and 40 distinct sources.

Table 7: Breakdown of the numbers of IP address that we that identified that
used specific generators: 3 or 12.
Blacklist |  $g$ value | Telescope | Backbone
---|---|---|---
|  | TCP | UDP | TCP | UDP
$\mathcal{B}_{ZMap}$ | 3 | 9 | 4 | 3 | -
12 | 11 | 4 | 2 | -
$\emptyset$ | 3 | 9 | 1 | 4 | -
12 | 6 | 2 | - | -
Table 8: Breakdown of generators used by more than one IP. The first line
means that we identify one group group of 2 IP located in the same /24 with
the same $g$ performing TCP scans in the network telescope and 6 group of 2 to
28 IPs .
Blacklist |  Src IP location | Telescope | Backbone
---|---|---|---
TCP | UDP | TCP | UDP
| #$g$ | #IP | #$g$ | #IP | #$g$ | #IP | #$g$ | #IP
$\mathcal{B}_{ZMap}$ | Same /24 | 1 | 2 | - |  | 6 | 2-28 | - |
- |  | - |  | 1 | 3 | - |
- |  | - |  | 1 | 4 | - |
Several /24 | - |  | - |  | 8 | 39 |  |
Distinct /24 | - |  | - |  | - |  | 1 | 2
Mixed | 1 | 3 | - |  | - |  | - |
$\emptyset$ | Same /24 | 17 | 2 | - |  | 6 | 2-28 | - |
Distinct /24 | 2 | 2 | 3 | 2 | - |  | - |
1 | 3 | - |  | - |  | - |

####  5.2.8 Generator reuse

We analyze the generator $g$ (see Section 3.1) values identified by our
method. Generator can be set using the seed option (-e) for repeatability or
reproducibility purposes, or, to perform sharding (see Section 3.1) from
several machines or network interfaces. We first notice that specific
generators (3 and 12) are dominant across scans. Table 7 details these
occurrences. We could not find an explanation to the unusual occurrence of
these peculiar values. Table 8 presents generator reuse across IP addresses
inside both datasets for $g$ other than 3 and 12. We observe several instance
of generator reuse across a number of IP ranging from 2 to 39. This is
consistent with the sharding observed on Figure 6. Furthermore, we notice that
generator reuse mainly occur across IP located in the same /24. We hypothesize
that scanning entities usually use several colocated machines or VMs from a
single provider. We however notice that only 1.4% (resp 34%) of group of
source IP in the telescope (resp. backbone) dataset sharing generator values
have a visibility $\mathcal{V}$ value smaller than 50%. We thus hypothesize
that the majority of generator reuse is linked to setting of a constant seed
(-e option) for reproducibility purpose, and not sharding.

Telescope Backbone

(a) TCP

(b) TCP

(c) UDP

(d) UDP

Figure 7: Emitted packet rate of scans with the ZMap fingerprint and breakdown
regarding the use of sampling. Black (resp. red) curves represents scans only
identified with or without (resp. only with) the sampled sequence. BL:
$\mathcal{B}_{ZMap}$ and no BL: $\emptyset$.

####  5.2.9 Emitted packet rate

The number of packets emitted between the first probe $o_{1}$ and the last one
$o_{m}$ can be retrieved by computing $\delta rk=rk(o_{m})-rk(o_{1})$. The
elapsed time between the first observed packet and the last is $\delta
t=t_{m}-t_{1}$ (see Figure 5). We define the emitted packet rate $epr$ as:
$epr=\frac{\delta rk}{\delta t}=\frac{rk(o_{m})-rk(o_{1})}{t_{m}-t_{1}}$.

Figure 7 depicts emitted packet rate of scans. In order to provide reference,
we build $epr$ values for a SYN scan that uses 100Mb, 1GbE and 10GbE. We chose
the SYN scan because it is the most common type of ZMap scan observed [16].
Red curves show scans that were only identified using sampled sequence while
black ones represents scans identified with or without sampled sequence. Scans
only identified using sampled sequence exhibit a higher emitted packet rate
than other scans. We observe that scans identified without any blacklist
exhibit a lower packet rate than scans detected with the default ZMap
blacklist. Emitted packet rates are usually lower than 100Mb for TCP scans in
the backbone dataset. Other scans (TCP and UDP for the telescope dataset and
UDP for the backbone dataset) are mostly smaller than 1GbE. 1.1% of scans in
the telescope dataset and 0.4% in the backbone dataset exhibit $epr$
consistent with a throughput greater than 1GbE. Their visibility $\mathcal{V}$
(see Section 5.2.7) values are very small: for the telescope dataset, the
median value is 3% and the mean is 4.5%, for the backbone dataset, these
values are 0.04% and 1.9%. We hypothesize that high speed packet rate
saturates network equipment in the upstream provider of the source IP,
yielding packet losses.

##  6 Discussions

Overall, Det2 identification performance in a controlled setup are perfect
(see Section 5.1.1). We however do not identify 58.5% ZMap scans using TCP and
90.5% using UDP in the telescope dataset, and 69.2% ZMap scans using TCP and
93.1% using UDP in the backbone dataset. By analyzing reverse DNS records, we
find that a significant proportion of scans with ZMap’s IPID originate from
entities that use custom blacklists (see Section 5.2.3). Other possble
explanations are the use of several threads (see Section 5.1.2), or acute
packet reordering (see Section 5.2.5). While threading and packet reordering
are linked to ZMap usage and network conditions, and thus beyond our reach,
customized blacklist can be accounted for using offset bruteforce Section 4.5.
We thus intend to accelerate offset bruteforcing using GPUs.

We identify two biases for our characterization Section 5.2. First, backbone
data capture duration is 48 hours. Computed progress $\mathcal{P}$ (see
Section 5.2.7) values of scans which were not completely captured may thus be
lower than their real value. We however could not access bigger backbone
dataset to increase the reliability of our data. Second, we identified and
characterized 28.5% of all scans in our datasets. Our characterization results
may thus be biased towards scans that were identified by the $Det2$ method. We
want to improve our identification methods to reduce this bias.

We show in Section 4.1 that, in the context of the exclusion requests
documented by Durumeric et al. [16], if $\mathcal{O}$ is a /16 subnetwork,
then probability that $\mathcal{O}$ fulfills the hypothesis regarding
blacklisted addresses is 77%. This probability increases to 98% if
$\mathcal{O}$ is a /20 subnetwork. The size difference between the backbone
dataset and the telescope one may thus explain why $Det2$ is less successful
on the backbone dataset.

The new sharding mechanism [5] introduced in September 2017 impacts some of
our metrics. The progress value $\mathcal{P}$ of a completely observed scan
will be $\frac{1}{d}$, with $d$ the number of shards. Our results are not
affected by this change because our data was collected before it occurred.
Future experiments shall however be careful when using feature like
$\mathcal{P}$.

Ruth et al. [34] use ICMP answers to ZMap scans to gather information on the
Internet’s control plane. We envision that our identification method is able
to detect packet loss or packet reordering on Internet. By using several ZMap
scan observation points, and by combining this input with routing information,
it may be possible to locate and diagnose performance problems or failures.

##  7 Conclusions

In this work, we propose two cryptogranalysis methods to identify ZMap
scanning. We then apply the $Det2$ method with pre-computed offsets to
synthetic and real-world traffic, and evaluate its efficiency and computing
cost. Finally, we provide an in-depth analysis of ZMap usage in the wild
regarding impact of packet reordering, targeted prefix, generator reuse,
probing progress and visibility, sharding and probing speed. We thus identify
several misuses, such as private IP address probing and packet rate above
upstream capacity, that waste network resources.

### Acknowledgments

We would like to thank the WIDE project for granting us access to the MAWI
traces, and Kensuke Fukuda for providing the machines that were used to
process the network traffic.

## References

  * [1] An Introduction to Project Sonar.  https://web.archive.org/web/20190405162045/https://www.rapid7.com/research/project-sonar/.  Accessed: 2019-04-05.
  * [2] MAWI.  https://web.archive.org/web/20190116132315/http://mawi.wide.ad.jp/mawi/.  Accessed: 2019-01-28.
  * [3] Set default of sender threads to 1.  https://web.archive.org/web/20190128162043/https://github.com/zmap/zmap/commit/c04bc6d060f0ce1f198ff7eda6bf1a685d3b8efa.  Accessed: 2019-01-28.
  * [4] Shodan.  https://web.archive.org/web/20190116132401/https://www.shodan.io/.  Accessed: 2019-01-16.
  * [5] Simplify sharding implementation.  https://web.archive.org/web/20190122170448/https://github.com/zmap/zmap/commit/0bb01d879ebef2c28f038dd032745c72ad5789e9.  Accessed: 2019-01-22.
  * [6] University of Michigan.  https://web.archive.org/web/20190405162042/http://researchscan271.eecs.umich.edu/.  Accessed: 2019-04-05.
  * [7] ZMap - Blacklisting.  https://web.archive.org/web/20190116132221/https://github.com/zmap/zmap/wiki/Blacklisting.  Accessed: 2019-01-16.
  * [8] ZMap - Rate Limiting and Sampling.  https://web.archive.org/web/20190116132111/https://github.com/zmap/zmap/wiki/Rate-Limiting-and-Sampling.  Accessed: 2019-01-16.
  * [9] David Adrian, Zakir Durumeric, Gulshan Singh, and J Alex Halderman.  Zippier zmap: Internet-wide scanning at 10 gbps.  In WOOT, 2014.
  * [10] Mark Allman, Vern Paxson, and Jeff Terrell.  A brief history of scanning.  In IMC, pages 77–82, 2007.
  * [11] Jon CR Bennett, Craig Partridge, and Nicholas Shectman.  Packet reordering is not pathological network behavior.  Transactions on Networking, 7(6):789–798, 1999.
  * [12] Nevil Brownlee.  One-way traffic monitoring with iatmon.  In PAM, pages 179–188, 2012.
  * [13] Henri Cohen.  A course in computational algebraic number theory, volume 138.  Springer Science & Business Media, 2013.
  * [14] Christian Doerr, Mourad el Maouchi, Sille Kamoen, and Jarno Moree.  Scan prediction and reconnaissance mitigation through commodity graphics cards.  In CNS, pages 287–295, 2016.
  * [15] Zakir Durumeric, David Adrian, Ariana Mirian, Michael Bailey, and J. Alex Halderman.  A search engine backed by Internet-wide scanning.  In CCS, pages 542–553, 2015.
  * [16] Zakir Durumeric, Michael Bailey, and J. Alex Halderman.  An internet-wide view of internet-wide scanning.  In USENIX Security, pages 65–78, 2014.
  * [17] Zakir Durumeric, Eric Wustrow, and J Alex Halderman.  Zmap: Fast internet-wide scanning and its security applications.  In USENIX Security, pages 47–53, 2013.
  * [18] Nicolas Falliere.  A distributed cracker for VoIP.  https://web.archive.org/web/20190131095815/https://www.symantec.com/connect/blogs/distributed-cracker-voip, 2011\.  Accessed: 2019-01-31.
  * [19] Oliver Gasser, Quirin Scheitle, Sebastian Gebhard, and Georg Carle.  Scanning the ipv6 internet: towards a comprehensive hitlist.  In TMA, 2016.
  * [20] D Jason Gibson.  Discrete logarithms and their equidistribution.  Unif. Distrib. Theory, 7:147–154, 2012.
  * [21] Eduard Glatz and Xenofontas Dimitropoulos.  Classifying internet one-way traffic.  In IMC, pages 37–50, 2012.
  * [22] Robert David Graham.  MASSCAN: Mass ip port scanner.  https://web.archive.org/web/20190116132542/https://github.com/robertdavidgraham/masscan.  Accessed: 2019-01-16.
  * [23] Sharad Jaiswal, Gianluca Iannaccone, Christophe Diot, Jim Kurose, and Don Towsley.  Measurement and classification of out-of-sequence packets in a tier-1 ip backbone.  Transactions on Networking, 15(1):54–66, 2007.
  * [24] Jaeyeon Jung, V. Paxson, AW. Berger, and H. Balakrishnan.  Fast portscan detection using sequential hypothesis testing.  In Proc. of SP 2004, pages 211–225, 2004.
  * [25] Sheharbano Khattak, David Fifield, Sadia Afroz, Mobin Javed, Srikanth Sundaresan, Vern Paxson, Steven J Murdoch, and Damon McCoy.  Do you see what i see? differential treatment of anonymous users.  In NDSS, 2016.
  * [26] Jon Kleinberg.  Bursty and hierarchical structure in streams.  Data Mining and Knowledge Discovery, 7(4):373–397, 2003.
  * [27] Derek Leonard and Dmitri Loguinov.  Demystifying internet-wide service discovery.  Transactions on Networking, 21(6):1760–1773, 2013.
  * [28] Derek Leonard, Zhongmei Yao, Xiaoming Wang, and Dmitri Loguinov.  Stochastic analysis of horizontal IP scanning.  In INFOCOM, pages 2077–2085, 2012.
  * [29] Johan Mazel, Romain Fontugne, and Kensuke Fukuda.  Profiling internet scanners: Spatiotemporal structures and measurement ethics.  In TMA, pages 1–9, 2017.
  * [30] Jeffrey C Mogul.  Observing TCP dynamics in real networks, volume 22.  1992\.
  * [31] David Murray and Terry Koziniec.  The state of enterprise network traffic in 2012.  In APCC, pages 179–184, 2012.
  * [32] Vern Paxson.  End-to-end internet packet dynamics.  In ACM SIGCOMM Computer Communication Review, volume 27, pages 139–152, 1997.
  * [33] Stephen Pohlig and Martin Hellman.  An improved algorithm for computing logarithms over gf (p) and its cryptographic significance (corresp.).  IEEE Transactions on information Theory, 24(1):106–110, 1978.
  * [34] Jan Rüth, Torsten Zimmermann, and Oliver Hohlfeld.  Hidden treasures-recycling large-scale internet measurements to study the internet’s control plane.  In PAM, 2019.
  * [35] Daniel Shanks.  Class number, a theory of factorization and genera.  In Proc. Symp. Pure Math, 1971, volume 20, pages 415–440, 1971\.
  * [36] Yi Wang, Guohan Lu, and Xing Li.  A study of internet packet reordering.  In ICOIN, pages 350–359, 2004.
  * [37] Eric Wustrow, Colleen Swanson, and J Alex Halderman.  Tapdance: End-to-middle anticensorship without flow blocking.  In USENIX Security, pages 159–174, 2014.

## Supplementary results

Telescope Backbone

(a) ZMap FP - TCP

(b) ZMap FP - UDP

(c) ZMap FP - UDP

(d) ZMap FP - UDP

(e) Non-ZMap FP - TCP

(f) Non-ZMap FP - UDP

Figure 8: Stacked histogram of observed packet rate. Attack success is green
while failure is red. Dark green represent scans that were only identified
with sampled sequence. Light green represent scans were identified with or
without sampled sequence. Vertical lines represent the theoretical observed
packet rates in our three /24 prefixes for a /0 SYN scan performed by ZMap
using a single source with 1GbE and 10GbE upstreams.

####  7.0.1 Observed packet rate

The number of observed packets sent by the scanning IP is $m$. We note the
receiving time of $o_{1}$ (resp. $o_{m}$), $t_{1}$ (resp. $t_{m}$) (see Figure
5). The elapsed time between the first observed packet and the last is $\delta
t=t_{m}-t_{1}$. We define the observed packet rate $opr$ as:
$opr=\frac{m}{\delta t}=\frac{m}{t_{m}-t_{1}}$.

Figure 8 presents the observed packet rate in our data. In order to provide
reference for $opr$ values, we build $opr$ values for a SYN scan that uses
standard network speeds such as 100Mb, 1GbE and 10GbE for each datasets. For
example, such a scan using 1GbE would generate 0.40 packet per second in the
telescope dataset, and 34 packets per second in the backbone dataset. We chose
the SYN scan because it is the most common type of ZMap scan observed [16]. In
both datasets, the observed packet rate of most scans with the ZMap
fingerprint are consistent with a throughput smaller than 1GbE. Some scans
nonetheless exhibit a throughput bigger than 1GbE. They may use the same IP on
several devices to perform sharding. We however assess that this behavior is
unlikely because it requires more configuration compared to standard sharding,
and, above all, increases detection odds. We thus hypothesize that these scans
actually targets small prefixes. We also observe that the $Det2$ method is
less successful when $opr$ increases. High throughput may increase packet
reordering, and thus degrades our identification abilities. Figure 8 shows
that scans without the ZMap fingerprint exhibit a much higher observed rate
than scans with the fingerprint. We hypothesize that these scans target
smaller network prefixes in higher proportion than ZMap scans.