Recently, the online market for exploit kits, malware, botnet rentals, tutorials, and other hacking products has continued to evolve, and what was once a rather hard-to-penetrate and exclusive market—whose buyers were primarily western governments [95]—has now become more accessible to a much wider population. Specifically, the darknet—portions of the Internet accessible through anonymization protocols such as Tor and i2p—has become populated with a variety of markets specializing in such products [94, 2]. In particular, 2015 saw the introduction of darknet markets specializing in zero-day exploit kits, designed to leverage previously undiscovered vulnerabilities. These exploit kits are difficult and time consuming to develop—and often are sold at premium prices.

The explosive increase in popularity of exploit markets and hacker forums presents a valuable opportunity to cyber defenders. These online communities provide a new source of information about potential adversaries, consequently forming the nascent cyber threat intelligence industry. Pre-reconnaissance cyber threat intelligence refers to information gathered prior to a malicious actor interactingwith a defended computer system. To provide a concrete example demonstrating the importance of pre-reconnaissance cyber threat intelligence, consider the case study shown in Table 1.1. A Microsoft Windows vulnerability was identified in February 2015. Microsoft's public press release regarding this vulnerability was essentially their way of warning customers of a security flaw. At the time of its release, there was no publicly known method to leverage this flaw in a cyber-attack (i.e., an available exploit). However, about a month later, an exploit was found to be on sale in a darknet exploit marketplace. It was not until July when FireEye, a major cybersecurity firm, identified that the Dyre Banking Trojan, designed to steal credit card information, exploited this particular vulnerability. This vignette illustrates how threat warnings gathered from the darknet can provide valuable information for security professionals in the form of early-warning threat indicators. Between Dyre and the similar Dridex banking trojan, nearly 6 out of every 10 global organizations were affected, a shocking statistic.

Introduction

Chapter 3 introduced darknet hacker communities and marketplaces, with Chapter 4 presenting a system for gathering data from these sites. In this chapter, we extend the work from [70], presenting techniques to analyze the aggregated dataset, with a goal of providing rich cyber threat intelligence. We identify and analyze users that participate in multiple online communities, look at some of the high-priced zero-day exploits for sale, discuss how governmentassigned vulnerability identifiers are used to indicate a product's target, and use unsupervised learning to categorize and study the product offerings of 17 darknet marketplaces. For product categorization, we use a combination of manual labeling with clustering techniques to identify specific categories. Through a series of case studies showcasing various findings relating to malicious hacker behavior, we hope to illustrate the utility of these cyber threat intelligence tools.

The price of a given product on a darknet marketplace is typically indicated in Bitcoin. The BTC to USD conversion rate is highly volatile. At the time of writing, the Bitcoin to USD conversion rate was $649.70 to 1 BTC, whereas during the experiments discussed during this chapter, which occurred only a few months prior to the writing of this book, the conversion rate was $380.03 to 1 BTC.

The goal of a cyber threat intelligence system is to aid cybersecurity professionals with their strategic cyber-defense planning and to address questions such as:

1. 1 What vendors and users have a presence in multiple darknet/deepnet markets/forums?

2. 2 What zero-day exploits are being developed by malicious hackers?

3. 3 What vulnerabilities do the latest exploits target?

4. 4 What types of products are exclusive to certain vendors and markets?

After aggregating the hacking-related products and hacking-related discussions from a number of darknet marketplaces and forums, respectively, we can begin answering these questions via an in-depth analysis of the data in order to provide a better understanding of the interactions within and between these communities.

Marketplace Data Characteristics

In this section, we describe the dataset used in this chapter. We examined the hacking-related products from 17 darknet marketplaces, finding many products that were cross-posted between markets, often by vendors of the same username. Figure 5.1 shows the count of vendors using the same screen-name across multiple marketplaces and Table 5.1 displays the dataset statistics, after removing duplicates (cross-posts).

Introduction

In the last chapter, we explored how to determine a cyber-attacker's optimal strategy for attacking a computer system based on malware and exploits available on the darkweb. In this chapter, we look at the case where the attacker is focused on industrial control systems (ICS): IT infrastructure that controls physical systems (electricity, water, industrial machinery, etc.). A critical feature of these complex ICS systems is the interdependencies among various components.

