Information Security

With the introduction of kernel integrity checking mechanisms in modern operating systems, such as PatchGuard on Windows OS, malware developers can no longer easily install stealthy hooks in kernel code and well-known data structures. Instead, they must target other areas of the kernel, such as the heap, which stores a large number of function pointers that are potentially prone to malicious exploits. These areas of kernel memory are currently not monitored by kernel integrity checkers.

We present a novel approach to monitoring the integrity of Windows kernel pools, based entirely on virtual machine introspection, called HookLocator. Unlike prior efforts to maintain kernel integrity, our implementation runs entirely outside the monitored system, which makes it inherently more difficult to detect and subvert. Our system also scales easily to protect multiple virtualized targets. Unlike other kernel integrity checking mechanisms, HookLocator does not require the source code of the operating system, complex reverse engineering efforts, or the debugging map files. Our empirical analysis of kernel heap behavior shows that integrity monitoring needs to focus only on a small fraction of it to be effective; this allows our prototype to provide effective real-time monitoring of the protected system.

A visual cryptography scheme (VCS) encodes a secret image into several share images, such that stacking sufficient number of shares will reveal the secret while insufficient number of shares provide no information about the secret. The beauty of VCS is that the secret can be decoded by human eyes without needing any cryptography knowledge nor any computation. Variance is first introduced by Hou et al. in 2005 to evaluate the visual quality of size invariant VCS. Liu et al. in 2012 thoroughly verified this idea and significantly improved the visual quality of previous size invariant VCSs. In this paper, we first point out the security defect of Hou et al.’s multi-pixel encoding method (MPEM) that if the secret image has simple contours, each single share will reveal the content of that secret image. Then we use variance to explain the above security defect.

In this paper we consider the problem of secret sharing where shares are encrypted using a public-key encryption (PKE) scheme and ciphertexts are publicly available. While intuition tells us that the secret should be protected if the PKE is secure against chosen-ciphertext attacks (i.e., CCA-secure), formally proving this reveals some subtle and non-trivial challenges. We isolate the problems that this raises, and devise a new analysis technique called “plaintext randomization” that can successfully overcome these challenges, resulting in the desired proof. The encryption of different shares can use one key or multiple keys, with natural applications in both scenarios.

In the present paper, we propose private stable matching protocols to solve the stable marriage problem with the round complexity \(O(n^2)\), where n is the problem size. In the multiparty setting, the round complexity of our protocol is better than all of the existing practical protocols. We also implement our protocol on a standard personal computer, smartphones, and tablet computers for experimental performance evaluation. Our protocols are constructed by using additive homomorphic encryption only, and this construction yields improved round complexity and implementation-friendliness. To the best of our knowledge, our experiment is the first implementation report of a private stable matching protocol that has a feasible running time.

Attribute-based encryption (ABE) schemes provide a fine-grained access control mechanism over encrypted data, and are useful for cloud online-storage services, or Pay-TV systems and so on. To apply ABE for such services, key exposure protection mechanisms are necessary. Unfortunately, standard security notions of ABE offer no protection against key exposure. One solution to this problem is to give forward security to ABE schemes. In forward secure cryptographic schemes, even if a secret key is exposed, messages encrypted during all time periods prior to the key leak remain secret. In this paper we propose an efficient Forward Secure Ciphertext-Policy Attribute-Based Encryption (FS-CP-ABE) which is efficient and fully secure. To construct efficient FS-CP-ABE, we first introduce a new cryptographic primitive called Ciphertext-Policy Attribute-Based Encryption with Augmented Hierarchy (CP-ABE-AH). Intuitively, CP-ABE-AH is an encryption scheme with both hierarchical identity based encryption and CP-ABE properties. Then we show that FS-CP-ABE can be constructed from CP-ABE-AH generically. We give the security definition of FS-CP-ABE, and security proofs based on three complexity assumptions. The size of public parameter is \(O(\log T)\), and the secret key size is \(O(\log ^2 T)\) where T is the number of time slots.

Currently, chosen-ciphertext (CCA) security is considered as the de facto standard security notion for public key encryption (PKE), and a number of CCA-secure schemes have been proposed thus far. However, CCA-secure PKE schemes are generally less efficient than schemes with weaker security, e.g., chosen-plaintext security, due to their strong security. Surprisingly, Cramer et al. (Asiacrypt 2007) demonstrated that it is possible to construct a PKE scheme from the decisional Diffie-Hellman assumption that yields (i) bounded CCA (BCCA) security which is only slightly weaker than CCA security, and (ii) one group element of ciphertext overhead which is optimal.

