nach oben

2010 | Buch

Kapitel lesen Erstes Kapitel lesen

Information, Security and Cryptology – ICISC 2009

12th International Conference, Seoul, Korea, December 2-4, 2009, Revised Selected Papers

herausgegeben von: Donghoon Lee, Seokhie Hong

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

ICISC 2009, the 12th International Conference on Information Security and Cryptology, was held in Seoul, Korea, during December 2–4, 2009. It was - ganized by the Korea Institute of Information Security and Cryptology (KIISC) and the Ministry of Public Administration and Security (MOPAS). The aim of this conference was to provide a forum for the presentation of new results in research, development, and applications in the ?eld of information security and cryptology. It also served as a place for research information exchange. The conference received 88 submissions from 22 countries, covering all areas of inf- mation security and cryptology. The review and selection processes were carried out in two stages by the Program Committee (PC) comprising 57 prominent - searchers via online meetings. First, at least three PC members blind-reviewed each paper, and papers co-authored by the PC members were reviewed by at least ?ve PC members. Second, individual review reports were revealed to PC members, and detailed interactive discussion on each paper followed. Through this process,thePC?nally selected 25papers from15countries. The acceptance rate was 28. 4%. The authors of selected papers had a few weeks to prepare for their ?nal versions based on the comments received from more than 80 ext- nal reviewers. The conference featured one tutorial and one invited talk. The tutorial was given by Amit Sahai from the University of California and the talk ´ was given by Michel Abdalla from Ecole normale sup´ erieure.

Inhaltsverzeichnis

Frontmatter

Key Management and Key Exchange

Generic One Round Group Key Exchange in the Standard Model

Abstract

Minimizing complexity of group key exchange (GKE) protocols is an important milestone towards their practical deployment. An interesting approach to achieve this goal is to simplify the design of GKE protocols by using generic building blocks. In this paper we investigate the possibility of founding GKE protocols based on a primitive called multi key encapsulation mechanism (mKEM) and describe advantages and limitations of this approach. In particular, we show how to design a one-round GKE protocol which satisfies the classical requirement of authenticated key exchange (AKE) security, yet without forward secrecy. As a result, we obtain the first one-round GKE protocol secure in the standard model. We also conduct our analysis using recent formal models that take into account both outsider and insider attacks as well as the notion of key compromise impersonation resilience (KCIR). In contrast to previous models we show how to model both outsider and insider KCIR within the definition of mutual authentication. Our analysis additionally implies that the insider security compiler by Katz and Shin from ACM CCS 2005 can be used to achieve more than what is shown in the original work, namely both outsider and insider KCIR.

M. Choudary Gorantla, Colin Boyd, Juan Manuel González Nieto, Mark Manulis

Modeling Leakage of Ephemeral Secrets in Tripartite/Group Key Exchange

Abstract

Recent advances in the design and analysis of secure two-party key exchange (2KE) such as the leakage of ephemeral secrets used during the attacked sessions remained unnoticed by the current models for group key exchange (GKE). Focusing on a special case of GKE — the tripartite key exchange (3KE) — that allows for efficient one-round protocols, we demonstrate how to incorporate these advances to the multi-party setting. From this perspective our work closes the most pronounced gap between provably secure 2KE and GKE protocols.

The proposed 3KE protocol is an implicitly authenticated protocol with one communication round which remains secure even in the event of ephemeral secret leakage. It also significantly improves upon currently known 3KE protocols, many of which are insecure. An optional key confirmation round can be added to our proposal to achieve the explicitly authenticated protocol variant.

Mark Manulis, Koutarou Suzuki, Berkant Ustaoglu

Efficient Certificateless KEM in the Standard Model

Abstract

We give a direct construction of a certificateless key encapsulation mechanism (KEM) in the standard model that is more efficient than the generic constructions proposed before by Huang and Wong [9]. We use a direct construction from Kiltz and Galindo’s KEM scheme [10] to obtain a certificateless KEM in the standard model; our construction is roughly twice as efficient as the generic construction.

Georg Lippold, Colin Boyd, Juan Manuel González Nieto

Public Key Cryptography

Accelerating Twisted Ate Pairing with Frobenius Map, Small Scalar Multiplication, and Multi-pairing

Abstract