However, despite the prevalence of markets for malware and exploits, and their potential threat to ICS, existing paradigms, including the framework presented in the previous chapter, do not account for the complex nature of ICS systems consisting of multiple interconnected components. In particular, it would prove useful to simulate a cyber-attack on a model of an existing system, to assess its degree of vulnerability. Such a model would also prove useful for automated cybersecurity systems that can learn defense and contingency strategies based on the model's simulations. This chapter takes the first steps toward addressing this need. In particular, we introduce a framework that allows for modeling of ICS systems with highly interconnected components (Section 7.3) and study this model through the lens of lattice theory [57]. We then turn our attention to the problem of determining the optimal/most dangerous strategy for a cyber-adversary with respect to this model and find it to be an NPComplete problem (Section 7.4). Next, we present a suite of algorithms for this problem based on A* search and introduce provably correct algorithms (Section 7.5). Our intuition is that these algorithms will obtain satisfactory performance in practice due to heuristic functions (for which we show admissibility). We demonstrate the performance of these algorithms by implementing them and performing a suite of experiments using both simulated and actual vulnerability data (Section 7.6). This chapter also includes some background on ICS (Section 7.2) and a brief overview of related work (Section 7.7).

Background

Contemporary cyber threat actors rely on a variety of malware and exploits purchased through various channels such as the darkweb [99] in order to carry out their attacks. The trend toward automation of industrial control systems (ICS) and toward “smart” utilities [50] has made understanding such adversarialbehavior directed against ICS a priority. For instance, code from the infamous Stuxnet [97] attack against Iranian nuclear facilities is available for public download.

Introduction

Cybersecurity is often referred to as offense dominant,meaning that the domain generally favors the attacker [67, 65]. The reasoning behind this is simple: a successful defense must block all pathways to a system while a successful attack requires only one. As the old hacker adage goes: “the defender must always be right—the attacker only needs to be right once.” This notion of an offense dominant cybersecurity stems directly from “best practices” in the field. These methods primarily rely on technical measures to improve defense. Traditionally these have included variations on patch management, firewall usage, intrusion detection, and antivirus. However, an adversary particularly keen on gaining access to a system can study such defenses with the goal of finding the gaps. These actions are not limited to nation states or large criminal enterprises. The community of malicious hackers is a key enabler for these activities. While important, technical defense measures alone are unlikely to halt attackers and the offense will have the advantage in this case. This chapter explores the use of cyber threat intelligence to address this problem. By gaining insights on the adversary's behavior, we can better address the offense-dominant problem inherent in cybersecurity. The new market for cyber threat intelligence has emerged in recent years due to the realization that technical defensivemeasures, by themselves, are insufficient to address cybersecurity.

Consider the Threat

Central to the idea of cyber threat intelligence (in its current incarnation) is the sharing of information on the latest observed threats. Such data may be collected by a third party (i.e., a company that specializes in incident response or network monitoring), shared directly between organizations, or shared through a group of organizations (i.e., the various Information Sharing and Analysis Centers or ISACs). Certainly, distribution in a manner that best maximizes such information sharing while respecting the privacy of organizations and individuals is a key concern here, as is the role of government in such arrangements. These are some of several short-term problems that are being addressed by threat intelligence firms today: big data management; identification of attack patterns; sanitization/dissemination of information; knowledge extraction; and others. However, these are all relatively short-term problems. This chapter focuses on a larger, more systemic issue with cyber threat intelligence as it stands today: the vast majority of it is inherently reactive.

In this chapter, we present an algebraic construction of a special type of LDPC code whose Tanner graph has a very specific structure. For an LDPC code of this type, its Tanner graph is locally connected. Every VN is only connected to the CNs that are confined to a (small) span of ρcol consecutive locations and every CN is only connected to VNs that are confined to a (small) span of ρrow consecutive locations. We call such constraints on the connections between VNs and CNs of a Tanner graph (ρcol,ρrow)-span-constraints. With this span-constraint, the Tanner graph of such an LDPC code is actually a chain of small Tanner graphs in which each graph is connected to its adjacent graphs on either side of it, except the first and the last ones. An LDPC code of this type is called a span-constrained LDPC code. The SC-LDPC code investigated in [59, 60, 22, 86] is a type of span-constrained LDPC code.

