Information Security and Cryptology - ICISC 2014

In 1999, Boneh and Durfee introduced small inverse problems which solve bivariate modular equations \(x(N+y)\equiv 1 \pmod {e}\). Sizes of solutions for \(x,y\) are bounded by \(X=N^{\delta }\) and \(Y=N^{\beta }\), respectively. They solved the problems for \( \beta ={1/2}\) in the context of small secret exponents attacks on RSA. They proposed a polynomial time algorithm which works when \( \delta <(7-2 \sqrt{7})/6 \approx {0.284}\), and further improved a bound to \( \delta <1-1/\sqrt{2}\approx {0.292}\). So far, small inverse problems for arbitrary \({\beta }\) have also been considered. Generalizations of Boneh and Durfee’s lattices to achieve the stronger bound provide the bound \( \delta <1-\sqrt{\beta }\). However, the algorithm works only when \( \beta \ge 1/4\). When \(0<\beta <1/4\), there have been several works which claimed the best bounds. In this paper, we revisit the problems for arbitrary \( \beta \). At first, we summarize the previous results for \(0<\beta <1/4\). We reveal that there are some results which are not valid and show that Weger’s algorithm provide the best bounds. Next, we propose an improved algorithm to solve the problem for \(0<\beta <1/4\). Our algorithm works when \( \delta <1-2(\sqrt{\beta (3+4 \beta )}-\beta )/3\). Our algorithm construction is based on the combinations of Boneh and Durfee’s two forms of lattices. This construction is more natural compared with previous works. In addition, we introduce an application of our result, small secret exponent attacks on Multi-Prime RSA with small primes differences.

Threshold RSA encryption and signing is a very useful tool to increase the security of the secret keys used. Key generation is, however, either done in a non-threshold way, or computationally inefficient protocols are used. This is not a big problem in a setup where one organization has a few high profile keys to secure, however, this does not scale well to systems with a lot of secret keys, like eID schemes where there exist one key pair per user, especially not if the we want the users’ personal devices like smart phones to participate in the threshold setup. In this paper we present novel approaches to distributed RSA key generation which are efficient enough to let smart phones participate. This is done by generating keys consisting of more than two primes instead of generating standard RSA keys.

We present a 2-party protocol based on the ideas of [BH98] which produces a 3-prime modulo. We demonstrate that the protocol is efficient enough to be used in practical scenarios even from a mobile device which has not been demonstrated before. Then we show the first 2-party distributed multiprime RSA key generation protocol that are as efficient as standard centralized key generation, even if security against malicious adversaries is desired. Further, we show that RSA keys based on moduli with more than two prime factors and where part of the factorization is leaked to the adversary are useful in practice by showing that commonly used schemes such as PSS-RSA and OAEP-RSA is secure even if the adversary knows a partial factorization of the multiprime moduli. From all other parties the generated keys cannot be distinguished from standard RSA keys, which is very important as this make these protocols compatible with existing infrastructure and standards.

The task-structured Probabilistic I/O Automata (task-PIOA) framework provides a method to formulate and to prove the computationally-bounded security of non-sequential processing systems in a formal way. Though existing works show security analyses of some classic cryptographic protocols (e.g., the EGL oblivious transfer) against simple adversaries (e.g., honest but curious adversary), there is no case study for fundamental cryptographic primitives (e.g., encryption and signature) against sufficiently strong adversaries (e.g., IND-CCA for encryption and EUF-CMA for signature). In this paper, we propose a formulation of signature against EUF-CMA in the task-PIOA framework. Using the task-PIOA framework allows us to verify security of signature schemes in the non-sequential scheduling manner. We show the validity and usefulness of our formulation by giving a formal security analysis of the FDH signature scheme. In order to prove the security, we also introduce a method to utilize the power of random oracles. As far as we know, this work is the first case study to clarify usefulness of random oracles in this framework.

Recently Yasuda, Takagi and Sakurai proposed a new and interesting signature scheme from the classification of quadratic forms over finite fields of odd characteristic published in PQCrypto 2013. In this paper we propose two algebraic attacks to their scheme using only linear algebra. Both attacks are motivated by Kipnis and Shamir’s attack to the oil-vinegar signature scheme. Namely we first turn the original problem to a geometric problem and then apply the theory of invariant subspace intensively. We show that Yasuda, Takagi and Sakurai’s scheme can be broken by our attacks with complexity \(O(m^{\frac{11}{2}}q^d)\) where \(m\) is the number of variables and \(q\) is the size of the base field. Here \(d\) is expected generally to be 1 and is confirmed in our tests. We also compare our attacks with Y. Hashimoto’s attack which is just published in PQCrypto 2014.

