Computer Security

The Connected Mobility Lab (CML) is a mobility solution created in collaboration between Siemens and BMW. The CML provides a multi-tenant cloud infrastructure where entities – mobility providers, financial service providers, users – might know each other or might be complete strangers. The CML encapsulates core services from different stakeholders and exposes an integrated, comprehensive, and innovative mobility service to its users. The different owners may have different security goals and impose their own rules and workflows on entities interacting with their services. Thus, there is a need to negotiate in order to reach mutually acceptable compromises, and inter-operate services within the CML. Especially, when different services collaborate to fulfill a purpose it is important to allow only authorized entities to execute the required tasks. To enforce such tasks to be executed in a particular order we need a workflow specification and enforcement method.

This paper presents a workflow specification and enforcement framework that guarantees the process integrity (for instance, a technical process) by enforcing an access control method that restricts the entities to do only what is allowed in the specified workflow. The framework also supports dynamic workflows that adapt to error conditions, and a method to support accountability. We evaluate our proposed framework on a CML business mobility use case. We extend the Petri Nets based workflow specification and enforcement framework proposed in [2] to achieve our goals.

The proliferation of 4G/LTE (Long Term Evolution)-capable mobile devices calls for new techniques and tools for assessing their vulnerabilities effectively and efficiently. Existing methods require significant human efforts, such as manual examination of LTE protocol specifications or manual analysis of LTE network traffic, to identify potential vulnerabilities. In this work, we investigate the possibility of automating vulnerability assessment of 4G/LTE mobile devices based on AI (Artificial Intelligence) techniques. Towards this end, we develop LEFT (LTE-Oriented Emulation-Instrumented Fuzzing Testbed), which perturbs the behavior of LTE network modules to elicit vulnerable internal states of mobile devices under test. To balance exploration and exploitation, LEFT uses reinforcement learning to guide behavior perturbation in an instrumented LTE network emulator. We have implemented LEFT in a laboratory environment to fuzz two key LTE protocols and used it to assess the vulnerabilities of four COTS (Commercial Off-The-Shelf) Android mobile phones. The experimental results have shown that LEFT can evaluate the security of 4G/LTE-capable mobile devices automatically and effectively.

PendingIntents are a powerful and universal feature of Android for inter-component communication. A PendingIntent holds a base intent to be executed by another application with the creator’s permissions and identity without the creator necessarily residing in memory. While PendingIntents are useful for many scenarios, e.g., for setting an alarm or getting notified at some point in the future, insecure usage of PendingIntents causes severe security threats in the form of denial-of-service, identity theft, and privilege escalation attacks. An attacker may gain up to SYSTEM privileges to perform the most sensitive operations, e.g., deleting user’s data on the device. However, so far no tool can detect these PendingIntent vulnerabilities.

In this work we propose PIAnalyzer, a novel approach to analyze PendingIntent related vulnerabilities. We empirically evaluate PIAnalyzer on a set of 1000 randomly selected applications from the Google Play Store and find 1358 insecure usages of PendingIntents, including 70 severe vulnerabilities. We manually inspected ten reported vulnerabilities out of which nine correctly reported vulnerabilities, indicating a high precision. The evaluation shows that PIAnalyzer is efficient with an average execution time of 13 seconds per application.

Fingerprinting of browsers has been thoroughly investigated. In contrast, mobile phone applications offer a far wider array of attributes for profiling, yet fingerprinting practices on this platform have hardly received attention.

In this paper, we present the first (to our knowledge) investigation of Android libraries by commercial fingerprinters. Interestingly enough, there is a marked difference with fingerprinting desktop browsers. We did not find evidence of typical fingerprinting techniques such as canvas fingerprinting. Secondly, we searched for behaviour resembling that of commercial fingerprinters. We performed a detailed analysis of six similar libraries. Thirdly, we investigated \(\sim \)30,000 apps and found that roughly 19% of these apps is using one of the these libraries. Finally, we checked how often these libraries were used by apps subject to the Children’s Online Privacy Protection Act (i.e. apps targeted explicitly at children), and found that these libraries were included 21 times.