An SC-LDPC code is an LDPC convolutional (LDPC-C) code viewed from a graphical point of view (or a spatial coupling point of view) [49, 104, 66, 67, 92]. An LDPC-C code [49, 104] is specified by a bi-infinite parity-check matrix whose nonzero entries are confined to a diagonal band of a certain width ρrow and a certain depth ρcol. The nonzero entries in every row are confined to a span of ρrow consecutive locations and the nonzero entries in every column are confined to a span of ρcol consecutive locations. With these constraints on the locations of the nonzero entries of the parity-check matrix of an LDPC-C code, every VN in its Tanner graph is only connected to the CNs that are confined to a span of ρcol consecutive locations and every CN is only connected to VNs that are confined to a span of ρrow consecutive locations. These constraints on the locations of the nonzero entries of the parity-check matrix of an LDPC-C code lead to the graphical (ρcol,ρrow)-span-constraint as mentioned above. Hence, an LDPC-C code is a span-constrained LDPC code, an SC-LDPC code.

Error control codes protect the accuracy of data in modern information systems, including computing, communication, and storage systems. Low-density parity-check (LDPC) codes and their relatives represent the state of the art in error control coding and are renowned for their ability to perform close to the theoretical limits. This book presents recent results on various LDPC code designs, making strong connections between two prominent design approaches, the algebraic-based and the graph-theoretic-based constructions. New codes and code construction techniques are presented.

Most methods for constructing LDPC codes can be classified into two general categories, the algebraic-based and the graph-theoretic-based constructions. The two best-known graph-theoretic-based construction methods are the progressive edge-growth (PEG) and the protograph-based (PTG-based) methods, devised in 2001 and 2003, respectively. Both of these techniques involve computer-aided design. One of the earliest algebraic-based methods for constructing LDPC codes is the superposition (SP) construction, proposed in 2002. In this book, the algebraic-based construction method is re-interpreted from both the algebraic and the graph-theoretic perspectives. From the algebraic point of view, it is shown that the SP-construction of LDPC codes includes, as special cases, most of the major algebraic construction methods developed since 2002. From the graph-theoretic point of view, it is shown that the SP-construction also includes the PTG-based construction as a special case. Based on this PTG/SP connection, an algebraic method is developed here to construct PTG-based LDPC codes.

There are advantages to putting the algebraic-based and the PTG-based constructions into a single framework, the SP framework. One advantage is that SP descriptions of codes tend to be relatively compact, enabling simple code specifications in standards and textbooks. Another advantage to studying LDPC codes under the SP framework is that students and practitioners need only learn a single code design approach rather than the myriad approaches that exist in the published literature.

Both binary and nonbinary code constructions will be presented under the SP framework. The SP-construction also leads to a new class of LDPC codes with a doubly quasi-cyclic (QC) structure as well as algebraic methods for constructing spatially and globally coupled LDPC codes. The globally coupled codes will be shown to possess a highly effective burst-erasure correction capability.

In this chapter, we first present some definitions and concepts of matrices which are relevant for later developments of various algebraic-based and graph-theoretic-based constructions of LDPC codes. Then, we give a brief presentation of LDPC codes and characterize their fundamental structural properties that affect their error performance over the AWGNC and the BEC. Good coverage of the fundamentals of LDPC codes and the major iterative algorithms for decoding these codes can be found in [74, 97, 95].

Matrices and Matrix Dispersions of Finite Field Elements

Let GF(q) be a finite field with q elements, where q is a power of a prime [73]. GF(q) is called a NB field if q ≠ 2 and a binary field if q = 2. A matrix A is said to be regular if every row has the same weight, called the row weight, every column has the same weight, called the column weight, and the row weight equals the column weight. If the row weight (or column weight) of a regular matrix A is w, we say that A has weight w and call it a weight-w regular matrix. For w ≠ 0, a weight-w regular matrix must be a square matrix. A binary weight-1 regular matrix is a permutation matrix (PM). It is clear that a weight-w regular matrix is the sum of w disjoint PMs. More generally, a rectangular matrix with constant column weight wc and constant row weight wr is said to be (wc, wr) -regular.

A square matrix over GF(q) is called a circulant if every row of the matrix is the cyclic-shift of the row above it one place to the right, and the top row is the cyclic-shift of the last row one place to the right. It is clear that a circulant is a regular matrix whose weight equals the weight of its top row. The top row of a circulant is called the generator of the circulant. A binary circulant of weight 1 is a binary circulant permutation matrix (CPM). It is clear that a weight-w circulant is the sum of w disjoint CPMs.

