Skip to main content
main-content

Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the 8th International Conference on Information Security and Cryptology, Inscrypt 2012, held in Beijing, China, in November 2012.

The 23 revised full papers presented were carefully reviewed and selected from 71 submissions. The papers cover the topics of side channel attacks, extractor and secret sharing, public key cryptography, block ciphers, stream ciphers, new constructions and protocols.

Inhaltsverzeichnis

Frontmatter

On the Multiple Fault Attacks on RSA Signatures with LSBs of Messages Unknown

In CHES 2009, Coron, Joux, Kizhvatov, Naccache and Paillier (CJKNP) introduced the multiple fault attack on RSA signatures with partially unknown messages. However, the complexity of their attack is exponential in the number of faulty signatures. At RSA 2010, this fault attack was improved, which runs in polynomial time in the number of faults. Both of the previous fault attacks deal with the general case. This paper considers the special situation that some least significant bits (LSBs) of messages are unknown. Because of this special case, our new multiple fault attack can handle a larger size of the unknown part of message. We provide two kinds of techniques to factor the RSA modulus N using the multiple faulty signatures. Comparisons between the previous attacks and the new attacks with a number of LSBs of the message unknown are given on the basis of the simulations.
Lidong Han, Wei Wei, Mingjie Liu

Differential Fault Analysis of Twofish

In this paper we propose Differential Fault Analysis (DFA) of Twofish which was one of the five AES finalists. It uses the concept of key-dependent S-boxes and Pseudo-Hadamard Transform, which make the cipher secure against differential attack. Each S-box is dependent on key because of which the S-box is not known to the attacker. Therefore, the existing DFA techniques which use the differential properties of S-box are not directly applicable to Twofish. We propose DFA based on an approximation technique. The attack retrieves the secret key using around 320 pairs of fault-free and faulty ciphertexts with attack time complexity of 240. To the best of author’s knowledge this is the first time a DFA attack is proposed on a cipher like Twofish which uses key-dependent S-box.
Sk Subidh Ali, Debdeep Mukhopadhyay

Improved Differential Cache Attacks on SMS4

Block ciphers that have Feistel structures are prone to a class of cache attacks known as differential cache attacks, which monitor power or timing side-channels to reveal the secret key. Differential cache attacks were first demonstrated on the block cipher CLEFIA, which has a type-2 generalized Feistel structure. In this paper we improve the attack methodology by showing that a sophisticated method of choosing plaintexts can result in a considerable reduction in attack complexity. This coupled with other cryptanalytic techniques, when applied to the block cipher SMS4, requires just 210 plaintexts to recover the SMS4 secret key from power traces for a 64 byte cache line. Further, the attack becomes more dangerous for large cache lines. For example, with a 128 byte cache line, only 52 power traces are required. Experimental validation of the complete attack has been done on an Intel Xeon microprocessor. Further we suggest an alteration to the SMS4 algorithm that can counter this attack.
Phuong Ha Nguyen, Chester Rebeiro, Debdeep Mukhopadhyay, Huaxiong Wang

An Extension of Fault Sensitivity Analysis Based on Clockwise Collision

This paper proposes an extension of fault sensitivity analysis based on clockwise collision. The original FSA attack uses the fault injections to exploit the sensitivity of calculations against the fault injections. While the clockwise collision fault sensitivity analysis (CC-FSA) uses the fault injections to detect the occurrence of the clockwise collision and to recover the secret key. Clockwise collision is a phenomenon for iterative hardware circuits, which leads to nearly impossible setup-time violations. Take an AES S-box as an instance, clockwise collision occurs when the S-box inputs for two consecutive clock cycles are identical in value. As a result, the combinational circuit in the second clock cycle has almost no signal toggle and a negligible critical path delay. This paper proposes and verifies the concept of CC-FSA using the clock-glitch-based fault injections and an unprotected AES implementation. We investigate the key recovery method for CC-FSA with a noisy data set and we consider CC-FSA can help the previous collision-based model-less FSA attack to identify the final 8-bit secret information without additional data and negligible computational overhead.
Yang Li, Kazuo Ohta, Kazuo Sakiyama

A Robust Fuzzy Extractor without ECCs

