{'fraction_non_alphanumeric': 0.03085588343332925, 'fraction_numerical': 0.005090171246654655, 'mean_word_length': 4.790539856173402, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Where's Crypto?: Automated Identification and Classification of Proprietary Cryptographic Primitives in Binary Code

The continuing use of proprietary cryptography in embedded systems across many industry verticals, from physical access control systems and telecommunications to machine-to-machine authentication, presents a significant obstacle to black-box security-evaluation efforts. In-depth security analysis requires locating and classifying the algorithm in often very large binary images, thus rendering manual inspection, even when aided by heuristics, time consuming. In this paper, we present a novel approach to automate the identification and classification of (proprietary) cryptographic primitives within binary code. Our approach is based on Data Flow Graph (DFG) isomorphism, previously proposed by Lestringant et al. Unfortunately, their DFG isomorphism approach is limited to known primitives only, and relies on heuristics for selecting code fragments for analysis. By combining the said approach with symbolic execution, we overcome all limitations of their work, and are able to extend the analysis into the domain of unknown, proprietary cryptographic primitives. To demonstrate that our proposal is practical, we develop various signatures, each targeted at a distinct class of cryptographic primitives, and present experimental evaluations for each of them on a set of binaries, both publicly available (and thus providing reproducible results), and proprietary ones. Lastly, we provide a free and open-source implementation of our approach, called Where's Crypto?, in the form of a plug-in for the popular IDA disassembler.

Particularly affected are embedded systems in industries with complicated multi-tiered supply chains where system integrators and OEMs end up integrating a significant number of black-box components, leading to system opacity compounded by the frequent absence of a Software Bill of Materials. Consequently, the use of a proprietary cryptographic primitive high up in the supply chain can end up trickling down in a wide variety of products by vendors essentially unaware they are incorporating it.
This situation presents a significant obstacle to securityevaluation efforts part of certification, compliance, secure procurement or individual research since it requires resorting to highly labor-intensive reverse-engineering in order to determine the presence and nature of these algorithms before they can be evaluated. In addition when a proprietary algorithm gets broken, details might not be published immediately as a result of NDAs or court injunctions [5] leaving other potentially affected parties to repeat such expensive efforts and hampering effective vulnerability management. As such, there is a real need for practical solutions to automatically scan binaries for the presence of as-of-yet unknown cryptographic algorithms.
Criteria In order to support the analysis of closed-source embedded systems for the use of proprietary cryptography, a suitable solution should meet the following criteria: (i) identification of as-of-yet unknown cryptographic algorithms falling within relevant taxonomical classes, (ii) efficient support of large, real-world embedded firmware binaries, and (iii) no reliance on full firmware emulation or dynamic instrumentation due to issues around platform heterogeneity and peripheral emulation. As discussed in Section 3, there is no prior work meeting all of these criteria.
Approach To meet the above criteria, our approach bases itself on a structural taxonomy of cryptographic primitives. The idea is that, since the vast majority of proprietary cryptography falls within established primitive classes [61], we can develop structural signatures allowing for the identification of any algorithm within these classes without having to rely on knowledge of the algorithm's particulars. To this end, we utilize a taxonomy based on [4,36,43,47] and illustrated in Figure 1. Note that this taxonomy is purely instrumental and does not intend to be exhaustive or allow for an exclusive partitioning of algorithms. Various ciphers could be classified as part of multiple taxonomical classes but this presents no problem to our purposes.
Cryptographic primitives Figure 1: Taxonomical tree of algorithm classes Our approach is built on two fundamentals: Data Flow Graph (DFG) isomorphism and symbolic execution. As described in Section 4, the limitations of prior work on DFG isomorphism [40] are overcome through augmentation with symbolic execution which allows us to specify structural signatures for taxonomic classes of cryptographic primitives and analyze binary code for matches. Additionally, our focus for this paper is on symmetric and unkeyed primitives only.
Contribution Our contribution is threefold. First, our novel approach combines subgraph isomorphism with symbolic execution, solving the open problem of fragment selection and eliminating the need for heuristics and thus, overcoming the limitations of prior work which rendered it unsuited to identifying unknown ciphers. To the best of our knowledge, as discussed in Section 3, there is currently no prior work in either industry or academia that addresses the problem of identifying unknown cryptographic algorithms.
Second, we propose a new domain-specific language (DSL) for defining the structural properties of cryptographic primitives. Clear guidelines are provided on using the new DSL along with several examples.
Finally, a free and open-source proof-of-concept (PoC) implementation, Where's Crypto?, is made available 1 and evaluated in terms of analysis time and accuracy against relevant real-world binaries. 1 https://github.com/wheres-crypto/wheres-crypto 2 Scope and limitations Normalization and optimization A single function can be represented as many different combinations of assembly instructions depending on architecture and compiler particularities. Attempting to construct a 1-to-1 mapping between semantic equivalence classes and DFGs is beyond the scope of this work. When our normalization maps two expressions to the same DFG node, they are semantically equivalent and while the inverse is not necessarily true, our approach can operate as if this were the case since, for a compiler to take advantage of semantic equivalences, it must be consistently aware of them and we can leverage this fact to recognize compiler-generated equivalences.
Implicit flows Data dependencies may also arise due to control-dependent assignments. For example, given two boolean variables a and b, statements a ← b and if a then b ← true; else b ← false are semantically equivalent. In the former, b directly flows to a, and therefore the dependency is apparent in its corresponding DFG, whereas in the latter, the dependency information is lost. Since data dependent branches increase side-channel susceptibility, developers should refrain from using them for cryptographic primitives. Therefore, we declare this class of information flows out of scope.
Function entry points Our PoC implementation relies on IDA's recognition of function entry points as input to our algorithm. As such, inaccuracies in IDA's function recognition will reduce our PoC's coverage. However, this is not an inherent limitation of our approach but merely of our PoC implementation.
Code obfuscation Since code obfuscation presents an inherent challenge to any binary-analysis approach, our approach assumes that the input it operates on is not obfuscated and delegates this de-obfuscation to a manual and/or automated pre-processing step.
Taxonomical constraints In our PoC evaluation and the examples of our DSL, we have limited our discussion to a subset of the taxonomy of cryptographic primitives. This is not an inherent limitation of our approach, but merely of our PoC and its evaluation. Our approach is essentially agnostic with respect to the employed taxonomy, which can be extended as users see fit, and only assumes that the algorithm the analyst is looking for is within one of its classes. Given that the vast majority of proprietary cryptography falls within a specific subset of established primitive classes [61], namely streamand block ciphers and hash functions, we do not consider this a practical issue.
False positives Certain cryptographic primitives are essentially underdefined. That is to say, their definitions are a subset of other algorithms and code patterns and as such, their matches are prone to false positives. We do not consider this a serious practical problem, however, since our solution is intended to assist a human analyst who will be easily capable of pruning a limited number of false positives compared to the burden of unassisted analysis required by the status quo.
Path oracle policy The path oracle policy discussed in Section 6.1 is chosen such that the resulting graph represents n iterations of an algorithm. While this typically satisfies our goals, there are a few exceptions to this rule. First, compilers sometimes ensure loop-guard evaluation during both entry and exit, resulting in a DFG representing n + 1 iterations. Second, cryptographic primitives with a constant iteration length, either inherently or as the result of function inlining, are beyond the control of the path oracle. Finally, loop unrolling will result in a DFG representing kn iterations, where k denotes the number of compiler-grouped iterations. In order to overcome this limitation, we suggest taking the possibility of iteration count deviating from n into account during signature construction as described in Section 10, for example by defining a minimum rather than an exact match.

Prior work
Prior work by academia and industry into the identification of cryptographic algorithms in binary code can be divided into (combinations of) the following approaches: Dedicated functionality identification The most naive and straight-forward approach consists of identifying dedicated cryptographic functionality in the form of OS APIs (e.g. Windows CryptoAPI/CNG) [44], library imports or dedicated instructions (e.g. AES-NI). This approach is inherently incapable of detecting unknown algorithms and as such unsuited for our purposes.
Data signatures The most common approach employed in practice [3,33,41,42,49,53,54,68] consists of identifying cryptographic algorithms on the basis of constants (e.g. IVs, Nothing-Up-My-Sleeve Numbers, padding) and lookup tables (e.g. S-Boxes, P-Boxes). This approach is unsuitable also for detecting known algorithms that do not rely on easily identifiable fixed data or have certain implementations, such as dynamically generating S-Boxes rather than embedding them.
Code heuristics Another series of approaches relies on code heuristics which are applied either statically or dynamically. One set of heuristics are code-augmented data signatures, like mnemonic-constant tuples [32,39], which take into account word sizes, endianness, and multiplicative and additive inverses but otherwise suffer from the same drawbacks as data signatures.
A second heuristic relies on the observation that symmetric cryptographic routines tend to consist of a high ratio of bitwise arithmetic instructions [16,32,39,44,53] and attempt to classify functions based on a threshold. The drawback of this approach is that it lacks granular taxonomical identification capabilities as well as being highly prone to false positives, especially on embedded systems where heavy bitwise arithmetic is typically present as part of memory-mapped register operations required for peripheral interaction.
Deep learning Hill et al. [35] have proposed a Dynamic Convolutional Neural Network based approach which, however, is unsuited for our purposes due to its reliance on dynamic binary instrumentation and its inherent inability to classify unknown algorithms.
Data flow analysis One set of approaches to data flow analysis relies on the static relation between functions and their inputs and outputs [17,32,44,50]. One approach here is to perform taint analysis and evaluate function I/O entropy changes, which relies on emulation and as such is unsuitable as per our criteria in Section 1. Another approach is to compare emulated or symbolically executed function I/O to a collection of reference implementations or test vectors, which is inherently incapable of detecting unknown algorithms.
Another approach [69] utilizes dynamic instrumentation and symbolic execution to translate candidate cryptographic algorithms into boolean formulas for subsequent comparison to reference implementations using guided fuzzing. However, the reliance of this approach on dynamic instrumentation and its inherent inability to recognize unknown algorithms render it unsuitable for our purposes.
Finally, there is the DFG isomorphism approach as proposed by [40] which extracts DFGs from a given binary and matches it against graphs of known cryptographic algorithms through the use of Ullmann's subgraph isomorphism algorithm [60]. A DFG is a Directed Acyclic Graph (DAG) representing the flow of data within a sequence of arithmetic/logic operations. A vertex represents either an operation, or an input variable. The presence of an edge between vertex v 1 and v 2 means that v 1 (or the result of operation v 1 ) is an input to operation v 2 . Due to the nature of DFGs, code flow information cannot be expressed. As such, the contributions of [40] are limited to linear sequences of instructions. Moreover, the authors argue that since cryptographic implementations ought to avoid data-dependent branching due to side-channel susceptibility, one can assume all cryptographic code is free from any sort of conditional instructions. This latter generalization introduces several limitations.
First, no straightforward strategy for selecting code fragments is proposed. Performing the analysis on a per-function basis is complicated by the fact that cryptographic implementations are commonly surrounded by some basic control logic, such as checks on input parameters. As a result, analysis can neither be applied to entire functions nor across function boundaries through inlining and hence the authors propose a limited set of selection heuristics constraining the work.
Second, the approach performs well when identifying known algorithms since once the algorithm is known one can take advantage of unique characteristics but this does not hold when attempting to identify unknown algorithms. Furthermore, a common pattern is that the class of a cryptographic primitive often only becomes apparent once the analysis incorporates conditional instructions. We clarify this point using the following toy examples.
Suppose that we would like to identify a proprietary stream cipher σ. A typical implementation contains a key-stream generator, generating pseudo-random bytes in a loop. Inevitably, this loop contains a conditional instruction causing the program to either re-enter or exit the loop, depending on the length parameter. As there is no support for conditional instructions depending on non-constant values, DFG G, generated from σ will, at most, represent a single iteration, covering a single unit of input length (bytes or otherwise). In this typical example, clearly, a stream cipher pattern will not become apparent in G. The example can be generalized to any pattern that becomes apparent only after several iterations, where no additional properties of the target primitive is known.
Similarly, suppose that we would like to identify a proprietary hash function θ, based on a Merkle-Damgård construction. θ invokes compression function F, which processes blocks of fixed input length. The Merkle-Damgård construction is then used to allow variable input lengths. As such, in order to generate a DFG wherein the construction is apparent, we need it to incorporate several iterations, and perform inlining of F. The former is problematic (as per the stream cipher example), and so is the latter in case F performs some kind of input validation, e.g. checking for NULL pointers.

Solution overview
Cryptographic primitives are essentially a set of arithmetic and logical operations representing an input/output relation. This structural relationship between operations and data can be expressed as a DFG. Since all particular algorithms will be structurally similar to the general primitive defining their taxonomical class, the problem of identifying an unknown algorithm assumed to belong to a well-defined taxonomical class can be formulated as a DFG subgraph isomorphism problem. However, due to slight differences in implementation and compiler peculiarities, DFG representations of semantically identical algorithms may differ and such representations require normalization before they can be subjected to isomorphism analysis. Lestringant et al. [40] demonstrated that, by repeatedly applying a set of rewrite rules to the DFG, a normalized version is obtained, wherein many of these variations are removed. Although no guarantee can be given that equivalent semantics will always map to the same DFG, the result is 'good enough' to serve as a data structure for the purpose.
The identification procedure consists of three stages. A diagram of the procedure is given in Figure 2. First, given the entry point of a function, we start executing it symbolically.
A DFG is constructed during the execution, where each instruction adds a set of nodes and edges to the graph. In case the symbolic analysis encounters a conditional instruction, it may decide to explore both the true and false execution paths. In such a case, the partially constructed DFG is copied and the construction continues independently for both execution paths. Hence, the final result of the DFG construction phase is, in fact, a set of DFGs describing the input/output relation corresponding to the execution path taken. Section 5 describes the construction phase in detail.
Second, once a DFG is fully constructed, we enter the purging phase. This phase is responsible for removing nodes from the graph that represent neither an output, nor a value used in the computation of any output. As such, the graph is reduced to a form in which it only represents the input/output relation, free from operations introduced due to register spilling and other possible implementation, compiler, and architecturespecific operations that are irrelevant to the function's semantics. Section 7 describes the purging phase in detail.
Last, with the finalized DFG at our disposal, we enter the pattern-matching phase, where we search for subgraphs in the DFG that are isomorphic to the graph signature of a given cryptographic primitive. If such a subgraph is identified, we conclude that the primitive is indeed present in the assembly instructions from which the DFG was generated. We use Ullmann's subgraph isomorphism algorithm for searching the DFG. Section 8 describes the pattern-matching phase in detail.

Data Flow Graph construction
The approach of constructing the DFG from assembly instructions builds upon that of [40]. This section summarizes their approach, and indicates where ours departs from it.
Suppose we have a sequence of assembly instructions. We construct its corresponding DFG, G = (V, E), by converting each instruction i into a set of operations O i , which can potentially be empty (e.g., a NOP or branch), or contain multiple operations (e.g., a complex instruction). We distinguish three cases based on input type, as follows: Immediate We create a vertex representing a constant value in G. It is linked by an edge to O i .
Register In case an instruction takes a register as an input operand, we create an edge between the last value written to that register and O i . In practice, this means we maintain an array containing, for each register, a reference to the vertex in G corresponding to that value.
Memory For operands that load or store from/to memory, we create LOAD and STORE operations. Both operations take a memory address vertex as input. Like any other vertex, the address can be a constant, or a more complex symbolic expression. Ideally, we would like all code fragments within a semantic equivalence class to map to the same DFG, and have the end result represent the semantics only, free from architecture and compiler-specific traits. The approach followed by [40] is to take the generated DFG, and repeatedly apply normalization rewrite rules until a fixed-point is reached. This is where our approach deviates from theirs, as we apply normalization as well, but continuously during graph construction. This enhances performance, which we argue below in Section 5.1, and allows us to efficiently keep track of the conditions that apply during symbolic execution (Section 6).  Figure 3: Flow of the graph-node creation process A diagram of the graph-node creation process is given in Figure 3. More concretely: there is a processor module, written for a specific architecture that translates each instruction into graph nodes. The processor module cannot autonomously create new graph nodes. Instead, it must interact with the broker. The broker is responsible for the application of normalization rewrite rules and is processor-architecture agnostic. The processor module provides a specification of the desired node to the broker, which in turn applies normalization rewrite rules to the specification. As such, the result matches the specification either exactly, or a different one that is semantically equivalent. After normalization, the broker queries the DFG for whether a node conforming to the normalized specification already exists. If it does, a reference to it is returned, rather than a new node being created. Consequently, there cannot exist two distinct nodes in a graph conforming to the same specification, or equivalent under normalization. We prove this property in Lemma 1.
Lemma 1. Let G = (V, E) be a DFG, and h denote the normalization transform, for which holds: (1) h(h(x)) = h(x) for all x ∈ U (universe). Consider arbitrary arithmetic/logical A broker request for op preserves the following properties: all nodes in G belong to a unique equivalence class under the normalization function.
Proof. Assume (i) and (ii) hold for V . We define q = h(op(v 1 , v 2 )) and distinguish two cases.
If q ∈ V , then G is not modified and (i) and (ii) are trivially preserved. If q ∈ V , then V = V ∪{q}. By applying (1), we get h(q) = q, and thus (i) holds for {q}. Since (i) already holds for V , (i) also holds for V . Furthermore, suppose that there exists ) and thus p = q. This contradicts q ∈ V , and hence no p ∈ V exists such that h(p) = h(q). Therefore, (ii) holds for V .
Since (i) and (ii) trivially hold for the base case, i.e., an empty graph G, where V = ∅, and the above shows preservation during the step case, the properties hold for any G. E is also subject to modifications, but they are not relevant for the proof.
At this point, we are ready to describe the normalization rewrite rules; they include operation simplification, commonsubexpression elimination, and subsequent memory access.
Operation simplification Suppose that we encounter an arithmetic/logic operation for which all input parameters are constants. Then, the operation can be replaced by its result. 4 12 Likewise, in case an element is the identity element for the operation it serves as an input to, the operation has no effect and can be removed. In case an element is the zero element, the operation's result can be replaced by zero.
Common subexpression elimination Often within a code fragment, the same value is re-computed several times. This is especially true when the instruction set allows for expressing complex operands, e.g. supporting offsets and shifts. Lemma 1 states that broker requests for nodes belonging to a certain equivalence class all result in references to the same graph node. Hence, common-subexpression elimination is already achieved by the design of the node-creation process.
Memory access Loading and storing of data from/to main memory is a common operation. However, this need not have a relation with semantics, but may due to register filling and spilling. We attempt to correct for this by substituting each LOAD operation by its result, which is known in case a preceding STORE operation to the same memory address node exists. It is important to be able to identify the potential equivalence of memory address nodes passed to the STORE and LOAD For associative operations, the result does not depend on the order in which they are executed. Therefore we translate nested associative operations into a single operation taking all inputs.