In the case of Barreto-Naehrig pairing-friendly curves of embedding degree 12 of order r, recent efficient Ate pairings such as R-ate, optimal, and Xate pairings achieve Miller loop lengths of \((1/4)\lfloor \log_2 r\rfloor\). On the other hand, the twisted Ate pairing requires \((3/4) \lfloor \log_2 r\rfloor\) loop iterations, and thus is usually slower than the recent efficient Ate pairings. This paper proposes an improved twisted Ate pairing using Frobenius maps and a small scalar multiplication. The proposal splits the Miller’s algorithm calculation into several independent parts, for which multi-pairing techniques apply efficiently. The maximum number of loop iterations in Miller’s algorithm for the proposed twisted Ate pairing is equal to the \((1/4) \lfloor \log_2 r \rfloor\) attained by the most efficient Ate pairings.

Yumi Sakemi, Shoichi Takeuchi, Yasuyuki Nogami, Yoshitaka Morikawa

Factoring Unbalanced Moduli with Known Bits

Abstract

Let n = pq > q ³ be an rsa modulus. This note describes a lll-based method allowing to factor n given 2log₂ q contiguous bits of p, irrespective to their position. A second method is presented, which needs fewer bits but whose length depends on the position of the known bit pattern. Finally, we introduce a somewhat surprising ad hoc method where two different known bit chunks, totalling \(\frac{3}{2}\log_2 q\) bits suffice to factor n.

The technique underlines the danger of using unbalanced moduli on leaky hardware implementations.

Eric Brier, David Naccache, Mehdi Tibouchi

Algebraic Cryptanalysis and Stream Cipher

Algebraic Cryptanalysis of SMS4: Gröbner Basis Attack and SAT Attack Compared

Abstract

The SMS4 block cipher is part of the Chinese WAPI wireless standard. This paper describes the specification and offers a specification for a toy version called simplified SMS4 (S-SMS4). We explore algebraic attacks on SMS4 and S-SMS4 using Gröbner basis attacks on equation systems over GF(2) and GF(2⁸), as well as attacks using a SAT solver derived from the GF(2) model. A comparison of SAT and Gröbner basis attacks is provided.

Jeremy Erickson, Jintai Ding, Chris Christensen

MXL3: An Efficient Algorithm for Computing Gröbner Bases of Zero-Dimensional Ideals

Abstract

This paper introduces a new efficient algorithm, called MXL₃, for computing Gröbner bases of zero-dimensional ideals. The MXL₃ is based on XL algorithm, mutant strategy, and a new sufficient condition for a set of polynomials to be a Gröbner basis. We present experimental results comparing the behavior of MXL₃ to F₄ on HFE and random generated instances of the MQ problem. In both cases the first implementation of the MXL₃ algorithm succeeds faster and uses less memory than Magma’s implementation of F₄.

Mohamed Saied Emam Mohamed, Daniel Cabarcas, Jintai Ding, Johannes Buchmann, Stanislav Bulygin

Improved Linear Cryptanalysis of SOSEMANUK

Abstract

The SOSEMANUK stream cipher is one of the finalists of the eSTREAM project. In this paper, we improve the linear cryptanalysis of SOSEMANUK presented in Asiacrypt 2008. We apply the generalized linear masking technique to SOSEMANUK and derive many linear approximations holding with the correlations of up to 2^− 25.5. We show that the data complexity of the linear attack on SOSEMANUK can be reduced by a factor of 2¹⁰ if multiple linear approximations are used. Since SOSEMANUK claims 128-bit security, our attack would not be a real threat on the security of SOSEMANUK.

Joo Yeon Cho, Miia Hermelin

Security Management and Efficient Implementation

Serial Model for Attack Tree Computations

Abstract

In this paper we extend the standard attack tree model by introducing temporal order to the attacker’s decision making process. This will allow us to model the attacker’s behaviour more accurately, since this way it is possible to study his actions related to dropping some of the elementary attacks due to them becoming obsolete based on the previous success/failure results. We propose an efficient algorithm for computing the attacker’s expected outcome based on the given order of the elementary attacks and discuss the pros and cons of considering general rooted directed acyclic graphs instead of plain trees as the foundations for attack modelling.

Aivo Jürgenson, Jan Willemson

Lightweight Cryptography and RFID: Tackling the Hidden Overheads

Abstract

The field of lightweight cryptography has developed significantly over recent years and many impressive implementation results have been published. However these results are often concerned with a core computation and when it comes to a real implementation there can be significant hidden overheads. In this paper we consider the case of cryptoGPS and we outline a full implementation that has been fabricated in ASIC. Interestingly, the implementation requirements still remain within the typically-cited limits for on-the-tag cryptography.

Axel Poschmann, Matt Robshaw, Frank Vater, Christof Paar

Side Channel Attack

Power Analysis of Single-Rail Storage Elements as Used in MDPL

Abstract

