nach oben

2012 | Buch

Kapitel lesen Erstes Kapitel lesen

Advances in Information and Computer Security

7th International Workshop on Security, IWSEC 2012, Fukuoka, Japan, November 7-9, 2012. Proceedings

herausgegeben von: Goichiro Hanaoka, Toshihiro Yamauchi

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

This book constitutes the refereed proceedings of the 7th International Workshop on Security, IWSEC 2012, held in Fukuoka, Japan, in November 2012. The 16 revised selected papers presented in this volume were carefully reviewed and selected from 53 submissions. They are organized in topical sections named: implementation; encryption and key exchange; cryptanalysis; and secure protocols.

Inhaltsverzeichnis

Frontmatter

Implementation

Model-Based Conformance Testing for Android

Abstract

With the surging computing power and network connectivity of smartphones, more third-party applications and services are deployed on these platforms and enable users to customize their mobile devices. Due to the lack of rigorous security analysis, fast evolving smartphone platforms, however, have suffered from a large number of system vulnerabilities and security flaws. In this paper, we present a model-based conformance testing framework for mobile platforms, focused on Android platform. Our framework systematically generates test cases from the formal specification of the mobile platform and performs conformance testing with the generated test cases. We also demonstrate the feasibility and effectiveness of our framework through case studies on Android Inter-Component Communication module.

Yiming Jing, Gail-Joon Ahn, Hongxin Hu

Application of Scalar Multiplication of Edwards Curves to Pairing-Based Cryptography

Abstract

Edwards curves have efficient scalar multiplication algorithms, and their application to pairing-based cryptography has been studied. In particular, if a pairing-friendly curve used in a pairing-based protocol is isomorphic to an Edwards curve, all the scalar multiplication appearing in the protocol can be computed efficiently. In this paper, we extend this idea to pairing-friendly curves not isomorphic but isogenous to Edwards curves, and add to pairing-friendly curves to which Edwards curves can be applied. Above all, pairing-friendly curves with smaller ρ-values provide more efficient pairing computation. Therefore, we investigate whether pairing-friendly curves with the minimal ρ-values are isogenous to Edwards curves for embedding degree up to 50. Based on the investigation, we present parameters of pairing-friendly curves with 160-bit and 256-bit security level at embedding degree 16 and 24, respectively. These curves have the minimal ρ-values and are not isomorphic but isogenous to Edwards curves, and thus our proposed method is effective for these curves.

Takanori Yasuda, Tsuyoshi Takagi, Kouichi Sakurai

Standardized Signature Algorithms on Ultra-constrained 4-Bit MCU

Abstract

In this work, we implement all three digital signature schemes specified in Digital Signature Standard (FIPS 186-3), including DSA and RSA (based on modular exponentiation) as well as ECDSA (based on elliptic curve point multiplication), on an ultra-constrained 4-bit MCU of the EPSON S1C63 family. Myriads of 4-bit MCUs are widely deployed in legacy devices, and some in security applications due to their ultra low-power consumption. However, public-key cryptography, especially digital signature, on 4-bit MCU is usually neglected and even regarded as infeasible. Our highly energy-efficient implementation can give rise to a variety of security functionalities for these ultra-constrained devices.

Chien-Ning Chen, Nisha Jacob, Sebastian Kutzner, San Ling, Axel Poschmann, Sirote Saetang

Very Short Critical Path Implementation of AES with Direct Logic Gates

Abstract

A lot of improvements and optimizations for the hardware implementation of AES algorithm have been reported. These reports often use, instead of arithmetic operations in the AES original \(\mathbb{F}_{2^8}\), those in its isomorphic tower field \(\mathbb{F}_{((2^{2})^{2})^2}\) and \(\mathbb{F}_{(2^4)^2}\). This paper focuses on \(\mathbb{F}_{(2^4)^2}\) which provides higher–speed arithmetic operations than \(\mathbb{F}_{((2^{2})^{2})^2}\). In the case of adopting \(\mathbb{F}_{(2^4)^2}\), not only high–speed arithmetic operations in \(\mathbb{F}_{(2^4)^2}\) but also high–speed basis conversion matrices from the \(\mathbb{F}_{2^8}\) to \(\mathbb{F}_{(2^4)^2}\) should be used. Thus, this paper improves arithmetic operations in \(\mathbb{F}_{(2^4)^2}\) with Redundantly Represented Basis (RRB), and provides basis conversion matrices with More Miscellaneously Mixed Bases (MMMB).

