Thang Hoang
email: hoangmin@oregonstate.edu

Attila A Yavuz
email: attila.yavuz@oregonstate.edu

F Betül Durak
email: betul.durak@epfl.ch

Jorge Guajardo
email: jorge.guajardomerchan@us.bosch.com

Oblivious Dynamic Searchable Encryption on Distributed Cloud Systems

Keywords: Searchable encryption, Write-only ORAM, Multi-server PIR, Privacy-preserving clouds

Dynamic Searchable Symmetric Encryption (DSSE) allows search/update operations over encrypted data via an encrypted index. However, DSSE has been shown to be vulnerable to statistical inference attacks, which can extract a significant amount of information from access patterns on encrypted index and files. While generic Oblivious Random Access Machine (ORAM) can hide access patterns, it has been shown to be extremely costly to be directly used in DSSE setting. By exploiting the distributed cloud infrastructure, we develop a series of Oblivious Distributed DSSE schemes called ODSE, which enable oblivious access on the encrypted index with a high security and improved efficiency over the use of generic ORAM. Specifically, ODSE schemes are 3×-57× faster than applying the state-of-the-art generic ORAMs on encrypted dictionary index in real network settings. One of the proposed ODSE schemes offers desirable security guarantees such as informationtheoretic security with robustness against malicious servers. These properties are achieved by exploiting some of the unique characteristics of searchable encryption and encrypted index, which permits us to harness the computation and communication efficiency of multi-server PIR and Write-Only ORAM simultaneously. We fully implemented ODSE and have conducted extensive experiments to assess the performance of our proposed schemes in a real cloud environment.

Introduction

Data outsourcing allows a client to store their data on the cloud to reduce data management and maintenance costs. Despite its merits, cloud services come with severe privacy issues. The client may encrypt their data with standard encryption to protect their privacy. However, these techniques also prevent the client from performing basic operations (e.g., search/update) over the outsourced encrypted data. This significantly degrades the benefits of cloud services. In the following, we first outline the current state-of-the-art techniques and their limitations and then, present our methods towards addressing these challenges.

State-of-the-art and Limitations

Information leakage in DSSE. The concept of searchable symmetric encryption (SSE) was first proposed by Song et al. [START_REF] Song | Practical techniques for searches on encrypted data[END_REF]. This construction can only search on static encrypted data. Curtmola et al. [START_REF] Curtmola | Searchable symmetric encryption: improved definitions and efficient constructions[END_REF] introduced single-keywordsearched SSE with formal security definition, followed by refinements with extended capabilities such as ranked query [START_REF] Wang | Secure ranked keyword search over encrypted cloud data[END_REF], multi-keyword search [START_REF] Sun | Privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking[END_REF] or their combinations [START_REF] Cao | Privacy-preserving multi-keyword ranked search over encrypted cloud data[END_REF]. Dynamic Searchable Symmetric Encryption (DSSE) was introduced by Kamara et al. [START_REF] Kamara | Dynamic searchable symmetric encryption[END_REF], which offers both search and update on encrypted files F via an encrypted index I representing keyword-file relationships. Many DSSE schemes have been proposed, each offering various performance, functionality and security trade-offs [START_REF] Bösch | A survey of provably secure searchable encryption[END_REF] (e.g., [START_REF] Kamara | Dynamic searchable symmetric encryption[END_REF][START_REF] Cash | Dynamic searchable encryption in very-large databases: Data structures and implementation[END_REF][START_REF] Bost | Forward and backward private searchable encryption from constrained cryptographic primitives[END_REF][START_REF] Zhang | Dynamic and efficient private keyword search over inverted index-based encrypted data[END_REF][START_REF] Zhou | Integrity preserving multi-keyword searchable encryption for cloud computing[END_REF][START_REF] Moataz | Substring search over encrypted data[END_REF]).

It is known that all standard DSSE schemes leak significant information, which are vulnerable to statistical inference analysis [START_REF] Islam | Access pattern disclosure on searchable encryption: Ramification, attack and mitigation[END_REF][START_REF] Liu | Search pattern leakage in searchable encryption: Attacks and new construction[END_REF][START_REF] Cash | Leakage-abuse attacks against searchable encryption[END_REF][START_REF] Zhang | All your queries are belong to us: The power of file-injection attacks on searchable encryption[END_REF]. There are two sources of information leakages in DSSE: (i) leakages through search and update on encrypted index I, (ii) leakages due to access of encrypted files F. Specifically, since the search and update tokens are deterministic, all DSSE schemes leak access patterns on both I and F. Furthermore, most of them also leak the content of updated files during the update (i.e., forward-privacy) and historical updates (add/delete) on the keyword during the search on I (i.e., backward-privacy). By exploiting these leakages, recent studies have shown that, sensitive information about encrypted queries and files can be recovered [START_REF] Liu | Search pattern leakage in searchable encryption: Attacks and new construction[END_REF][START_REF] Cash | Leakage-abuse attacks against searchable encryption[END_REF]. Zhang et al. [START_REF] Zhang | All your queries are belong to us: The power of file-injection attacks on searchable encryption[END_REF] has presented file-injection attacks that can determine which keywords have been searched, especially in forward-insecure DSSE schemes. Although some DSSE schemes with improved security (e.g., forward and backward privacy) have been proposed (e.g., [START_REF] Bost | Forward and backward private searchable encryption from constrained cryptographic primitives[END_REF]), they rely on extremely costly public key operations and still leak access patterns. Liu et al. [START_REF] Liu | Search pattern leakage in searchable encryption: Attacks and new construction[END_REF] demonstrated an attack that can determine which keywords have been searched by observing the frequency of search queries (search patterns). Zhang et al. [START_REF] Zhang | All your queries are belong to us: The power of file-injection attacks on searchable encryption[END_REF] has indicated that, future research on DSSE should focus on sealing information leakages rather than accepting them by default. Unless these leakages are prevented, a trustworthy deployment of DSSE for privacy-critical applications may remain extremely difficult.

Performance Hurdles of the Existing Approaches to Reduce Information Leakages in DSSE. Several attempts (e.g., [START_REF] Hoang | Practical and secure dynamic searchable encryption via oblivious access on distributed data structure[END_REF][START_REF] Bosch | Distributed searchable symmetric encryption[END_REF]) are either highly costly or unable to completely seal all leakages in DSSE access patterns. Generic Oblivious Random Access Machine (ORAM) [START_REF] Stefanov | Path oram: an extremely simple oblivious ram protocol[END_REF] 4 can hide access patterns, and therefore, it can prevent most of the information leakages in DSSE. Garg et al. [START_REF] Garg | Tworam: Round-optimal oblivious ram with applications to searchable encryption[END_REF] proposed TWORAM scheme, which optimizes the round-trip communication under O(1) client storage when using ORAM to hide file access patterns5 in DSSE. Despite its merits, prior studies (e.g., [START_REF] Cash | Dynamic searchable encryption in very-large databases: Data structures and implementation[END_REF][START_REF] Naveed | The fallacy of composition of oblivious ram and searchable encryption[END_REF]) stated that generic ORAM (e.g., [START_REF] Stefanov | Path oram: an extremely simple oblivious ram protocol[END_REF]) is still costly to be used in DSSE due to its logarithmic communication overhead. Although several ORAMs with O(1) bandwidth complexity have been introduced recently, they are still very costly due to the use of Homomorphic Encryption (HE). The performance of such schemes has been shown to be worse than O(log N )-bandwidth ORAMs [START_REF] Abraham | Asymptotically tight bounds for composing oram with pir[END_REF].

Our Research Objective and Contributions

It is imperative to seal information leakages from accessing encrypted files F and encrypted index I. Since the size of individual files in F might be arbitrarily large and each search/update query might involve a different number of files, to the best of our knowledge, generic ORAM seems to be the only option for oblivious access on F. The objective of this paper is to design oblivious access techniques on I, which are more efficient than using generic ORAM, by exploiting special properties of searchable encryption and I as elaborated in Figure 1.

Particularly, we identify a suitable data structure for I that allows search and update to operate on separate dimensions. This property permits us to harness communication-efficient techniques such as Write-Only ORAM for update and, by exploiting distributed cloud infrastructure, multi-server PIR for search with low computation overhead. Note that the low communication and computation are important factors in practice since they directly translate into the low endto-end delay and consequently, improve the quality of services of cloud systems. Notice that the price to pay for such low delay is the collusion vulnerability in the distributed setting, where we assume a limited number of servers that can collude with each other, which is the common adversarial model of multi-server PIR techniques (see §2 and §4).

We propose a series of Oblivious Distributed Encrypted Index I on the distributed cloud infrastructure with the application on DSSE, which we refer to as ODSE (Figure 1). We present two ODSE schemes called ODSE wo xor and ODSE wo it , each offering various desirable performance and security properties as follows.

• Low end-to-end delay: ODSE schemes achieve low end-to-end-delay, which are 3×-57×faster than the use of efficient generic ORAMs (e.g., [START_REF] Stefanov | Path oram: an extremely simple oblivious ram protocol[END_REF][START_REF] Ren | Ring oram: Closing the gap between small and large client storage oblivious ram[END_REF]) (with optimization [START_REF] Garg | Tworam: Round-optimal oblivious ram with applications to searchable encryption[END_REF]) on encrypted index under real network settings (see §5). • Full obliviousness with Information-theoretic security: ODSE seals information leakages due to accesses on encrypted index I that lead into statistical attacks such as forward/backward privacy, query types (search/update), hidden size and access patterns. ODSE wo xor and ODSE wo it offer computational and information-theoretic security for I and operations on it, respectively.

• Robustness against malicious servers: ODSE wo it can tolerate a certain number of malicious servers in the system.

• Full-fledged implementation and open-sourced framework: We fully implemented all the proposed ODSE schemes, and evaluated their performance on real-cloud infrastructure. To the best of our knowledge, we are among the first to opensource an oblivious access framework for DSSE encrypted index that can be publicly used for comparison and wide adaptation (see §5).