Miscellaneous translations
Besides the rewrite rules described above, we apply additional miscellaneous rules that do not fit any of the aforementioned categories. They are listed in Appendix B.

Advantages
Applying the normalization rewrite rules during construction of the graph has several advantages over doing so once the graph is fully generated. First, in case normalization function h has constant running time complexity, then the running time complexity of the construction phase, including normalization, grows linearly with the number of assembly instructions, whereas repeated application on a wholly generated DFG has quadratic complexity. Second, by Lemma 1, equivalence of any pair of node references can be evaluated in constant time, simply by checking whether v 1 = v 2 . As such, substitution of LOAD operations by their result can be achieved in constant time. The property is also utilized extensively during symbolic execution (Section 6). Suppose some predicate P restricts the domain of node v 1 ∈ V . Then, a condition depending on v 2 ∈ V , can be evaluated immediately without the need for proving equivalence of v 1 and v 2 first.

Symbolic execution
During the analysis of a function, we may encounter conditional instructions. By definition, a conditional instruction carries a condition. We define the terms determined and underdetermined conditions. These terms relate to the terminology used in the classification of systems of linear equations. For determined conditions, the input variables are restricted to a domain such that there is only a single possible evaluation result. For example, a conditional jump instruction at the end of a loop consisting of a fixed number of iterations. Conversely, for underdetermined conditions, the input variables are not restricted enough to determine a fixed outcome. Below we describe how we approach this class of conditions.
During the DFG construction of any function f , we keep a state S = (G, P, B), where G = (V, E) is the partially constructed DFG. P is a predicate consisting of conditions that apply. These conditions restrict unknown variables to a certain domain. We define predicate P so that satisfaction of P guarantees that G represents the input/output relation of f . The inverse of this statement need not be true. Finally, backlog B is a mapping between an execution address and a list of booleans. For all underdetermined conditional instructions encountered during the construction of G, B keeps a record of which evaluation result was chosen (i.e., true/false). Since the analysis may encounter the same conditional instruction several times, a list is kept. We define B e,i ∈ B, as the evaluation result chosen during the i th occurrence of the underdetermined conditional instruction located at execution address e.
The graph construction begins by initializing S = (G, P, B) to the empty state, i.e. G is an empty graph, P = true, and B has no record of any evaluation result. Then, we begin the construction by processing the instruction located at the entry point of function f . Some instructions may manipulate the execution flow, e.g., a branch instruction, in which case, we continue the construction at its target address. The construction is complete when we encounter an instruction causing the execution flow to return to f 's calling function. For example, in ARM assembly, this is achieved by writing the initial value of register LR, as set by the callee of f , to the program counter register PC.
We represent a condition c in the form of a tuple (v 1 , o, v 2 ), where v 1 , v 2 ∈ V , and o ∈ {<, ≤, =, ≥, >} is the operator. c may be a determined condition. If either v 1 or v 2 is nonconstant, c need not be underdetermined, since predicate P may sufficiently restrict v 0 or v 1 so that c is determined. Conversely, in case c is underdetermined, we are forced to choose which execution path to follow. Alternatively, we may follow both paths, by creating a copy of state S, and subsequently assigning each execution path to one of the instances. This way, the resulting final graph construction consists of several DFGs; each one representing a different execution path. We refer to this practice as forking state S. Forking at the occurrence of every underdetermined condition maximizes code coverage. However, it is infeasible due to the state explosion problem. Therefore, we should devise a balanced strategy for when to apply it -as elaborated below.