The ever-growing need for cheaper, faster, and more reliable communication and storage systems has forced many researchers to seek means to attain the ultimate limits on reliable information transmission and storage. Low-density parity-check (LDPC) codes are currently the most promising coding technique to achieve the channel capacities (or Shannon limits) for a wide range of channels. Discovered by Gallager in 1962 [40], these codes were rediscovered in the late 1990s [83, 81]. Ever since their rediscovery, a great deal of research effort has been expended in design, construction, encoding, decoding algorithms, structural analysis, performance analysis, generalizations, and applications of these remarkable codes. Many LDPC codes have been adopted as standard codes for various current and next-generation communication systems, such as wireless, optical, satellite, space, digital video broadcast (DVB), multi-media broadcast (MMB) systems, and others. Applications to high-density data storage systems, such as flash memories, are now being seriously investigated. In fact, they appear in some recent data storage products. This rapid dominance of LDPC codes in applications is due to their capacity-approaching performance, which can be achieved with practically implementable iterative decoding algorithms. More applications of these codes are expected to come and their future is promising. However, further research is needed to better understand the structural properties and performance characteristics of these codes.

Most methods to construct LDPC codes can be classified into two general categories: graph-theoretic-based and algebraic-based (or matrix-theoretic-based) methods. The best-known graph-theoretic-based construction methods are the progressive edge-growth (PEG) [43, 44] and the protograph (PTG) based methods [105]. The algebraic-based methods for constructing LDPC codes were first introduced in 2000 [56, 55, 38, 57]. Since then, various algebraic methods for constructing LDPC codes, binary and nonbinary, have been developed using mathematical tools such as finite geometries, finite fields, and combinatorial designs [58, 76, 110, 109, 35, 107, 3, 19, 39, 74, 111, 102, 101, 112, 64, 65, 116, 97, 100, 50, 99, 113, 114, 25, 46, 26, 70, 68, 77, 78]. Most of the algebraic constructions have several important ingredients including base matrices, matrix dispersion (or matrix expansion), and masking. By a proper choice and combination of these ingredients, algebraic LDPC codes with excellent overall error performance can be constructed. Algebraic LDPC codes have, in general, much lower error-floors than randomly constructed LDPC codes.

The two key components in the SP-construction of an LDPC code are an SP-base matrix Bsp and a replacement set R of sparse member matrices. To ensure that the Tanner graph of an SP-LDPC code has girth at least 6, it is, in general, required that the SP-base matrix Bsp satisfies the RC-constraint and the member matrices in the replacement set R satisfy both the RC- and the PW-RC-constraints. In this chapter, we present several algebraic constructions of RC-constrained SP-base matrices and replacement sets whose member matrices satisfy both the RC- and the PW-RC-constraints. More constructions of RC-constrained SP-base matrices and replacement sets will be presented in Chapters 7 to 11 and Appendix A.

RC-Constrained Base Matrices

The algebraic methods presented in [58, 35, 3, 101, 112, 64, 65, 50, 113, 114, 46, 70, 68] can be used to construct RC-constrained SP-base matrices. All these methods are based on finite geometries, finite fields, and combinatorial designs (such as balanced incomplete block designs (BIBDs) or Latin squares). In this section, we use the construction based on finite Euclidean geometries. In Chapter 7, we will present a very flexible and powerful construction based on finite fields.

Consider the two-dimensional Euclidean geometry (EG) over the field GF(q) [84, 74, 97] (see Appendix A), denoted by EG(2,q). This geometry consists of q2 + q lines, each consisting of q points. Among these lines, q + 1 lines pass through the origin of the geometry. Based on the q2 - 1 lines of EG(2,q) not passing through the origin, it is possible to construct a (q + 1) × (q + 1) array HEG of CPMs and ZMs of size (q - 1) × (q - 1) [46, 26] which satisfies the RC-constraint [58, 97, 46] (see Appendix A). This array HEG contains q + 1 ZMs which can be put on the main diagonal of the array. Since HEG satisfies the RC-constraint, any subarray of HEG also satisfies the RC-constraint and hence can be used as an SP-base matrix for constructing an SP-LDPC code. The Tanner graph of the SP-LDPC code constructed based on this SP-base matrix has girth at least 6.