In this paper, we propose two novel BCCA-secure PKE schemes with optimal ciphertext length that are based on computational assumptions rather than decisional assumptions and that yield shorter (or at least comparable) public key sizes. Our first scheme is based on the computational bilinear Diffie-Hellman assumption and yields \(O(\lambda q)\) group elements of public key length, and our second scheme is based on the factoring assumption and yields \(O(\lambda q^2)\) group elements of public key length, while in Cramer et al.’s scheme, a public key consists of \(O(\lambda q^2)\) group elements, where \(\lambda \) is the security parameter and q is the number of decryption queries. Moreover, our second scheme is the first PKE scheme which is BCCA-secure under the factoring assumption and yields optimal ciphertext overhead.

Smartphones have become the most popular mobile devices. Due to their simplicity, portability and functionality comparable to recent computers users tend to store more and more sensitive information on mobile devices rendering them an attractive target for malware writers. As a consequence, mobile malware population is doubled every single year. Many approaches to detect mobile malware infections directly on mobile devices have been proposed. Detecting and blocking voice and SMS messages related to mobile malware in a mobile operator’s network has, however, gained little attention so far. The 4GMOP proposed in this paper aims at closing this gap.

In this paper, we propose a realistic malware attack against the smart grid. The paper first briefs the architecture of the smart grid in general. And then we explain our proposed attack that is specifically tailored for the smart grid infrastructures. The attack considers the characteristics of recent real malware attacks such as deceptive hardware attack and multi-stage operation. We believe this analysis will benefit the design and implementation of secure smart grid infrastructures by demonstrating how a sophisticated malware attack can damage the smart grid.

The notion of controllability, informally the ability to force a system into a desired state in a finite time or number of steps, is most closely associated with control systems such as those used to maintain power networks and other critical infrastructures, but has wider relevance in distributed systems. It is clearly highly desirable to understand under which conditions attackers may be able to disrupt legitimate control, or to force overriding controllability themselves. Following recent results by Liu et al., there has been considerable interest also in graph-theoretical interpretation of Kalman controllability originally introduced by Lin, structural controllability. This permits the identification of sets of driver nodes with the desired state-forcing property, but determining such nodes is a W[2]-hard problem. To extract these nodes and represent the control relation, here we apply the Power Dominating Set problem and investigate the effects of targeted iterative multiple-vertex removal. We report the impact that different attack strategies with multiple edge and vertex removal will have, based on underlying non-complete graphs, with an emphasis on power-law random graphs with different degree sequences.

ARIA is a 128-bit SPN block cipher selected as a Korean standard. This paper processes meet-in-the-middle attacks on reduced-round ARIA. Some 4-round and 5-round significant distinguishing properties which involve much fewer bytes parameters are proposed. Based on these better distinguishers, attacks on 7-round ARIA-192/256 and 8-round ARIA-256 are mounted with much lower complexities than previous meet-in-the-middle attacks. Furthermore, we present 7-round attack on ARIA-128 and 9-round attack on ARIA-256, which are both the first results for ARIA in terms of the meet-in-the-middle attack.

Algebraic and fast algebraic attacks have posed serious threats to some deployed LFSR-based stream ciphers. Previous works on this topic focused on reducing the time complexity by lowering the degree of the equations, speeding up the substitution step by Fast Fourier Transform and analysis of Boolean functions exhibiting the optimal algebraic immunity. All of these works shared and overlooked a common base, i.e., establishing an adequate equation system first, which actually in some cases dominates the time or memory complexity if the direct methods are used, especially in fast algebraic attacks. In this paper, we present a complete analysis of the establishing equation procedure and show how the Frobenius form of the monomial state rewriting matrix can be applied to considerably reduce the complexity of this step.

In 2009, Heninger and Shacham presented an algorithm using the Hensel’s lemma for reconstructing the prime factors of the modulus \(N = r_1r_2\). This algorithm computes the prime factors of N in polynomial time, with high probability, assuming that a fraction greater than or equal to 59 % random bits of its primes \(r_1\) and \(r_2\) is given. In this paper, we present the analysis of Hensel’s lemma for a multiprime modulus \(N = \prod ^u_{i=1}r_i\) (for \(u\ge 2\)) and we generalise the Heninger and Shacham’s algorithm to determine the minimum fraction of random bits of its prime factors that is sufficient to factor N in polynomial time with high probability.

