Information Security

Advanced cryptographic protocols such as anonymous credentials, voting schemes, and e-cash are typically constructed by suitably combining signature, commitment, and encryption schemes with zero-knowledge proofs. Indeed, a large body of protocols have been constructed in that manner from Camenisch-Lysyanskaya signatures and generalized Schnorr proofs. In this paper, we build a similar framework for lattice-based schemes by presenting a signature and commitment scheme that are compatible with Lyubashevsky’s Fiat-Shamir proofs with abort, currently the most efficient zero-knowledge proofs for lattices. The latter proofs provide a weaker, relaxed form of soundness, i.e., the witnesses that the knowledge extractor can obtain are guaranteed to lie only in a domain that is larger than the one from which the inputs of honest provers need to come. To cope with this soundness problem, we define corresponding notions of relaxed signature and commitment schemes. We demonstrate the flexibility and efficiency of our new primitives by constructing a new lattice-based anonymous attribute token scheme and providing concrete parameters to securely instantiate this scheme.

In his invited talk, joint between CHES 2016 and CRYPTO 2016 on the Future of Embedded Security, Paul Kocher suggested to move the security into chips because hardware is the lowest level and thus security can not be compromized by a lower layer. In this paper, we propose a generic PUF-driven secure code execution architecture that employs instruction-level code encryption. Our design foresees a tight integration of a Physically Unclonable Function (PUF) and the decryption of encrypted program code directly inside the processor’s instruction pipeline to avert revealing keys or decrypted code in externally accessible registers or memory. The architecture prevents code-injection by executing only code encrypted for individual target CPUs, has an adaptable impact on performance, and requires only minor changes to the software development process. Our PUF-based code encryption defends also from reverse engineering attempts and enforces IP protection. A proof-of-concept implementation demonstrates the feasibility of our proposed architecture.

Dynamic analysis of Android malware suffers from techniques that identify the analysis environment and prevent the malicious behavior from being observed. While there are many analysis solutions that can thwart evasive malware on Windows, the application of similar techniques for Android has not been studied in-depth. In this paper, we present Lumus, a novel technique to uncover evasive malware on Android. Lumus compares the execution traces of malware on bare metal and emulated environments. We used Lumus to analyze 1,470 Android malware samples and were able to uncover 192 evasive samples. Comparing our approach with other solutions yields better results in terms of accuracy and false positives. We discuss which information are typically used by evasive malware for detecting emulated environments, and conclude on how analysis sandboxes can be strengthened in the future.

Software is usually built on top of shared libraries. Vulnerabilities that lie in those dependencies may have huge impact on multiple software. ICU (International Components for Unicode) is one of the most widely used common components in modern software, providing Unicode and Globalization support. ICU is used in a wide range of software from over 70 companies and organizations, including very popular software such as Chrome, Android, macOS, iOS, Windows 10, Edge, Firefox.

In this paper, we proposed a fuzzing method to discover vulnerabilities in ICU library that are reachable from upper layer application software. We also built a prototype named ICUFuzzer to uncover triggerable bugs in browsers’ JavaScript Engine, with which we have detected three zero-day vulnerabilities affecting popular browsers like Chrome, Safari and Firefox. According to our further analysis, one of the bugs can be exploited to leak sensitive memory informations to bypass mitigations like ASLR and PIE.

Communication security has become an indispensable demand of smartphone users. End-to-end encryption is the key factor for providing communication security, which mainly relies on public key cryptography. The main and unresolved issue for public key cryptography is to correctly match a public key with its owner. Failing to do so could lead to man-in-the-middle attacks. Different public key verification methods have been proposed in the literature. The methods which are based on verification by the users themselves are preferable with respect to cost and deployability than the methods such as digital certificates that involve the use of trusted third parties. One of these methods, fingerprinting was recently replaced by a method called safety number in the open source messaging application, SIGNAL. The developers of SIGNAL claimed this change would bring usability and security advantages however no formal user study was conducted supporting this claim. In this study, we compare the usability and security aspects of these two methods with a user study on 42 participants. The results indicate with significance that the safety number method leads to more successful results in less time for public key verification as compared to the fingerprint method.