Path Oracle
The strategy of when to apply forking only loosely relates to the symbolic execution itself. Therefore, we introduce the Path Oracle, a separate entity that is queried during the graph construction phase, for every occurrence of an underdetermined condition c. It decides whether c should evaluate to true or false, or that the construction should fork and follow both execution paths.

Algorithm 1 Conditional Instruction
e is evaluated for S, skipped for S For every decision made by the path oracle, P and B in S are updated accordingly. The pseudocode given in Algorithm 1 depicts how this is done. In short, predicate P is updated to include condition c (or the negation thereof), thereby maintaining satisfaction of its defining property, i.e. satisfaction of P guarantees G represents the input/output relation of f . An entry is added to backlog B, reflecting the decision made by the path oracle. B has no purpose beyond weighing into the decisions made by the path oracle.

Path Oracle Policy
Through experimental evaluation, we settled on the following policy for the path oracle: the goal of the policy is, for some number n, to obtain a DFG representing exactly n iterations of a primitive with variable input length. The primitive can subsequently be identified by searching for a pattern consisting of exactly n iterations in the resulting DFG. We define d e,i ∈ {TAKE_TRUE, TAKE_FALSE, TAKE_BOTH} as the path oracle's decision for the i th query for the conditional instruction found at execution address e. The policy for the path oracle is defined as follows: We justify the choice of policy by means of an example. Suppose that we encounter an underdetermined condition c at address e. We do not know which of the two possible execution paths leads to a cryptographic primitive (if any). Hence, for i = 0, i.e., the first occurrence, we fork the state and explore both. Suppose that, at a later point during the graph construction, one instance visits address e again, hence i = 1, and finds itself with another underdetermined condition c . Since, at this point, P incorporates c (or ¬c), the outcome of c can be evaluated. As c is underdetermined, c = c is guaranteed.
Such behavior is typical for a loop-guard statement. If this is indeed the case, the execution path taken at i = 0 made us revisit e. In light of our goal of constructing a DFG comprising of n iterations of a primitive, we replicate this path choice n − 1 times, and subsequently take the opposite path, causing the execution flow to exit the loop. Finally, the construction phase yields two DFGs: one representing 0 iterations, and another representing n iterations. A description of the strategy being applied to a concrete example is given in Appendix A. Furthermore, since each conditional instruction may introduce at most one additional DFG, the total number of DFGs generated from f is finite.