It is clear that the standard DSSE constructions (e.g., [START_REF] Cash | Dynamic searchable encryption in very-large databases: Data structures and implementation[END_REF]) are much faster, but also less secure than our proposed methods in the sense of leaking more information beyond the access patterns (e.g., forward-privacy, backward-privacy) over the encrypted index. Compared with standard DSSE where access patterns are leaked by default, ODSE schemes offer higher security by sealing all these leakages at the cost of higher latency. Nevertheless, they are more efficient than using generic ORAM techniques atop the DSSE encrypted index to seal such leakages in some certain cases regarding database and query sizes. We provide the detail analysis in §5.

Preliminaries and Building Blocks

Notation. We denote F p as a finite field where p is a prime. Operators || and ⊕ denote the concatenation and XOR, respectively. (•) bin denotes the binary representation. u • v denotes the inner product of two vectors u and v. x $ ← S denotes that x is randomly and uniformly selected from set S. Given I as a row/column of a matrix, I[i] denotes accessing i-th component of I. Given a matrix I, I[ * , j . . . j ] denotes accessing columns j to j of I. Let E = (Enc, Dec, Gen) be an IND-CPA symmetric encryption: κ ← E.Gen(1 θ ) generating key with security parameter θ; C ← E.Enc κ (M ) encrypting plaintext M with key κ; M ← E.Dec κ (C) decrypting ciphertext C with key κ.

Shamir Secret Sharing (SSS). We present (t, )-threshold Shamir Secret Sharing (SSS) scheme [START_REF] Shamir | How to share a secret[END_REF] in Figure 2. Given a secret α ∈ F p , the dealer generates a random t-degree polynomial f and evaluates f (x i ) for party P l ∈ {P 1 , . . . , P }, where x l ∈ F p \ {0} is the deterministic identifier of P l . We denote the share for P l as α l . The secret can be reconstructed by combining at least t + 1 correct shares via Lagrange interpolation. Note that the secret can be recovered from a ( α 1, . . . , α ) ← SSS.CreateShare(α, t): Create shares of value α 1: (a1, . . . , at)

$ ← Fp 2: return ( α 1, . . . , α ), where α i ← α + t u=1 au • x u l for 1 ≤ l ≤ α ← SSS.
Recover({A}, t): Recover the value α from its shares 1:

Randomly select t + 1 shares { α x i } t+1 i=1 among A 2: g(x) ← LagrangeInterpolation {(xi, α x i )} t+1 i=1 3: return α, where α ← g(0)
Fig. 2. Shamir Secret Sharing (SSS) scheme [START_REF] Shamir | How to share a secret[END_REF].

number of incorrect shares by error correction techniques (discussed in §4). We use this property to improve the robustness of our protocol in malicious settings.

SSS is t-private so that any combinations of t shares leak no information about the secret. SSS offers homomorphic properties including addition, scalar multiplication, and partial multiplication. We extend the notion of share of value to indicate the share of vector: v i = ( v 1 l , . . . , v n l ) denotes the share of vector v for party P , in which v i is the share of component v i in v.