Being the first generic algorithm for finding the best differential and linear characteristics, Matsui’s branch and bound search algorithm (EUROCRYPT 1994) and its variants have played an important role in the security analysis of symmetric-key primitives. However, Matsui’s algorithm is difficult to implement, optimize, and be applied to different ciphers with reusable code. Another approach getting popular in recent years is to encode the search problem as a Mixed Integer Linear Programming (MILP) model which can be solved by open-source or commercially available optimizers. In this work, we show how to tweak the objective functions of the MILP models for finding differential characteristics such that a set of constraints derived from the bounding condition of Matsui’s algorithm can be incorporated into the models. We apply the new modeling strategy to PRESENT (S-box based SPN design), SIMON (Feistel structure), and SPECK (ARX construction). For PRESENT, the resolution time is significantly reduced. For example, the time to prove that the exact lower bound of the probabilities of the differential characteristics for 7-round PRESENT is reduced from 48638 s to 656 s. For SIMON, obvious acceleration is also observed, and for the ARX cipher SPECK, the new model is unable to speed up the resolution. In the future, it is interesting to investigate how to integrate other search heuristics proposed in the literature of symmetric-key cryptanalysis into the MILP models, and how to accelerate the resolution of MILP models for finding characteristics of ARX ciphers.

In this paper, we revisit the relationship between the probability of differential trails and the input difference of each round for SIMON-like block ciphers. The key observation is that not only the Hamming weight but also the positions of active bits of the input difference have effect on the probability. Based on this, our contributions are mainly twofold. Firstly, we rebuild the MILP model for SIMON-like block ciphers without quadratic constraints. Accordingly, we give the accurate objective function and reduce its degree to one by adding auxiliary variants to make the model easy to solve. Secondly, we search for optimal differential trails for SIMON and SIMECK based on this model. To the best of our knowledge, this is the first time that related-key differential trails have been obtained. Besides, we not only recover the single-key results in [11], but also obtain impossible differentials through this method.

Previous research on linear cryptanalysis with Speck has proved that good linear trails and a meaningful distinguisher for variants of Speck can be found. In this paper we use two different linear approximations of modular addition to search for even better linear trails. Also, we have added a heuristic to search for large bias approximations for the state conversion approach. We will explain how the automatic search works and discuss its performance. Finally we illustrate that linear approximations with large bias exist in variants of Speck.

In this paper, we describe a new cube searching method called conditional searching. The main idea of this new searching method is to reduce the searching space and contains two main steps: finding complementary variables and searching conditional cubes. At the first step, we introduce a concept of complementary variables corresponding to cube variables to ensure that cube variables are not multiplied with each other in the first few propagations. According to the taps in the feedback functions, two main strategies are given to find complementary variables. At the second step, we first give a simple algorithm to estimate the maximal size of conditional cubes that don’t contain any complementary variable. Then another algorithm is given to search conditional cubes. We can confirm the maximum numbers of initialization rounds of some NFSR-based cryptosystems such that the generated keystream bit does not achieve the maximum algebraic degree with our cube searching method and the algebraic degree estimated method numeric mapping. We apply our method to Trivium to verify the validity and our searching space is about \(2^{12.5}\) much smaller than that of existing results. We also introduce two Trivium-variants named Par-Trivium and Loc-Trivium, and apply the method to them. We can get an upper bound of the maximum initialization rounds when we change the parameters or the key and IV loading locations in Trivium. The applications provide some insights into the taps used in the feedback functions of such stream ciphers. We believe that our method is useful in both cryptanalysis and design of NFSR-based cryptosystems.

Searchable symmetric encryption (SSE) schemes are commonly proposed to enable search in a protected unstructured documents such as email archives or any set of sensitive text files. However, some SSE schemes have been recently proposed in order to protect relational databases. Most of the previous attacks on SSE schemes have only targeted its common use case, protecting unstructured data. In this work, we propose a new inference attack on relational databases protected via SSE schemes. Our inference attack enables a passive adversary with only basic knowledge about the meta-data information of the target relational database to recover the attribute names of some observed queries. This violates query privacy since the attribute name of a query is secret.

