Information and Communications Security

Algebraic side-channel attacks are a type of side-channel analysis which can recover the secret information with a small number of samples (e.g., power traces). However, this type of side-channel analysis is sensitive to measurement errors which may make the attacks fail. In this paper, we propose a new method of algebraic side-channel attacks which considers noisy leakages as integers restricted to intervals and finds out the secret information with the help of a constraint programming compiler named BEE. To demonstrate the efficiency of this new method in algebraic side-channel attacks, we analyze some popular implementations of block ciphers—PRESENT, AES, and SIMON under the Hamming weight or Hamming distance leakage model. For AES, our method requires the least leakages compared with existing works under the same error model. For both PRESENT and SIMON, we provide the first analytical results of them under algebraic side-channel attacks in the presence of errors. To further demonstrate the wide applicability of this new method, we also extend it to cold boot attacks. In the cold boot attacks against AES, our method increases the success rate by over \(25\,\%\) than previous works.

Database outsourcing reduces the cost of data management; however, the confidentiality of the outsourced data is a main challenge. Existing solutions [9, 13, 16, 17] either adopt multiple encryption schemes for data confidentiality that only support limited operations, or focus on providing efficient retrieval with problematic update support. In this paper, we propose a secure database outsourcing scheme (SEDB) based on Shamir’s threshold secret sharing for practical confidentiality against honest-but-curious database servers. SEDB supports a set of commonly used operations, such as addition, subtraction, and comparison, and is among the first to support multiplication, division, and modulus. We implement a prototype of SEDB, and the experiment results demonstrate a reasonable processing overhead.

In this paper, we investigate how to implement Direct Anonymous Attestation (DAA) on mobile devices, whose processing and storage capabilities are limited. We propose a generic framework providing a secure and efficient DAA functionality based on ARM TrustZone. Our framework is flexible enough to support multiple DAA schemes, and is efficient by leveraging the powerful ARM processor in secure mode to perform computations originally delegated to the Trusted Platform Module (TPM). Besides, our framework uses an SRAM PUF commonly available in the On-Chip Memory (OCM) of mobile devices for secure storage of user signing keys, which achieves a low-cost design. We present a prototype system that supports four DAA schemes on real TrustZone hardware, and give evaluations on its code size and performance together with comparisons of the four schemes with different curve parameters. The evaluation results indicate that our solution is feasible, efficient, and well-suited for mobile devices.

In recent years, memory disclosure attacks, such as cold boot attack and DMA attack, have posed huge threats to cryptographic applications in real world. In this paper, we present a CPU-bounded memory disclosure attacks resistant yet efficient software implementation of elliptic curves cryptography on general purpose processors. Our implementation performs scalar multiplication using CPU registers only in kernel level atomatically to prevent the secret key and intermediate data from leaking into memory. Debug registers are used to hold the private key, and kernel is patched to restrict access to debug registers. We take full advantage of the AVX and CLMUL instruction sets to speed up the implementation. When evaluating the proposed implementation on an Intel i7-2600 processor (at a frequency of 3.4 GHz), a full scalar multiplication over binary fields for key length of 163 bits only requires 129 \(\mu s\), which outperforms the unprotected implementation in the well known OpenSSL library by a factor of 78.0 %. Furthermore, our work is also flexible for typical Linux applications. To the best of our knowledge, this is the first practical ECC implementation which is resistant against memory disclosure attacks so far.

Virtual economy develops rapidly and accounts for quite a large proportion in the entire economy. Markets of virtual goods, such as games, apps and cloud services, are quite active and contribute a lot to the revenue of platforms and providers. The existing virtual economy systems mainly rely on the trustworthiness of the platforms who maintain the accounts of all participants, which is short of transparency. Another concern is how to maintain the market order when conspiracy between participants happens. In this paper, we extend the Verito scheme (NDSS 2013) and introduce a new participant Payment to obtain our 4P_VES scheme, in which collusion between two parties can be detected while satisfying required properties of transparency and accountability at the same time. We also analyze the properties and prove the security of our scheme. Finally, we evaluate the additional cost compared with Verito and find that our scheme is a cost affordable and practical one which enhances the system’s independency and security.