Private Information Retrieval (PIR). PIR enables private retrieval of a data item from a (unencrypted) public database server. We recall two efficient multi-server PIR protocols: (i) XOR-based PIR [START_REF] Chor | Private information retrieval[END_REF] (Figure 3 Write-Only ORAM. ORAM allows the user to hide the access patterns when accessing their encrypted data on the cloud. In contrast to generic ORAM where both read and write operations are hidden, Blass et al. [START_REF] Blass | Toward robust hidden volumes using write-only oblivious ram[END_REF] proposed a Write-Only ORAM scheme, which only hides the write pattern in the context of hidden volume encryption. Intuitively, 2n memory slots are used to store n blocks, each assigned to a distinct slot and a position map is maintained to keep track of block's location. Given a block to be rewritten, the client reads λ slots chosen uniformly at random and writes the block to a dummy slot among λ slots. Data in all slots are encrypted to hide which slot is updated. By selecting λ sufficiently large (e.g., 80), one can achieve a negligible failure probability, which might occur when all λ slots are non-dummy. It is possible to select a small λ (e.g., 4). In this case, the client maintains a stash component S of size O(log n) to temporarily store blocks that cannot be rewritten when all read slots are full.

The Proposed ODSE Schemes

Intuition. In DSSE, keyword search and file update on I are read-only and write-only operations, respectively. This property permits us to leverage specific bandwidth-efficient oblivious access techniques for each operation such as multiserver PIR (for search) and Write-Only ORAM (for update) rather than using generic ORAM. The second requirement is to identify an appropriate data structure for I so that the above techniques can be adapted. We found that forward index and inverted index are the ideal choices for the file update and keyword search operations, respectively as proposed in [START_REF] Hahn | Searchable encryption with secure and efficient updates[END_REF]. However, doing search and update on two isolated indexes can cause an inconsistency, which requires the server to perform synchronization. The synchronization operation leaks significant information [START_REF] Hahn | Searchable encryption with secure and efficient updates[END_REF]. To avoid this problem, it is necessary to integrate both search index and update index in an efficient manner. Fortunately, this can be achieved by leveraging a two-dimensional index (i.e., matrix), which allows keyword search and file update to be performed in two separate dimensions without creating any inconsistency at their intersection. This strategy permits us to perform computation-efficient (multi-server) PIR on one dimension, and communication-efficient (Write-Only) ORAM on the other dimension to achieve oblivious search and update, respectively, with a high efficiency.

ODSE Models and Data Structures

System Model. Our model comprises a client and servers S = (S 1 , . . . , S ), each storing a version of the encrypted index. In our system, the encrypted files are stored on S , a separate server different from S (as in [START_REF] Hoang | Practical and secure dynamic searchable encryption via oblivious access on distributed data structure[END_REF]), which can be obliviously accessed via a generic ORAM (e.g., [START_REF] Stefanov | Path oram: an extremely simple oblivious ram protocol[END_REF]). In this paper, we only focus on oblivious access of the encrypted index on S.

Threat Model. In our system, the client is trusted and the servers S are untrusted. We consider the servers to be semi-honest, meaning that they follow the protocol faithfully, but can record the protocol transcripts to learn information regarding the client's access pattern. However, our system can be easily extended to deal with malicious servers that attempt to tamper the input data to compromise the correctness and the security of the system (see §4). We allow upto t < (privacy parameter) servers among S to be colluding, meaning that they can share their own recorded protocol transcripts with each other. We present the formal security model in §4.

Data Structures. Assume that the outsourced database can store up to N distinct files and M unique keywords, our index is an incidence matrix I, where each cell I[i, j] ∈ {0, 1} represents the relationship between the keyword at row i and the file at column j. Each keyword and file is assigned to a unique row and column index, respectively. Each row of I represents the search result of a keyword while the content (unique keywords) of a file is represented by a column.

Since we use Write-Only ORAM for file update, the number of columns in I are doubled and a stash S is used to store columns of I during the update. Therefore, the size of search index I is M × 2N .

We leverage two static hash tables T w , T f as in [START_REF] Yavuz | Dynamic searchable symmetric encryption with minimal leakage and efficient updates on commodity hardware[END_REF] to keep track of the location of keywords and files in I, respectively. They have the following structure: T := key, value , where key is a keyword or file ID and value ← T [key] is the (row/column) index of key in I. Since there are 2N columns in I while only N files, we denote D as the set of dummy columns that are not assigned to a particular file. Once I is constructed, the client sends I i to server S i , and keeps σ as secret.

F = {f id 1 , . . . , f idn } 3. Construct I for i = 1 . . . , m and j = 1, . . . , n: (a) T f [idj] ← Π(j), Tw[wi] ← Π (i), x ← Π [wi] and y ← Π[idj] (b) If wi appears in f id j , set I [x, y] ← 1 4. Generate master key as κ ← Gen(1 θ ) 5. Encrypt I for i = 1, . . . , M and j = 1 . . . , 2N : (a) τi ← KDFκ(i) (b) I[i, j] ← E.Encτ i (I [i, j]) 6
Search. Intuitively, to search for a keyword w, the client and server execute the XOR-based PIR protocol on the row dimension of I to privately retrieve the row data of w. Since the row is encrypted rather than being public as in the traditional PIR model, the client performs decryption on the retrieved data and filter dummy column indexes to obtain the search result. The detail is as follows. xor offers highly-efficient search and update operations, it has the following security limitations: (i) it can only (at most) detect but cannot recover from malicious servers, which might tamper the data to compromise the privacy and correctness of the protocol. In privacy-critical applications, it is desirable to recover from malicious servers to improve the robustness of the protocol; (ii) the encrypted index and update operations on it are only computationally-secure due to the IND-CPA encryption.

To address the limitations of ODSE wo xor , we introduce ODSE wo it that offers (i) improved robustness against malicious servers with a partial recover capability, and (ii) the highest level of security (i.e., information-theoretic) for both I and operations on it. The main idea is to share the index with SSS, and harness SSSbased PIR to conduct private search. The robustness comes from the ability to recover the secret shared by SSS in the presence of incorrect shares (see §4).

Setup:

The client first constructs an index I representing keyword-file relationships as in ODSE wo xor .Setup. Instead of encrypting I , the client creates shares of I by SSS. Since SSS operates on elements in F p , each row of I is split into log 2 p -bit chunks before SSS computation. So, the index I i is the SSS share of I for server S i , which is a matrix of size M × 2N , where I i [i, j] ∈ F p and N = N/ log 2 p . The detail is as follows. Update: We execute Write-Only ORAM on the column dimension of the encrypted index for the file update. Recall that in ODSE wo xor , λ random columns of the original index I are read to update one column. In ODSE wo it , each column of the index I i on S i contains the share of log 2 p successive columns of I . Therefore, the client reads λ = λ log 2 p random columns of I i from t + 1 servers to recover λ columns of I before performing update. The detail is as follows.

ODSE wo it .Update(f id , I, σ): Update file f id 1. Initialize I [i] ← 0 for i = 1 . . . , M 2. Set Î[xi] ← 1,

Security

Definition 1 (ODSE security). Let op = (op 1 , . . . , op q ) be an operation sequence over the distributed encrypted index I, where op i ∈ Search(w), Update(f id ) , w is a keyword to be searched and f id is a file with keywords to be updated. Let ODSE j (o) represent the ODSE client's sequence of interactions with server S j , given an operation sequence o.

An ODSE is t-secure if ∀L ⊆ {1, . . . , } s.t. |L| ≤ t, for any two operation sequences op and op where |op| = |op |, the views {ODSE i∈L (op)} and {ODSE i∈L (op )} observed by a coalition of up to t servers are (perfectly, statistically or computationally) indistinguishable. Remark 1. One might observe that search and update operations in ODSE schemes are performed on rows and columns of the encrypted index, respectively. This access structure might enable the adversary to learn whether the operation is search or update, even though each operation is secure. Therefore, to achieve security as in Definition 1, where the query type should also be hidden, we can invoke both search and update protocols (one of them is the dummy operation) regardless of whether the intended action is search or update.

We argue the security of our proposed schemes as follows. it leverages an SSS-based PIR protocol and therefore, achieves t-privacy for keyword search due to the t-privacy property of SSS [START_REF] Goldberg | Improving the robustness of private information retrieval[END_REF]. (ii) Oblivious Update: The index in ODSE wo it is SSS-shared, which is information-theoretically secure in the presence of t colluding servers. ODSE wo it also employs Write-Only ORAM, which offers statistical security due to negligible write failure probability. Therefore in general, the update access pattern of ODSE wo it scheme is information-theoretically (statistically) indistinguishable in the coalition of up to t servers. (iii) ODSE Security: By Remark 1, ODSE wo it performs both search and update protocols regardless of the actual operation. As analyzed above, search is t-private and update pattern is statistically t-indistinguishable. Therefore, ODSE wo it is information-theoretically (statistically) t-secure by Definition 1.

Malicious Input Tolerance

We have shown that ODSE schemes offer a certain level of collusion-resiliency in the honest-but-curious setting where the server follows the protocol faithfully.

In some privacy-critical applications, it is necessary to achieve data integrity in the malicious environment, where the adversary can tamper the query and data to compromise the correctness and privacy of the protocol. We show that ODSE schemes can be extended to detect and be robust against malicious servers as follows. In ODSE wo xor , we can leverage Message Authentication Code (e.g., HMAC) as presented in [START_REF] Moataz | Chf-oram: a constant communication oram without homomorphic encryption[END_REF], where authenticated tag for each row and each column of I is generated. The server will perform operations (i.e., PIR, Write-Only ORAM) on such tags as similar to encrypted index data and send the result to the client. The client can recover/decrypt the row/column as well as its authenticated tag verify the integrity.

Since ODSE wo it relies on SSS as the building block, we can not only detect but also be robust against malicious server. The main idea is to leverage list decoding algorithm as in [START_REF] Goldberg | Improving the robustness of private information retrieval[END_REF], given that the Lagrange interpolation in SSS.Recover algorithm does not return a consistent value. Such techniques also allow to determine precisely which server has tampered the data. We refer readers to [START_REF] Goldberg | Improving the robustness of private information retrieval[END_REF] for detailed description. In general, the list decoding allows t m ≤ t < -√ t number of incorrect shares of α (t) .

Experimental Evaluation

Configurations

Implementation details. We implemented all ODSE schemes in C++. Specifically, we used Google Sparsehash to implement hash tables T f and T w . We utilized Intel AES-NI library to implement AES-CTR encryption/decryption in ODSE wo xor . We leveraged Shoup's NTL library for pseudo-random number generator and arithmetic operations over finite field. We used ZeroMQ library for client-server communication. We used multi-threading technique to accelerate PIR computation at the server. Our code is publicly available at https://github.com/thanghoang/ODSE Hardware and network settings. We used Amazon EC2 with r4.4xlarge instance for server(s), each equipped with 16 vCPUs Intel Xeon @ 2.3 GHz and 122 GB RAM. We used a laptop with Intel Core i5 @ 2.90 GHz and 16 GB RAM as the client. All machines ran Ubuntu 16.04. The client established a network connection with the server via WiFi. We used a real network setting, where the download and upload throughputs are 27 and 5 Mbps, respectively.

Dataset. We used subsets of the Enron dataset to build I containing from millions to billions of keyword-file pairs. The largest database in this study contain around 300,000 files with 320,000 unique keywords. Our tokenization is identical to [START_REF] Naveed | The fallacy of composition of oblivious ram and searchable encryption[END_REF] so that our keyword distribution and query pattern is similar to [START_REF] Naveed | The fallacy of composition of oblivious ram and searchable encryption[END_REF].

Instantiation of compared techniques. We compared ODSE with a standard DSSE scheme [START_REF] Cash | Dynamic searchable encryption in very-large databases: Data structures and implementation[END_REF], and the use of generic ORAM atop the DSSE encrypted index. The performance of all schemes was measured under the same setting and in the average-case cost, where each query involves half of the keywords/files in the database. We configured ODSE schemes and their counterparts as follows.

• ODSE: We used two servers for ODSE wo xor and three servers for ODSE wo it scheme. We selected λ = 4 for ODSE wo xor , and λ = 4 with F p where p is a 16-bit prime for ODSE wo it . We note that selecting larger p (up to 64 bits) can reduce the PIR computation time, but also increase the bandwidth overhead. We chose a 16-bit prime field to achieve a balanced computation vs. communication overhead.

• Standard DSSE : We selected one of the most efficient DSSE schemes by Cash et al. in [START_REF] Cash | Dynamic searchable encryption in very-large databases: Data structures and implementation[END_REF] (i.e., Π dyn 2lev variant) to showcase the performance gap between ODSE and standard DSSE. We estimated the performance of Π dyn 2lev using the same software/hardware environments and optimizations as ODSE (e.g., parallelization, AES-NI acceleration). Note that we did not use the Java implementation of this scheme available in Clusion library [START_REF]The clusion library[END_REF] for comparison due to its lack of hardware acceleration support (no AES-NI) and the difference between running environments (Java VM vs. C). Our estimation is conservative in that, we used numbers that would be better than the Clusion library.

• Using generic ORAM atop DSSE encrypted index : We selected non-recursive Path-ORAM [START_REF] Stefanov | Path oram: an extremely simple oblivious ram protocol[END_REF] and Ring-ORAM [START_REF] Ren | Ring oram: Closing the gap between small and large client storage oblivious ram[END_REF], rather than recent ORAMs as ODSE counterparts since they are the most efficient generic ORAM schemes to date. Since we focus on encrypted index rather than encrypted files in DSSE, we did not explicitly compare our schemes with TWORAM [START_REF] Garg | Tworam: Round-optimal oblivious ram with applications to searchable encryption[END_REF] but instead, used one of their techniques to optimize the performance of using generic ORAM on DSSE encrypted index. Specifically, we applied the selected ORAMs on the dictionary index containing keyword-file pairs as in [START_REF] Naveed | The fallacy of composition of oblivious ram and searchable encryption[END_REF] along with the round-trip optimization as in [START_REF] Garg | Tworam: Round-optimal oblivious ram with applications to searchable encryption[END_REF]. Note that our estimates are also conservative where memory access delays were excluded, and cryptographic operations were optimized and parallelized to make a fair comparison between the considered schemes.

Overall Results

Figure 5 presents the end-to-end delays of ODSE schemes and their counterparts, where both search and update are performed in ODSE schemes to hide the actual type of operation (see Remark 1). ODSE offers a higher security than standard DSSE at the cost of a longer delay. However, ODSE schemes are 3×-57× faster This delay is for encrypted index with 300,000 files and 320,000 keywords regarding network and configuration settings in §5.1.

* The encrypted index in ODSE wo it is information-theoretically (IT) secure because it is SSS. Other schemes employ IND-CPA encryption so that their index is computationally secure (see §4).

‡ All ODSE schemes perform search and update protocols to hide the actual query type. In ODSE wo xor , search is IT-secure due to SSS-based PIR and update is computationally secure due to IND-CPA encryption. Hence, its overall security is computational.

† is # servers. In ODSE wo it , encrypted index and search query are SSS with the same privacy level. Generic ORAM-based solutions have a stronger adversarial model than ours since they are not vulnerable to collusion that arises in the distributed setting.

than the use of generic ORAMs to hide the access patterns. Specifically, with an encrypted index containing ten billions of keyword-file pairs, Π dyn 2lev cost 36 ms and 600 ms to finish a search and update operation, respectively. ODSE wo xor and ODSE wo it took 2.8 s and 7.1 s respectively, to accomplish both keyword search and file update operations, compared with 160 s by using Path-ORAM with the round-trip optimization [START_REF] Garg | Tworam: Round-optimal oblivious ram with applications to searchable encryption[END_REF]. ODSE wo xor is the most efficient in terms of search, whose delay was less than 1 s. This is due to the fact that ODSE wo xor only requires XOR operations and the size of the search query is minimal (i.e., a binary string). ODSE wo it is more robust (e.g., malicious tolerant) and more secure (e.g., unconditional security) than ODSE wo xor at the cost of higher search delay (i.e., 4 s) due to the larger search query and SSS arithmetic computations. For the file update, ODSE wo it costs 3 s, which is slightly higher than ODSE wo xor (i.e., 2.2 secs) since it needs to transmit more data (4 blocks vs. 4 columns) to more servers (3 vs. 2). We further provide a comparison of ODSE schemes with their counterparts in Table 1. We dissected the total cost to investigate which factors contributed the most to the latency of ODSE schemes as follows.

Detailed Cost Analysis

Figure 6 presents the total delays of separate keyword search and file update operations, as well as their detailed costs in ODSE schemes. Note that ODSE performs both search and update (one of them is dummy) to hide the actual type of operation performed by the client. theory libraries (i.e., NTL), all these computations only contributed to a small fraction of the total delay.

• Client-server communication: Data transmission is the dominating factor in the delay of ODSE schemes. The communication cost of ODSE wo xor is smaller than that of other ODSE schemes, since the size of search query and the data transmitted from servers are binary vectors. In ODSE wo it , the size of components in the select vector is 16 bits. The communication overhead of ODSE wo it can be reduced by using a smaller finite field, but at the cost of increased PIR computation on the server side.

• Server processing: The cost of PIR operations in ODSE wo xor is negligible as it uses XOR. The PIR computation of ODSE wo it is reasonable, as it operates on a bunch of 16-bit values. For update operations, the server-side cost is mainly due to memory accesses for column update. ODSE wo it is highly memory accessefficient since we organized the memory layout for column-friendly access. This layout minimizes the memory access delay not only in update but also in search, since the inner product in PIR also accesses contiguous memory blocks by this organization. In ODSE wo xor , we stored the matrix for row-friendly access to permit efficient XOR operations during search. However, this requires file update to access non-contiguous memory blocks. Hence, the file update in ODSE wo xor incurred a higher memory access delay than that of ODSE wo it as shown in Figure 6. • Storage overhead: The main limitation of ODSE schemes is the size of encrypted index, whose asymptotic cost is O(N • M ), where N and M are the number of files and unique keywords, respectively. Given the largest database being experimented, the size of our encrypted index is 23 GB. The client storage includes two hash tables of size O(M ) and O(N log N ), the stash of size O(M • log N ), the set of dummy column indexes of size O(N log N ), a counter vector of size Ω(N ) and a master key (in ODSE wo xor scheme). Empirically, with the same database size discussed above, the client requires approximately 22 MB in both ODSE schemes.

Experiment with various query sizes

We studied the performance of our schemes and their counterparts in the context of various keyword and file numbers involved in search and update operations that we refer to as "query size". As shown in Figure 7, ODSE schemes are more efficient than using generic ORAMs when more than 5% of keywords/files in the database are involved in the search/update operations. Since the complexity of ODSE schemes is linear to the number of keywords and files (i.e., O(M + N )), their delay is constant and independent from the query size. The complexity of ORAM approaches is O(r log 2 (N • M )), where r is the query size. Although the bandwidth cost of ODSE schemes is asymptotically linear, their actual delay is much lower than using generic ORAM, whose cost is poly-logarithmic to the total number of keywords/files but linear to the query size. This confirms the results of Naveed et al. in [START_REF] Naveed | The fallacy of composition of oblivious ram and searchable encryption[END_REF] on the performance limitations of generic ORAM and DSSE composition, wherein we used the same dataset for our experiments.

Conclusion

We proposed a new set of Oblivious Distributed DSSE schemes called ODSE, which achieve full obliviousness, hidden size pattern, and low end-to-end delay simultaneously. Specifically, ODSE wo xor achieves the lowest end-to-end delay with the smallest communication overhead among all of its counterparts with the highest resiliency against colluding servers. ODSE wo it achieves the highest level of privacy with information-theoretic security for access patterns and the encrypted index, along with the robustness against malicious servers. Our experiments demonstrated that ODSE schemes are one order of magnitude faster than the most efficient ORAM techniques over DSSE encrypted index. We have released the full implementation of our ODSE schemes for public use and wide adaptation.

Fig. 1 .

 1 Fig. 1. Our research objective and high-level approach.

Fig. 3 .Fig. 4 .

 34 Fig. 3. XOR-based PIR [10]. b ← PIR sss (x, b1, . . . , b ): Retrieve a data item indexed x from public database Client: Let e = (e1, . . . , em), where ex ← 1, ei ← 0 for 1 ≤ i = x ≤ n 1: for i = 1, . . . , m do 2: ( ei 1, . . . , ei ) ← SSS.CreateShare(ei, t) 3: e l ← ( e1 l , . . . , em l ) and send e l to server S l for 1 ≤ l ≤ Server: each S l storing b l = (b lm , . . . , b lm ) on receiving e l : 4: b l ← e l • b l and send b i to client Client: on receiving b 1, . . . , b : 5: return b ← SSS.Recover( b 1, . . . , b , t) Fig. 4. SSS-based PIR [13].

  . Let D contain column indexes that are not assigned to any file IDs 7. Output (I, σ), where I ← {I1, . . . , I } with Ii = I and σ ← (κ, Tw, T f , c)

R

  ← ODSE wo xor .Search(w, I, σ): Search for keyword w 1. Get row index x of the searched keyword w as x ← Tw[w] 2. Execute I[x, * ] ← PIR xor (x, I1, . . . , I ) protocol (Figure 3) with servers: (a) Each server inputs its encrypted index Ii, where each row of Ii is interpreted as an item in the database (b) Client inputs x, and receives I[x, * ] from protocol's output 3. Decrypt I[x, * ] for j = 1, . . . , 2N : (a) I [x, j] ← E.Decτ x (I[x, j]) where τx ← KDFκ(x) 4. Output R ← id in Stash S and id s.t. T f [id] = j where I[x, j] = 1 and j / ∈ D Update: The overall strategy is to perform a Write-Only ORAM on the column of I to achieve oblivious file update operations as follows. ODSE wo xor .Update(f id , I, σ): Update file f id 1. Initialize a new column as Î[i] ← 0, for i = 1, . . . , M 2. Set Î[xi] ← 1, where xi ← Tw[wi] for each keyword wi appearing in f id 3. Add id, Î to Stash S, add T f [id] to dummy set D 4. Download λ random columns of encrypted index I from a server: (a) Randomly select λ column indexes J ← {j1, . . . j λ } (b) Get λ columns {I l [ * , j]}j∈J from random server S l 5. Decrypt each column I l [ * , j] for each j ∈ J and for i = 1, . . . , M : (a) τi ← KDFκ(i) (b) I [i, j] ← E.Decτ i (I l [i, j]) 6. For each dummy column I [ * , ĵ]: (a) Pick a pair id, Î from stash S, and set I [ * , ĵ] ← Î (b) Set T f [id] ← ĵ, and remove ĵ from dummy set D 7. Re-encrypt λ columns as Î[i, j] ← E.Encτ i (I [i, j]) for i = 1 . . . , M and ∀j ∈ J 8. Send λ columns { Î[ * , j]}j∈J to servers, where each server Si updates its encrypted index as Ii[ * , j] ← Î[ * , j], for each j ∈ J 3.3 ODSE wo it : Robust and IT-Secure ODSE Although ODSE wo

(

  I, σ) ← ODSE wo it .Setup(F): Create distributed share index from input files F 1. Construct I by executing steps 1-3 in ODSE wo xor .Setup procedure 2. Create SSS of I for i = 1, . . . , M and j = 1, . . . , 2N : (a) Î[i, j] bin ← I [i, (j -1) • log 2 p + 1, . . . , j • log 2 p ] (b) (I1[i, j], . . . , I [i, j]) ← SSS.CreateShare( Î[i, j], t) 3. Output (I, σ), where I ← {I1, . . . , I } and σ ← (Tw, T f , D) Similar to ODSE wo xor , the client sends I i to server S i and keep σ as secret. Search. The client executes the SSS-based PIR protocol on the row dimension of encrypted index to retrieve the row of searched keyword as follows. R ← ODSE wo it .Search(w, I, σ): Search for keyword w 1. Get row index x of the searched keyword w as x ← Tw[w] 2. Execute Î[x, j] ← PIR sss (x, I1[ * , j], . . . , I [ * , j] ) protocol (Figure 4) with servers for j = 1, . . . , 2N : (a) Each server Si inputs a column of its shared index Ii[ * , j], where each cell Ii[x, j] is interpreted as an item in the database (b) Client inputs x, and receives Î[x, j] from protocol's output. Note that client executes SSS.Recover with privacy parameter of 2t, instead of t (step 5 in Figure 4) to recover Î[x, j] correctly. 3. Form the row as I [x, * ] ← Î[x, 1] bin || . . . || Î[x, 2N ] bin 4. Output R ← id in Stash S and id s.t. T f [id] = j where I[x, j] = 1 and j / ∈ D

  where xi ← Tw[wi] for each keyword wi appearing in f id 3. Add id, Î to Stash S, add T f [id] to dummy set D 4. Download λ random columns of shared index I from t + 1 servers: (a) Randomly selected λ column indexes J ← {j1, . . . j λ } (b) Get λ columns {I l [ * , j]} j∈J ,l=1...t+1 from t + 1 servers 5. Recover λ columns for each j ∈ J and i = 1 . . . , M : (a) Î[i, j] ← SSS.Recover( I1[i, j], . . . , I [i, j] , t) (b) I [i, j • log 2 p , ..., (j + 1) • log 2 p ] ← Î[i, j] bin 6. For each dummy column I [ * , ĵ]: (a) Pick a pair id, Î from stash S, and set I [ * , ĵ] ← Î (b) Set T f [id] ← ĵ, and remove ĵ from dummy set D 7. Create SSS for λ column for each j ∈ J , and i = 1 . . . , M : (a) I[i, j] bin ← I [i, j • log 2 p , . . . , (j + 1) • log 2 p ] (b) ( Î1[i, j], . . . , Î [i, j]) ← SSS.CreateShare( Î[i, j], t) 8. Send Îl [ * , j]) to S l for each j ∈ J and l = 1 . . . , . Each server S l updates its share index as I l [ * , j] ← Îl [ * , j] for each j ∈ J