Randomized response is attractive for privacy preserving data collection because the provided privacy can be quantified by means such as differential privacy. However, recovering and analyzing statistics involving multiple dependent randomized binary attributes can be difficult, posing a significant barrier to use. In this work, we address this problem by identifying and analyzing a family of response randomizers that change each binary attribute independently with the same probability. Modes of Google’s Rappor randomizer as well as applications of two well-known classical randomized response methods, Warner’s original method and Simmons’ unrelated question method, belong to this family. We show that randomizers in this family transform multinomial distribution parameters by an iterated Kronecker product of an invertible and bisymmetric \(2\times 2\) matrix. This allows us to present a simple and efficient algorithm for obtaining unbiased maximum likelihood parameter estimates for \(k\)-way marginals from randomized responses and provide theoretical bounds on the statistical efficiency achieved. We also describe the efficiency – differential privacy tradeoff. Importantly, both randomization of responses and the estimation algorithm are simple to implement, an aspect critical to technologies for privacy protection and security.

Most cloud providers afford their tenants with cryptographic services that greatly escalate the protection of users’ private keys. Isolated from the guest operating systems (OSes), the keys are kept confidential even if the OS kernel is compromised. However, existing cryptographic services are ineffective in the access control of these critical services. In particular, they enforce controls for the key accesses mainly based on non-cryptographic authentication/authorization information (i.e., the identity and the password). Some platforms leverage other information such as the resource identification of the Virtual machine (VM) (e.g., IP address). Therefore, once the password is leaked, the attacker could invoke the cryptographic service in the victim VM. Moreover, sophisticated attackers can exploit vulnerabilities in the guest OS kernel and stealthily invoke cryptographic services. In this paper, we propose a new scheme named En-ACCI to improve the security of cryptographic service invocation in the cloud and achieve better access controls as well as auditing by leveraging the rich VM context provided by virtual machine introspection (VMI). To the best of our knowledge, we are the first in the literature to discuss these security issues involved in the invocation of cryptographic services in the cloud. We address the challenges by using an access control mechanism atop a set of optimization to VMI. We have implemented a prototype of En-ACCI, and our evaluation demonstrates that En-ACCI effectively addresses the authorization and audit issues in the cloud-based cryptographic service and the introduced performance overhead is modest.

We propose a multi-authority fast data cloud-outsourcing (MFDCO) scheme especially suitable for mobile devices. It is a multi-authority online/offline encapsulation scheme based on efficient large-universe ciphertext-policy attribute-based encryption, and supports fine-grained access control, dynamic revocation, and public validity test. Any party can become an authority to participate in the distribution of attribute credential and credential updating. Apart from the initial generation of public global parameters, there is no requirement for any coordination among distinct authorities. In addition, the MFDCO scheme allows data owners to enforce fine-grained access control through lightweight online operations, which is extremely friendly for mobile users. It is equipped with an efficient revocation mechanism to realize dynamic access credential revocations. It also allows public encapsulation validity test, thus preventing attackers from stuffing users’ data storage accounts with invalid encapsulations, as well as achieving security against active attacks. Comprehensive analyses illustrate that the MFDCO scheme is suitable for commercial sensitive data cloud-outsourcing, especially in public cloud environment.

Security protocols using public-key cryptography often requires large number of costly modular exponentiations (MEs). With the proliferation of resource-constrained (mobile) devices and advancements in cloud computing, delegation of such expensive computations to powerful server providers has gained lots of attention. In this paper, we address the problem of verifiably secure delegation of MEs using two servers, where at most one of which is assumed to be malicious (the OMTUP-model). We first show verifiability issues of two recent schemes: We show that a scheme from IndoCrypt 2016 does not offer full verifiability, and that a scheme for n simultaneous MEs from AsiaCCS 2016 is verifiable only with a probability 0.5909 instead of the author’s claim with a probability 0.9955 for \(n=10\). Then, we propose the first non-interactive fully verifiable secure delegation scheme by hiding the modulus via Chinese Remainder Theorem (CRT). Our scheme improves also the computational efficiency of the previous schemes considerably. Hence, we provide a lightweight delegation enabling weak clients to securely and verifiably delegate MEs without any expensive local computation (neither online nor offline). The proposed scheme is highly useful for devices having (a) only ultra-lightweight memory, and (b) limited computational power (e.g. sensor nodes, RFID tags).