Purging process
Once the construction is complete, graph G represents the input/output relation of function f , given predicate P. However, it contains other information as well, such as nodes created from temporary STORE operations to the stack, and expressions rewritten by the broker, leaving the source nodes unused.
For example, suppose that v represents ADD(x, y). Then, a request to the broker for ADD(v, z) yields node w, representing ADD(x, y, z). w does not depend on v and, unless v is referenced independently elsewhere, v is not part of f 's input/output relation.
Leaf nodes are, by definition, graph nodes that are not used as an input to any arithmetic/logical operation. Our approach becomes the following: for each leaf node v, we check whether it is part of f 's semantics. We consider leaf node v to be part of f 's semantics, if v is either (i) the return value of f , (ii) a STORE operation, and the target address is not relative to the SP register. Thus, information is stored outside of the stack, or (iii) a CALL operation, i.e. a function call not subject to inlining.
In case none of the above applies, v and its incoming edges can be removed from G, without affecting semantics.  In order to detect subgraph isomorphism, we need a means of expressing the signature graph. Figure 4 depicts a diagram of the signature domain-specific language (DSL). Appendix C provides a concrete example. The round boxes denote a keyword, whereas the square boxes denote a data type. New graph nodes are generated through the expression data type. Its specification is described below. The IDENTIFIER keyword allows one to specify a friendly name for the signature. The VARIANT keyword enforces the creation of a new empty DFG. Subsequent expressions are added to this graph. Subgraph isomorphism detection is performed with all graphs belonging to a signature definition, allowing one to specify multiple variants of a signature. The label data type is an optional field. It allows the node to be referenced by another expression, enabling node sharing between expressions. Analogous to assembly instructions, a DFG declared in the expression language is also subject to the normalization process by the broker (Section 5), and subsequently subject to the purging process (Section 7). In case the TRANSIENT keyword is specified, the node created from the expression is considered to be non-essential, and may be removed during the purging process in case it was translated by the broker. A diagram of the expression data type is given in Figure 5. It is recursively defined, and hence allows for nested subexpressions. The + keyword denotes the addition of two or more subexpressions. The <</>> keywords denote a left and right shift, respectively. The label data type is a reference to a previously defined graph node. The literal data type denotes a constant value. The STORE, LOAD, XOR, OR, AND, MULT and ROTATE keywords followed by subexpressions surrounded by parentheses provoke creation of a new graph node. The following subexpressions serve as input nodes. Finally, the OPAQUE keyword signifies a special wildcard node. A comparison against a node of any other type by the subgraphisomorphism algorithm always yields true. The opaque node type can have any number of input nodes, including zero. The optional clamp-label data type allows one to assign a name to the node type. Consequently, a comparison against a node of any other type yields true, with the restriction that all opaque nodes carrying the same type label must map to nodes of the same type. We refer to this practice as type clamping.
Within the realm of identifying unknown primitives, defining a special wildcard applicable to a group of nodes would make sense. However, to the best of our knowledge, the nature of subgraph-isomorphism algorithms does not allow for the augmentation of any such algorithm to support one-to-many mappings. Alternatively, one may declare several variants of a signature, where for each variant, the opaque group is denoted by a different number of nested opaque operations, i.e. OPAQUE, OPAQUE(OPAQUE), etc. This way, any group consisting of a finite number of operations can be expressed. A particular syntax could trigger the translation automatically. However, the number of variants grows exponentially in the number of times this hypothetical syntax is used, dramatically affecting the running time of the analysis. Therefore, we omit the syntax altogether and enforce the explicit declaration of multiple variants.