Kenta Nekado, Yasuyuki Nogami, Kengo Iokibe

Encryption and Key Exchange

One-Round Authenticated Key Exchange with Strong Forward Secrecy in the Standard Model against Constrained Adversary

Abstract

Forward secrecy (FS) is a central security requirement of authenticated key exchange (AKE). Especially, strong FS (sFS) is desirable because it can guarantee security against a very realistic attack scenario that an adversary is allowed to be active in the target session. However, most of AKE schemes cannot achieve sFS, and currently known schemes with sFS are only proved in the random oracle model. In this paper, we propose a generic construction of AKE protocol with sFS in the standard model against a constrained adversary. The constraint is that session-specific intermediate computation results (i.e., session state) cannot be revealed to the adversary for achieving sFS, that is shown to be inevitable by Boyd and González Nieto. However, our scheme maintains weak FS (wFS) if session state is available to the adversary. Thus, our scheme satisfies one of strongest security definitions, the CK⁺ model, which includes wFS and session state reveal. The main idea to achieve sFS is to use signcryption KEM while the previous CK⁺ secure construction uses ordinary KEM. We show a possible instantiation of our construction from Diffie-Hellman problems.

Kazuki Yoneyama

Compact Stateful Encryption Schemes with Ciphertext Verifiability

Abstract

Increasingly wider deployment of encryption schemes call for schemes possessing additional properties such as randomness re-use, compactness and ciphertext verifiability. While novel approaches such as stateful encryption schemes contributes for randomness re-use (to save computational efforts), the requirements such as ciphertext verifiability leads to increase in the size of ciphertext. Thus, it is interesting and challenging to design stateful encryption schemes that offer ciphertext verifiability and result in compact ciphertexts. We propose two new stateful public key encryption schemes with ciphertext verifiability. Our schemes offer more compact ciphertexts when compared to all existing stateful public key encryption schemes with ciphertext verifiability. Our first scheme is based on the SDH assumption and the second scheme is based on the CDH assumption. We have proved both the schemes in the random oracle model.

S. Sree Vivek, S. Sharmila Deva Selvi, C. Pandu Rangan

Structured Encryption for Conceptual Graphs

Abstract

We investigate the problem of privately searching encrypted data that is structured in the form of knowledge. Our rationale in such an investigation lies on the potential emergence of knowledge-based search using natural language, which makes content searches more effective and is context-aware when compared with existing keyword searches. With knowledge-based search, indexes and databases will consist of data stored using knowledge representation techniques such as description logics and conceptual graphs. This leads naturally to the issue of how to privately search this data, especially when most existing searchable encryption schemes are keyword-based. We propose the first construction with CQA2-security for searching encrypted knowledge, where the knowledge is represented in a well-established formalism known as basic conceptual graphs. Our proposals are based on structured encryption schemes of Chase and Kamara [8].

Geong Sen Poh, Moesfa Soeheila Mohamad, Muhammad Reza Z’aba

Symmetric-Key Encryption Scheme with Multi-ciphertext Non-malleability

Abstract

A standard notion of non-malleability is that an adversary cannot forge a ciphertext c′ from a single valid ciphertext c for which a plaintext m′ of c′ is meaningfully related to a plaintext m of c. The multi-ciphertext non-malleability is a stronger notion; an adversary is allowed to obtain multiple ciphertexts c ₁,c ₂,... in order to forge c′. We provide an efficient symmetric-key encryption scheme with an information-theoretic version of the multi-ciphertext non-malleability in this paper by using ℓ-wise almost independent permutations of Kaplan, Naor, and Reingold.

Akinori Kawachi, Hirotoshi Takebe, Keisuke Tanaka

Cryptanalysis

Slide Cryptanalysis of Lightweight Stream Cipher RAKAPOSHI

Abstract

In this paper, we analyze a slide property of RAKAPOSHI stream cipher. To begin, we show that any Key-IV pair has a corresponding slide Key-IV pair that generates an n-bit shifted keystream with probability of 2^− 2n. Then we exploit this property in order to develop a key recovery attack on RAKAPOSHI in the related key setting. Our attack is able to recover a 128-bit key with time complexity of 2⁴¹ and 2³⁸ chosen IVs. The result reveals that RAKAPOSHI is vulnerable to the related key attack. After that, we consider a variant of the slide property, called partial slide property. It enables us to construct a method for speeding up the brute force attack by a factor of 2 in the single key setting. Finally, we consider a slide property of K2 v2.0 stream cipher, and discuss the possibility of an attack exploiting the slide property.