Fig. 5 .

 5 Fig. 5. Latency of ODSE schemes and their counterparts.

Fig. 6 .

 6 Fig. 6. Detailed search (S) and update (U) costs of ODSE schemes.

3 Fig.

 3 Fig. Latency of ODSE schemes and their counterparts with different fraction of keywords/files involved in a search/update operation.

  Setup. Let Π and Π be random permutations on {1, . . . , 2N } and {1, . . . , M } respectively. The procedure to setup encrypted index for ODSE wo xor is as follows. Create distributed encrypted index from input files F 1. Initialize a matrix I of size M × 2N , Set I [ * , * ] ← 0 2. Extract unique keywords (w1, . . . , wm) from files

	3.2 ODSE wo xor : Fast ODSE
	We introduce ODSE wo xor that harnesses XOR-based PIR and Write-Only ORAM
	to achieve low search and update latency.

(I, σ) ← ODSE wo xor .Setup(F):

  Theorem 1. ODSE wo xor scheme is computationally ( -1)-secure by Definition 1. Proof. (Sketch) (i) Oblivious Search: ODSE wo xor leverages XOR-based PIR and therefore, achieves ( -1)-privacy for keyword search as proven in [10]. (ii) Oblivious Update: ODSE wo xor employs Write-Only ORAM which achieves negligible write failure probability and therefore, it offers the statistical security without counting the encryption. The index in ODSE wo xor is IND-CPA encrypted, which offers computational security. Therefore in general, the update access pattern of ODSE wo xor scheme is computationally indistinguishable. ODSE wo xor performs Write-Only ORAM with an identical procedure on servers (e.g., the indexes of accessed columns are the same in servers), and therefore, the server coalition does not affect the update privacy of ODSE wo xor . (iii) ODSE Security: By Remark 1, ODSE wo xor performs both search and update regardless of the actual operation. As analyzed, search is ( -1)-private and update pattern is computationally secure.

	Therefore, ODSE wo xor achieves computational ( -1)-security by Definition 1.
	Theorem 2. ODSE wo it scheme is statistically t-secure by Definition 1.
	Proof. (Sketch) (i) Oblivious Search: ODSE wo