In distance-bounding protocols a prover wants to prove that it is located within a distance bound \(\mathbb {D}\) from a verifier. Distance-bounding (\(\mathtt {DB}\)) protocols have numerous applications including authentication and proximity checking. The privacy problem in \(\mathtt {DB}\) protocols was limited to privacy against MiM adversaries. Gambs et al. [11] extended this limitation and proposed a protocol that provides strong privacy when the verifier is malicious, or honest-but-curious registration authority. The protocol however does not provide resistance against terrorist-fraud.

In this paper we consider private \(\mathtt {DB}\) protocols that provide the strongest level of security against all known \(\mathtt {DB}\) attacks, in particular terrorist-fraud, and provide anonymity of the prover and unlinkability of its sessions against malicious verifiers and assuming an honest-but-curious registration authority. We define private distance-bounding as a special ZKPoK in which a prover presents a commitment on its long-term private-key, and later proves in zero-knowledge that; (i) she knows the committed value, (ii) she knows a signature of the authority on the committed value (registration proof), and (iii) she is located within a pre-defined distance to the verifier. The prover stays anonymous and its sessions will be unlinkable. We propose a protocol \(\mathtt {PDB}\) with these properties that resists against all known attacks including terrorist-fraud. \(\mathtt {PDB}\) is based on Bussard-Bagga [5] (\(\mathtt {DBPK}\)-\(\mathtt {Log}\)). \(\mathtt {PDB}\) also fixes the vulnerability of the protocol pointed out by Bay et al. [2] resulting in a secure public-key \(\mathtt {DB}\) protocol, hence answering the open question of constructing a secure public-key \(\mathtt {DB}\) protocol.

Distance (upper)-bounding (DUB) allows a verifier to know whether a proving party is located within a certain distance bound. DUB protocols have many applications in secure authentication and location based services. We consider the dual problem of distance lower bounding (DLB), where the prover proves it is outside a distance bound to the verifier. We motivate this problem through a number of application scenarios, and model security against distance fraud (DF), Man-in-the-Middle (MiM), and collusion fraud (CF) attacks. We prove impossibility of security against these attacks without making physical assumptions. We propose approaches to the construction of secure protocols under reasonable assumptions, and give detailed design of our DLB protocol and prove its security using the above model. This is the first treatment of the DLB problem in the untrusted prover setting, with a number of applications and raising new research questions. We discuss our results and propose directions for future research.

Oblivious transfer is one of the basic building blocks of cryptography. Due to its importance as a building block in the construction of secure multiparty computation protocols, the efficiency and security are two big issues in its design. In this paper, we present an efficient, universal composable (UC) secure adaptive oblivious transfer without q-type assumptions. The proposed protocol is UC secure under Decision Linear (DLIN), Decision Bilinear Diffie-Hellman (DBDH) and Square Decision Bilinear Diffie-Hellman (SqDBDH) assumptions in the presence of malicious adversary in static corruption model. The proposed protocol exhibits low computation and communication overheads as compared to the existing similar schemes.

SSL/TLS protocol is designed to protect the end-to-end communication by cryptographic means. However, the widely applied SSL/TLS protocol is facing many inadequacies on current mobile platform. Applications may suffer from MITM (Man-In-The-Middle) attacks when the certificate is not appropriately validated or local truststore is contaminated. In this paper, we present a hybrid certificate validation approach combining basic certificate validation against a predefined norm truststore with ways by virtue of aid from online social network friends. We conduct an analysis of official and third-party ROMs. The results show that some third-party ROMs add their own certificates in the truststore, while some do not remove compromised CA certificates from the truststore, which makes defining a norm truststore necessary. And the intuition to leverage social network friends to validate certificate is out of the distributed and “always online” feature of mobile social network. We implemented a prototype on Android, named TAGDROID. A thorough set of experiments assesses the validity of our approach in protecting SSL communication of mobile devices without introducing significant overhead.

