Information Security and Cryptology - ICISC 2015

A redactable signature scheme (\({\mathsf {RSS}}\)) allows removing parts of a signed message by any party without invalidating the respective signature. State-of-the-art constructions thereby focus on messages represented by one specific data-structure, e.g., lists, sets or trees, and adjust the security model accordingly. To overcome the necessity for this myriad of models, we present a general framework covering arbitrary data-structures and even more sophisticated possibilities. For example, we cover fixed elements which must not be redactable and dependencies between elements. Moreover, we introduce the notion of designated redactors, i.e., the signer can give some extra information to selected entities which become redactors. In practice, this often allows to obtain more efficient schemes. We then present two \(\mathsf {RSS}\)s; one for sets and one for lists, both constructed from any EUF-CMA secure signature scheme and indistinguishable cryptographic accumulators in a black-box way and show how the concept of designated redactors can be used to increase the efficiency of these schemes. Finally, we present a black-box construction of a designated redactor \(\mathsf {RSS}\) by combining an \(\mathsf {RSS}\) for sets with non-interactive zero-knowledge proof systems. All the three constructions presented in this paper provide transparency, which is an important property, but quite hard to achieve, as we also conceal the length of the original message and the positions of the redactions.

In the ordinary security model for signature schemes, we consider an adversary that may forge a signature on a new message using only his knowledge of other valid message and signature pairs. To take into account side channel attacks such as tampering or fault-injection attacks, Bellare and Kohno (Eurocrypt 2003) formalized related-key attacks (RKA), where stronger adversaries are considered. In RKA for signature schemes, the adversary can also manipulate the signing key and obtain signatures for the modified key. This paper considers RKA security of two established signature schemes: the Schnorr signature scheme and (a well-known variant of) DSA. First, we show that these signature schemes are secure against a weak notion of RKA. Second, we demonstrate that, on the other hand, neither the Schnorr signature scheme nor DSA achieves the standard notion of RKA security, by showing concrete attacks on these. Lastly, we show that a slight modification of both the Schnorr signature scheme and (the considered variant of) DSA yields fully RKA secure schemes.

Attribute-based signature scheme (ABS) is a functional variant of digital signature scheme proposed in 2008 by Maji et al. The two basic requirements of ABS (and a hard task to achieve) is collusion resistance and attribute privacy. In this paper, we employ the two-tier signature (TTS) technique to achieve the collusion resistance. Here TTS was proposed in 2007 by Bellare et al., where a signer receives two tier secret keys sequentially. The secondary secret key is served as a one-time key at the timing of signing. First, we propose a definition of an attribute-based two-tier signature scheme (ABTTS). Then we provide ABTTS concretely that enjoys existential unforgeability against chosen-message attacks, collusion resistance and attribute privacy, in the standard model. For the construction, enhancing the Camenisch-Lysyanskaya signature, we construct signature bundle schemes that are secure under the Strong RSA assumption and the Strong Diffie-Hellman assumption, respectively. These signature bundle schemes enable ABTTS to achieve attribute privacy. Then, using the signature bundle as a witness in the \(\varSigma \)-protocol of the boolean proof, we obtain attribute-based identification schemes (ABIDs). Finally, by applying the TTS technique to ABIDs, we achieve ABTTSs. A feature of our construction is that ABTTS in the RSA setting is pairing-free.

Broadcasting is a very efficient way to securely transmit information to a large set of geographically scattered receivers, and in practice, it is often the case that these receivers can be grouped in sets sharing common characteristics (or attributes). We describe in this paper an efficient ciphertext-policy attribute-based broadcast encryption scheme (CP-ABBE) supporting negative attributes and able to handle access policies in conjunctive normal form (CNF). Essentially, our scheme is a combination of the Boneh-Gentry-Waters broadcast encryption and of the Lewko-Sahai-Waters revocation schemes; the former is used to express attribute-based access policies while the latter is dedicated to the revocation of individual receivers. Our scheme is the first one that involves a public key and private keys having a size that is independent of the number of receivers registered in the system. Its selective security is proven with respect to the Generalized Diffie-Hellman Exponent (GDHE) problem on bilinear groups.

The Snowden revelations have shown that intelligence agencies have been successful in undermining cryptography and put in question the exact security provided by the underlying intractability problem. We introduce a new class of intractability problems, called Learning with Errors in the Exponent (LWEE). We give a tight reduction from Learning with Errors (LWE) and the Representation Problem (RP) in finite groups, two seemingly unrelated problem, to LWEE. The argument holds in the classical and quantum model of computation.