Fuzzy extractors are important secure schemes that are used to extract reliably reproducible uniform randomness from noise and biased biometric data. It is well known that the error-correction codes (ECCs) only work best when the noise patterns likely to occur are completely random, and typical error-correction codes are unable to capitalize on the errors with low entropy. Consequently, a new robust fuzzy extractor without ECCs was proposed and constructed. Our fuzzy extractor adopts the error-correction method based on incoming (1 − θ)-neighborhood and extracts more min-entropy under the condition of not-uniform noise patterns than those using standard error-correction codes. In addition, we also analyzed the proposed scheme’s correctness and efficiency, and proved its security and robustness mainly. The result shows that the proposed fuzzy extractor has the better practical value.
Jintao Yao, Kangshun Li, Mingwu Zhang, Min Zhou

An Efficient Rational Secret Sharing Protocol Resisting against Malicious Adversaries over Synchronous Channels

Current works solve the problem of rational secret sharing from one or some, but not all, of the following aspects: achieving a more appealing equilibrium concept, avoiding strong communication models and resisting against adversaries. To address one issue above, they need to lower the satisfaction in other issues. In this paper we construct a t-out-of-n rational secret sharing protocol, which achieves an enhanced notion of computational strict Nash equilibrium with respect to adversary structure \(\mathcal{A}\), runs over synchronous (non-simultaneous) broadcast channels and tolerates a malicious adversary who controls a minority of players. To the best of our knowledge, compared with current works tolerating adversaries, we are the first to yield positive results in all the three research aspects above. The feasibility of our protocol is based on the use of publicly verifiable secret sharing. Under the assumptions related to discrete logarithm and ElGamal cryptosystem, computational bounded players have an incentive not to deviate no matter how adversaries behave.
Yang Yu, Zhanfei Zhou

Visual Cryptography for Natural Images and Visual Voting

Visual cryptography is a type of secret sharing which encodes a secret image into several shadow images in such a way that the stacking of certain images printed on transparencies will reveal the secret. The decryption is done directly by the human visual system without any extra calculations. Most of previous researches essentially handle only binary images, as the underling encoding matrices are all Boolean matrices. For gray-level image, we need to halftone it into binary image before encoding. Although binary image can be used to simulate gray-level image, its visual quality is deteriorated, especially for fine images. The first part of this paper presents a method to provide much more gray-levels than previous schemes, given the same pixel expansion, and thus establishes the visual cryptography scheme suitable for natural images. The second part of this paper presents a visual voting scheme that need no counting process and guarantees anonymity.
Teng Guo, Feng Liu, ChuanKun Wu

RCCA Security for KEM+DEM Style Hybrid Encryptions

RCCA security is a weaker notion than CCA security, and has been proven to be sufficient for several cryptographic tasks. This paper adapts RCCA security to the most popular hybrid paradigms, KEM+DEM and Tag-KEM/DEM.
It is open to construct an RCCA-secure scheme more efficient than CCA-secure ones. In the setting of Tag-KEM, we solve this by presenting a natural RCCA-secure RSA-based Tag-KEM scheme, named as RSA-TKEM, which is more efficient than all existing methods for constructing a CCA-secure RSA-based Tag-KEM scheme.
Unfortunately, combining our RSA-TKEM with passive secure one-time pad following Tag-KEM/DEM paradigm yields an RCCA-insecure hybrid encryption. This shows passive security of DEM is not sufficient now, and Tag-KEM/DEM looses its advantage over KEM+DEM. In spite of this and for completeness, we show RCCA secure DEMs are still sufficient to achieve RCCA-secure hybrid encryptions by following Tag-KEM/DEM.
In addition, we show RCCA-secure KEM is sufficient for achieving CCA-secure hybrid encryptions. This is done by introducing a new hybrid paradigm, named as KEM/Tag-DEM, where the ciphertext of KEM is used as a tag for Tag-DEM scheme rather than reversely in Tag-KEM/DEM, so that the security of KEM can be weakened to RCCA one. Tag-DEMs can be constructed as efficiently as DEMs, so RCCA-secure KEMs more efficient than CCA-secure ones become more appealing.
Yuan Chen, Qingkuan Dong

Embedded Surface Attack on Multivariate Public Key Cryptosystems from Diophantine Equations