Recent efficient pairings such as Ate pairing use two efficient subgroups of rational point such that \(\pi (P)=P\) and \(\pi (Q)=[p]Q\), where \(\pi \), \(p\), \(P\), and \(Q\) are the Frobenius map for rational point, the characteristic of definition field, and torsion points for pairing, respectively. This relation accelerates not only pairing but also pairing–related operations such as scalar multiplications. It holds in the case that the embedding degree \(k\) divides \(r-1\), where \(r\) is the order of torsion rational points. Thus, such a case has been well studied. Alternatively, this paper focuses on the case that the degree divides \(r+1\) but not \(r-1\). First, this paper shows a transitive representation for \(r\)–torsion points based on the fact that the characteristic polynomial \(f(\pi )\) becomes irreducible over \(\mathbb {F}_{r}\) for which \(\pi \) also plays a role of variable. In other words, this paper proposes an elliptic curve discrete logarithm on such a torsion group. After that, together with some example parameters, it is shown how to prepare such pairing–friendly elliptic curves.

Applebaum (EUROCRYPT 2011) showed how to convert a public key encryption (PKE) scheme which is key dependent message (KDM) secure with respect to projection functions (also called projection-KDM secure) to a scheme which is KDM secure with respect to functions computable by polynomially bounded-size circuits (also called bounded-KDM secure). This result holds in both of the chosen plaintext attack (CPA) setting and the chosen ciphertext attack (CCA) setting. Bellare et al. (CCS 2012) later showed another conversion from a projection-KDM secure scheme to a bounded-KDM secure one, which is more efficient than Applebaum’s, but works only in the CPA setting. In this work, we show an efficient conversion from a projection-KDM-CCA secure PKE scheme to a bounded-KDM-CCA secure PKE scheme. To see that our conversion leads to more efficient bounded-KDM-CCA secure schemes than Applebaum’s, we show that by combining our result with several known results, we can obtain currently the most efficient bounded-KDM-CCA secure PKE scheme based on the symmetric external Diffie-Hellman (SXDH) assumption.

In this paper, we propose a new phase-based enumeration algorithm based on two interesting and useful observations for \(y\)-sparse representations of short lattice vectors in lattices from SVP challenge benchmarks [24]. Experimental results show that the phase-based algorithm greatly outperforms other famous enumeration algorithms in running time and achieves higher dimensions, like the Kannan-Helfrich enumeration algorithm. Therefore, the phase-based algorithm is a practically excellent solver for the shortest vector problem (SVP).

The linear cryptanalysis proposed by Matsui is one of the most effective attacks on block ciphers, and he demonstrated an experimental cryptanalysis against DES at CRYPTO 1994. In this paper, we show how to optimize the linear cryptanalysis on modern microprocessors. Nowadays, there are two methods of implementing the linear cryptanalysis. Method 1 reduces the time complexity by reducing the number of computations of round functions, and Method 2 applies the fast Fourier transform (FFT). We implement both methods optimized for modern microprocessors and compare them in terms of computation time so as to discover which method is more appropriate for practical cryptanalysis. From the results of comparative experiments, we show that the fastest implementation depends on the number of given known plaintexts (KPs) and that of guessed key bits. These results clarify the criteria for selecting the method to implement the linear cryptanalysis. Taking the experimental results into account, we implement the linear cryptanalysis on FEAL-8X. In 2014, Biham and Carmeli showed an implementation of linear cryptanalysis that was able to recover the secret key with \(2^{14}\) KPs. Our implementation breaks FEAL-8X with \(2^{12}\) KPs and is the best attack on FEAL-8X in terms of data complexity.

We present two new algorithms, FEA-1 and FEA-2, for secure and efficient format-preserving encryption. Each algorithm is built from a family of dedicated tweakable blockciphers supporting various block bit-lengths. The tweakable blockciphers in the same family have similar structures and are based on common building blocks, enabling security analyses in the same frameworks. Their security follows largely from the structures, the round functions, and the tweak schedules. Their structures are new tweakable Feistel schemes, which are shown to be indistinguishable from tweakable random permutations against adaptive chosen tweak, plaintext, and ciphertext attacks. Their building blocks are shown to have cryptographically strong properties. The proposed algorithms outperform existing ones. They are several times faster than FF1-AES on test platforms.

