Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2010 | Book

Cryptanalysis of Reduced-Round MIBS Block Cipher Read chapter Read first chapter

Cryptology and Network Security

9th International Conference, CANS 2010, Kuala Lumpur, Malaysia, December 12-14, 2010. Proceedings

Editors: Swee-Huay Heng, Rebecca N. Wright, Bok-Min Goi

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

The 9th International Conference on Cryptology and Network Security (CANS 2010) was held in Kuala Lumpur, Malaysia during December 12–14, 2010. The conference was co-organized by the Multimedia University (MMU), Malaysia, and Universiti Tunku Abdul Rahman (UTAR), Malaysia. The conference received 64 submissions from 22 countries, out of which 21 were accepted after a careful and thorough review process. These proceedings also contain abstracts for two invited talks. All submissions were reviewed by at least three members of the Program Committee; those authored or co-authored by Program Committee members were reviewed by at least ?ve reviewers. P- gram Committee members were allowed to use external reviewers to assist with their reviews, but remained responsible for the contents of the review and r- resenting papers during the discussion and decision making. The review phase was followed by a 10-day discussion phase in which each paper with at least one supporting review was discussed, additional experts were consulted where needed, and ?nal decisions were made. We thank the Program Committee for their hard work in selecting the p- gram. We also thank the external reviewers who assisted with reviewing and the CANS Steering Committee for their help. We thank Shai Halevi for use of his Web-Submission-and-Review software that was used for the electronic s- mission and review of the submitted papers, and we thank the International Association for Cryptologic Research (IACR) for Web hosting of the software.

Table of Contents

Frontmatter

Block Ciphers

Cryptanalysis of Reduced-Round MIBS Block Cipher
Abstract
This paper presents the first independent and systematic linear, differential and impossible-differential (ID) cryptanalyses of MIBS, a lightweight block cipher aimed at constrained devices such as RFID tags and sensor networks. Our contributions include linear attacks on up to 18-round MIBS, and the first ciphertext-only attacks on 13-round MIBS. Our differential analysis reaches 14 rounds, and our impossible-differential attack reaches 12 rounds. These attacks do not threaten the full 32-round MIBS, but significantly reduce its margin of security by more than 50%. One fact that attracted our attention is the striking similarity of the round function of MIBS with that of the Camellia block cipher. We actually used this fact in our ID attacks. We hope further similarities will help build better attacks for Camellia as well.
Asli Bay, Jorge Nakahara Jr., Serge Vaudenay
Impossible Differential Cryptanalysis of ARIA Reduced to 7 Rounds
Abstract
This paper studies the security of the block cipher ARIA against impossible differential cryptanalysis. We find a new impossible differential property of ARIA, and propose an attack against ARIA-256 reduced to 7 rounds based on this property, while previous attacks can only attack ARIA up to 6 rounds. Our new attack needs 2125 chosen plaintexts and 2238 7-round encryptions. This is the best result for impossible differential cryptanalysis of ARIA known so far.
Chenghang Du, Jiazhe Chen
An Algorithm Based Concurrent Error Detection Scheme for AES
Abstract
With the wide-spread practical applications of AES, not only high performance, but also strong reliability is desirable to all the cryptosystem. In this paper, a lightweight concurrent AES error detection scheme which is based on the algorithm based fault tolerant (ABFT) technique is proposed. Two versions of scheme are presented to satisfy different application requirements. The first general version scheme can detect single error for the whole AES process with high efficiency. Another run-time version scheme is used to immediately end the error round with no time delay and no computation wasted on the rest rounds for propagating errors. Utilizing the ready-made arithmetic units in AES, single error can be detected by the sender and prevent the misdirected information from sending out. The results of the hardware FPGA implementation and simulation show that the proposed scheme can be integrated both on software and hardware without making many changes to the original AES implementation.
Chang N. Zhang, Qian Yu, Xiao Wei Liu

Invited Talk I