Takanori Isobe, Toshihiro Ohigashi, Masakatu Morii

Boomerang Distinguishers for Full HAS-160 Compression Function

Abstract

This paper studies a boomerang-attack-based distinguisher against full steps of the compression function of HAS-160, which is the hash function standard in Korea. The attack produces a second-order collision for the full steps of the compression function with a complexity of 2^76.06, which is faster than the currently best-known generic attack with a complexity of 2⁸⁰. Previously Dunkelman et al. in 2009 applied a boomerang-based key-recovery attack on the internal block cipher of HAS-160. Because the goal of their attack is different from ours, the attack on the compression function has been reconstructed and optimized from scratch. As a result of the exhaustive search of the message difference, we found that the same message difference as theirs is the best choice for the first subcipher. We then propose some improvement to construct a differential characteristic from the message difference, which the probability of the characteristic increases from 2^− 47 to 2^− 44. Thus our new characteristic also improves their key-recovery attack on the internal block cipher of HAS-160.

Yu Sasaki, Lei Wang, Yasuhiro Takasaki, Kazuo Sakiyama, Kazuo Ohta

Polynomial-Advantage Cryptanalysis of 3D Cipher and 3D-Based Hash Function

Abstract

This paper evaluates a block cipher mode, whose round functions of both the key schedule and the encryption process are independent of the round indexes. Previously related-key attack has been applied to such block cipher mode, and it can work no matter how many rounds are iterated in the cipher. This paper presents an accelerated key-recovery attack on this block cipher mode in the single-key setting. Similarly, our attack can also work no matter how many rounds are iterated in the cipher. More interestingly, the effectiveness of our attack, e.g. the relative advantage, increases with the number of rounds.

3D is a dedicated block cipher following the target mode. We apply the key-recovery attack to 3D cipher, and extend it to collision and preimage attacks on 3D-based hash functions. For a l-round instance of 3D (l is recommended as 22 by the designer), the complexity of recovering the secret key is \(2^{512}/\sqrt{l/2}\) data, \(2^{512}/\sqrt{l/2}\) offline computation, and \(2^{512}/\sqrt{l/2}\) memory requirement. And the success probability is 0.63. Thus compared with the brute-force attack, the complexity is accelerated by a factor of \(0.315*\sqrt{l/2}\) in the sense of total computations (including both online and offline computations) under the same success probability 0.63. The total computations of finding collision and preimage on 3D-based hash functions are 2²⁵⁷/l and 2⁵¹³/l, namely accelerated by a factor of l/2 in the sense of total computations under the same success probability. Moreover, differently from the key-recovery attack, the collision and preimage attacks don’t need to increase the memory requirement compared with the brute-force attack.

Finally we stress that all our attacks are polynomial-advantage attacks.

Lei Wang, Yu Sasaki, Kazuo Sakiyama, Kazuo Ohta

Annihilators of Fast Discrete Fourier Spectra Attacks

Abstract

Spectra attacks proposed recently are more data efficient than algebraic attacks against stream cipher. They are also time-and-space efficient. A measurement of the security of a stream cipher against spectra attacks is spectral immunity, the lowest spectral weight of the annihilator of the key stream. We study both the annihilator and the spectral immunity. We obtain a necessary and sufficient condition for the existence of low spectral weight annihilator and find it is more difficult to decide the (non)existence of the low weight annihilator for spectra attacks than for algebraic attacks. We also give some basic properties of annihilators and find the probability of a periodic sequence to be the annihilator of another sequence of the same period is low. Finally we prove that the spectral immunity is upper bounded by half of the period of the key stream. As a result, to recover any key stream, the least amount of bits required by spectra attacks is at most half of its period.

Jingjing Wang, Kefei Chen, Shixiong Zhu

Meet-in-the-Middle Attack on Reduced Versions of the Camellia Block Cipher

Abstract

The Camellia block cipher has a 128-bit block length and a user key of 128, 192 or 256 bits long, which employs a total of 18 rounds for a 128-bit key and 24 rounds for a 192 or 256-bit key. It is a Japanese CRYPTREC-recommended e-government cipher, a European NESSIE selected cipher, and an ISO international standard. In this paper, we describe a few 5 and 6-round properties of Camellia and finally use them to give (higher-order) meet-in-the-middle attacks on 10-round Camellia with the FL/FL^− 1 functions under 128 key bits, 11-round Camellia with the FL/FL^− 1 and whitening functions under 192 key bits and 12-round Camellia with the FL/FL^− 1 and whitening functions under 256 key bits.