Let X = (x 1,..,x n ) and Y = (y 1,...,y m ) be a pair of corresponding plaintext and ciphertext for a cryptosystem. We define an embedded surface of this cryptosystem as any polynomial equation:
$$ E(X, Y) = E(x_1,..,x_n,y_1,...,y_m)=0, $$
which is satisfied by all such pairs. In this paper, we present a new attack on the multivariate public key cryptosystems from Diophantine equations developed by Gao and Heindl by using the embedded surfaces associated to this family of multivariate cryptosystems.
Jintai Ding, Ai Ren, Chengdong Tao

Verifiable Structured Encryption

Structured encryption schemes generalise symmetric searchable encryption (SSE) schemes by allowing encrypted search on arbitrarily structured data, instead of keyword-based search only. Both structured encryption and SSE schemes mainly consider security against passive adversaries, until recently where SSE schemes secure against active adversaries were proposed. This means in addition of querying encrypted data, the adversaries can modify encrypted data in the storage. SSE schemes secure against such adversaries are termed verifiable SSE. In this paper, we examine verifiable SSE and propose an extension for structured encryption under the active adversary setting. We first define verifiable structured encryption and its security under the notion of reliability similar to verifiable SSE, but with difference on how a tag for verifiability is defined. This is mainly due to the notions of semi-private data that does not exist in a verifiable SSE scheme. We then present constructions secure under this model and prove security of the constructions.
Moesfa Soeheila Mohamad, Geong Sen Poh

Nested Merkle’s Puzzles against Sampling Attacks

We propose a new private key establishment protocol which is based on the Merkle’s puzzles scheme. This protocol is designed to provide the honest parties the ability to securely and continuously communicate over an unprotected channel. To achieve the continuous security over unbounded communication sessions we propose to use a nested Merkle’s puzzles approach where the honest parties repeatedly establish new keys and use previous keys to encrypt the puzzles of the current key establishment incarnation. We provide an implementation of the idea in the random oracle model and analyze its security. In addition, we implement the protocol in the standard cryptographic model, basing its security on the lattice shortest vector problem. The iterative nested scheme we propose enlarges the probability that the set of randomly chosen puzzles will contain hard puzzles, comparing with the probability that a single randomly chosen set consists of hard puzzles. Our nested Merkle puzzles scheme copes with δ-sampling attack where the adversary chooses to solve δ puzzles in each iteration of the key establishment protocol, decrypting the actual current communication when the adversary is lucky to choose the same puzzles the receiver chooses. We analyze the security of our schemes in the presence of such an attack.
Shlomi Dolev, Nova Fandina, Ximing Li

Optimizing Guessing Strategies for Algebraic Cryptanalysis with Applications to EPCBC

In this paper we demonstrate how to use Mixed Integer Linear Programming to optimize guessing strategies for algebraic cryptanalysis with applications to the block cipher EPCBC. Using our optimized guessing strategy we are able to attack 5 rounds of EPCBC-96 and 8 rounds of EPCBC-48 faster than brute force using one and two known plaintexts resp. Finally, we are able to identify a class of weak keys for which the attack is faster than brute force for up to 7 rounds of EPCBC-96. Alongside results on EPCBC we believe that the proposed technique of optimized guessing is a useful tool in a more general context of algebraic cryptanalysis.
Michael Walter, Stanislav Bulygin, Johannes Buchmann

A General Model for MAC Generation Using Direct Injection

This paper presents a model for generating a MAC tag by injecting the input message directly into the internal state of a nonlinear filter generator. This model generalises a similar model for unkeyed hash functions proposed by Nakano et al. We develop a matrix representation for the accumulation phase of our model and use it to analyse the security of the model against man-in-the-middle forgery attacks based on collisions in the final register contents. The results of this analysis show that some conclusions of Nakano et al regarding the security of their model are incorrect. We also use our results to comment on several recent MAC proposals which can be considered as instances of our model and specify choices of options within the model which should prevent the type of forgery discussed here. In particular, suitable initialisation of the register and active use of a secure nonlinear filter will prevent an attacker from finding a collision in the final register contents which could result in a forged MAC.
Harry Bartlett, Mufeed AlMashrafi, Leonie Simpson, Ed Dawson, Kenneth Koon-Ho Wong

Collision Attacks on Variant of OCB Mode and Its Series