Cryptography for Unconditionally Secure Message Transmission in Networks (Invited Talk)
Abstract
We consider the model of unconditionally secure (r-round, n-channel) message transmission schemes which was introduced by Dolev et al. [1]. In this model, there are n channels between a sender and a receiver, and an infinitely powerful adversary A may corrupt (observe and forge) the messages sent through t out of n channels. The sender wishes to send a secret s to the receiver in r-round without sharing any key with the receiver.
Kaoru Kurosawa

Wireless Network Security

Performance and Security Aspects of Client-Side SSL/TLS Processing on Mobile Devices
Abstract
The SSL/TLS protocol is the de-facto standard for secure Internet communications, and supported by virtually all modern e-mail clients and Web browsers. With more and more PDAs and cell phones providing wireless e-mail and Web access, there is an increasing demand for establishing secure SSL/TLS connections on devices that are relatively constrained in terms of computational resources. In addition, the cryptographic primitives executed on the client side need to be protected against side-channel analysis since, for example, an attacker may be able to monitor electromagnetic emanations from a mobile device. Using an RSA-based cipher suite has the advantage that all modular exponentiations on the client side are carried out with public exponents, which is uncritical regarding performance and side-channel leakage. However, the current migration to AES-equivalent security levels makes a good case for using an Elliptic Curve Cryptography (ECC)-based cipher suite. We show in this paper that, for high security levels, ECC-based cipher suites outperform their RSA counterparts on the client side, even though they require the integration of diverse countermeasures against side-channel attacks. Furthermore, we propose a new countermeasure to protect the symmetric encryption of messages (i.e. “bulk data”) against Differential Power Analysis (DPA) attacks. This new countermeasure, which we call Inter-Block Shuffling (IBS), is based on an “interleaved” encryption of a number of data blocks using a non-feedback mode of operation (such as counter mode), and randomizes the order in which the individual rounds of the individual blocks are executed. Our experimental results indicate that IBS is a viable countermeasure as it provides good DPA-protection at the expense of a slight degradation in performance.
Johann Großschädl, Ilya Kizhvatov
A Practical Cryptographic Denial of Service Attack against 802.11i TKIP and CCMP
Abstract
This paper proposes a highly efficient cryptographic denial of service attack against 802.11 networks using 802.11i TKIP and CCMP. The attacker captures one frame, then modifies and transmits it twice to disrupt network access for 60 seconds. We analyze, implement and experimentally validate the attack. We also propose a robust solution and recommendations for network administrators.
Martin Eian
User Tracking Based on Behavioral Fingerprints
Abstract
The pervasiveness of wireless communications networks is advancing particularly in metropolitan areas. Broadband computer networks as IEEE 802.11 are seriously competing with cellular network technologies such as UMTS and HSDPA. Unfortunately, this increased mobility comes with privacy and security related issues. We are currently in the process of identifying possible attacks on the privacy of wireless network users, since the development of effective countermeasures is only possible with a thorough understanding of such attacks.
One serious threat we are discussing here, is the tracking of users in metropolitan networks by means of determining their physical location. Any individual user can be identified either by the devices she is using or by the behavior she is displaying. Suitable features range from single identifiers such as IP or MAC addresses to complex conglomerates of different values that provide valuable information due to their combination.
This article focuses on the extraction and analysis of features that are valuable for fingerprinting by employing Activation Patterns, a concept based on artificial intelligence and machine learning techniques. The concept is applied to email header data, since this allows for an effective illustration of the employed techniques. Furthermore, due to the human understandable data, we can easily evaluate the effectiveness of the concept before we start to analyze more complex data-sets.
Günther Lackner, Peter Teufl, Roman Weinberger

Hash Functions