The 3GPP Task Force recently supplemented mobile LTE network security with an additional set of confidentiality and integrity algorithms, namely 128-EEA3 and 128-EIA3 built on top of ZUC, a new keystream generator. We contribute two techniques to improve the software performance of these algorithms. We show how delayed modular reduction increases the efficiency of the LFSR feedback function, yielding performance gains for ZUC and thus both 128-EEA3 and 128-EIA3. We also show how to leverage carryless multiplication to evaluate the universal hash function making up the core of 128-EIA3. Our software implementation results on Qualcomm’s Hexagon DSP architecture indicate significant performance gains when employing these techniques: up to roughly a 2.4-fold and a 4-fold throughput improvement for 128-EEA3 and 128-EIA3, respectively.

For some block ciphers such as AES, substitution box (S-box) based on multiplicative inversion is the most complex operation. Efficient constructions should be found for optimizing features like the area, the amount of memory, etc. Composite representations in finite fields are the prominent ways to represent the multiplicative inverse operation in a compact way. In this manuscript, different constructions based on composite fields are shown to represent the AES, Camellia and SMS4 S-boxes. Mainly, this manuscript describes representations in \(GF((2^4)^2)\). From these representations, an evaluation is performed to choose those feasible solutions that help to merge the AES, Camellia and SMS4 S-boxes into a single one. For instance, by using merged matrices and the same composite polynomial basis, it is possible to reduce from 172 XOR gates (independent matrices) to 146 XOR gates (merged matrices).

From contactless payments to remote car unlocking, many applications are vulnerable to relay attacks. Distance bounding protocols are the main practical countermeasure against these attacks. At FSE 2013, we presented SKI as the first family of provably secure distance bounding protocols. At LIGHTSEC 2013, we presented the best attacks against SKI. In this paper, we present the security proofs. More precisely, we explicate a general formalism for distance-bounding protocols. Then, we prove that SKI and its variants is provably secure, even under the real-life setting of noisy communications, against the main types of relay attacks: distance-fraud and generalised versions of mafia- and terrorist-fraud. For this, we reinforce the idea of using secret sharing, combined with the new notion of a leakage scheme. In view of resistance to mafia-frauds and terrorist-frauds, we present the notion of circular-keying for pseudorandom functions (PRFs); this notion models the employment of a PRF, with possible linear reuse of the key. We also use PRF masking to fix common mistakes in existing security proofs/claims.

Telephony systems are imperative for information exchange offering low cost services and reachability to millions of customers. They have not only benefited legitimate users but have also opened up a convenient communication medium for spammers. Voice spam is often encountered on telephony systems in various forms, such as by means of an automated telemarketing call asking to call a number to win a reward. A large percentage of voice spam is generated through automated system which introduces the classical challenge of distinguishing machines from humans on telephony systems. CAPTCHA is a conventional solution deployed on the web to address this problem. Audio-based CAPTCHAs have been proposed as a solution to curb voice spam. In this paper, we conducted a field study with 90 participants in order to answer two primary research questions: quantifying the amount of inconvenience telephony-based CAPTCHA may cause to users, and how various features of the CAPTCHA, such as duration and size, influence usability of telephony-based CAPTCHA. Our results suggest that currently proposed CAPTCHAs are far from usable, with very low solving accuracies, high solving times and poor overall user experience. We provide certain guidelines that may help improve existing CAPTCHAs for use in telephony systems.

Participation on Online Social Networks (OSNs) inherently requires information sharing and thus exposes individuals to privacy risks. Risk mitigation then has been encouraged through adoption of usable privacy controls. Apparently stronger privacy enhancing technologies (PETs) decrease both risk and perceptions of risk. As a result individuals feel safer and may respond by in fact accepting more risk. Such perverse results have been observed offline. Risk perception offline has been understood to be a function of characteristics of the risks involved rather than as a calculus grounded only in the probability of the risk and the magnitude of harm. In this work we use nine characteristics of risk from a classic and proven offline model of perceived risk to conduct a survey based evaluation of perceptions of privacy risks on Facebook. We find that these dimensions of risk provide a statistically significant explanation of perceived risk of information sharing on Facebook.

Attribute-based encryption (ABE) is well suited for fine-grained access control for data residing on a cloud server. However, existing approaches for user revocation are not satisfactory. In this work, we propose a new approach which works by splitting an authorized user’s decryption capability between the cloud and the user herself. User revocation is attained by simply nullifying the decryption ability at the cloud, requiring neither key update nor re-generation of cloud data. We propose a concrete scheme instantiating the approach, which features lightweight computation at the user side. This makes it possible for users to use resource-constrained devices such as mobile phones to access cloud data. We implement our scheme, and also empirically evaluate its performance.