In this paper, we re-evaluate the security-bound of full round AES against biclique attack. Under some reasonable restrictions, we exhaustively analyze the most promising class of biclique cryptanalysis as applied to AES through a computer-assisted search and find optimal attacks towards lowest computational and data complexities:

This paper proposes applying differential fault analysis (DFA) to the Simon family of lightweight block ciphers. We perform DFA by examining the characteristics of the AND operation which is a non-linear function of Simon. Then, we evaluate in detail the number of fault injections required to obtain a secret key. To the best of our knowledge, we are the first to show how to extract the entire secret key for all parameters in the Simon family using a practical fault model based on random faults. As an example, for Simon with a \(128\)-bit block size and a \(128\)-bit secret key, we can extract the entire secret key using \(7.82\) fault injections on average. The results of simulations performed on a PC show that the average number of fault injections required to retrieve a round key agrees with that based on theoretical results. We believe that this study gives new insight into the field of fault analysis because Simon has a property specific to non-linear functions in that it uses the AND operation while not using a substitution box which most block ciphers employ.

Social networks, in which huge numbers of people spread massive information, are developing quite rapidly. Here people can obtain interesting information much more quickly and conveniently. However, people’s privacies leak easily here too. A lot of works have been done to deal with this problem. Most of them focused on either attribute information or structure information. It is insufficient, because both attributes and structures, including sensitive attributes, are important in social networks, and we need to protect both of them. In this paper, we introduce a novel approach for privacy-preserving considering both attribute and structure information. In particular, sensitive attributes are considered to resist re-identification attacks. Moreover, we define the entropy to measure capability of preserving sensitive attributes.

We investigate how to solve several classical network flow problems using secure multi-party computation. We consider the shortest path problem, the minimum mean cycle problem and the minimum cost flow problem. To the best of our knowledge, this is the first time the two last problems have been addressed in a general multi-party computation setting. Furthermore, our study highlights the complexity gaps between traditional and secure implementations of the solutions, to later test its implementation. It also explores various trade-offs between performance and security. Additionally it provides protocols that can be used as building blocks to solve complex problems. Applications of our work can be found in: communication networks, routing data from rival company hubs; distribution problems, retailer/supplier selection in multi-level supply chains that want to share routes without disclosing sensible information; amongst others.

We introduce the use of timing channels for digital watermarking of embedded hardware and software components. In addition to previous side channel watermarking schemes, timing analysis offers new perspectives for a remote verification of mobile and embedded products. Timing channels make it possible to detect the presence of a watermark solely by measuring program execution times.

We propose schemes for embedding authorship and fingerprint marks that are built upon conditional timing delays. We provide experimental evidence by protecting an implementation of an image binarization circuit on an FPGA board that is connected over Ethernet to a remote PC. The circuit constantly leaks the watermark over the timing channel by modulating its execution time, which is successfully detected by using an oscilloscope and an EM probe, as well as by using software on a remote PC. Our solution for a remote verification is of special interest for highly performant services as they force an adaptive adversary towards enhanced costs in time, memory, and circuitry when bypassing these schemes.

Application plagiarism or application cloning is an emerging threat in mobile application markets. It reduces profits of original developers and sometimes even harms the security and privacy of users. In this paper, we introduce a new concept, called camouflaged applications, where external features of mobile applications, such as icons, screenshots, application names or descriptions, are copied. We then propose a scalable detection framework, which can find these suspiciously similar camouflaged applications. To accomplish this, we apply text-based retrieval methods and content-based image retrieval methods in our framework. Our framework is implemented and tested with 30,625 Android applications from the official Google Play market. The experiment results show that even the official market is comprised of 477 potential camouflaged victims, which cover 1.56 % of tested samples. Our paper highlights that these camouflaged applications not only expose potential security threats but also degrade qualities of mobile application markets. Our paper also analyze the behaviors of detected camouflaged applications and calculate the false alarm rates of the proposed framework.