Subgraph isomorphism
Subgraph isomorphism is a well-documented problem, and is known to be NP complete. The solution proposed by Ullmann [60] is a recursion backtracking algorithm with pruning. Our framework implements this algorithm, with support for type clamping (see Section 8). For brevity, we avoid further details about Ullmann's algorithm and our optimizations to it here, and refer the reader to the documentation included with our framework's source code instead. Support for type clamping is implemented in the prune routine of the algorithm. Each time a candidate node c in the code graph is assigned to another node e in the signature graph, a check is introduced whether e carries the opaque type, and a clamp label. If so, the clamp label l is checked for previous assignment to a particular node type. If not, then l is assigned to type(c), the type of the code node. At that point, all candidates c for opaque signatures nodes carrying clamp label l, for which type(c) = type(c ), are invalidated.

Signatures
Before diving into the practical performance evaluation, we highlight the signatures used throughout the analysis, along with relevant details and a motivation as to why they are included. All signature definition files are included in our implementation of the framework. The list given below should not be interpreted as an attempt to cover the entirety of cryptographic primitives in existence. Rather, they showcase the applicability of our framework. The selection of signatures was made with a strong focus on proprietary algorithms in embedded environments. As such, they consist of symmetric and unkeyed primitives only, although there is no fundamental incompatibility with asymmetric primitives.