This paper introduces a new parameter called 1-st minimum algebraic immunity \(AI_{min}(f)\), along with some theoretical properties of \(AI_{min}(f)\). Based on our results, we propose a guess-then-algebraic attack on LFSR-based stream ciphers with nonlinear filter Boolean function f. Our method takes some particular guessing strategy by taking advantage of the properties of \(AI_{min}(f)\), and makes full use of each guessed bit to generate as many equations of degree \(AI_{min}(f)\) as possible. The cost of time and data is less than that of the traditional algebraic attack under some condition. Our attack suggests that \(AI_{min}(f)\) should not be too small, which is a new design criterion for the filter Boolean function f. We apply our method to a 80-stage keystream generator with a MAI Boolean function f as its filter, while \(AI_{min}(f)\) is very small, which disobeys our criterion. The time and data complexities of the traditional algebraic attack are \(O(2^{73.56})\) and \(O(2^{24.52})\) respectively, with a memory cost of \(O(2^{49})\). The time and data complexity of our method are \(O(2^{56.86})\) and \(O(2^{5.36})\) respectively, and the memory cost is \(O(2^{10.72})\).

Although private lookup is less general than oblivious RAM (ORAM), it allows us to give new and/or more efficient SMC protocols for a number of important computational tasks. In this paper, we present protocols for executing deterministic finite automata (DFA), and for finding shortest distances in sparse graphs.

All our protocols are given in the arithmetic black box model, which allows them to be freely composed and used in larger applications.

High performance, small code size, and good scalability are important requirements for software implementations of multi-precision arithmetic algorithms to fit resource-limited embedded systems. In this paper, we describe optimization techniques to speed up multi-precision multiplication and squaring on the AVR ATmega series of 8-bit microcontrollers. First, we present a new approach to perform multi-precision multiplication, called Reverse Product Scanning (RPS), that resembles the hybrid technique of Gura et al., but calculates the byte-products in the inner loop in reverse order. The RPS method processes four bytes of the two operands in each iteration of the inner loop and employs two carry-catcher registers to minimize the number of add instructions. We also describe an optimized algorithm for multi-precision squaring based on the RPS technique that is, depending on the operand length, up to 44.3 % faster than multiplication. Our AVR Assembly implementations of RPS multiplication and RPS squaring occupy less than 1 kB of code space each and are written in a parameterized fashion so that they can support operands of varying length without recompilation. Despite this high level of flexibility, our RPS multiplication outperforms the looped variant of Hutter et al.’s operand-caching technique and saves between 40 and 51 % of code size. We also combine our RPS multiplication and squaring routines with Karatsuba’s method to further reduce execution time. When executed on an ATmega128 processor, the “karatsubarized RPS method” needs only 85 k clock cycles for a 1024-bit multiplication (or 48 k cycles for a squaring). These results show that it is possible to achieve high performance without sacrificing code size or scalability.

Identity-based encryption (IBE) is an advanced form of public key encryption and one of the most important cryptographic primitives. Of the many constructions of IBE schemes, the one proposed by Boneh and Boyen (in Eurocrypt 2004) is quite important from both practical and theoretical points of view. The scheme was standardized as IEEE P1363.3 and is the basis for many subsequent constructions. In this paper, we investigate its multi-challenge security, which means that an adversary is allowed to query challenge ciphertexts multiple times rather than only once. Since single-challenge security implies multi-challenge security, and since Boneh and Boyen provided a security proof for the scheme in the single-challenge setting, the scheme is also secure in the multi-challenge setting. However, this reduction results in a large security loss. Instead, we give tight security reduction for the scheme in the multi-challenge setting. Our reduction is tight even if the number of challenge queries is not fixed in advance (that is, the queries are unbounded). Unfortunately, we are only able to prove the security in a selective setting and rely on a non-standard parameterized assumption. Nevertheless, we believe that our new security proof is of interest and provides new insight into the security of the Boneh-Boyen IBE scheme.