Furthermore, we present the very first construction of a semantically secure public-key encryption system based on LWEE in groups of composite order. The heart of our construction is an error recovery “in the exponent” technique to handle critical propagations of noise terms.

LowMC is a family of block ciphers developed particularly for use in multi-party computations and fully homomorphic encryption schemes, where the main performance penalty comes from non-linear operations. Thus, LowMC has been designed to minimize the total quantity of logical “and” operations, as well as the “and” depth. To achieve this, the LowMC designers opted for an incomplete S-box layer that does not cover the complete state, and compensate for it with a very dense, randomly chosen linear layer. In this work, we exploit this design strategy in a cube-like key-recovery attack. We are able to recover the secret key of a round-reduced variant of LowMC with 80-bit security, where the number of rounds is reduced from 11 to 9. Our attacks are independent of the actual instances of the used linear layers and therefore, do not exploit possible weak choices of them. From our results, we conclude that the resulting security margin of 2 rounds is smaller than expected.

Integral attack is an extremely important and extensively investigated cryptanalytic tool for symmetric-key primitives. In this paper, we improve the integral attack against bit-oriented ciphers. First, we propose the match-through-the-Sbox technique based on a specific property of the Sbox. Instead of computing the inverse of the Sbox in partial decryption, we independently calculate two Boolean functions which accept less input bits. The time complexity is thus reduced and the number of attacked rounds will be stretched. Second, we devise an easy-to-implement algorithm for construction of the integral distinguisher, which is then proved to be very effective for constructing lower order distinguishers. It shows SIMON 32, 48, 64, 96 and 128 has 13-, 14-, 17-, 21- and 25-round integral distinguisher, respectively, significantly improving the recent results from EUROCRYPT 2015. Finally, our techniques are applied to several ciphers. We attack one more round than the previous best integral attack for PRESENT and first evaluate the securities of SIMON family (except for SIMON 32) and RECTANGLE with integral attack.

The Kalyna block cipher has recently been established as the Ukranian encryption standard in June, 2015. It was selected in a Ukrainian National Public Cryptographic Competition running from 2007 to 2010. Kalyna supports block sizes and key lengths of 128, 256 and 512 bits. Denoting variants of Kalyna as Kalyna-b / k, where b denotes the block size and k denotes the keylength, the design specifies \(k \in \{b, 2b\}\). In this work, we re-evaluate the security bound of some reduced round Kalyna variants, specifically Kalyna-128 / 256 and Kalyna-256 / 512 against key recovery attacks in the single key model. We first construct new 6-round distinguishers and then use these distinguishers to demonstrate 9-round attacks on these Kalyna variants. These attacks improve the previous best 7-round attacks on the same.

Our 9-round attack on Kalyna-128/256 has data, time and memory complexity of \(2^{105}\), \(2^{245.83}\) and \(2^{226.86}\) respectively. For our 9-round attack on Kalyna-256/512, the data/time/memory complexities are \(2^{217}\), \(2^{477.83}\) and \(2^{451.45}\) respectively. The attacks presented in this work are the current best on Kalyna. We apply multiset attack - a variant of meet-in-the-middle attack to achieve these results.

LBlock is a 32-round lightweight block cipher with a 64-bit block size and an 80-bit key. This paper presents a new impossible differential attack on LBlock by improving the previous best result for 1 more round. Based on the nibble conditions, detailed differential properties of LBlock S-Boxes and thorough exploration of subkey relations, we set up well precomputation tables to collect the data needed and propose an optimal key-guessing arrangement to effectively reduce the time complexity of the attack. With these techniques, we launch an impossible differential attack on 24-round LBlock. To the best of our knowledge, this attack is currently the best in terms of the number of rounds attacked (except for biclique attacks).

We analyze the point decomposition problem (PDP) in binary elliptic curves. It is known that PDP in an elliptic curve group can be reduced to solving a particular system of multivariate non-linear equations derived from the so called Semaev summation polynomials. We modify the underlying system of equations by introducing some auxiliary variables. We argue that the trade-off between lowering the degree of Semaev polynomials and increasing the number of variables provides a significant speed-up.

In this paper, we present high speed parallel multiplication and squaring algorithms for the Mersenne prime \(2^{521}-1\). We exploit 1-level Karatsuba method in order to provide asymptotically faster integer multiplication and fast reduction algorithms. With these optimization techniques, ECDH on NIST’s (and SECG’s) curve P-521 requires 8.1/4 M cycles on an ARM Cortex-A9/A15, respectively. As a comparison, on the same architecture, the latest OpenSSL 1.0.2d’s ECDH speed test for curve P-521 requires 23.8/18.7 M cycles for ARM Cortex-A9/A15, respectively.