On the Collision and Preimage Resistance of Certain Two-Call Hash Functions
Abstract
In this paper we present concrete collision and preimage attacks on a large class of compression function constructions making two calls to the underlying ideal primitives. The complexity of the collision attack is above the theoretical lower bound for constructions of this type, but below the birthday complexity; the complexity of the preimage attack, however, is equal to the theoretical lower bound.
We also present undesirable properties of some of Stam’s compression functions proposed at CRYPTO ’08. We show that when one of the n-bit to n-bit components of the proposed 2n-bit to n-bit compression function is replaced by a fixed-key cipher in the Davies-Meyer mode, the complexity of finding a preimage would be 2 n/3. We also show that the complexity of finding a collision in a variant of the 3n-bits to 2n-bits scheme with its output truncated to 3n/2 bits is 2 n/2. The complexity of our preimage attack on this hash function is about 2 n . Finally, we present a collision attack on a variant of the proposed m + s-bit to s-bit scheme, truncated to s − 1 bits, with a complexity of O(1). However, none of our results compromise Stam’s security claims.
Nasour Bagheri, Praveen Gauravaram, Majid Naderi, Søren S. Thomsen
Integral Distinguishers of Some SHA-3 Candidates
Abstract
In this paper, we study structural Integral properties on reduced versions of the compression functions of some SHA-3 candidates: Hamsi-256, LANE-256 and Grøstl-512. More precisely, we improve on the Integral distinguishers of Hamsi-256 (less time complexity or deterministic instead of probabilistic) and present the first known Integral distinguishers for LANE-256 and improved Integral distinguisher for Groestl-512. Whereas the SHA-3 competition focuses the cryptographic world attention on the design and the attacks of hash functions, results in this paper analyze the resistance of some SHA-3 candidates against structural properties built on Integral distinguishers.
Marine Minier, Raphael C. -W. Phan, Benjamin Pousse
Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE
Abstract
The SHA-3 competition organized by NIST [1] aims to find a new hash standard as a replacement of SHA-2. Till now, 14 submissions have been selected as the second round candidates, including Skein and BLAKE, both of which have components based on modular addition, rotation and bitwise XOR (ARX). In this paper, we propose improved near-collision attacks on the reduced-round compression functions of Skein and BLAKE. The attacks are based on linear differentials of the modular additions. The computational complexity of near-collision attacks on a 4-round compression function of BLAKE-32, 4-round and 5-round compression functions of BLAKE-64 are 221, 216 and 2216 respectively, and the attacks on 20-round compression functions of Skein-256, Skein-512 and a 24-round compression function of Skein-1024 have a complexity of 297, 252 and 2452 respectively.
Bozhan Su, Wenling Wu, Shuang Wu, Le Dong

Public Key Cryptography