Table 1 .

 1 Comparison of ODSE and its counterparts for oblivious access on I.

				Security		Delay (s)	Distributed Setting †
	Scheme	Forward privacy	Backward privacy	Hidden access pattern	Encrypted index *	Search Update	Privacy level	Improved Robustness
	Standard DSSE [9]				Computational 0.036	0.62	-	-
	Path-ORAM[25]			Computational Computational	160.6	-	-
	Ring-ORAM [22]			Computational Computational	137.4	-	-
	ODSE wo xor			Computational ‡ Computational	2.8		-1
	ODSE wo it			Information theoretic	Information theoretic	7.1		< /2

•

  Client processing: As shown in Figure6, client computation contributes the least amount to the overall search delay (less than 10%) in all ODSE schemes.

	The client computation comprises the following operations: (1) Generate select
	queries (with SSS in ODSE wo it and PRF in ODSE wo xor ); (2) SSS recovery and IND-CPA decryption (in ODSE wo xor ); (3) Filter dummy columns. Note that the client
	delay of ODSE schemes can be further reduced (by at least 50%-60%) via pre-
	computation of some values such as row keys and select queries (only contain
	shares of 0 or 1). For the file update, the client performs decryption and re-
	encryption on λ columns (in ODSE wo xor ), or SSS over λ blocks (in ODSE wo it ). Since
	we used crypto acceleration (i.e., Intel AES-NI) and highly optimized number

By generic ORAM, we mean oblivious techniques that can hide operation type (whether it is read or write), as opposed to PIR or Write-Only ORAM.

It differs from the objective of this paper, where we focus on hiding access patterns on the encrypted index in DSSE (see §5 for clarification).


Sebastian Neuner
email: sneuner@sba-research.org

Artemios G Voyiatzis
email: avoyiatzis@sba-research.org

Spiros Fotopoulos
email: spiros@physics.upatras.gr3mulliner.org

Collin Mulliner
email: collin@mulliner.org

Edgar R Weippl
email: eweippl@sba-research.org

USBlock: Blocking USB-based Keypress Injection Attacks

Keywords: Security, USB, BadUSB, Linux kernel, system security ://srlabs.de/badusb/

The Universal Serial Bus (USB) is becoming a prevalent attack vector. Rubber Ducky and BadUSB are two recent classes of a whole spectrum of attacks carried out using fully-automated keypress injections through innocent-looking USB devices. So far, defense mechanisms are insufficient and rely on user participation in the trust decision. We propose USBlock, a novel approach to detect suspicious USB devices by analyzing the temporal characteristics of the USB packet traffic they generate, similarly to intrusion detection approaches in networked systems. Our approach is unique in that it does not to involve at all the user in the trust decision. We describe a proof-of-concept implementation for Linux and we assess the effectiveness and efficiency of our approach to cope with temporal variations in typing habits and dynamics of legitimate users.

Introduction

The Universal Serial Bus (USB) is by far the most widely-used connector for modern computer systems. It is used to connect a plethora of peripheral devices to computers, including keyboards, mice, cameras, printers, and storage media. Many different attack vectors abuse the pervasiveness of USB, as for example dropping USB thumb drives on parking lots for users to pick up and attach on their computers [START_REF] Tischer | Users Really Do Plug in USB Drives They Find[END_REF]. As network-based defenses steadily improve and can block efficiently the malicious network traffic reaching an organization, USB becomes an attractive entry point for penetrating an organization.

Under the hood, USB is more than a simple connector. It is a complex communication protocol, often implemented and offered as a firmware. Lately, there are devices on the market with the ability to update their USB firmware. This capability has been exploited as a subtle attack vector, hiding malicious functionality on an abstraction layer that modern computer antivirus cannot cope with. BadUSB 4 and Rubber Ducky 5 classes of attacks are successful demonstrations of the attack feasibility. The associated threat is rather high: at this level the device interfaces directly with device drivers that run in the most privileged level of modern consumer-grade operating systems (e.g., as ring-0 modules of the Linux kernel).

In this paper, we provide insights on how these USB-protocol-level attacks work and explore how their attack patterns can be detected at the system level. Such an approach relieves the end user from being involved in trust decisions and thus, makes the security of the system less dependent to user actions. Specifically, we make the following contributions:

-We study the behavioral characteristics of Rubber Ducky and BadUSB classes of attacks. -We devise criteria for automating their detection.

-We design, implement, and evaluate a simple yet very effective and extensible system-level countermeasure based on USB packet traffic analysis to detect and defend against such attacks without requiring user intervention.

The rest of the paper is structured as follows: Section 2 provides the necessary background information for the USB protocol and related attacks and defenses. Section 3 studies the temporal characteristics of USB-based attacks and proposes a system-level defense mechanism. Section 4 describes a prototype implementation of our proposal and evaluates its efficiency in real-world settings. Finally, Section 5 presents our conclusions and discusses future directions of work.

Background

The USB protocol

USB is the most widely-used computer peripheral connector today. USB 3.2 is its latest revision. The USB device communication is based on a tiered-star topology with one dedicated master controller. Besides the controller, a hub manages the connected USB devices. If the master controller acts as a hub too, then the hub is called the "root hub". Every USB hub uses seven bits to address connected USB devices. This leads to a limit of 127 attachable USB devices per hub.

The connection of a USB device to a hub works as follows 6 : The USB hub waits for new devices to be plugged in. Upon connection, channels for communication are created: the so-called "endpoints", acting as sources and sinks of data. The endpoints are logically grouped together to "interfaces" and are announced to the host via "interface descriptors".

The USB communication is realized by exchanging "USB packets" over the shared serial bus. The USB protocol defines four transfer types (Control, Isochronous, Interrupt, and Bulk) and three packet types (Token, Data, and Status).

Modern operating systems, including Microsoft Windows, Linux, and Apple Mac OS, utilize the information collected by the hub from the connected USB devices to (dynamically) load the appropriate device drivers. For each announced interface descriptor of a device, the operating system combines the device-provided device class, interface class, and vendor and product identifiers (VID and PID respectively) to decide which capabilities are provided by the device and to bind the appropriate device driver(s).

As an example, a modern USB mouse may offer the capabilities of a human interface device (HID) and those of a display (e.g., to display its sensitivity level). Or a USB headset may offer the capabilities of an audio output device and that of a constrained HID for its volume up/down and mute buttons. In such cases, the devices will have two different interfaces and each of them will get a different driver bound to it.

USB protocol security

The USB protocol does not dictate a form of device authentication. Rather, every USB hub blindly trusts any information announced by the connected device about their capabilities. We note that modern USB devices incorporate, for legitimate reasons, multiple functionalities (e.g., a mouse announcing itself also as a display device). Such functionalities are hard for a user to link together and reason for any associated risk. These combined with the wide prevalence of USB devices, render USB an attractive attack vector [START_REF] Anderson | Seven deadliest USB attacks[END_REF][START_REF] Wang | Exploiting smart-phone USB connectivity for fun and profit[END_REF].

In the past, the entry barrier for realizing attacks based on the inherent weaknesses of the USB protocol was very high. It dropped significantly by the time USB firmware chips with reflashing capabilities became available on the open market7 . On the one hand, firmware updates for consumer products are often a necessity due to shortened time-to-market and insufficient testing. The alternative would be a product recall which would cause a logistics nightmare. On the other hand, firmware updates significantly lower the resources and expertise for launching USB-based attacks.

Figure 1 depicts the principle of a USB device and endpoint setups, which occur during the Control transfer phase using Setup packets. In this example, the device announces support for two functionalities, namely a mass storage and a keyboard (HID device). The former seems like a normal behavior, assuming that the user plugged in a USB thumb drive or external disk. In this case, the user expects that the operating system (host) will load the mass storage device driver and be able to further interact with the storage device. However, we note that without having knowledge of the device specifics, this announcement could also have been an attack vector. The latter announcement forces the host to bind a keyboard driver as well. If the announcement comes from a modified, malicious firmware, then the first step of the attack is already successful. The firmware then launches the second step of its attack. This involves sending keypresses from the (non-existent) keyboard. This "USB-based keypress injection attack" assumes that the system interaction caused by these keypresses will go unnoticed by the user and, thus, will succeed to deliver the malicious actions (e.g., download from the Internet or access from the USB storage and then execute a zero-day malware).