Fair conduct of elections is essential for the smooth existence of democratic societies. In order to response voting security concerns, security researchers have developed tamper-resistant and voter verifiable methods. These end-to-end voting schemes are unique because they give voters the option to both verify the voting scheme’s functionality and to check that their votes have been recorded after leaving the polling booth. Helios and \(\mathrm{P{\hat{r}}et}\) á voter are the most usable voter verifiable, end-to-end voting schemes using mixnet. Helios is a web-based open-audit voting system utilizing mixnet and secure cryptographic primitives. It satisfies almost all the security properties like privacy, individual and universal verifiability, and mixnet integrity etc. However, the proof of mixnet integrity is complex to understand and costly in terms of computations that effects conducting large-scale elections. For a voter, it is rarely impossible to verify the correctness of election results without trusting on election administrator and the candidates for the correctness of election result. In this paper, we address this issue by presenting a simple and fast method for conducting end-to-end voting and allowing public verification of the correctness of the announced vote tallying results. Our method is based on existing Helios structure, we call it Apollo that facilitates a direct proof of mixnet integrity, and also satisfies all the security properties.

In collaborative recommendation systems, privacy may be compromised, as users’ opinions are used to generate recommendations for others. In this paper, we consider an online collaborative recommendation system, and we measure users’ privacy in terms of the standard notion of differential privacy. We give the first quantitative analysis of the trade-offs between recommendation quality and users’ privacy in such a system by showing a lower bound on the best achievable privacy for any algorithm with non-trivial recommendation quality, and proposing a near-optimal algorithm. From our results, we find that there is actually little trade-off between recommendation quality and privacy, as long as non-trivial recommendation quality is to be guaranteed. Our results also identify the key parameters that determine the best achievable privacy.

Vulnerable software represents a tremendous threat to modern information systems. Vulnerabilities in widespread applications may be used to spread malware, steal money and conduct target attacks. To address this problem, developers and researchers use different approaches of dynamic and static software analysis; one of these approaches is called fuzzing. Fuzzing is performed by generating and sending potentially malformed data to an application under test. Since first appearance in 1988, fuzzing has evolved a lot, but issues which addressed to effectiveness evaluation have not fully investigated until now.

In our research, we propose a novel approach of fuzzing effectiveness evaluation and improving, taking into account semantics of executed code along with a quantitative assessment. For this purpose, we use specific metrics of source code complexity assessment specially adapted to perform analysis of machine code. We conducted effectiveness evaluation of these metrics on 104 wide-spread applications with known vulnerabilities. As a result of these experiments, we were able to identify the best metrics that is more suitable to find bugs. In addition we proposed a set of open-source tools for improving fuzzing effectiveness. The experimental results of effectiveness assessment have shown viability of our approach and allowed to reduce time costs for fuzzing campaign by an average of 26–28 % for 5 well-known fuzzing systems.

Cell phones have evolved into general purpose computing devices, which are tightly integrated into many IT infrastructures. As such, they provide a potential malware entry point that cannot be easily dismissed if attacks by determined adversaries are considered. Most likely, such targeted attacks will employ rootkit technologies so as to hide their presence for as long as possible.

We have designed a rootkit detector that will allow to inspect the complete state of a smart phone, turning up a rootkit if present. Our solution draws on the strong isolation provided by virtualization to protect our detector from attempts to disable it. In comparison to mainstream hypervisors such as Xen and KVM, our hypervisor consist of only 7.000 SLOC, allowing for systems with a small trusted computing base. We implemented a full prototype using a low-cost embedded board and a full Android stack and validated its effectiveness against an exemplary rootkit that employs advanced countermeasures. Also, various benchmark measurements of the prototype proved that the performance degradation incurred by our design, while noticable, is not prohibitive.

It is common for attackers to launch famous Drive-by-download attacks by using malicious JavaScript on the Internet. In a typical case, attackers compromise legitimate websites and inject malicious JavaScript which is used to bounce the visitors to other pre-set malicious pages and infect them. In order to evade detectors, attackers obfuscate their malicious JavaScript so that the maliciousness can be hidden. In this paper, we propose a new approach for detecting suspicious obfuscated JavaScript based on information-theoretic measures and the idea of novelty detection. According to results of experiments, it can be seen the new system improves several potential weaknesses of previous systems.