We design a group key exchange protocol with forward secrecy where most of the participants remain offline until they wish to compute the key. This is well suited to a cloud storage environment where users are often offline, but have online access to the server which can assist in key exchange. We define and instantiate a new primitive, a blinded KEM, which we show can be used in a natural way as part of our generic protocol construction. Our new protocol has a security proof based on a well-known model for group key exchange. Our protocol is efficient, requiring Diffie–Hellman with a handful of standard public key operations per user in our concrete instantiation.

In cloud computing, delegated computing raises the security issue of guaranteeing data authenticity during a remote computation. Existing solutions do not simultaneously provide fast correctness verification, strong security properties, and information-theoretic confidentiality. We introduce a novel approach, in the form of function-dependent commitments, that combines these strengths. We also provide an instantiation of function-dependent commitments for linear functions that is unconditionally, i.e. information-theoretically, hiding and relies on standard hardness assumptions. This powerful construction can for instance be used to build verifiable computing schemes providing information-theoretic confidentiality. As an example, we introduce a verifiable multi-party computation scheme for shared data providing public verifiability and unconditional privacy towards the servers and parties verifying the correctness of the result. Our scheme can be used to perform verifiable computations on secret shares while requiring only a single party to compute the audit data for verification. Furthermore, our verification procedure is asymptotically even more efficient than performing operations locally on the shared data. Thus, our solution improves the state of the art for authenticated computing, verifiable computing and multi-party computation.

In this paper, we focus on constructing IBE from hardness assumptions without pairings. Especially, we propose two IBE schemes that are provably secure under new number theoretic assumptions over the group \(\mathbb {Z}_{N^2}^*\), in the Random Oracle (RO) model. We essentially take advantage of the underlying algebraic structure to overcome the difficulties in devising an IBE scheme.

More precisely, our contributions are two-fold and can be summarised as follows: (i) We give two concrete pairing-free constructions of IBE based on a variant of DDH assumption and Paillier’s \(\mathsf {DCR}\) assumption respectively over the group \(\mathbb {Z}_{N^2}^*\). These schemes are quite efficient and easily to be proven \(\mathsf {IND}\text {-}\mathsf {ID}\text {-}\mathsf {CPA}\) in the random oracle model. (ii) We also provide a generic construction of selectively secure IBE from DDH group with a \(\mathsf {DL}\)-solvable subgroup in the standard model by employing puncturable PRFs and indistinguishability obfuscation.

In this paper, we propose a new notion of multi-key homomorphic proxy re-encryption (MH-PRE) in which inputs of homomorphic evaluation are encrypted by different public keys and the evaluated ciphertext is decrypted by a single secret key. We obtain it by adding the re-encryption property of proxy re-encryption to multi-key homomorphic encryption (MHE). MHE, firstly proposed by López-Alt, Tromer and Vaikuntanathan (STOC 2012), can perform homomorphic evaluations on ciphertexts from different keys, but decrypting the output ciphertext of the homomorphic evaluation requires all the secret keys associated to the input ciphertexts. In order to decrypt the output ciphertext with a single secret key, we introduce the notion of the re-encryption to MHE. In particular, we construct an MH-PRE scheme by applying the key switching technique to the MHE scheme of Peikert and Shiehian (TCC 2016).