Confidential information might be leaked through electro-magnetic radiation from a computer display. To detect the electromagnetic radiation that contains text information, this paper proposed an evaluation method without reconstructing the displayed image. In this method, sparse decomposition in wavelet is used to describe the characteristics of electromagnetic radiation signals contain text information. By using this method, it is easy to detect text information leakage in electromagnetic radiation from a computer display.

Side-channel distinguishers aim to reveal the secrets used in crypto devices by utilizing the subtle dependence between some sensitive intermediate values and physical leakages produced during its executions. For this purpose, one or more points of interest (POIs) corresponding to manipulations of one sensitive intermediate value are usually selected and then fed into distinguishers. However, it turns out in practice that POIs selected, even they are from the same leakage traces, will have significant impacts on the key recovery efficacy of distinguishers. Therefore, it makes a very practical sense to investigate the concrete impacts of POIs selections on side-channel distinguishers, and then pick out from those POIs selections available the most appropriate one for a certain distinguisher. In order to address these problems, we propose an evaluation framework for the analysis of POIs selections for side-channel distinguishers. Basically, our framework consists of two stages: the first stage captures the validity of points selected, while the second one reflects their quality with respect to a certain distinguisher. Specifically, on the one hand, in order to measure the goodness of one POIs selection, we introduce a quantitative metric of accuracy rate, from a perspective of statistics; on the other hand, we adopt the widely accepted security metric of success rate proposed by Standaert et al. at EUROCRYPT 2009 to reflect the quality of the points selected. Eventually, taking five typical POIs selections and three popular side-channel distinguishers as concrete study cases, we perform simulated attacks and practical attacks as well, the results of which not only fully justify our proposed methods but also reveal some interesting observations.

In order to minimize the impact of secret signing key exposure in attribute based signature scenario, we design two attribute based key-insulated signature (ABKIS) with message recovery schemes for expressive linear secret-sharing scheme (LSSS)-realizable access structures utilizing only 4 bilinear pairing operations in verification process and making the message-signature length constant. The first scheme deals with small universes of attributes while the second construction supports large universe of attributes. The signing key is computed according to LSSS access structure over signer’s attributes, and is later updated at discrete time periods with the help of a physically secure but computationally limited device, called helper, without changing the access structure. A signing key for some time period is used to sign every message during that time period. The original message is not required to be transmitted with the signature, however, it can be recovered during verification procedure. The size of signing key in the proposed schemes is quadratic in number of attributes. The (strong) key-insulated security of our ABKIS primitives is reduced to the classical computational Diffie Hellman Exponent problem in selective attribute set and random oracle model. We also show that both the proposed signature constructions provide signer privacy.

XOR-based visual cryptographic schemes for non-monotonic (k, n)-threshold access structures deviate from the fact that the superset of any collection of \(k+1\) or more participants may not get the secret back while providing their shares together. In this paper, we generalize this access structure to non-monotonic t-\((k,n)^*\)-access structure in which t-essential participants along with any other \((k-t)\) participants can reveal the secret, \(0 \le t \le k\) and \(2 \le k \le n\). This notion is a generalization of the non-monotonic (k, n)-threshold access structure in the sense that if we take \(t=0\), we get the non-monotonic (k, n)-threshold access structure. Visual cryptographic schemes for t-\((k,n)^*\)-threshold access structure based on Boolean “OR” operations are available in the literature. However the contrast of the reconstructed image is very poor, resulting a very bad recovery of the secret image visually. In this paper we study the same scenario for the “XOR” based model which provides much better relative contrast for the reconstructed secret image. We provide an efficient technique, based on simple linear algebra, to construct the basis matrices realizing the XOR-based non-monotone (k, n)-VCS with t many essential parties. The contrast of the scheme is significantly better than the existing OR-based schemes. Finally, for some restricted t-\((k,n)^*\) non-monotonic access structures, we provide a scheme which not only achieves the optimal relative contrast but also achieves the optimal pixel expansion.