So far, various attacks exploiting the inherent weaknesses of the USB protocol have been proposed [START_REF] Nissim | USB-based attacks[END_REF]. We review the most characteristic of them in the following paragraphs.

BadUSB and IRON-HID

The BadUSB attack enables a USB storage device to act not only as a SCSI device (mass storage), but also as an HID one. By acting as a keyboard, the data coming from the connected USB device is interpreted as keypresses. An attack can install a backdoor to the host system or "call home" over the network for example. From that point on, the attacker has total control over the infected host system.

Researchers and practitioners work both on improving BadUSB-like attacks and reducing their attack surfaces. In the so-called "IRON-HID" attack, additional programmable hardware (e.g., a Teensy board 8 ) is hidden in places like keyboards and portable USB batteries [START_REF] Han | IRON-HID: Create your own bad USB (white paper)[END_REF]. By connecting a smartphone to the crafted USB battery via a crafted USB On-The-Go cable, the smartphone is switched into USB host mode. From that moment on, the smartphone is able to eavesdrop on all USB communications. IRON-HID can be used also to inject fake keypresses with the aim to brute-force the Android screen unlock PIN.

Rubber Ducky

The Rubber Ducky is a physical device designed by the Hak5 group 9 . The Rubber Ducky works as a normal keyboard when it comes to driver binding: it simply needs the operating system's HID driver to work. However, the Rubber Ducky delivers USB-based payloads (keypresses pre-defined by an attacker) upon being connected to the victim system.

The pre-defined keypresses are written in Ducky Script, a simple-to-use scripting language 10 . Once the payload is developed, it is compiled into a binary and placed on the microSD card of the Rubber Ducky device. Upon connecting the Rubber Ducky to a host computer, the built-in Atmel AT32UC3B1256 chip of Rubber Ducky emulates the pre-defined keypresses in the fastest rate the USB port can deliver and the device driver of the attacked system can handle.

BadAndroid

BadAndroid11 , like BadUSB, adds malicious functionality to an otherwise benign Android device. In contrast with BadUSB, the firmware of the Android device needs not be flashed.

A possible attack scenario using BadAndroid looks like the following: using social engineering, an attacker pretends that she needs to charge the battery of her Android smartphone and asks to plug it in to the target's laptop. While the smartphone is connected for charging, BadAndroid actually alters the routing table of the host (laptop) system without the user noticing, i.e., it changes the default network gateway of the laptop to be the IP address of the Android smartphone. From that moment on, all the network traffic of the laptop is routed via the smartphone, enabling the attacker to inspect and alter the whole bidirectional network traffic.

In a second attack scenario, BadAndroid could change the entries for the laptop's DNS servers and, therefore, redirect the laptop's traffic to servers controlled by the attacker.

BadBIOS

A maliciously-crafted BIOS hidden on the USB device could be installed on the computer by emulating keypresses at boot time 12 . This BadBIOS overrides the original BIOS and becomes the default BIOS to boot from. This allows an attacker to execute commands even before the actual operating system is loaded.

The applicability of BadBIOS is demonstrated 13 for modern Smart TVs. In this case, a Smart TV is forced to produce high-frequency audio signals. These signals contain information which is then transmitted to other devices.

Other attacks

The published literature includes USB-based attacks that exploit weaknesses beyond the ones spawned by BadUSB. The teensy USB development board 14 is designed to instrument and audit USB drivers, ports, and related software. This board is reprogrammable and can be used to launch attacks that are based on emulating keypresses and mouse movements.

The current version of the USBdriveby attack tool 15 targets Apple iOS devices. Once successful, USBdriveby alters the routing entries of the attacked system so as to redirect traffic to spoofed websites. The tool also installs a backdoor for the case the user detects the route modifications and changes them back to the legitimate ones.

Defenses against USB-based attacks

There have been proposals in the literature for defending against USB-based attacks, especially after the Stuxnet malware, which spread via infected USB drives and penetrated air-gapped systems [START_REF] Langner | Stuxnet: Dissecting a cyberwarfare weapon[END_REF][START_REF] Guri | GSMem: Data exfiltration from air-gapped computers over GSM frequencies[END_REF]. A first attempt towards more organizational security of USB device security is described in [START_REF] Yang | TMSUI: A trust management scheme of USB storage devices for industrial control systems[END_REF]. There, a trust management scheme, namely TMSUI, is proposed. TMSUI protects an ICS by allowing the connection of USB storage devices only on certain protected terminals and only for a specific amount of time.

ProvUSB is an architecture for fine-grained provenance collection and tracking on smart USB devices [START_REF] Tian | ProvUSB: Block-level provenance-based data protection for USB storage devices[END_REF]. ProvUSB aims at environments where the use of pre-approved-only USB drives can be controlled and enforced.

UScramBle is a proposal for protecting against eavesdropping attacks that are feasible due to the broadcast nature of (pre-USB 3.0) hub-to-device communication [START_REF] Neugschwandtner | A Transparent Defense Against USB Eavesdropping Attacks[END_REF]. It can be used to defend against reverse engineering of legitimate devices.

A line of defense against BadUSB-like attacks incorporates the user into the trust decision. One example is USBWall [START_REF] Kang | USBWall: A Novel Security Mechanism to Protect Against Maliciously Reprogrammed USB Devices[END_REF]. USBWall uses a Beagle Board 16 in order to enumerate USB devices on behalf of the operating system. As soon as the enumeration is carried out, the user is asked to decide whether the USB device must be removed from the system or is safe for further use. USBCheckIn is a hardware-based approach, where the user is forced to actively interact with the HID using guided patterns so as to authorize its use [START_REF] Griscioli | USBCheckIn: Preventing BadUSB attacks by forcing human-device interaction[END_REF].

The "G DATA USB Keyboard Guard" software17 is another system that relies on the users' decision whether a USB device is malicious or benign. There, when a new HID device is connected to the protected computer, the software asks the user to decide if the device interface(s) are to be trusted or not. Once a decision is made, the device (in fact, the combination of product and vendor identifiers) is either whitelisted or blacklisted so as to avoid asking again in the future. If an attacker flashes a malicious device to present with a previously whitelisted combination of product and vendor identifiers (e.g., a legitimate keyboard), then their attack will go unnoticed.

GoodUSB is a similar approach described in [START_REF] Tian | Defending Against Malicious USB Firmware with GoodUSB[END_REF]. GoodUSB includes a Linux kernel module that maps USB devices to specific whitelisted drivers. Upon connection of a new USB device, GoodUSB involves the user to decide if it should allow or deny the new device. If the user marks the device as malicious, the control is transferred to a virtualized USB honeypot running on QEMU-KVM. This allows to monitor and profile the activity of the USB device for further analysis.

USBFILTER is a packet-level filter (firewall) for USB communications developed for the Linux kernel space [START_REF] Tian | Making USB great again with USBFILTER[END_REF]. The user defines access rules in USBTables, the userland component of USBFILTER and the kernel-space component checks each USB packet received for match with one of the rules and decides to either forward or drop it. By design, USBFILTER supports only per-packet processing. Given the simplicity of the supported rules, attackers can evade the rules by adjusting their behavior accordingly; overall USBFILTER is a deterministic solution that detects already known attacks and does not have any anomaly detection capabilities [START_REF] Nissim | USB-based attacks[END_REF].

Cinch is an approach similar in principles to USBFILTER [START_REF] Angel | Defending against malicious peripherals with Cinch[END_REF]. However, Cinch isolates all USB devices from the host and passes communication through a virtual machine acting as a gateway that enforces the access policies.

SandUSB offers a GUI for the users to mark a newly plugged-in device as malicious or benign [START_REF] Loe | Sandusb: An installation-free sandbox for usb peripherals[END_REF]. Should the users consider the device being malicious, they can either blacklist it or redirect it to a USB sandbox for further analysis.

A Novel Approach for Detection of USB-based Keypress Injection Attacks

We consider a keypress injection attack as the most severe USB-based threat to system security. This is because a carefully-crafted attack, launched through innocent-looking keypresses, leverages the powerful resources and flexibility of the host system so as to take over the full control of the system itself. The proposed defenses against keypress injection attacks until now have in common that they rely at some point on user decisions. The user insights in such low-level system trust decisions is not an optimal solution. This is especially true when such interactions break their mental model for the primary task at hand, so as to cope with a secondary one [START_REF] Dingledine | Anonymity loves company: Usability and the network effect[END_REF][START_REF] Fidas | When security meets usability: A user-centric approach on a crossroads priority problem[END_REF].

In the following, we explore how we can detect and defend against USBbased keypress injection attacks by performing USB packet traffic analysis at the system level, without involving the user in the decision loop. Our aim is to simplify attack detection and offer neutralization upon connection of a malicious USB device that acts as a keyboard. This includes fast detection and no user involvement in the security decision.

Threat model

We assume an enterprise environment where computers are equipped with USB ports and the users are free to plug in and unplug USB devices for their dayto-day work duties (e.g., mass storage devices, headsets, and web cameras for teleconferences).

We further assume that the attackers succeed in connecting a crafted device with a malicious USB firmware to one or more of these computers. This can be achieved by the attackers themselves, if they have physical access to the targeted computer, inside or outside the premises of the enterprise. Or, by handing in a malicious device to legitimate users and exploit their curiosity (e.g., drop a USB thumb drive in their postal mailbox) or apply a social engineering attack vector (e.g., "can you please print the file from my USB thumb drive?").

We do not consider attack vectors such as USB storage media loaded with malware (e.g., exploit the "autorun" feature). Mitigations for such attacks are already offered by commercial antivirus products [START_REF] Pham | Universal serial bus based software attacks and protection solutions[END_REF]. We also do not consider attacks that exploit (unknown) vulnerabilities of the USB device drivers of the host operating system triggered by malformed USB packets [START_REF] Johnson | Protecting against malicious bits on the wire: Automatically generating a USB protocol parser for a production kernel[END_REF]. Rather, we assume that all USB packets are well-formed and valid according to the USB protocol.