AES, MD5, SHA1
Despite this paper's strong focus on unknown primitives, there are several arguments to be made for the inclusion of AES, MD5 and SHA1. First, they allow for corroboration of, and straight comparison with the result by [40]. Second, and more importantly, they demonstrate that our proposed symbolic execution approach effectively solves the code fragment selection problem, without resorting to heuristics.

Figure 6: DFG of a Feistel structure
A Feistel cipher is a symmetric structure used in many block ciphers, including DES. Hence, a generic classifier capable of identifying them poses an interesting use case. In a Feistel cipher, a plaintext block P is split in two pieces L 0 and R 0 . Then, for each round i ∈ [0, 1, . . . , n], compute where ⊕ denotes bitwise exclusive-or, F the round function, and K i the sub-key for round i. Translating this definition into a DFG, one yields the graph provided in Figure 6. The next step is to construct a signature that represents the DFG from Figure 6. However, F is an algorithm-specific set of operations, of which thus no properties are known. The OPAQUE operator (see Section 8), is applicable to a single node only, whereas F consists of an unknown number of operations. F is known to take R i and K i as an input, where i ∈ [0, 1, . . . , n]. No properties are known for K i . Hence, we represent F by introducing several variants of the signature. In the first, we substitute F with OPAQUE(R i ), in the second with OPAQUE(OPAQUE(R i )), etc., until we reach 8 levels of operations. Thus, the signature identifies Feistel ciphers with an F whose input/output relation contains between 1 and 8 successive operations.

(Non-)Linear feedback shift register
(Non-)Linear feedback shift registers ((N)LFSRs) are often used in pseudo-random number generators, and key-stream generators for stream ciphers. When designed carefully, an (N)LFSR offers relatively strong randomness, whilst requiring very few logic gates, often making it an attractive choice for algorithms designed for use in embedded devices. Both hardware and software implementations of (N)LFSRs are common.
An (N)LFSR R is initialized with a seed value. Each round, a new bit is generated using the feedback function L from a subset of the bits in the current state of R. R is an LFSR, if L is linear, e.g. an exclusive-or over the input bits. Conversely, R is an NLFSR if L is non-linear. All bits in register R are shifted one position to the left, discarding the most significant bit, and the newly generated bit is placed at position 0. Subsequently, an output bit is generated by feeding R to some function F. Hence, we have R 0 = seed. Then, for each round i ∈ [0, 1, . . . , n], where << x denotes a left shift by x bits and | denotes bitwise OR. Figure 7 depicts a translation of the definition given above into a DFG. In order to express this graph in a signature, we replace L and F with OPAQUE operators. The property that R i+1 depends on R i via L is lost. However, the signature remains distinctive enough in order to warrant very few false positives (see Section 11).