Verifiable decryption allows one to prove the correct decryption of encrypted data. When the encrypted data is derived from homomorphic evaluations in the context of fully homomorphic encryption (FHE), verifiable decryption will be very useful in cloud computing or cryptographic protocols, e.g., secure medical computation, cryptographically verifiable election, etc. In this paper, we consider the problem of proving the correct decryption of an FHE ciphertext. Namely, we are interested in zero-knowledge proofs of knowledge of triples \((m, \mathbf {s}, \mathbf {c})\) such that the message m is the correct decryption of a ciphertext \(\mathbf {c}\) for a secret key \(\mathbf {s}\). While analogous statements admit efficient zero-knowledge proof protocols in the discrete logarithm setting, they have never been addressed in FHE so far. We provide such verifiable decryption for Brakerski-Gentry-Vaikuntanathan (BGV) scheme, since this scheme was recognized as one of the most efficient leveled FHE schemes. Our solution is nearly “one shot”, in the sense that a single instance of the proof already has negligible soundness error, yielding compact proofs even for individual ciphertexts. Furthermore, to illustrate the applicability of verifiable decryption, we also give two example instantiations.

Cryptographic techniques are employed to ensure the security of voting systems in order to increase its wide adoption. However, in such electronic voting systems, the public bulletin board that is hosted by the third party for publishing and auditing the voting results should be trusted by all participants. Recently a number of blockchain-based solutions have been proposed to address this issue. However, these systems are impractical to use due to the limitations on the voter and candidate numbers supported, and their security framework, which highly depends on the underlying blockchain protocol and suffers from potential attacks (e.g., force-abstention attacks). To deal with two aforementioned issues, we propose a practical platform-independent secure and verifiable voting system that can be deployed on any blockchain that supports an execution of a smart contract. Verifiability is inherently provided by the underlying blockchain platform, whereas cryptographic techniques like Paillier encryption, proof-of-knowledge, and linkable ring signature are employed to provide a framework for system security and user-privacy that are independent from the security and privacy features of the blockchain platform. We analyse the correctness and coercion-resistance of our proposed voting system. We employ Hyperledger Fabric to deploy our voting system and analyse the performance of our deployed scheme numerically.

The advent of crowdsourcing has brought with it multiple privacy challenges. For example, essential monitoring activities, while necessary and unavoidable, also potentially compromise contributor privacy. We conducted an extensive literature review of the research related to the privacy aspects of crowdsourcing. Our investigation revealed interesting gender differences and also differences in terms of individual perceptions. We conclude by suggesting a number of future research directions.

In many privacy-preserving protocols, protection of the user’s identity, called anonymity, is a desirable feature. Another issue is that, if a signed document is leaked then anyone can be convinced of the authenticated data, which is strictly not allowed for sensitive data, instead the authentication only by a designated receiver is recommended. There are many scenarios in real life, for example e-auction, where both the functionalities– anonymity and designated verification are required simultaneously. For such an objective, in this paper we introduce a compact scheme of identity-based strong designated verifier group signature (ID-SDVGS) by combining the good features of strong designated verifier signature and group signature in ID-based setting. This scheme provides anonymity to the signer of a designated verifier signature with the feature of the revocation of signer’s identity in case of misuse or dispute. Moreover, our scheme fulfils all the security properties of the individual components. We have obtained an ID-based instantiation of the generic group signature given by Bellare et al. in Eurocrypt 2003, and have proposed our scheme on that framework. To the best of our knowledge, this is the first construction of ID-SDVGS.

A signature scheme is said to be weakly unforgeable, if it is hard to forge a signature on a message not signed before. A signature scheme is said to be strongly unforgeable, if it is hard to forge a signature on any message. In some applications, the weak unforgeability is not enough and the strong unforgeability is required, e.g., the Canetti, Halevi and Katz transformation.

Leakage-resilience is a property which guarantees that even if secret information such as the secret-key is partially leaked, the security is maintained. Some security models with leakage-resilience have been proposed. The auxiliary (input) leakage model, or hard-to-invert leakage model, proposed by Dodis et al. in STOC’09 is especially meaningful one, since the leakage caused by a function which information-theoretically reveals the secret-key, e.g., one-way permutation, is considered.