Jiqiang Lu, Yongzhuang Wei, Enes Pasalic, Pierre-Alain Fouque

Secure Protocols

Efficient Concurrent Oblivious Transfer in Super-Polynomial-Simulation Security

Abstract

In this paper, we show a concurrent oblivious transfer protocol in super-polynomial-simulation (SPS) security. Our protocol does not require any setup and does not assume any independence among the inputs. In addition, our protocol is efficient since it does not use any inefficient primitives such as general zero-knowledge proofs for all NP statements. This is the first concurrent oblivious transfer protocol that achieves both of these properties simultaneously. The security of our protocol is based on the decisional Diffie-Hellman (DDH) assumption.

Susumu Kiyoshima, Yoshifumi Manabe, Tatsuaki Okamoto

Efficient Secure Primitive for Privacy Preserving Distributed Computations

Abstract

Scalar product protocol aims at securely computing the dot product of two private vectors. As a basic tool, the protocol has been widely used in privacy preserving distributed collaborative computations. In this paper, at the expense of disclosing partial sum of some private data, we propose a linearly efficient Even-Dimension Scalar Product Protocol (EDSPP) without employing expensive homomorphic crypto-system and third party. The correctness and security of EDSPP are confirmed by theoretical analysis. In comparison with six most frequently-used schemes of scalar product protocol (to the best of our knowledge), the new scheme is a much more efficient one, and it has well fairness. Simulated experiment results intuitively indicate the good performance of our novel scheme. Consequently, in the situations where divulging very limited information about private data is acceptable, EDSPP is an extremely competitive candidate secure primitive to achieve practical schemes of privacy preserving distributed cooperative computations. We also present a simple application case of EDSPP.

Youwen Zhu, Tsuyoshi Takagi, Liusheng Huang

Generic Construction of GUC Secure Commitment in the KRK Model

Abstract

This paper proposes a generic construction of GUC secure commitment against static corruptions in the KRK (Key Registration with Knowledge) model. The GUC security is a generalized version of universally composable security which deals with global setup used by arbitrary many protocols at the same time. The proposed construction is the first GUC secure protocol in which the commit phase is non-interactive (whereas the reveal phase is interactive). Thus, the proposed construction is suitable for applications where many values are committed to a few receivers within a short time period. The proposed construction uses simple tools, a public key encryption (PKE) scheme, a Sigma protocol, a non-interactive authenticated key exchange (NI-AKE) scheme, a message authentication code (MAC), for which efficient constructions have been presented. For the sake of simplicity of the proposed construction, which uses GUC secure authenticated communication (constructed from MAC and NI-AKE), we have not achieve full adaptive security because GUC secure authenticated communication in the KRK model is impossible.

Itsuki Suzuki, Maki Yoshida, Toru Fujiwara

Backmatter

Titel: Advances in Information and Computer Security
herausgegeben von: Goichiro Hanaoka
Toshihiro Yamauchi
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-34117-5
Print ISBN: 978-3-642-34116-8
DOI: https://doi.org/10.1007/978-3-642-34117-5

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Implementation

Model-Based Conformance Testing for Android

Application of Scalar Multiplication of Edwards Curves to Pairing-Based Cryptography

Standardized Signature Algorithms on Ultra-constrained 4-Bit MCU

Very Short Critical Path Implementation of AES with Direct Logic Gates

Encryption and Key Exchange

One-Round Authenticated Key Exchange with Strong Forward Secrecy in the Standard Model against Constrained Adversary

Compact Stateful Encryption Schemes with Ciphertext Verifiability

Structured Encryption for Conceptual Graphs

Symmetric-Key Encryption Scheme with Multi-ciphertext Non-malleability

Cryptanalysis

Slide Cryptanalysis of Lightweight Stream Cipher RAKAPOSHI

Boomerang Distinguishers for Full HAS-160 Compression Function

Polynomial-Advantage Cryptanalysis of 3D Cipher and 3D-Based Hash Function

Annihilators of Fast Discrete Fourier Spectra Attacks

Meet-in-the-Middle Attack on Reduced Versions of the Camellia Block Cipher

Secure Protocols

Efficient Concurrent Oblivious Transfer in Super-Polynomial-Simulation Security

Efficient Secure Primitive for Privacy Preserving Distributed Computations

Generic Construction of GUC Secure Commitment in the KRK Model

Backmatter

Premium Partner