Searchable Symmetric Encryption (SSE) enables a client to securely outsource large encrypted database to a server while supporting efficient keyword search. Most of the existing works are designed against the honest-but-curious server. That is, the server will be curious but execute the protocol in an honest manner. Recently, some researchers presented various verifiable SSE schemes that can resist to the malicious server, where the server may not honestly perform all the query operations. However, they either only considered single-keyword search or cannot handle very large database. To address this challenge, we propose a new verifiable conjunctive keyword search scheme by leveraging accumulator. Our proposed scheme can not only ensure verifiability of search result even if an empty set is returned but also support efficient conjunctive keyword search with sublinear overhead. Besides, the verification cost of our construction is independent of the size of search result. In addition, we introduce a sample check method for verifying the completeness of search result with a high probability, which can significantly reduce the computation cost on the client side. Security and efficiency evaluation demonstrate that the proposed scheme not only can achieve high security goals but also has a comparable performance.

Order-preserving encryption (OPE) and order-revealing encryption (ORE) are among the core ingredients for encrypted databases (EDBs). In this work, we study the leakage of OPE and ORE and their forward security.

We propose generic yet powerful file-injection attacks (FIAs) on OPE/ORE, aimed at the situations of possessing order by and range queries. Our FIAs only exploit the ideal leakage of OPE/ORE (in particular, no need of data denseness or frequency). We executed some experiments on real datasets to test the performance, and the results show that our FIAs can cause an extreme hazard on most of the existing OPEs and OREs with high efficiency and 100% recovery rate.

We then formulate forward security of ORE, which is of independent of interest, and propose a practical compilation framework for achieving forward secure ORE in order to resist the perniciousness of FIA. The compilation framework can transform most of the existing OPEs/OREs into forward secure OREs, with the goal of minimizing the extra burden incurred on computation and storage. We also execute some experiments to analyze its performance.

A method of detecting and interrupting unauthorized, browser-based cryptomining is proposed, based on semantic signature-matching. The approach addresses a new wave of cryptojacking attacks, including XSS-assisted, web gadget-exploiting counterfeit mining. Evaluation shows that the approach is more robust than current static code analysis defenses, which are susceptible to code obfuscation attacks. An implementation based on in-lined reference monitoring offers a browser-agnostic deployment strategy that is applicable to average end-user systems without specialized hardware or operating systems.

A certain amount of web traffic is attributed to web bots on the Internet. Web bot traffic has raised serious concerns among website operators, because they usually consume considerable resources at web servers, resulting in high workloads and longer response time, while not bringing in any profit. Even worse, the content of the pages it crawled might later be used for other fraudulent activities. Thus, it is important to detect web bot traffic and characterize it. In this paper, we first propose an efficient approach to detect web bot traffic in a large e-commerce marketplace and then perform an in-depth analysis on the characteristics of web bot traffic. Specifically, our proposed bot detection approach consists of the following modules: (1) an Expectation Maximization (EM)-based feature selection method to extract the most distinguishable features, (2) a gradient based decision tree to calculate the likelihood of being a bot IP, and (3) a threshold estimation mechanism aiming to recover a reasonable amount of non-bot traffic flow. The detection approach has been applied on Taobao/Tmall platforms, and its detection capability has been demonstrated by identifying a considerable amount of web bot traffic. Based on data samples of traffic originating from web bots and normal users, we conduct a comparative analysis to uncover the behavioral patterns of web bots different from normal users. The analysis results reveal their differences in terms of active time, search queries, item and store preferences, and many other aspects. These findings provide new insights for public websites to further improve web bot traffic detection for protecting valuable web contents.

The advent of cloud computing has inspired an increasing number of users outsourcing their data to remote servers to enjoy flexible and affordable data management services. However, storing data in a remote cloud server raises data privacy and security concerns, i.e., the integrity and origin of the query results. Although some solutions have been proposed to address these issues, none of them consider the arbitrary dissemination control of authenticated tree-structured data while disseminating to other users.

To address the above concerns, in this paper, we first propose a novel and efficient redactable signature scheme which features editable homomorphic operation and redaction control on tree-structured data. Subsequently, we prove the security properties of our scheme and conduct extensive theoretical and experimental analyses. The experimental results show that our scheme outperforms the existing solutions in disseminating of authenticated tree-structured data with privacy protection and dissemination control in outsourced database (ODB) model.