Patterns of keypress injection attacks

The first step for developing appropriate defenses is to get a better understanding of the keypress injection attack patterns. Towards this direction, we experimented with two USB device types that their firmware can be updated and for which appropriate reflashing tools are available. The first one was a Rubber Ducky device. The second one was a Toshiba USB 3.0 USB drive.

In the case of Rubber Ducky, it sufficed to compile a new firmware, which contained an attack payload, by using the provided compiler and then copy the firmware on its SD card.

The case of the benign Toshiba USB drive required some additional steps. First, the original firmware of the device was dumped, then the attack payload was integrated in the firmware, and finally the firmware was written back to the chip. This was not an error-free process. Our first attempts ended up with unusable (bricked) devices and unreliable functionality of the controller chip resulting in unstable behavior.

We also prepared a desktop computer that acted as the host for the attacks. We used the Wireshark network protocol analyzer 18 to monitor the USB connections and collect the related USB packet traces for further analysis.

As an attack demonstration scenario, we opted to use the automatic launch of a text editor in the Linux operating system, including some text filling. Once connected, the malicious devices registered themselves as keyboards and sent the necessary keypresses. The sequence of events was as follows:

1. An artificial delay of 500 milliseconds. 2. Send the ALT key followed by the F2 key in order to prepare an application launch.