HTML5-based mobile applications are becoming more and more popular because they can run on different platforms. Several newly introduced mobile OS natively support HTML5-based applications. For those that do not provide native support, such as Android, iOS, and Windows Phone, developers can develop HTML5-based applications using middlewares, such as PhoneGap. In these platforms, programs are loaded into a web component, called WebView, which can render HTML5 pages and execute JavaScript code. In order for the program to access the system resources, which are isolated from the content inside WebView due to its sandbox, bridges need to be built between JavaScript and the native code (e.g. Java code in Android). Unfortunately, such bridges break the existing protection that was originally built into WebView. In this paper, we study the potential risks of HTML5-based applications, and investigate how the existing mobile systems’ access control supports these applications. We focus on Android and the PhoneGap middleware. However, our ideas can be applied to other platforms. Our studies indicate that Android does not provide an adequate access control for this kind of applications. We propose a fine-grained access control mechanism for the bridge in Android system. We have implemented our scheme in Android and have evaluated its effectiveness and performance.

The widespread use of JavaScript (JS) as the dominant web programming language opens the door to attacks such as Cross Site Scripting that steal sensitive information from users. Information flow tracking successfully addresses current browser security shortcomings, but current implementations incur a significant runtime overhead cost that prevents adoption.

We present a novel approach to information flow security that distributes the tracking workload across all page visitors by probabilistically switching between two JavaScript execution modes. Our framework reports attempts to steal information from a user’s browser to a third party that maintains a blacklist of malicious URLs. Participating users can then benefit from receiving warnings about blacklisted URLs, similar to anti-phishing filters.

Our measurements indicate that our approach is both efficient and effective. First, our technique is efficient because it reduces performance impact by an order of magnitude. Second, our system is effective, i.e., it detects 99.45 % of all information flow violations on the Alexa Top 500 pages using a conservative 5 % sampling rate. Most sites need fewer samples in practice; and will therefore incur even less overhead.

In this paper, we investigate the current state of practice about mixed-content websites, websites that are accessed using the HTTPS protocol, yet include some additional resources using HTTP. Through a large-scale experiment, we show that about half of the Internet’s most popular websites are currently using this practice and are thus vulnerable to a wide range of attacks, including the stealing of cookies and the injection of malicious JavaScript in the context of the vulnerable websites. Additionally, we investigate the default behavior of browsers on mobile devices and show that most of them, by default, allow the rendering of mixed content, which demonstrates that hundreds of thousands of mobile users are currently vulnerable to MITM attacks.

Ordered multisignatures are digital signatures which allow multiple signers to guarantee the signing order as well as the validity of a message, and thus are useful for constructing secure routing protocols. Although one of approaches to constructing the ordered multisignatures is to utilize aggregate signatures, there is no known scheme which is provably secure without using aggregate signatures under a reasonable complexity assumption in the standard model. In this paper we propose a provably secure ordered multisignature scheme under the CDH assumption in the standard model from scratch. Our proposed scheme has a positive property that the data size of signatures and the number of computations of bilinear maps are fixed with respect to the number of signers and the message length.

Random number generators have direct applications in information security, online gaming, gambling, and computer science in general. True random number generators need an entropy source which is a physical source with inherent uncertainty, to ensure unpredictability of the output. In this paper we propose a new indirect approach to collecting entropy using human errors in the game play of a user against a computer. We argue that these errors are due to a large set of factors and provide a good source of randomness. To show the viability of this proposal, we design and implement a game, conduct a user study in which we collect user input in the game, and extract randomness from it. We measure the rate and the quality of the resulting randomness that clearly show effectiveness of the approach. Our work opens a new direction for construction of entropy sources that can be incorporated into a large class of video games.

In order to analyze a variety of cryptosystems, Boneh, Boyen and Goh introduced a general framework, the Uber assumption. In this article, we explore some particular instances of this Uber assumption; namely the n-\(\mathsf {CDH}\)-assumption, the \(n^{th}\)-\(\mathsf {CDH}\)-assumption and the \(Q\)-\(\mathsf {CDH}\)-assumption. We analyse their relationships from a security point of view. Our analysis does not rely on any other property of the considered group and, in particular, does not use the generic group model.