Accompanying the wide spread of Android mobile devices and the openness feature of Android ecosystem, untrusted Android apps are flooding into user’s device and prepared to perform various unwanted operations stealthily. To better manage installed apps and secure mobile devices, Android app behaviour regulating schemes are required. In this paper, we present WrapDroid, a dynamic app behaviour regulating scheme on Android device. Different from other similar approaches, the key components of WrapDroid are implemented based on dynamic memory instrumentation and system call tracing and require no modification to Android system source code. Thus, WrapDroid could be flexibly adopted by Android devices. Moreover, by automatically reconstructing call context of Java or native operations, WrapDroid may provide a full range of control on both java runtime and system call layers of an app. We also develop a WrapDroid prototype and evaluate it on several devices from different mainstream OEMs. Evaluation results show that WrapDroid can effectively regulate the behaviors of Android apps according to given policies with negligible performance overhead.

This paper presents the first non-trivial collision attack on the double-block-length compression function presented at FSE 2006 instantiated with round-reduced AES-256: \(f_0(h_0\Vert h_1,M)\Vert f_1(h_0\Vert h_1,M)\) such that where \(\Vert \) represents concatenation, \(E\) is AES-256 and \(c\) is a non-zero constant. The proposed attack is a free-start collision attack. It uses the rebound attack proposed by Mendel et al. It finds a collision with time complexity \(2^{8}\), \(2^{64}\) and \(2^{120}\) for the instantiation with 6-round, 8-round and 9-round AES-256, respectively. The space complexity is negligible. The attack is effective against the instantiation with 6-/8-round AES-256 if the \(16\)-byte constant \(c\) has a single non-zero byte. It is effective against the instantiation with 9-round AES-256 if the constant \(c\) has four non-zero bytes at some specific positions.

Since Wang’s attacks on the standard hash functions MD5 and SHA-1, design and analysis of hash functions have been studied a lot. NIST selected Keccak as a new hash function standard SHA-3 in 2012 and announced that Keccak was chosen because its design is different from MD5 and SHA-1/2 so that it could be secure against the attacks to them and Keccak ’s hardware efficiency is quite better than other SHA-3 competition candidates. However, software efficiency of Keccak is somewhat worse than present standards and other candidates. Since software efficiency becomes more important due to increase of kinds and volume of communication/storage data as cloud and big data service spread widely, its software efficiency degradation is not desirable.

In this paper, we present a new fast hash function family LSH, whose software efficiency is above four times faster than SHA-3, and 1.5–2.3 times faster than other SHA-3 finalists. Moreover it is secure against all critical hash function attacks.

Lossless data embedding theory has entered a new era for data hiding and information security. In a lossless scheme, the original data and the embedded data should be completely recoverable. Our \(n\)-pairs pattern method is a significant advance in lossless data hiding schemes. This paper shows that the proposed \(n\)-pairs pattern method can achieve greater embedding capacity while keeping distortion at the same level as the PS-K method (Pattern Substitution by pseudo random number generator to produce a key K). The performance of the \(n\)-pairs pattern method is thus shown to be better than the performance of PS-K.

Montgomery modular multiplication constitutes the “arithmetic foundation” of modern public-key cryptography with applications ranging from RSA, DSA and Diffie-Hellman over elliptic curve schemes to pairing-based cryptosystems. The increased prevalence of SIMD-type instructions in commodity processors (e.g. Intel SSE, ARM NEON) has initiated a massive body of research on vector-parallel implementations of Montgomery modular multiplication. In this paper, we introduce the Cascade Operand Scanning (COS) method to speed up multi-precision multiplication on SIMD architectures. We developed the COS technique with the goal of reducing Read-After-Write (RAW) dependencies in the propagation of carries, which also reduces the number of pipeline stalls (i.e. bubbles). The COS method operates on 32-bit words in a row-wise fashion (similar to the operand-scanning method) and does not require a “non-canonical” representation of operands with a reduced radix. We show that two COS computations can be “coarsely” integrated into an efficient vectorized variant of Montgomery multiplication, which we call Coarsely Integrated Cascade Operand Scanning (CICOS) method. Due to our sophisticated instruction scheduling, the CICOS method reaches record-setting execution times for Montgomery modular multiplication on ARM-NEON platforms. Detailed benchmarking results obtained on an ARM Cortex-A9 and Cortex-A15 processors show that the proposed CICOS method outperforms Bos et al’s implementation from SAC 2013 by up to 57 % (A9) and 40 % (A15), respectively.