While big data becomes a main impetus to the next generation of IT industry, big data privacy, as an unevadable topic in big data era, has received considerable attention in recent years. To deal with the privacy challenges, differential privacy has been widely discussed as one of the most popular privacy-enhancing techniques. However, with today’s differential privacy techniques, it is impossible to generate a sanitized dataset that can suit different algorithms or applications regardless of the privacy budget. In other words, in order to adapt to various applications and privacy budgets, different kinds of noises have to be added, which inevitably incur enormous costs for both communication and storage. To address the above challenges, in this paper, we propose a novel scheme for outsourcing differential privacy in cloud computing, where an additive homomorphic encryption (e.g., Paillier encryption) is employed to compute noise for differential privacy by cloud servers to boost efficiency. The proposed scheme allows data providers to outsource their dataset sanitization procedure to cloud service providers with a low communication cost. In addition, the data providers can go offline after uploading their datasets and noise parameters, which is one of the critical requirements for a practical system. We present a detailed theoretical analysis of our proposed scheme, including proofs of differential privacy and security. Moreover, we also report an experimental evaluation on real UCI datasets, which confirms the effectiveness of the proposed scheme.

Our main technical contribution is mx-u, an efficient scheme with small cross-user leakage, whose security is based on the decisional Diffie-Hellman assumption. We prove a tight bound on the leakage of mx-u in the presence of an honest-but-curious adversary that colludes with a non-adaptively chosen subset of users. We report on experiments showing that mx-u is efficient and that cross-user leakage grows slowly as queries are performed.

Dynamic searchable symmetric encryption (DSSE) is a useful cryptographic tool in encrypted cloud storage. However, it has been reported that DSSE usually suffers from file-injection attacks and content leak of deleted documents. To mitigate these attacks, forward security and backward security have been proposed. Nevertheless, the existing forward/backward-secure DSSE schemes can only support single keyword queries. To address this problem, in this paper, we propose two DSSE schemes supporting range queries. One is forward-secure and supports a large number of documents. The other can achieve both forward security and backward security, while it can only support a limited number of documents. Finally, we also give the security proofs of the proposed DSSE schemes in the random oracle model.

In this paper, we analyze the security of an end-to-end encryption scheme (E2EE) of LINE, a.k.a Letter Sealing. LINE is one of the most widely-deployed instant messaging applications, especially in East Asia. By a close inspection of their protocols, we give several attacks against the message integrity of Letter Sealing. Specifically, we propose forgery and impersonation attacks on the one-to-one message encryption and the group message encryption. All of our attacks are feasible with the help of an end-to-end adversary, who has access to the inside of the LINE server (e.g. service provider LINE themselves). We stress that the main purpose of E2EE is to provide a protection against the end-to-end adversary. In addition, we found some attacks that even do not need the help of E2E adversary, which shows a critical security flaw of the protocol. Our results reveal that the E2EE scheme of LINE do not sufficiently guarantee the integrity of messages compared to the state-of-the-art E2EE schemes such as Signal, which is used by WhatApp and Facebook Messenger.

Wildcarded identity-based encryption allows a sender to simultaneously encrypt messages to a group of users matching a certain pattern, defined as a sequence of identifiers and wildcards. We propose a new wildcarded identity-based encryption scheme with generalized key delegation, which reduces the ciphertext size to be constant. To the best of our knowledge, our proposal is the first wildcarded identity-based encryption scheme that generates a constant size ciphertext regardless of the depth of the identities. The proposed scheme also improves the decryption time by minimizing the wildcard conversion cost. According to our experiment results, decryption of the proposed scheme is 3, 10, and 650 times faster than existing WIBE, WW-IBE, and CCP-ABE schemes. The proposal also subsumes the generalized key derivation naturally by allowing wildcards in the key delegation process. We prove CPA security of the proposed scheme and extend it to be CCA secure.

Ring signatures make it possible for a signer to anonymously and, yet, convincingly leak a secret by signing a message while concealing his identity within a flexibly chosen ring of users. Unlike group signatures, they do not involve any setup phase or tracing authority. Despite a lot of research efforts in more than 15 years, most of their realizations require linear-size signatures in the cardinality of the ring. In the random oracle model, two recent constructions decreased the signature length to be only logarithmic in the number N of ring members. On the downside, their suffer from rather loose reductions incurred by the use of the Forking Lemma. In this paper, we consider the problem of proving them tightly secure without affecting their space efficiency. Surprisingly, existing techniques for proving tight security in ordinary signature schemes do not trivially extend to the ring signature setting. We overcome these difficulties by combining the Groth-Kohlweiss \(\varSigma \)-protocol (Eurocrypt’15) with dual-mode encryption schemes. Our main result is a fully tight construction based on the Decision Diffie-Hellman assumption in the random oracle model. By full tightness, we mean that the reduction’s advantage is as large as the adversary’s, up to a constant factor.