Three versions of OCB appeared in the literature: OCB1, OCB2 and OCB3. Ferguson pointed out that OCB1 could not resist against collision attacks, which was improved by Mathiassen. Zhang, Xing and Yang made the first attempt to improve OCB1 against this prevailing attack in blockcipher modes of operation, and proposed a new authenticated encryption mode OCB-ZXY, using offset dependent plaintext block transformation (ODPBT) technique. Our research shows that: 1) OCB-ZXY still cannot resist against collision attacks. 2) OCB2 and OCB3 also suffer from collision attacks, even more severely than OCB1. 3) Even if OCB2 and OCB3 adopt the ODPBT technique, collision attacks still exist.
Zhelei Sun, Peng Wang, Liting Zhang

The Security and Performance of “GCM” when Short Multiplications Are Used Instead

We study the security and performance of an altered Galois/Counter Mode (GCM) of operation. Recent studies (e.g. Krovetz and Rogaway FSE 2011) show that GCM performs rather poorly in modern software implementation because of polynomial hashing in the large field GF(2 n ) (n denotes the block size of the underlying cipher). This paper investigates whether we can use polynomial hashing in the ring GF(2 n/2) X GF(2 n/2) instead. Such a change would normally compromise the level of security down to Θ(2 n/4) Nonetheless, our security proofs show that we can avoid such degradation by masking and then encrypting the hash result, guided by the tentative suggestion made by Ferguson in 2005. We also provide experimental data showing that the modified GCM runs at 1.777 cycles per byte on an Intel Sandy Bridge processor. This makes about 31% reduction from 2.59 cycles per byte of Gueron’s GCM implementation presented at Indocrypt 2011.
Kazumaro Aoki, Kan Yasuda

Estimating Resistance against Multidimensional Linear Attacks: An Application on DEAN

In this paper, we investigate an algorithm which can be used to compute improved estimates of squared correlations of linear approximations over key-alternating block ciphers. The algorithm was previously used by Cho [5] to compute estimates of expected squared correlations and capacities of multidimensional linear approximations of PRESENT. The goal of this paper is to investigate the applicability and usefulness of this algorithm for a nonbinary AES-like symmetric key-alternating block cipher DEAN designed by Baignères et al. [2] who estimated that the best LLR-based distinguisher will require the full code book of about 260 known plaintext blocks to succeed over four rounds of DEAN. We give evidence that there is an LLR-based multidimensional linear distinguisher with estimated data complexity 250 over six rounds of DEAN. Turning this to a (partial) key-recovery attack over the full eight-round DEAN is likely to succeed.
Risto M. Hakala, Atle Kivelä, Kaisa Nyberg

Fast Evaluation of T-Functions via Time-Memory Trade-Offs

We present two low time-cost methods to evaluate arbitrary T-function on k-bit words; both methods use only fast computer instructions (integer addition and/or bitwise logical instructions) and calls to memory. The methods can be applied in a design of T-function-based stream ciphers for fast encryption software in heavy-traffic networks.
Tao Shi, Vladimir Anashin, Dongdai Lin

Construction of Resilient and Nonlinear Boolean Functions with Almost Perfect Immunity to Algebraic and Fast Algebraic Attacks

In this paper, we study a class of Boolean functions with good cryptographic properties. We show that the functions of this class are 1-resilient and have optimal algebraic degree and good nonlinearity. Further, we prove that the functions of this class have at least sub-maximum algebraic immunity. We also check that, at least for small values of the number of variables, the functions of this class have very good nonlinearity, maximum algebraic immunity and almost perfect immunity to fast algebraic attacks.
Tianze Wang, Meicheng Liu, Dongdai Lin

An Improved Time-Memory-Data Trade-Off Attack against Irregularly Clocked and Filtered Keystream Generators

In this paper, we propose a new key recovery attack against irregularly clocked keystream generators, using the approach of time-memory-data trade-offs. The main idea behind our attack is creating several look-up tables and finally recovering the initial states of LFSR d and LFSR c synchronously, by alternatively deriving the initial states of LFSR d and LFSR c along the chains. We show that our attack is more efficient, and improves the previous attacks on the cipher model. Especially, we prove that our attack almost always needs less complexity than that of the normal time-memory-data trade-off attack [3] on the cipher model. We test our attack on LILI-128, and find out that it can successfully break the cipher with 256.6 bit-comparison operations, 249 pairs of 89-bit words memory and 259 keystream bits. This result is better than those in [15,6], which possess the complexity of 262 parity checks and 263 bit operations respectively. Moreover, our attack can be divided and computed in parallel, and the actual runtime of the attack can be reduced depending on the number of computers we access.
Lin Jiao, Mingsheng Wang, Bin Zhang, Yongqiang Li