Several dual-rail logic styles make use of single-rail flip-flops for storing intermediate states. We show that single mask bits, as applied by various side-channel resistant logic styles such as MDPL and iMDPL, are not sufficient to obfuscate the remaining leakage of single-rail flip-flops.

By applying simple models for the leakage of masked flip-flops, we design a new attack on circuits implemented using masked single-rail flip-flops. Contrary to previous attacks on masked logic styles, our attack does not predict the mask bit and does not need detailed knowledge about the attacked device, e.g., the circuit layout. Moreover, our attack works even if all the load capacitances of the complementary signals are perfectly balanced and even if the PRNG is ideally unbiased. Finally, after performing the attack on DRSL, MDPL, and iMDPL circuits we show that single-bit masks do not influence the exploitability of the revealed leakage of the masked flip-flops.

Amir Moradi, Thomas Eisenbarth, Axel Poschmann, Christof Paar

A Timing Attack against Patterson Algorithm in the McEliece PKC

Abstract

The security of McEliece public-key cryptosystem is based on the difficulty of the decoding problem which is NP-hard. In this paper we propose a timing attack on the Patterson Algorithm, which is used for efficient decoding in Goppa codes. The attack is based on the relation between the error vector weight and the iteration number of the extended Euclidean algorithm used in Patterson Algorithm. This attack enables the extraction of the secret error vector with minimal overhead. A countermeasure is proposed and verified for a FPGA implementation.

Abdulhadi Shoufan, Falko Strenzke, H. Gregor Molter, Marc Stöttinger

Side-Channel Analysis of Cryptographic Software via Early-Terminating Multiplications

Abstract

The design of embedded processors demands a careful trade-off between many conflicting objectives such as performance, silicon area and power consumption. Finding such a trade-off often ignores the issue of security, which can cause, otherwise secure, cryptographic software to leak information through so-called micro-architectural side channels. In this paper we show that early-terminating integer multipliers found in various embedded processors (e.g., ARM7TDMI) represent an instance of this problem. The early-termination mechanism causes differences in the time taken to execute a multiply instruction depending on the magnitude of the operands (e.g., up to three clock cycles on an ARM7TDMI processor), which are observable via variations in execution time and power consumption. Exploiting the early-termination mechanism makes Simple Power Analysis (SPA) attacks relatively straightforward to conduct, and may even allow one to attack implementations with integrated countermeasures that would not leak any information when executed on a processor with a constant-latency multiplier. We describe several case studies, including both secret-key (RC6, AES) and public-key algorithms (RSA, ECIES) to demonstrate the threat posed by embedded processors with early-terminating multipliers.

Johann Großschädl, Elisabeth Oswald, Dan Page, Michael Tunstall

Privacy Enhanced Technology

First CPIR Protocol with Data-Dependent Computation

Abstract

We design a new (n, 1)-CPIR protocol BddCpir for ℓ-bit strings as a combination of a noncryptographic (BDD-based) data structure and a more basic cryptographic primitive (communication-efficient (2, 1)-CPIR). BddCpir is the first CPIR protocol where server’s online computation depends substantially on the concrete database. We then show that (a) for reasonably small values of ℓ, BddCpir is guaranteed to have simultaneously log-squared communication and sublinear online computation, and (b) BddCpir can handle huge but sparse matrices, common in data-mining applications, significantly more efficiently compared to all previous protocols. The security of BddCpir can be based on the well-known Decisional Composite Residuosity assumption.

Helger Lipmaa

Efficient Fuzzy Matching and Intersection on Private Datasets

Abstract

At Eurocrypt’04, Freedman, Nissim and Pinkas introduced a fuzzy private matching problem. The problem is defined as follows. Given two parties, each of them having a set of vectors where each vector has T integer components, the fuzzy private matching is to securely test if each vector of one set matches any vector of another set for at least t components where t < T. In the conclusion of their paper, they asked whether it was possible to design a fuzzy private matching protocol without incurring a communication complexity with the factor \(T \choose t\). We answer their question in the affirmative by presenting a protocol based on homomorphic encryption, combined with the novel notion of a share-hiding error-correcting secret sharing scheme, which we show how to implement with efficient decoding using interleaved Reed-Solomon codes. This scheme may be of independent interest. Our protocol is provably secure against passive adversaries, and has better efficiency than previous protocols for certain parameter values.

Qingsong Ye, Ron Steinfeld, Josef Pieprzyk, Huaxiong Wang

Efficient Privacy-Preserving Face Recognition

Abstract