Sequential Block Permutation
Variable-length primitives constructed from fixed-length ones are a common phenomenon. For example, all hash functions built on the Merkle-Damgård construction have this characteristic, such as MD5, SHA1 and SHA2. Other examples include block ciphers in a chaining mode of operation. We refer to this construct as a sequential block permutation.
Let H i be the i th output block of a sequential block permutation function, B i be the i th input block, c be the fixed-length compression function, for i ∈ [0, 1, . . . , n]. I denotes the initialization vector. Then, we define the sequential block permutation as A DFG representation of this definition is given in Figure 8. On inspection we find that it only provides structural guidance, and does not prescribe any arithmetic or logic operations. The definition of H prescribes that compression function c takes two inputs: (i) The output of its preceding instance, except for the first instance, which depends on the IV.
(ii) Any of the input blocks B 0 , B 1 , . . . , B n . In order to express this in a signature definition, we may opt to use an approach similar to how the Feistel cipher signature definition is constructed. However, Figure 8 does not define any operation that serves as an 'anchor point' for c, analogous to the XOR-operation in the Feistel structure. As such, any pattern of repeated operations satisfies property (i). Hence, we must also take property (ii) into account. Let c i be the i th instance of c. The number of arithmetic/logical operations in c i transforming the output of c i−1 need not be related to that of input block B i . Therefore, in order to translate c into several variants of the signature, we have to perform a translation for both the path between c i and c i−1 , and that between c i and B i . The number of variants grows exponentially in the number of such translations. On top of that, the compression function c can be vastly more complex than a round function in a Feistel cipher. For example, the MD5 compression function in itself consists of 64 rounds. Therefore, the upper bound of the number of operations that c may consist of is an order of magnitude higher than what one would typically find in a Feistel cipher's round function. All in all, we conclude that the number of signature variants, and therewith the running time complexity of the analysis, becomes prohibitively large.
Fortunately, there is no need to restrict ourselves to subgraph isomorphism as a means of identifying primitives. Rather, we can apply any algorithm to the DFGs generated by the graph construction framework, which is our approach for the sequential block permutation use case. We take several observations into account. First, input blocks B 0 , B 1 , . . . , B n are typically loaded from a memory address. Second, c has a fixed (unknown) block size, and thus we can safely assume that the offsets between the load addresses of B i , B i+1 and B i+2 are constant. From these observations, we devise the following approach: (i) We identify all nodes representing LOAD (ADD(x, k)), where x is an arbitrary graph node, and k is a constant. For each instance of x, we construct a list of tuples the offsets between v 0 , v 1 and v 2 are constant, and at least 16 bytes. As such, a DFG generated from a sequential block permutation function yields at least one tuple such that v i maps to B i , for all i ∈ [0, 1, 2].
(ii) For all tuples, we determine the shortest path between v 0 and v 1 . This can be done by means of a simple breadthfirst search. If v 0 maps to B 0 and v 1 to B 1 , then this path should take us through two instances of c (see Figure 8).
(iii) Suppose that such a path exists, then we would like to confirm that a similar path exists between v 1 and v 2 . We take v 1 as a starting point, and traverse paths with edge directions and node types resembling those on the path between v 0 and v 1 . Once such a path has been found, it should reach v 2 . Satisfaction of this property is a strong positive indicator.
(iv) To gain more certainty, we also verify that the node types of all inputs and outputs for all the nodes on both paths match. However, in case v 0 maps to B 0 , some inputs may originate from the IV, whereas they originate from computed values during the second round. Therefore, we tolerate constant inputs and inputs of type LOAD in this step.
The definition given in this section resembles exactly that of the Merkle-Damgård construction, with the omission of the padding function applied to the last block. We studied the possibility of creating a Merkle-Damgård classifier built on the sequential block permutation classifier. This appeared to be infeasible due to a combination of factors. First, no concrete data dependencies are defined for the padding function, but only a set of properties (see [31] for so-called MD-compliant padding). If we assume that the padding function encodes the input length, then the final instance of compression function c should take a node representing it as an input. Therefore, we have to reliably determine the input length, which need not coincide with n (see Section 2), identify the final instance of c, which depends on whether the encoded input length fits within the padding space, and make additional assumptions about the length encoding. As such, we conclude the distinction of the Merkle-Damgård construction within the broader class of sequential block permutation functions relies on too many assumptions, and leave it as a manual effort for the human analyst.

Experimental evaluation
We evaluate our solution's performance with respect to accuracy and running time on the following three test sets: (a) a collection of shared libraries and executables part of the OpenWRT 2 network equipment firmware, (b) a collection of proprietary cipher implementations built from public sources, and (c) a collection of representative real-world embedded firmwares from relevant verticals (PLCs, ECUs).
While not containing proprietary cryptography, the Open-WRT project is publicly available without legal issues around redistribution, contrary to firmwares which do. As such, this evaluation benefits the reproducibility of our work, as well as demonstrates the general principle, accuracy and performance of our work on a test set representative of high-end embedded device firmware. Given the uncertainty over the legality of redistribution, we refer to the original sources of the proprietary cipher implementations rather than publish our binary test set. Due to copyright restrictions, we unfortunately lack permission to publish the real-world embedded firmwares.