The use of passwords for user authentication has become ubiquitous in our everyday lives. However, password theft is becoming a common occurrence due to a variety of security problems associated with passwords. As such, many organizations are moving towards adopting alternative solutions like one-time passwords, which are only valid for a single session. Nevertheless, various one-time password schemes also suffer from a number of drawbacks in terms of their method of generation or delivery. This paper presents the design of a challenge-response visual one-time password authentication scheme that is to be used in conjunction with the camera on a mobile device. The main purpose of the proposed scheme is to be able to send a challenge over a public channel for a user to obtain a session key, while safeguarding the user’s long-term secret key. In this paper, we present the authentication protocol, the various design considerations and the advantages provided by the scheme.

A proxy signature scheme enables a signer to transfer its signing rights to any other user, called the proxy signer, to produce a signature on its behalf. Multi-proxy signature is a proxy signature primitive which enables a user to transfer its signing rights to a group of proxy signers in such a way that every member of the authorized group must “participate” to sign a document on behalf of the original signer. We propose an efficient and provably secure identity-based multi-proxy signature scheme from bilinear map based on the hardness of the computational Diffie-Hellman problem. The proposed scheme is proved secure against adaptive chosen message and adaptive chosen-ID attack in random oracle model under the computational Diffie-Hellman assumption. Moreover, we do an efficiency comparison with the existing identity-based multi-proxy signature schemes and show that our scheme is upto 56 % more efficient in computation than the existing schemes.

Attribute-Based Encryption (ABE) offers fine-grained decryption policy such that users can do decryption if their attributes satisfy the policy. Such flexibility enables it applicable in various applications in government and business. However, there are two issues that should be solved first before it is deployed in practice, namely user revocation and decryption outsourcing. In this paper, we adopt the slightly modified Lewko et al.’s fully-CCA-secure Ciphertext-Policy-ABE (CP-ABE) combining with Boneh et al.’s idea of mediated cryptography to propose a CP-ABE with SEcurity Mediator (SEM) supporting immediate user revocation. At the same time, by the introduce of SEM, we intendedly outsource most of the computation workload in decryption to SEM side and leave only one exponentiation and one division at user side for decryption. It is proved fully-RCCA-CCA-secure in random oracle model.

We propose a new approach to Captcha which estimates human cognitive ability, in particular visual search ability, to differentiate humans from computers. We refer to this Captcha as Movtcha (Matching Objects by Visual Search To Tell Computers and Humans Apart). The design of Movtcha takes into account the analysis of human behavior to minimize noise during cognitive feature estimation. Our empirical results suggest that Movtcha can provide accuracy and usability comparable to other established Captchas. Our system is suitable for large scale applications since image selection, challenge generation and response evaluation are automated. Movtcha, unlike other Captchas, surpasses language and experience barriers by presenting both challenge and response in clear form and therefore can be used by people all across the world.

The EMV chip-and-pin system is one of the most widely used cryptographic system in securing credit card and ATM transactions. As suggested by the EMV consortium, the existing RSA-based EMV system will be upgraded to Elliptic Curve Cryptography (ECC) based system. In CCS 2013, Brzuska et al. made the first step to analyze the security of the ECC-based EMV channel establishment protocol in a channel establishment security model, and showed that a slightly modified version of the protocol meets the intended security goals. In this paper, we continue this strand of research by analyzing the security of the ECC-based EMV protocol in a strong channel establishment security model which allows the adversary to get ephemeral private keys of the involved parties. We find that the original protocol is not secure in our security model because the adversary can impersonate a Card entity. Then we slightly modify the protocol almost with no addition of computation cost and show that the resulting protocol is secure in our security model under standard cryptographic assumptions.