Practical Algebraic Cryptanalysis for Dragon-Based Cryptosystems
Abstract
Recently, the Little Dragon Two and Poly-Dragon multivariate based public-key cryptosystems were proposed as efficient and secure schemes. In particular, the inventors of the two schemes claim that Little Dragon Two and Poly-Dragon resist algebraic cryptanalysis. In this paper, we show that MXL2, an algebraic attack method based on the XL algorithm and Ding’s concept of Mutants, is able to break Little Dragon Two with keys of length up to 229 bits and Poly-Dragon with keys of length up to 299. This contradicts the security claim for the proposed schemes and demonstrates the strength of MXL2 and the Mutant concept. This strength is further supported by experiments that show that in attacks on both schemes the MXL2 algorithm outperforms the Magma’s implementation of F4.
Johannes Buchmann, Stanislav Bulygin, Jintai Ding, Wael Said Abd Elmageed Mohamed, Fabian Werner
Generating Parameters for Algebraic Torus-Based Cryptosystems
Abstract
Algebraic torus-based cryptosystems are public key cryptosystems based on the discrete logarithm problem, and have compact expressions compared with those of finite field-based cryptosystems. In this paper, we propose parameter selection criteria for the algebraic torus-based cryptosystems from the viewpoints of security and efficiency. The criteria include the following conditions: consistent resistance to attacks on algebraic tori and their embedding fields, and a large degree of freedom to select parameters suitable for each implementation. An extension degree and a characteristic size of a finite field on which the algebraic tori are defined are adjustable. We also provide examples of parameters satisfying the criteria.
Tomoko Yonemura, Yoshikazu Hanatani, Taichi Isogai, Kenji Ohkuma, Hirofumi Muratani
Analysis of the MQQ Public Key Cryptosystem
Abstract
MQQ is a multivariate public key cryptosystem (MPKC) based on multivariate quadratic quasigroups and a special transform called “Dobbertin transformation” [17]. The security of MQQ, as well as any MPKC, reduces to the difficulty of solving a non-linear system of equations easily derived from the public key. In [26], it has been observed that that the algebraic systems obtained are much easier to solve that random non-linear systems of the same size. In this paper we go one step further in the analysis of MQQ. We explain why systems arising in MQQ are so easy to solve in practice. To do so, we consider the so-called the degree of regularity; which is the exponent in the complexity of a Gröbner basis computation. For MQQ systems, we show that this degree is bounded from above by a small constant. This is due to the fact that the complexity of solving the MQQ system is the minimum complexity of solving just one quasigroup block or solving the Dobbertin transformation. Furthermore, we show that the degree of regularity of the Dobbertin transformation is bounded from above by the same constant as the bound observed on MQQ system. We then investigate the strength of a tweaked MQQ system where the input of the Dobbertin transformation is replaced with random linear equations. It appears that the degree of regularity of this tweaked system varies both with the size of the quasigroups and the number of variables. We conclude that if a suitable replacement for the Dobbertin transformation is found, MQQ can possibly be made strong enough to resist pure Gröbner attacks for adequate choices of quasigroup size and number of variables.
Jean-Charles Faugère, Rune Steinsmo Ødegård, Ludovic Perret, Danilo Gligoroski
Efficient Scalar Multiplications for Elliptic Curve Cryptosystems Using Mixed Coordinates Strategy and Direct Computations
Abstract
Scalar multiplication is the heart of elliptic curve cryptosystems. Several techniques have been proposed for efficient scalar multiplication. Mixed coordinate strategy is a useful technique for implementing efficient scalar multiplication. It splits a scalar multiplication into a few parts, and performs each part in the best coordinate. Also, the running time of scalar multiplication can be reduced by applying direct computations in the evaluation stage. This technique directly computes points of the form 2P + Q from points P and Q on the elliptic curve. In this paper, we apply mixed coordinate strategy and direct computations to various scalar multiplication algorithms such as binary method, NAF and window NAF methods, MOF and window MOF methods to find the best combinations of mixed coordinates strategy and direct computations for scalar multiplication with respect to the computational costs and memory consumption.
Roghaie Mahdavi, Abolghasem Saiadian

Invited Talk II

Cryptography Meets Hardware: Selected Topics of Hardware-Based Cryptography (Invited Talk)
Abstract
Modern cryptography provides a variety of methods and protocols that allow different entities to collaborate securely without mutual trust, and hence constitutes the basic technology for a wide range of security and privacy critical applications. However, even the most basic cryptographic functionalities such as commitments, oblivious transfer, or set intersection require computationally expensive public key cryptography when implemented in software only, and their secure universal composition cannot be achieved without additional setup assumptions.
Ahmad-Reza Sadeghi

Secure Mechanisms