Performance on OpenWRT binaries
The empirical evaluation is conducted on an AMD Ryzen 3600 machine with 16 GB of RAM, which is considered to be mid-range hardware nowadays. The version of OpenWRT used is 19.07.2, which is the latest version at time of writing. We begin by investigating the impact of the parameters defined throughout this paper. We do this by running the analysis on libcrypto.so.1.1, taking on different parameter values, and measuring performance in terms of running time and accuracy. We then choose sensible parameter values based on a trade-off between the two, and use them for the remainder of the section, unless specified otherwise. Section 6.1.1 defines n, the target number of iterations. The (N)LFSR and sequential block permutation classifiers are affected by this value. The others target a single instance only. The latter identifies two successive instances of some compression function c. The IV and length padding may provoke differences in the DFG in the first and the last instance of c, respectively. Taking n = 4 circumvents this. A pattern of 4 successive (N)LSFR rounds is also sufficiently distinctive. Therefore, for the remainder of this section, we take n = 4.
Formally, the construction of a DFG from binary code, as described in Section 5, is a special case of execution, and is thus affected by the halting problem. As such, graphconstruction is not guaranteed to terminate. Therefore, we introduce a graph construction timeout t timeout . Figure 9a depicts a histogram of graph construction time t for all graphs constructed during the analysis of libcrypto.so.1.1. It shows that, for the vast majority of all graphs, construction completes within 10s. Thus, we take t timeout = 10s. Figure 9b depicts the time taken to complete the entire analysis pipeline over every function in libcrypto.so.1.1, under the influence of varying inline depth d. Figure 9c contains accuracy measurements for each signature. True negatives are omitted since they cover an overwhelming majority of results, and thus impact readability. Before discussing the results, we will first provide guidelines on how the chart should be interpreted. Recall that the signature evaluation is performed on graphs, and the graph construction step may yield several graphs. As such, several signature evaluation results may exist per function. The measurements provided in Figure 9c are aggregated on a per-function level.
Let f be any function in the binary under analysis, and let signature s α denote a signature whose goal is to identify prim- itive α. Furthermore, let F be the set of DFGs generated from f during the graph construction phase. Finally, match(s α , G) denotes that signature s α was identified in graph G, imp(f , α) denotes that f implements cryptographic primitive α. A result is marked as a true positive if imp(f , α) ∧ ∃ G .G ∈ F ∧ match(s α , G), i.e. f implements cryptographic primitive α, and its signature is found in at least one graph in F. Indeed, there is no guarantee that all DFGs in F contain algorithm α, and hence it is expected that the signature is not found in every graph in F. A result is marked as a false pos- The results in Figure 9c show that accuracy does not substantially improve when choosing d > 2. However, doing so does impact the running time. We conclude that, for libcrypto.so.1.1, d = 2 is a reasonable trade-off between accuracy and running time. As such, we take d = 2 for the remainder of this section, unless specified otherwise.
At this point, sensible values for n, d and t timeout have been selected. We continue the evaluation by feeding various binaries within OpenWRT containing cryptographic primitives to our analysis framework. The results are listed in Table 1. Each cell in the table depicts the symbol name in the corresponding binary of the first positive result, or, in case of a false negative, the symbol name where a positive result is expected.
The above results indicate our solution is capable of successfully identifying the vast majority of cryptographic primitives present in various binaries in timely manner. Should accuracy take precedence over performance, it is possible to tune the discussed parameters to improve detection.

Performance on proprietary algorithms
In this section, we turn our attention to proprietary algorithms. Most algorithms included in this section were originally confidential, but have been leaked to the public or reverse engineered. As such, source code for all samples is publicly available. Due to uncertainty over the legality of redistribution, we point to the original sources for reference.   The results show that all the cryptographic primitives were identified, except for the Megamos cipher. Verdult et al. [63] revealed that the Megamos cipher contains an NLFSR, and thus, the analysis should point this out. Further examination reveals that the non-linear feedback function is implemented as a subroutine, and the shift register is updated depending on its return value via an if-statement. This is a direct violation of the implicit flow limitation inherent to DFG-based approaches discussed in Section 2.

Conclusions
Despite the ubiquitous availability of royalty-free, publicly documented, and peer-reviewed cryptographic primitives and implementations, proprietary alternatives have persisted across many industry verticals, especially in embedded systems. Due to the undocumented and proprietary nature of said primitives, subjecting them to security analysis often requires locating and classifying them in often very large binary images, which is a time-consuming, labor-intensive effort, even when aided by heuristics.
In order to overcome this obstacle in an automated fashion, a solution should have the capability of identifying as-of-yet unknown cryptographic algorithms, support large, real-world firmware binaries, and not depend on peripheral emulation.
As of yet, no prior work exists that satisfies these criteria.
Our novel approach combines DFG isomorphism with symbolic execution, and introduces a specialized DSL in order to enable identification of unknown proprietary cryptographic algorithms falling within well-defined taxonomical classes. The approach is the first of its kind, is architecture and platform agnostic, and performs well in terms of both accuracy and running time on real-world binary firmware images.
Future work DFGs do not allow for the expression of code flow information. Potentially valuable indicators, such as whether two nodes originate from the same execution address, hinting to a round function, are therefore lost. We leave the incorporation of code flow information for future work.  Since P ∧ c is underdetermined, we query the path oracle, and obtain TAKE_FALSE, causing another visit of the loop's body. Finally, at i = n, we get c = R8 ≤ n and P = (R8 > n−1). We obtain TAKE_TRUE from the path oracle. Thus, the construction terminates. We obtain two graphs; one corresponding to predicate R8 ≤ 0, and another corresponding to R8 = n. The latter describes n iterations of the algorithm, exactly conforming to our goal. The former describes zero iterations, and thus, contains a negligible amount of nodes. Therefore, we accept the small amount of overhead this graph induces during later stages of the analysis.

B Miscellaneous rewrite rules
Besides the rewrite rules already described, we apply additional miscellaneous rules. They were conceived through continuous application of our framework to code fragments from various sources, and subsequent stumbling upon variations between the processed result generated from supposedly semantically equivalent code. We highlight these rules here.
There are various means of doubling the value of an arbitrary expression x. For example, MULT(x, 2), but also ADD(x, x) and x<<1. We represent all variants by MULT(x, 2). R1 + R1 2 MULT Furthermore, suppose we have an arbitrary expression x, and constants c 1 and c 2 . Then, the results of AND(x >> c 1 , c 2 ) and AND(ROTATE(x, c 1 ), c 2 ), are equivalent if c 2 < 2 32−c 1 and c 1 < 32, for a 32-bit architecture. This property is sometimes exploited by compilers in order to minimize code size, particularly in cases where the underlying architecture supports complex instruction operands that allow for rotation, but no shifting. In such a scenario, we represent both variants by AND(x >> c 1 , c 2 ).

D Implementation
An implementation of the framework described in this paper is available for download 14 . It comes in the form of a plug-in for the popular IDA disassembler. At the time of writing, support is implemented for 32 bits ARM binaries. The architecture is modular, and expanding support to other architectures is relatively straightforward. Figure 11 shows a sample analysis report, and a DFG plot generated by our implementation.
(a) Sample analysis report (b) DFG plot generated from assembly instructions indicating an LFSR Figure 11: An impression of the implementation of our framework