3. An artificial delay of 500 milliseconds. 4. Send a string of characters for launching a text editor (e.g., gEdit or mousepad), followed by the ENTER key. 5. An artificial delay of 500 milliseconds. 6. Send one paragraph of text comprising 515 characters from the Bacon Ipsum (http://baconipsum.com/) text.

Albeit not malicious in nature, the attach scenario above serves as a baseline for building weaponized attacks, such as opening a terminal, disabling any running antivirus service, and running a wget command to download malicious code to the attacked system. The artificial delays are necessary to provide the operating system with enough time to successfully respond to issued commands, e.g., opening the text editor. The attack script sends 526 keypresses in total.

We ran each attack (BadUSB and Rubber Ducky) ten times and collected in total 20 Wireshark traces. We analyzed these traces and focused on the timing patterns of the KEY DOWN events that are sent when a key on a keyboard is pressed.

Figure 2 depicts the distribution of the distance between each of the 5,260 recorded events (i.e., the interarrival time of the keypresses) for each of the ten repetitions of each attack in box-and-whisker diagrams. There are only a couple of outliers for each trace (Capture ID), which are at about 1.35 seconds (in the case of BadUSB) and 1.00 seconds (in the case of Rubber Ducky). The median value in both cases is about 6 ms and almost all values are concentrated in a narrow band around this value, as depicted in Figure 2a and Figure 2b.

This was a stable behavior in all traces and for both attacks; Rubber Ducky exhibits a greater variability, but still within the narrow band. We ran repeated experiments with all the payloads made available by the Rubber Ducky authors 19 . There were in total more than 70 different payloads at the time of writing. The analysis of the traces revealed that all of the payloads produced the keypresses with no delay, i.e., the USB-based keypress injection attacks try to conclude their malicious actions as fast as possible. From an attack point of view, it is a rational choice to inject keypresses as fast as possible: for an attack to be successful, all the events of the script must execute without being interrupted by any user-initiated typing activity. Since the attacked system has two keyboards now, it is possible that the user continues their typing activity. In this case, typing will intermix with the (fake) keypresses of the attack script and, thus, neutralize the latter by accident (and possibly frustrate the user with the extra characters). The less the time in between the (fake) keypresses, the more the probability of a successfully-launched attack. This is a key observation for the design of our defense.

Keystroke dynamics

Research in keystroke dynamics (or keystroke-based biometrics) suggests that human typing patterns exhibit variations and these "typing dynamics" can be strong enough to be used for authentication or identification purposes [START_REF] Teh | A survey of keystroke dynamics biometrics[END_REF]. Also, human beings cannot perform better than 80 ms between their keypressess [START_REF] Umphress | Identity verification through keyboard characteristics[END_REF]. In contrast, our analysis reveals that BadUSB-like attacks inject keypresses at an almost stable rate of 6 ms. These two rates differ by an order of magnitude.

USBlock: blocking malicious USB packet traffic

USBlock is a defense we devised that exploits the temporal gap between human and BadUSB-like attack typing dynamics. The design assumption is that a USB host monitor (i.e., USBlock) has access to precise timing information of received USB packets and is able to distinguish fast between the normal typing behavior of human beings and the abnormal keypress sequence (AKS) timings of BadUSBlike attacks.

A simple case of an AKS is a "rapid (keypress) event sequence" (RES). We define a RES using two components, a time threshold value t and a sequence threshold value s. We say that a RES occurred whenever we observe a sequence of s consecutive keypresses with an interarrival time less than t seconds between each of them. If a RES occurs, a defense action must be taken.

The selection of the exact values for t and s is a design choice. The t-threshold can be any value 0.006 < t < 0.08, i.e., anything between the 6 ms median value of the BadUSB-like attacks and the lower limit of 0.08 seconds for humans. A t close to the lower bound of 0.006 makes USBlock more prone to false negatives, thus, risking a successful attack going unnoticed. Yet, it reduces the probability of false positives, as humans cannot type that fast. In contrast, a t close to the upper bound 0.08 makes USBlock more prone to false positives, thus, risking user complaints on legitimate usage Our analysis of the collected attack and human-typing traces (cf. Section 4) suggests that a t = 0.02 is a sufficient threshold for the current generation of BadUSB-like attacks.

An s = 1 makes USBlock blindly aggressive (many false positives), penalizing even in a single occurrence of a keypress under the timing threshold. In contrast, a large s (e.g., over 100) allows USBlock to make confident decisions on the presence of an AKS. However, one must account two additional points. First, if the decision algorithm does not react in real-time, it risks to allow an attack to have occurred already by the time a (correct) decision is made. This is unacceptable from a security point of view. Second, the length of the attack vector, i.e., the number of keypresses injected to realize the attack, might be lower than s (e.g., only 20 or 30 keypresses compared to an s = 100). In this case, USBlock will fail to detect the attack altogether, as there are not enough "malicious" keypresses present to react on.

Our analysis of the available traces suggests that a short s = 3 offers the clear advantage that a keypress injection attack is detected and prevented just after the very first few fast keypresses are sent. The attack traces contained not a single case where two or more outlier values came in pairs or bursts. Furthermore, to the best of our knowledge, no attack vector can be realized with only three keypresses. Hence, s = 3 is an excellent choice.

The capabilities of USBlock are better demonstrated with an example of a defense realization against current generation of Ducky Script malicious payloads. A USB monitor runs as a piece of software on the host system and measures the interarrival times of keypresses sent by each connected USB device for a RES, using the t and s parameters. When a RES is detected, the USB monitor instructs the USB hub to switch off the power of the USB port for some (e.g., ten) seconds (configurable). It also instructs the operating system to unload (unbound) the respective device driver. This in effect blocks access to the suspicious device. We highlight that no additional piece of hardware is needed for performing these actions. The disconnection approach ensures that no user involvement is required in restoring the connectivity of other USB devices that are possibly attached to the specific USB port where the attack occurred.

One may argue that the design opts for a rather aggressive reaction to suspicious events. We believe that our two-step disablement approach accommodates this. It is better for users to notice an occasional interruption of their normal flow (in case the events are indeed produced that fast by human beings) rather than risking an infection by a malicious device. If the interruptions become too frequent, it is an indication of an attack in progress (e.g., a USB drive trying to relaunch the attack). In this case, it would be better for the IT support personnel to inspect the offending system.

USBlock defenses against advanced attacks

USBlock with RES defends currently against all known malicious Ducky Script payloads. The approach of USBlock is generic enough and allows to realize and integrate new defenses against new attacks. As the cat-and-mouse game between attackers and defenders might evolve for BadUSB-like attacks, RES can be replaced by a more complex AKS detection logic. Such logic will push attackers to adjust keypress injection rates to mimic human behavior. This task will be more and more difficult to both realize in the constrained environment of USB firmware and to match specific user typing patterns. At the moment, this is not deemed necessary and would incur additional and unnecessary processing overhead.

We note that USBlock with RES cannot be defeated by malicious firmware that delays the launch of the payload (i.e., the start of the attack), once the fake device is plugged. USBlock is continuously monitoring for keypress events. Hence, when a RES occurs, USBlock will detect it, no matter how long ago the fake device was plugged.

One may argue that a malicious Ducky Script can introduce delays between keypresses to avoid detection. However, the constant interarrival time of the keypresses is an easily-detectable AKS pattern. Should a Ducky Script can generate random delays between keypresses, these must occur as a human typing pattern, sparse in time. At this rate, they will become intermixed with the normal typing activity of the user (and thus, neutralized) or they will become noticeable by the user, as the attacks do not happen "in the blink of an eye" anymore (e.g., the cursor is moved or the focus of the working window is lost). Should the user is incapable or unwilling of noticing the additional typing activity on their monitor, we must resort on enterprise network security defenses that might be able to detect the malicious activity of the attacked system, once infected.

Clearly, analyzing the typed command strings (from humans or scripts) and reasoning about their (possibly) malicious intentions is beyond the scope of USBlock. Such fine-grained keypress analysis will probably not be acceptable by the users, as it severely violates their privacy creating an Orwellian feeling of constant monitoring.

One may argue that a malicious USB firmware can monitor the status of the operating system and launch the payload during periods of user inactivity (e.g., when there is no typing activity for a long time). We are not aware of such capabilities for Ducky Scripts and, to the best of our knowledge, such information cannot be requested by the USB firmware from the operating system over USB packets. Even if such capabilities exist in first place, USBlock is on the side of the operating system. Thus, it can also access such information and integrate them into its decision logic to block malicious USB traffic. We further note that such an attack cannot be launched at all if the screen is locked (e.g., due to inactivity or a precautious measure by the user when plugging an untrusted device).

Limitations of USBlock

While USBlock defends successfully against keypress injection attacks, it does not come free of limitations. USBlock lies and relies on information at the level of the operating system. As such, it cannot defend against attacks launched at the BIOS level, as is the case of BadBIOS discussed in Section 2.

Hardware keys, like Yubico YubiKey20 , are a popular means of two-factor authentication. Such devices identify themselves to the operating system as keyboards and "type" one-time passwords and other sensitive information on behalf of their owner. Hence, USBlock will interpret the YubiKey rapid keypresses as an attack. To overcome this, USBlock implements internally the following check for YubiKey devices: if a connected USB device reports a (VID, PID) of Yubico, the RES logic is disabled for this device. Rather, USBlock monitors the USB device traffic to ensure that the USB packet payload comprise exclusively "MODHEX" characters 21 . This is an improved approach over (VID, PID) whitelisting [START_REF] Tian | Defending Against Malicious USB Firmware with GoodUSB[END_REF], as anyone can fake the reported (VID, PID). As discussed earlier in Section 2, these are inherent limitations of the USB protocol itself rather than of USBlock. The host system must blindly trust the information provided by peripheral devices without any authentication support.

Proof-of-concept implementation and evaluation

We now describe a proof-of-concept implementation of the designed system and its evaluation in realistic environments. The evaluation comprises two parts: the first part relates to the long-term stability of the prototype and to evaluating the effect of the temporal variations in typing habits; the second part explores the typing dynamics of different users.

Proof-of-concept implementation

We realized a proof-of-concept implementation for the Linux operating system comprising two parts. The first part is a Linux loadable kernel module (for kernel version 4.2) that monitors for the keypresses. Being in the kernel, this part is as close as possible to the raw information about keypresses received from the USB device and enriches them with very precise timings. The kernel module then forwards the enriched information to the second part residing in userland. The communication between the two parts occurs over a netlink socket that is registered in both the kernel space and userland. This is an approach similar to the one of [START_REF] Tian | Making USB great again with USBFILTER[END_REF]. However, the latter does not support timestamps and multipacket processing, which are necessary for our aims.

The second part is a Python script. This part implements the rapid event sequence (RES) detection logic and is responsible for unbinding the offending USB driver from the kernel. This effectively disconnects the device interface from the system. If the driver of the device is automatically re-bound (as part of an ongoing attack), then, as an additional protective measure, the driver for the corresponding USB hub on which the device is connected is also unbound for ten seconds. This effectively removes all the devices connected on this hub. The unbind/re-bind procedure is repeated until a user action is initiated or a system administrator takes over. We note that the USB packet processing, from kernel capture to RES detection (via the Python script) and reaction, requires on average about 0.3 ms per packet. Hence, it takes 1 ms to detect an s = 3 RES. This is more than enough processing time, given that the median interarrival time for BadUSB-like keypress injections is about 6 ms.

Evaluation of temporal variations

We evaluated the effect of temporal variations in typing as follows. We installed the prototype in one of the authors' computers, a notebook running Ubuntu 15.10. The notebook was used on a day-to-day basis with a USB-connected keyboard for a period of three months. The aim was twofold: on the one hand, to evaluate the stability of the prototype and to discover any problems that it might cause; on the other hand, to study the user's typing behavior in the course of a long period that involved a multitude of typing activities including code development, debugging, system administration tasks, scientific paper writing, preparation of talks and presentations, shell scripting, email typing, and web browsing.

We instrumented the kernel module usbmon [START_REF] Zaitcev | The usbmon: USB monitoring framework[END_REF] to collect and log the USB events and act as a middleware between the kernel and our offline analysis tools. In userland, the TShark part of the Wireshark bundle was used to "listen" to USB events sent by usbmon. A Python script was used to generate pcap-formatted files containing all the USB-related events. A second Python script was then used to process the files and store the collected information into a database for later analysis.

Overall, we did not experience any kind of stability problems while operating the prototype and the additional monitoring infrastructure. Neither we experienced any kind of measurable performance degradation. It did not cause any side effects (at least that we became aware of). Thus, the temporal variations in typing did not affect the operation of the prototype.

We collected in total timing information for more than 466,000 keypresses over more than 60 working days. Less than 1% of them were below the t = 0.02 second threshold, while the vast majority ranked quite higher. The median value of interarrival times was 0.10 seconds, while the average time was 0.21 seconds.

There was no single case of three or more consecutive keypresses with an interarrival time below the defined threshold. Thus, it was never the case that the prototype unbound the USB keyboard device driver, i.e., we experienced no false positives.

Evaluation of typing dynamics

The second phase of the evaluation was a study on the effect of the typing dynamics. We designed a small-scale user study so as to collect evidence about typing patterns and compare them against the behavior of the Rubber Ducky and BadUSB attacks as well as published literature for typing dynamics.

We developed a research prototype system comprising a headless Raspberry Pi Model 2B running Ubuntu server 15.10, a USB keyboard, and a battery pack for autonomous operation. Similarly to the previous evaluation, we used a kernel module to collect the keypress timing information and send them to a userland application. The latter collected and aggregated the information prior to storing them into a database for later processing.

We recruited 33 volunteers from our organization for this experiment. We visited each participant at their desk and asked them to type a short text in the comfort of their desk using our research prototype system. We offered the participants the option to either plug in their keyboard or use the keyboard of our prototype. All but one participants opted to use our keyboard, as it felt more convenient for them not to unplug their keyboard, or because they were using laptops and docking stations.

We asked the participants to type the same, randomly-selected paragraph of the Bacon Ipsum text comprising 71 characters. Figure 3 depicts the distribution of the distance between each of the 71 recorded events (i.e., the keypresses interarrival time) produced by each participant in box-and-whisker diagrams. The diagrams indicate that each participant exhibited different typing patterns. Almost all diagrams contain a large number of outliers towards larger numbers. Delays of one or even three seconds between keypresses are noticed. The overall median value was 0.20 seconds and the average time reached 0.30 seconds. Despite the per-participant differences, there was not a single case where our research prototype detected erroneously a RES, i.e., once more, there were zero false positives.

Our typing dynamics analysis results are in alignment with published literature [START_REF] Teh | A survey of keystroke dynamics biometrics[END_REF]. Hence and for the sake of research efficiency and economy, we opted not to expand the study to more participants.

The second part of the evaluation confirmed that typing dynamics are quite stable among users, despite some unavoidable differentiations. More importantly, even in short texts, the human typing dynamics are clearly above the detection threshold we have defined and clearly distinguishable from that of the Rubber Ducky and BadUSB attacks (cf. Figures 3 and2). Thus, such information can serve as a heuristic for detecting and defending against the attacks.

Conclusions and future work

BadUSB-like attacks are a realistic threat. Yet, system-level defenses cannot be realized in the form of malware analysis tools for USB firmware. USB device whitelisting can offer some protection in specific usage scenarios, but its usability is hindered when scaling in enterprise-level networks. Proposed defenses in the literature mandate the user involvement in the trust decisions. This is a suboptimal, error-prone design choice.

In this paper, we studied the temporal characteristics of BadUSB-like attacks. We proposed USBlock to block malicious USB packet traffic. Our proposal is extensible and can integrate additional features for coping with future, advanced attacks. Residing on the side of the operating system, USBlock has an advantage over a malicious USB firmware payload executing on a peripheral device and interacting with the main system.

We implemented a proof-of-concept defense module for the Linux kernel. We evaluated its stability under different usage patterns for three months and studied the user temporal variations and typing dynamics in a small-scale study. The collected evidence suggest that our implementation caused no issues while human typing behavior was clearly distinguishable from that of the existing known attacks.

Our findings indicate that it is feasible to realize advanced defense mechanisms for BadUSB-like attacks by integrating system-level temporal characteristics and without involving the user in the trust decisions.

Further validation of our findings by the network and system security community can provide stronger confidence for the applicability of our approach. We envision that such information as well as information regarding the spread of USB devices across an enterprise network can be used as additional feature in order to enrich the malware detection process and enhance our arsenal in fighting cybercrime.

Fig. 1 :

 1 Fig. 1: USB packet sequence diagram (malicious behavior)

Fig. 2 :

 2 Fig. 2: Interarrival times of KEY DOWN events in collected traces (outliers exclused for the sake of clarity)

Fig. 3 :

 3 Fig. 3: Temporal variations in the typing dynamics experiment.

https://adamcaudill.com/2014/10/02/making-badusb-work-for-you-derbycon/

https://www.pjrc.com/teensy/

https://hak5.org

https://github.com/hak5darren/USB-Rubber-Ducky/wiki/Duckyscript

https://srlabs.de/blog/wp-content/uploads/2014/07/BadAndroid-v0.1.zip

https://srlabs.de/wp-content/uploads/2014/11/SRLabs-BadUSB-Pacsec-v2. pdf

https://nakedsecurity.sophos.com/2015/11/16/badbios-is-back-this-time-on-your-tv/

https://www.pjrc.com/teensy/

http://samy.pl/usbdriveby/

https://beagleboard.org

https://www.gdatasoftware.com/en-usb-keyboard-guard

https://wireshark.org/

https://github.com/hak5darren/USB-Rubber-Ducky/wiki/Payloads

https://www.yubico.com/products/yubikey-hardware/

The modified hexadecimal characters are {b, c, d, e, f, g, h, i, j, k, l, n, r, t, u, v}, cf. https://www.yubico.com/support/knowledge-base/categories/ articles/one-time-password-otp/.

Acknowledgements

This research was supported by the Austrian Research Promotion Agency (FFG) through the BRIDGE 1 grant P846070 (SpeedFor) and the COMET K1-Centres programme line (SBA2). S. Neuner was also supported by the Austrian Marshall Plan Foundation through a Marshall Plan Scholarship. We thank Prof. E. Kirda and W. Robertson for their valuable support during the early stages of this research as well as the participants in the typing experiments.