Towards a Cryptographic Treatment of Publish/Subscribe Systems
Abstract
Publish/subscribe mechanism is a typical many-to-many messaging paradigm when multiple applications want to receive the same message or when a group of applications want to notify each other. Nonetheless, there exist only a few works that deal with this topic formally, in particular addressing their security issues. Although security issues and requirements for content-based publish/subscribe systems have been partially addressed by Wang et al., there are no formal definition for all of these security requirements in the literature. As a result, most of the existing schemes do not have any security proof and there is no way to justify whether those schemes are really secure or not in practice. Furthermore, there is no comprehensive scheme that satisfies the most essential security requirements at the same time. In this paper, for the first time in the literature, we introduce the security model for all security requirements of content-based publish/subscribe systems. We then exhibit a new publish/subscriber system that fulfills most of the security requirements. Furthermore, we also provide a comprehensive proof for our concrete construction according to the new model.
Tsz Hon Yuen, Willy Susilo, Yi Mu
STE3D-CAP: Stereoscopic 3D CAPTCHA
Abstract
We present STE3D-CAP (pronounced as “steed-cap” /’stidkæp/), a text-based CAPTCHA that is built from stereoscopic 3D images. This is a completely new direction in CAPTCHA techniques. Our idea is to incorporate stereoscopic 3D images in order to present the CAPTCHA challenge in 3D, which will be easy for humans to read (as the text stands out in the 3D scene) but hard for computers. The main idea is to produce a stereo pair, two images of the distorted 3D text objects generated from two different camera/eye viewpoints, that are presented to a human user’s left and right eyes, respectively. When the two images are supplied to hardware capable of displaying stereoscopic 3D images, the resulting CAPTCHA can easily be solved by humans, as the text will appear to stand out from the rest of the scene, but computers will not be able to solve them easily. As per the usual practice, the text in the produced images will be distorted (e.g. translated, scaled, warped) and overlapped but additionally the depth of the 3D text objects in the stereoscopic images will add a degree of complexity to the CAPTCHA and make it harder for CAPTCHA attacks (due to positive and negative parallax in the stereo pair). We demonstrate that the existing attacks on STE3D-CAP will fail with an overwhelming probability and that we can increase our CAPTCHA’s resistance to segmentation attacks whilst maintaining usability. We also note that our technique is applicable to other stereoscopic approaches, such as anaglyph.
Willy Susilo, Yang-Wai Chow, Hua-Yu Zhou
TRIOB: A Trusted Virtual Computing Environment Based on Remote I/O Binding Mechanism
Abstract
When visiting cloud computing platforms, users are very concerned about the security of their personal data. Current cloud computing platforms have not provided a virtual computing environment which is fully trusted by users. Meanwhile, the management domain of cloud computing platform is subject to malicious attacks, which can seriously affect the trustworthiness of the virtual computing environment. This paper presents a new approach to build a trusted virtual computing environment in data centers. By means of three innovative technologies, the user’s data can be remotely stored into trusted storage resources, the user’s virtual computing environment is isolated, and the user can automatically detect the rootkit attacks against the cloud computing management domain. We design and implement a Xen-based prototype system called TRIOB. This manuscript presents the design, implementation, and evaluation of TRIOB, with a focus on rootkits detection.
Haifeng Fang, Hui Wang, Yiqiang Zhao, Yuzhong Sun, Zhiyong Liu

Cryptographic Protocols

Dynamic Group Key Exchange Revisited
Abstract
In a dynamic group key exchange protocol, besides the basic group setup protocol, there are also a join protocol and a leave protocol, which allow the membership of an existing group to be changed more efficiently than rerunning the group setup protocol. The join and leave protocols should ensure that the session key is updated upon every membership change so that the subsequent sessions are protected from leaving members (backward security) and the previous sessions are protected from joining members (forward security). In this paper, we present a new security model for dynamic group key exchange. Comparing to existing models, we do a special treatment to the state information that a user may use in a sequence of setup/join/leave sessions. Our treatment gives a clear and more concise definition of session freshness for group key exchange in the dynamic setting. We also construct a new dynamic group key exchange protocol that achieves strong security and high efficiency in the standard model.
Guomin Yang, Chik How Tan
Towards Practical and Secure Coercion-Resistant Electronic Elections
Abstract
Coercion-resistance is the most effective property to fight coercive attacks in Internet elections. This notion was introduced by Juels, Catalano, and Jakobsson (JCJ) at WPES 2005 together with a voting protocol that satisfies such a stringent security requirement. Unfortunately, their scheme has a quadratic complexity (the overhead for tallying authorities is quadratic in the number of votes) and would therefore not be suitable for large scale elections. Based on the work of JCJ, Schweisgut proposed a more efficient scheme. In this paper, we first show that Schweisgut’s scheme is insecure. In particular, we describe an attack that allows a coercer to check whether a voter followed or not his instructions. We then present a new coercion-resistant election scheme with a linear complexity that overcomes the drawbacks of these previous proposals. Our solution relies on special anonymous credentials and is proven secure, in the random oracle model, under the q-Strong Diffie-Hellman and Strong Decisional Diffie-Hellman Inversion assumptions.
Roberto Araújo, Narjes Ben Rajeb, Riadh Robbana, Jacques Traoré, Souheib Youssfi