In this work, we propose a generic construction of a signature scheme strongly unforgeable and resilient to polynomially hard-to-invert leakage which can be instantiated under standard assumptions such as the decisional linear assumption. We emphasize that our signature scheme is not only the first one resilient to polynomially hard-to-invert leakage under standard assumptions, but also the first one which is strongly unforgeable and has hard-to-invert leakage-resilience.

Group signatures are signatures providing signer anonymity where signers can produce signatures on behalf of the group that they belong to. Although such anonymity is quite attractive considering privacy issues, it is not trivial to check whether a signer has been revoked or not. Thus, how to revoke the rights of signers is one of the major topics in the research on group signatures. In particular, scalability, where the signing and verification costs and the signature size are constant in terms of the number of signers N, and other costs regarding signers are at most logarithmic in N, is quite important. In this paper, we propose a revocable group signature scheme which is currently more efficient compared to previous all scalable schemes. Moreover, our revocable group signature scheme is secure under simple assumptions (in the random oracle model), whereas all scalable schemes are secure under q-type assumptions. Finally, we implemented our scheme by employing the Barreto-Lynn-Scott curves over a 455-bit prime field (BLS455), and the Barreto-Naehrig curves over a 382-bit prime field (BN382), respectively, by using the RELIC library. We showed that the running times of our signing algorithm were approximately 21 ms (BLS455) and 17 ms (BN382), and those of our verification algorithm were approximately 31 ms (BLS455) and 24 ms (BN382), respectively.

In the last decade, the use of fast flux technique has become established as a common practice to organise botnets in Fast Flux Service Networks (FFSNs), which are platforms able to sustain illegal online services with very high availability. In this paper, we report on an effective fast flux detection algorithm based on the passive analysis of the Domain Name System (DNS) traffic of a corporate network. The proposed method is based on the near-real-time identification of different metrics that measure a wide range of fast flux key features; the metrics are combined via a simple but effective mathematical and data mining approach. The proposed solution has been evaluated in a one-month experiment over an enterprise network, with the injection of pcaps associated with different malware campaigns, that leverage FFSNs and cover a wide variety of attack scenarios. An in-depth analysis of a list of fast flux domains confirmed the reliability of the metrics used in the proposed algorithm and allowed for the identification of many IPs that turned out to be part of two notorious FFSNs, namely Dark Cloud and SandiFlux, to the description of which we therefore contribute. All the fast flux domains were detected with a very low false positive rate; a comparison of performance indicators with previous works show a remarkable improvement.

Browser fingerprinting is a relatively new method of uniquely identifying browsers that can be used to track web users. In some ways it is more privacy-threatening than tracking via cookies, as users have no direct control over it. A number of authors have considered the wide variety of techniques that can be used to fingerprint browsers; however, relatively little information is available on how widespread browser fingerprinting is, and what information is collected to create these fingerprints in the real world. To help address this gap, we crawled the 10,000 most popular websites; this gave insights into the number of websites that are using the technique, which websites are collecting fingerprinting information, and exactly what information is being retrieved. We found that approximately 69% of websites are, potentially, involved in first-party or third-party browser fingerprinting. We further found that third-party browser fingerprinting, which is potentially more privacy-damaging, appears to be predominant in practice. We also describe FingerprintAlert, a freely available browser add-on we developed that detects and, optionally, blocks fingerprinting attempts by visited websites.

Continuous risk monitoring is considered in the context of cybersecurity management for the Industrial Internet-of-Thing. Cyber-risk management best practice is for security controls to be deployed and configured in order to bring down risk exposure to an acceptable level. However, threats and known vulnerabilities are subject to change, and estimates of risk are subject to many uncertainties, so it is important to review risk assessments and update controls when required. Risks are typically reviewed periodically (e.g. once per month), but the accelerating pace of change means that this approach is not sustainable, and there is a requirement for continuous monitoring of cybersecurity risks. The method described in this paper aims to alert security staff of significant changes or trends in estimated risk exposure to facilitate rational and timely decisions. Additionally, it helps predict the success and impact of a nascent security breach allowing better prioritisation of threats and selection of appropriate responses. The method is illustrated using a scenario based on environmental control in a data centre.