Automatic recognition of human faces is becoming increasingly popular in civilian and law enforcement applications that require reliable recognition of humans. However, the rapid improvement and widespread deployment of this technology raises strong concerns regarding the violation of individuals’ privacy. A typical application scenario for privacy-preserving face recognition concerns a client who privately searches for a specific face image in the face image database of a server.

In this paper we present a privacy-preserving face recognition scheme that substantially improves over previous work in terms of communication-and computation efficiency: the most recent proposal of Erkin et al. (PETS’09) requires \(\mathcal{O}(\log M)\) rounds and computationally expensive operations on homomorphically encrypted data to recognize a face in a database of M faces. Our improved scheme requires only \(\mathcal{O}(1)\) rounds and has a substantially smaller online communication complexity (by a factor of 15 for each database entry) and less computation complexity.

Our solution is based on known cryptographic building blocks combining homomorphic encryption with garbled circuits. Our implementation results show the practicality of our scheme also for large databases (e.g., for M = 1000 we need less than 13 seconds and less than 4 MByte online communication on two 2.4GHz PCs connected via Gigabit Ethernet).

Ahmad-Reza Sadeghi, Thomas Schneider, Immo Wehrenberg

Cryptographic Protocol

Linear, Constant-Rounds Bit-Decomposition

Abstract

When performing secure multiparty computation, tasks may often be simple or difficult depending on the representation chosen. Hence, being able to switch representation efficiently may allow more efficient protocols.

We present a new protocol for bit-decomposition: converting a ring element x ∈ ℤ_M to its binary representation, x _{(logM) − 1},...,x ₀. The protocol can be based on arbitrary secure arithmetic in ℤ_M; this is achievable for Shamir shared values as well as (threshold) Paillier encrypted ones, implying solutions for both these popular MPC primitives. For additively homomorphic primitives (which is typical, and the case for both examples) the solution is constant-rounds and requires only O(logM) secure ring multiplications.

The solution is secure against active adversaries assuming the existence of additional primitives. These exist for both the Shamir sharing based approach as well as the Paillier based one.

Tord Reistad, Tomas Toft

Attacking and Repairing the Improved ModOnions Protocol

Abstract

In this paper, we present a new class of attacks against an anonymous communication protocol, originally presented in ACNS 2008. The protocol itself was proposed as an improved version of ModOnions, which uses universal re-encryption in order to avoid replay attacks. However, ModOnions allowed the detour attack, introduced by Danezis to re-route ModOnions to attackers in such a way that the entire path is revealed. The ACNS 2008 proposal addressed this by using a more complicated key management scheme. The revised protocol is immune to detour attacks. We show, however, that the ModOnion construction is highly malleable and this property can be exploited in order to redirect ModOnions. Our attacks require detailed probing and are less efficient than the detour attack, but they can nevertheless recover the full onion path while avoiding detection and investigation. Motivated by this, we present a new modification to the ModOnion protocol that dramatically reduces the malleability of the encryption primitive. It addresses the class of attacks we present and it makes other attacks difficult to formulate.

Nikita Borisov, Marek Klonowski, Mirosław Kutyłowski, Anna Lauks-Dutka

Secret Handshakes with Revocation Support

Abstract

Revocation of credentials in Secret Handshakes is a difficult challenge, as it mixes the conflicting requirements of tracing revoked users and of the untraceability and unlinkability of legitimate protocol players. The schemes proposed in the literature are either limited versions of secret handshake supporting revocation, or they support more complete versions of secret handshake with no possibility of introducing revocation. In this paper we present a simple protocol that allows a user to prove to a verifier possession of a credential. Credentials can be revoked simply by publishing a value in a revocation list. This protocol is extremely flexible, as with it, we can achieve revocation for each of the different nuances of Secret Handshakes known in the literature. We prove the security of the new scheme without random oracles.

Alessandro Sorniotti, Refik Molva

Cryptanalysis of Hash Function

Practical Rebound Attack on 12-Round Cheetah-256

Abstract

In this paper, we propose cryptanalysis of the hash function Cheetah-256. Cheetah is accepted as a first round candidate of SHA-3 competition hosted by NIST [1], but it is not in the second round.

First, we discuss relation between degrees of freedom injected from round message blocks and round number of a pseudo-collision attack on hash functions with S boxes and MDS diffusion. A pseudo-collision attack on 8-round Cheetah-256 can be derived by trivially applying original rebound techniques.

Then, we propose a rebound differential path for semi-free start collision attack on 12-round Cheetah-256 and an observation of the neutral bytes’ influence on state values. Based on this observation, algebraic message modifications are designed using the neutral bytes and total complexity is reduced to 2²⁴. This is a practical rebound attack.