Elliptic curve cryptosystem (ECC) is widely used in cryptographic device. Despite its solid mathematical security, ECC is still vulnerable to many kinds of physical attacks. In this paper, we present two new lattice-based differential fault attacks (DFA) against the famous ECC signature algorithm standard-ECDSA with wNAF algorithm of scalar multiplication. Compared with the fault attack proposed in Crypto’2000, our first attack adopts a different way to deduce parts of the nonce k. The former recovered parts of k mainly by guessing technique, while our attack combines the guessing technique and solving equation with one unknown. So our attack is applicable for the weaker attack scenes allowing more random faulty bits. In our second proposed attack, instead of injecting faults during calculating kG, we focus on injecting faults during calculating wNAF transformation of k before calculating kG. If the targets during wNAF transformation of k are skipped by fault injection, we can build some DFA models to retrieve parts of k. In both of the two attacks, the attacker can mount lattice attack to recover the private key in ECDSA with the derived parts of k. Finally, we verify the feasibility of our proposed attacks by experiments.

A cold boot attack is a kind of side-channel attack that exploits a property of dynamic random-access memory. Using a cold boot attack, attackers can extract decayed key material from a running computer’s memory, which is a serious threat to computers using disk encryption software. Previously, an algorithm was presented that recovers a secret key from a decayed Advanced Encryption Standard key schedule. However, this method cannot recover a secret key if reverse bit flipping occurs, even in only one position, because this algorithm assumes a perfect asymmetric decay model. To remedy this limitation, we propose an algorithm based on the maximum likelihood approach, which can recover a secret key in an imperfect asymmetric decay model, i.e., where bit flipping occurs in both directions. We also give the theoretical bound of our algorithm and verify the validity thereof.

This paper proposes three new padding methods designed to withstand padding oracle attacks, which aim at recovering a plaintext without knowing the secret key by exploiting oracle’s characteristic of checking the padding during decryption. Of the ten existing padding methods, only two (ABYT-PAD and ABIT-PAD) can withstand padding oracle attacks. However, these methods are not efficient since they either use a random number generator or require MAC verification in applications. The three new padding methods proposed in this paper are secure against padding oracle attacks and more efficient compared to the two aforementioned padding methods.

The last decade has witnessed a major change in the methods of Integrated Circuit (IC) fingerprinting and random key generation.The invention of Physically Unclonable functions (PUFs) was a milestone in the development of these methods. Ring-oscillator (RO) PUFs are one of the popular intrinsic PUF instances in authentication and random number generation applications. Similar to other types of PUFs, unpredictability and unclonability are the key requirements for the security of RO-PUFs. However, these requirements cannot be perfectly met for RO-PUFs, as demonstrated by studies investigating different attacks against RO-PUFs. In addition to semi-invasive attacks, modeling attacks have been proposed that aim to predict the response to an arbitrarily chosen challenge. To this end, the adversary collects only a small number of challenge response pairs (CRPs), and then attempts to constitute a model of the challenge-response behavior of the PUF. Nevertheless, it is not ensured that a model will be delivered after learning the seen CRPs, whose number is solely estimated instead of being properly proved. Aiming to address these issues, this paper presents a Probably Approximately Correct (PAC) learning framework enabling the learning of an RO-PUF for arbitrary levels of accuracy and confidence. Indeed, we prove that a polynomial-size Decision List (DL) can represent an RO-PUF. Thus, an arbitrarily chosen RO-PUF can be PAC learned by collecting only a polynomial number of CRPs. The “hidden” polynomial size of the respective representation of an RO-PUF therefore accounts for the success of the previously proposed (heuristic) attacks. However, our proposed bound is provably better, when comparing the number of CRPs required for our attack with already existing bounds calculated by applying heuristic techniques. Finally, by conducting experiments we complement the proof provided in our PAC learning framework.

We propose an anonymous authentication scheme which security is based on Physical Unclonable Function. Our scheme is resistant to typical attacks mounted against regular systems with security based on computational assumptions. Its tampering and cloning resistance is based on the assumption that cloning of the PUF device is impossible. The scheme withstand collusion attacks: no coalition of adversaries can successfully authenticate without a registered device. It provides unconditional anonymity: it is infeasible to determine which device, out of the all registered, was used for authorization. The anonymity feature withstand attacks of the very powerful adversary which has access to all public parameters, as well all secrets - including the master secret of the system creator.