Anonymous Credentials

Predicate Encryption with Partial Public Keys
Abstract
Predicate encryption is a new powerful cryptographic primitive which allows for fine-grained access control for encrypted data: the owner of the secret key can release partial keys, called tokens, that can decrypt only a specific subset of ciphertexts. More specifically, in a predicate encryption scheme, ciphertexts and tokens have attributes and a token can decrypt a ciphertext if and only if a certain predicate of the two associated attributes holds.
In this paper, ciphertext attributes are vectors x of fixed length ℓ over an alphabet Σ and token attributes, called patterns, are vectors y of the same length over the alphabet Σ ⋆  = Σ ∪ { ⋆ }. We consider the predicate Match(x, y) introduced by [BW06] which is true if and only if x = 〈x 1,...,x ℓ〉 and y = 〈y 1,...,y ℓ〉 agree in all positions i for which \(y_i\ne\star\).
Various security notions are relevant for predicate encryption schemes. First of all, one wants the ciphertexts to hide its attributes (this property is called semantic security). In addition, it makes sense also to consider the property of token security, a security notion in which the token is required not to reveal any information on the associated pattern. It is easy to see that predicate privacy is impossible to achieve in a public-key setting. In [SSW09], the authors considered the notion of a predicate encryption scheme in the symmetric-key setting and gave the first construction with token security.
In this paper, we consider the notion of a partial public key encryption (as suggested in [SSW09]) in which a partial public key allows a user to generate only a subset of the ciphertexts. We give a construction which is semantically secure and in which a token does not reveal any information on the associated pattern except for the locations of the ⋆’s. The proofs of security of our construction are based on hardness assumptions in bilinear groups of prime order; this greatly improves the efficiency of the construction when compared to previous constructions ([SSW09]) which used groups of composite orders.
Our security proofs do not use random oracles.
Carlo Blundo, Vincenzo Iovino, Giuseppe Persiano
Anonymous Credential Schemes with Encrypted Attributes
Abstract
In anonymous credential schemes, users obtain credentials on certain attributes from an issuer, and later show these credentials to a relying party anonymously and without fully disclosing the attributes. In this paper, we introduce the notion of (anonymous) credential schemes with encrypted attributes, in which issuers certify credentials on encrypted attributes to users. These schemes allow for the possibility that none of the involved parties, including the user, learns the values of the attributes. In fact, we will treat several variations differing in which parties see which attributes in the clear. We present efficient constructions of these new credential schemes, starting from a credential scheme by Brands, and we show that the security of Brands’ original scheme is retained. Finally, we sketch several interesting applications of these novel credential schemes.
Jorge Guajardo, Bart Mennink, Berry Schoenmakers
One Time Anonymous Certificate: X.509 Supporting Anonymity
Abstract
It is widely admitted that group signatures are today one of the most important cryptographic tool regarding privacy enhancing technologies. As evidence, the ISO organization has began a subject on authentication mechanisms supporting anonymity, in which group signatures are largely studied. However, it seems difficult to embed group signatures into other standards designed for classical authentication and signature mechanisms, such as the PKI X.509 certification. In fact, X.509 public key certificates are today widely used but not designed to support anonymity. One attempt has been done by Benjumea et al. but with the drawback that (i) the solution loses the principle of one certification per signer, (ii) revocation cannot be performed efficiently and (iii) the proposed architecture can not be applied to anonymous credentials, a concept close to group signature and today implemented by IBM or Microsoft. This paper presents a new approach which permits to use the X.509 standard to group signature schemes and anonymous credentials in a more standard and efficient way than related work.
Aymen Abed, Sébastien Canard
Backmatter
Metadata
Title
Cryptology and Network Security
Editors
Swee-Huay Heng
Rebecca N. Wright
Bok-Min Goi
Copyright Year
2010
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-17619-7
Print ISBN
978-3-642-17618-0
DOI
https://doi.org/10.1007/978-3-642-17619-7

Premium Partner

    Image Credits