We introduce RiffleScrambler: a new family of directed acyclic graphs and a corresponding data-independent memory hard function with password independent memory access. We prove its memory hardness in the random oracle model.

RiffleScrambler is similar to Catena – updates of hashes are determined by a graph (bit-reversal or double-butterfly graph in Catena). The advantage of the RiffleScrambler over Catena is that the underlying graphs are not predefined but are generated per salt, as in Balloon Hashing. Such an approach leads to higher immunity against practical parallel attacks. RiffleScrambler offers better efficiency than Balloon Hashing since the in-degree of the underlying graph is equal to 3 (and is much smaller than in Ballon Hashing). At the same time, because the underlying graph is an instance of a Superconcentrator, our construction achieves the same time-memory trade-offs.

Recent advances in cryptography promise to let us run complex algorithms in the encrypted domain. However, these results are still mostly theoretical since the running times are still much larger than their equivalents in the plaintext domain. In this context, Majority Judgment is a recent proposal for a new voting system with several interesting practical advantages, but which implies a more involved tallying process than first-past-the-post voting. To protect voters’ privacy, such a process needs to be done by only manipulating encrypted data.

In this paper, we then explore the possibility of computing the (ordered) winners in the Majority Judgment election without leaking any other information, using homomorphic encryption and multiparty computation. We particularly focus on the practicality of such a solution and, for this purpose, we optimize both the algorithms and the implementations of several cryptographic building blocks. Our result is very positive, showing that this is as of now possible to attain practical running times for such a complex privacy-protecting tallying process, even for large-scale elections.

We analyze the FOO electronic voting protocol in the provable security model using the technique of Computationally Complete Symbolic Attacker (CCSA). The protocol uses commitments, blind signatures and anonymous channels to achieve vote privacy. Unlike the Dolev-Yao analyses of the protocol, we assume neither perfect cryptography nor existence of perfectly anonymous channels. Our analysis reveals new attacks on vote privacy, including an attack that arises due to the inadequacy of the blindness property of blind signatures and not due to a specific implementation of anonymous channels. With additional assumptions and modifications, we were able to show that the protocol satisfies vote privacy in the sense that switching votes of two honest voters is undetectable to the attacker. Our techniques demonstrate effectiveness of the CCSA technique for both attack detection and verification.

Location privacy has mostly focused on scenarios where users remain static. However, investigating scenarios where the victims present a particular mobility pattern is more realistic. In this paper, we consider abstract attacks on services that provide location information on other users in the proximity. In that setting, we quantify the required effort of the attacker to localize a particular mobile victim. We prove upper and lower bounds for the effort of an optimal attacker. We experimentally show that a Linear Jump Strategy (LJS) practically achieves the upper bounds for almost uniform initial distributions of victims. To improve performance for less uniform distributions known to the attacker, we propose a Greedy Updating Attack Strategy (GUAS). Finally, we derive a realistic mobility model from a real-world dataset and discuss the performance of our strategies in that setting.

We present an improved constant-round secure two-party protocol for integer comparison functionality, which is one of the most fundamental building blocks in secure computation.

Our protocol is in the so-called client-server model, which is utilized in real-world MPC products such as Sharemind, where any number of clients can create shares of their input and distribute to the servers who then jointly compute over the shares and return the shares of result to the client. In the client-aided client-server model, as mentioned briefly by Mohassel and Zhang (S&P’17), a client further generates and distributes some necessary correlated randomness to servers. Such correlated randomness admits efficient protocols since otherwise servers have to jointly generate randomness by themselves, which can be inefficient.

Secure multi-party computation (MPC) protocols are powerful privacy enhancing technologies. Yet, their scalability is limited for data intensive applications due to the circuit computation model. Therefore, RAM based secure computation (RAM-SC) has been proposed, which combines MPC with Oblivious RAM (ORAM). Unfortunately, realizing efficient RAM-SC applications by hand is a tedious and error-prone task, which requires expert knowledge in both cryptographic primitives and circuit design. To make things worse, a multitude of ORAMs with different trade-offs has been proposed. To overcome this entry barrier to RAM-SC, we present a two-fold approach. First, we explore all cost dimensions of relevant ORAMs in various deployment scenarios. Second, we present a fully automatized compilation approach from ANSI-C to RAM-SC. The presented compiler analyzes the input source code and extracts relevant information about the usage patterns of all arrays in the code. The results of the analysis are then used to predict the runtime of suitable ORAMs and to identify the ORAM that achieves minimal runtime. Thus, for the first time, RAM-SC also becomes accessible to non-domain experts.