We present a two-way Oblivious Pseudorandom Function (\(\mathsf{mOPRF}\)) secure in the malicious model under the Decisional Composite Residuosity (DCR) and Decisional Diffie-Hellman (DDH) assumptions. Using this \(\mathsf{mOPRF}\), we construct an optimistic mutual Private Set Intersection (\(\mathsf{mPSI}\)) protocol preserving fairness. Unlike existing optimistic protocols our mPSI supports semi-trusted arbiter instead of fully-trusted arbiter. Semi-trusted arbiter never get access to the private information of any of the parties while follow the protocol honestly. Our design is the first fair \(\mathsf{mPSI}\) with linear communication and computation complexities, and is proven to be secure in the standard model against malicious parties under Decisional \(q\)-Diffie-Hellman Inversion (D\(q\)-DHI), DCR and DDH assumptions.

In an unconditionally secure Distributed Oblivious Transfer (DOT) protocol, a receiver contacts at least \(k\) servers to obtain one of the \(n\) secrets held by a sender. Once the protocol has been executed, the sender does not know which secret was chosen by the receiver and the receiver has not gained information on the secrets she did not choose. In practical applications, the probability distribution of the secrets may not be uniform, e.g., when DOT protocols are used in auctions, some bids may be more probable than others.

In this kind of scenario, we show that the claim “a party cannot obtain more than a linear combination of secrets” is incorrect; depending on the probability distribution of the secrets, some existing polynomial interpolation-based DOT protocols allow a cheating receiver, or a curious server, who has obtained a linear combination of the secrets to determine all the secrets.

We devise a multiple (concurrent) commitment scheme operating on large messages. It uses an ideal global setup functionality in a minimalistic way. The commitment phase is non-interactive. It is presented in a modular way so that the internal building blocks could easily be replaced by others and/or isolated during the process of design and implementation. Our optimal instantiation is based on the decisional Diffie-Hellman (DDH) assumption and the (adversarially selected group) Diffie-Hellman knowledge (DHK) assumption which was proposed at CRYPTO 1991. It achieves UC security against static attacks in an efficient way. Indeed, it is computationally cheaper than Lindell’s highly efficient UC commitment based on common reference strings and on DDH from EUROCRYPT 2011.

Due to the frequent use of Internet in our daily life, privacy is a major issue in designing any cryptographic primitive. Adaptive oblivious transfer with access policy (\(\mathsf{AOT}\)-\(\mathsf{AP}\)) is a widely used primitive to create privacy preserving databases in which different messages have different access policies, allowing only those receivers who have the necessary permissions to access the databases. We provide the first fully-simulatable \(\mathsf{AOT}\)-\(\mathsf{AP}\) without the third party called issuer. To achieve our goal, we present a new ciphertext policy attribute based encryption (CP-ABE), which is a variant of Water’s CP-ABE. The Boneh-Boyen signature is employed to control the malicious behavior of the parties, and proposed CP-ABE is used to encrypt each message of the database under some access policy. The proposed protocol is secure under \(q\)-Strong Diffie-Hellman and \(q\)-Decision Bilinear Diffie-Hellman Exponent assumptions in static corruption model in the presence of malicious adversary. Moreover, our \(\mathsf{AOT}\)-\(\mathsf{AP}\) is as efficient as the existing similar schemes.

Side-channel analysis aims at cryptography implementation by exploiting and analyzing side-channel information. Side-channel leakage of software implementation does not only depend on operators (instruction) and operands (value) but also on where operators and operands are called or stored in the memory. However, in contrast to the leakage of the operator and operand values, the exploitable leakage caused by the memory address is quite small. Side-channel analysis aiming at memory address usually needs a huge number of samples to eliminate the algorithmic noise. This paper presents a new attack method exploiting the leakage from consecutive addresses when accessing multiple-byte operands during evaluation of an exponentiation. By folding the observed side-channel leakage, one measurement is enough to perform statistical side-channel analysis and successfully reveal the secret key. Since only one measurement is sufficient, this attack even works in the presence of common side-channel countermeasures such as exponent randomization and message blinding.

In this paper we present improvements to the differential fault analysis (DFA) of the stream cipher Trivium proposed in the work of M. Hojsík and B. Rudolf. In particular, we optimize the algebraic representation of obtained DFA information applying the concept of Mutants, which represent low degree equations derived after processing of DFA information. As a result, we are able to minimize the number of fault injections necessary for retrieving the secret key. Therefore, we introduce a new algebraic framework that combines the power of different algebraic techniques for handling additional information received from a physical attack. Using this framework, we are able to recover the secret key by only an one-bit fault injection. In fact, this is the first attack on stream ciphers utilizing minimal amount of DFA information. We study the efficiency of our improved attack by comparing the size of gathered DFA information with previous attacks.