Shuang Wu, Dengguo Feng, Wenling Wu

Preimage Attacks on Reduced Steps of ARIRANG and PKC98-Hash

Abstract

In this paper, we present the preimage attacks on step-reduced ARIRANG and PKC98-Hash. Our attacks find the preimages of 35 steps out of 40 steps of ARIRANG and 80 steps out of 96 steps of PKC98-Hash, faster than the brute force attack. We applied recently developed techniques of preimage attack. Our attack for ARIRANG is the improvement of the previous attack, and our attack for PKC98-hash is the first analysis result of its preimage resistance.

Deukjo Hong, Bonwook Koo, Woo-Hwan Kim, Daesung Kwon

Improved Preimage Attack for 68-Step HAS-160

Abstract

In this paper, we improve previous preimage attacks on hash function HAS-160, which is standardized in Korea. We show that the last 68 steps out of 80 steps of HAS-160 can be attacked, while a previous attack works for only intermediate 52 steps. We also show that the first 67 steps of HAS-160 can be attacked. These attacks are based on the meet-in-the-middle attack, which is also used in the previous attack. Recently, various techniques of preimage attacks have been proposed on other hash functions. We show that these techniques can also be applied to HAS-160 and the number of attacked steps can be improved. For the attack on 68 steps, we first generate pseudo-preimages with a complexity of 2^150.7, and then convert them to a preimage with a complexity of 2^156.3. This attack uses a memory of 2¹² ×7 words. To the best of our knowledge, attacking 68 steps is the best of all attacks on HAS-160 hash function.

Deukjo Hong, Bonwook Koo, Yu Sasaki

Distinguishing Attack on Secret Prefix MAC Instantiated with Reduced SHA-1

Abstract

In this paper, we present a new distinguishing attack which works for secret prefix MAC based on 65-step (12-76) SHA-1. By birthday paradox, we first guarantee the existence of an internal collision at the output of the first iteration, then identify it by choosing the second message block smartly, and finally distinguish the specific MAC from a random function by making use of a near-collision differential path. The complexity of our new distinguisher is 2^80.9 queries with success probability 0.51. In comparison, we also present a distinguisher on secret prefix MAC instantiated with 63-step (8-70) SHA-1 according to Wang’s method introduced at FSE 2009 [21], which needs about 2¹⁵⁷ queries with success probability 0.70.

Siyuan Qiao, Wei Wang, Keting Jia

Network Security

Cryptanalysis of a Message Recognition Protocol by Mashatan and Stinson

Abstract

At CANS 2008, Mashatan and Stinson suggested a message recognition protocol for ad hoc pervasive networks. The protocol provides a procedure to resynchronize in case of a (possibly adversarial) disruption of communication. We show that this resynchronization process does not provide the functionality intended and in fact enables an adversary to create selective forgeries. The computational effort for the attack is negligible and allows the insertion of arbitrary messages.

Madeline González Muñiz, Rainer Steinwandt

Analysis of the Propagation Pattern of a Worm with Random Scanning Strategy Based on Usage Rate of Network Bandwidth

Abstract

There have been many studies on modeling the propagation patterns of Internet worms since the advent of Morris worm. Among them, there is a well defined propagation model, which is generally called random constant spread (RCS) model. However, there are some limitations to model the propagation patterns of new emergent Internet worms with the RCS model because the model uses the only number of infected hosts as the factor of a worm’s propagation. The new worms have several considerable characteristics: utilization of a faster scanning strategy, miniaturization of the size of a worm’s propagation packet, denial of service by network saturation, and maximum damage before human-mediated responses. These characteristics make it difficult to notice much harder than before whether a worm propagates itself or not. Therefore, a basic factor instead of the number of infected hosts, which is used by the RCS model, is required to model the propagation patterns of new worms. In this paper, only analysis and simulation results based on usage rate of network bandwidth, which can be considered as a basic factor, are presented about the propagation pattern of a worm with random scanning strategy. Miniaturization of the size of a propagation packet and utilization of a faster scanning strategy are related to the size of worm’s propagation packet and its propagation rate, respectively. It is presented that the latter is more sensitive than the former.

Kwang Sun Ko, Hyunsu Jang, Byuong Woon Park, Young Ik Eom

Backmatter

Titel: Information, Security and Cryptology – ICISC 2009
herausgegeben von: Donghoon Lee
Seokhie Hong
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-14423-3
Print ISBN: 978-3-642-14422-6
DOI: https://doi.org/10.1007/978-3-642-14423-3