The motivation for this work comes from the need to strengthen security of secure multi-party protocols with the ability to guarantee that the participants provide their truthful inputs in the computation. This is outside the traditional security models even in the presence of malicious participants, but input manipulation can often lead to privacy and result correctness violations. Thus, in this work we treat the problem of combining secure multi-party computation (SMC) techniques based on secret sharing with signatures to enforce input correctness in the form of certification. We modify two currently available signature schemes to achieve private verification and efficiency of batch verification and show how to integrate them with two prominent SMC protocols.

Advances in software virtualization and network processing lead to increasing network softwarization. Software network elements running on commodity platforms replace or complement hardware components in cloud and mobile network infrastructure. However, such commodity platforms have a large attack surface and often lack granular control and tight integration of the underlying hardware and software stack. Often, software network elements are either themselves vulnerable to software attacks or can be compromised through the bloated trusted computing base. To address this, we protect the core security assets of network elements - authentication credentials and cryptographic context - by provisioning them to and maintaining them exclusively in isolated execution environments. We complement this with a secure and scalable mechanism to enroll network elements into software defined networks. Our evaluation results show a negligible impact on run-time performance and only a moderate performance impact at the deployment stage.

Attribute based encryption (ABE) has potential to be applied in various cloud computing applications. However, the Snowden revelations show that powerful adversaries can corrupt users’ machines to compromise the security, and many implementations of provably secure encryption schemes may present undetectable vulnerabilities that can expose secret, e.g., the scheme still works properly even some backdoors have been stealthily engineered on users’ machines. Undoubtedly, ABE is also facing the above security threats. Recently, Mironov and Stephens-Davidowitz proposed cryptographic reverse firewall (CRF) to solve the problem. Unfortunately, no CRF-based protection for ABE has been proposed so far due to the complex system model and the extra access structure component. Besides, the encryption scheme in the CRF framework will suffer double computation latency, which is worse for ABE that has already yielded expensive operations. In this paper, we propose a concessive online/offline ciphertext-policy attribute based encryption with cryptographic reverse firewalls (COO-CP-ABE-CRF), which can resist the exfiltration of secret information and achieve selective CPA security. Furthermore, compared with the original scheme without CRF, our scheme reduces the total computation cost by half. Moreover, we develop an extensible library called \(\mathsf{libabe}\) that is compatible with Android devices, and we implement the prototype on a laptop and a mobile phone. The experimental results indicate that the scheme is efficient and practical.

Attribute-based encryption (ABE) as one of the most interesting multi-recipient public encryption systems, naturally requires some “tracing mechanisms” to identify misbehaving users to foster accountability when unauthorized key re-distributions are taken place.

We give a generic construction of (black-box) traceable ABE which only doubles the ciphertext size of the underlying ABE scheme. When instantiating properly, it yields the first such scheme with constant size ciphertext and expressive access control.

Furthermore, we extend our generic construction of traceable ABE to support authority accountability. This property is essential for generating an un-deniable proof for user misbehaviors. Our new generic construction gives the first black-box traceable ABE with authority accountability, and constant size ciphertext. All properties are achieved in standard security models.

Attribute-based encryption (ABE) enables limiting access to encrypted data to users with certain attributes. Different aspects of ABE were studied, such as the multi-authority setting (MA-ABE), and policy hiding, meaning the access policy is unknown to unauthorized parties. However, no practical scheme so far provably provides both properties, which are often desirable in real-world applications: supporting decentralization while hiding the access policy. We present the first practical decentralized ABE scheme with a proof of being policy-hiding. Our construction is based on a decentralized inner-product predicate encryption scheme, introduced in this paper, which hides the encryption policy. It results in an ABE scheme supporting conjunctions, disjunctions and threshold policies, that protects the access policy from parties that are not authorized to decrypt the content. Further, we address the issue of receiver privacy. By using our scheme in combination with vector commitments, we hide the overall set of attributes possessed by the receiver from individual authorities, only revealing the attribute that the authority is controlling. Finally, we propose randomizing-polynomial encodings that immunize the scheme in the presence of corrupt authorities.