New Sequences of Period p n and p n  + 1 via Projective Linear Groups

Two pseudorandom number generators are devised based on the projective linear group over \(\mathbb{F}_{p^n}\), outputting balanced sequences on \(\mathbb{F}_{p}\) meeting some statistical randomness properties. Sequences generated by the first generator have least period p n  + 1 if p n  ≥ 7, and linear complexity at least p n  − p n − 1. Furthermore, autocorrelation of such sequences oscillates within a low amplitude except for the trivial peaks. If p n  ∉ {2,4,8,16}, sequences generated by the second generator have least period p n , linear complexity at least p n − 1 + 1, and good k-error linear complexity when p = 2. If p = 2 and 2 n is large enough, then for a binary sequence generated by either generator, a randomly chosen 2-tuple is almost uniformly distributed in {00,01,10,11}, the probability that a randomly chosen 3-tuple is a run of length one is approximately 1/4. For such a binary sequence \(\vec{s}\) and integers 0 < i 1 < i 2 < ⋯ < i k  ≤ m, s(t) + s(t + i 1) + s(t + i 2) + ⋯ + s(t + i k ) is equal to 0 or 1 at almost the same probability when m is far less than 2 n/2.
Lin Wang, Zhi Hu

Touch Gestures Based Biometric Authentication Scheme for Touchscreen Mobile Phones

Nowadays, touchscreen mobile phones make up a larger and larger share in the mobile market. Users also often use their mobile phones (e.g., Android phones) to store personal and sensitive data. It is therefore important to safeguard mobile phones by authenticating legitimate users and detecting impostors. In this paper, we propose a novel user authentication scheme based on touch dynamics that uses a set of behavioral features related to touch dynamics for accurate user authentication. In particular, we construct and select 21 features that can be used for user authentication. To evaluate the performance of our scheme, we collect and analyze touch gesture data of 20 Android phone users by comparing several known machine learning classifiers. The experimental results show that a neural network classifier is well-suited to authenticate different users with an average error rate of about 7.8% for our selected features. Finally, we optimize the neural network classifier by using Particle Swarm Optimization (PSO) to deal with variations in users’ usage patterns. Experimental results show that the average error rate of our optimized scheme is only about 3%, achieved solely by analyzing the touch behavior of users on an Android phone.
Yuxin Meng, Duncan S. Wong, Roman Schlegel, Lam-for Kwok

Secure Product Tracking in Supply Chain

In this paper, we propose a secure and efficient product tracking mechanism implemented using wireless sensor nodes. This mechanism aims at tracking goods, and actions performed by each actor of the supply chain, while preserving the actors’ privacy. Our solution is based on generating identifiers of the actors and their activities using AND Anti collusion codes. The identifiers are encrypted using homomorphic encryption to ensure security against adversaries, and to be able to compress the collected identifiers. In this work, wireless sensor nodes are not required to perform complex computation, which makes our solution feasible.
Mehdi Khalfaoui, Refik Molva, Laurent Gomez

The Bussard-Bagga and Other Distance-Bounding Protocols under Attacks

The communication between an honest prover and an honest verifier can be intercepted by a malicious man-in-the-middle (MiM), without the legitimate interlocutors noticing the intrusion. The attacker can simply relay messages from one party to another, eventually impersonating the prover to the verifier and possibly gaining the privileges of the former. This sort of simple relay attacks are prevalent in wireless communications (e.g., RFID-based protocols) and can affect several infrastructures from contactless payments to remote car-locking systems and access-control verification in high-security areas. As the RFID/NFC technology prevails, a practical and increasingly popular countermeasure to these attacks is given by distance-bounding protocols. Yet, the security of these protocols is still not mature. Importantly, the implications of the return channel (i.e., knowing whether the protocol finished successfully or not) in the security of some distance-bounding protocols have not been fully assessed. In this paper, we demonstrate this by a series of theoretical and practical attacks.
We first show that the Bussard-Bagga protocol DBPK-Log does not fulfill its goal: it offers no protection against distance fraud and terrorist fraud. Then, we show how to mount several concrete MiM attacks against several follow-up variants, including the protocol by Reid et al.
Aslı Bay, Ioana Boureanu, Aikaterini Mitrokotsa, Iosif Spulber, Serge Vaudenay

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise