nach oben

2006 | Buch

Kapitel lesen Erstes Kapitel lesen

Topics in Cryptology – CT-RSA 2006

The Cryptographers’ Track at the RSA Conference 2006, San Jose, CA, USA, February 13-17, 2005. Proceedings

herausgegeben von: David Pointcheval

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

The RSA R Conference, with over 15,000attendees, as well as over 225 sponsors and exhibitors, is the largest computer security event of the year. The Cr- tographers’ Track is one of the many parallel tracks. These proceedings contain the papers presented during the sixth edition. The tradition indeed started in 2001, and is by now well established: the Cryptographers’ Track at the RSA Conference is among the major events in cryptography. There were 72 submitted contributions, of which 22 were selected for p- sentation. They cover all aspects of cryptography (symmetric and asymmetric cryptography, constructions and attacks, new trends). In addition, the program includes two invited talks, by Xiaoyun Wang on “Cryptanalysis of Hash fu- tions and Potential Dangers,” and Philip MacKenzie on “Passwords Will Not Die: How Cryptography Can Help Deal with Them. ” All the submissions were reviewed by at least three members of the Program Committee. Iamverygratefultothe24membersfortheirhardandconscientious work.

Inhaltsverzeichnis

Frontmatter

Attacks on AES

Cache Attacks and Countermeasures: The Case of AES

Abstract

We describe several software side-channel attacks based on inter-process leakage through the state of the CPU’s memory cache. This leakage reveals memory access patterns, which can be used for cryptanalysis of cryptographic primitives that employ data-dependent table lookups. The attacks allow an unprivileged process to attack other processes running in parallel on the same processor, despite partitioning methods such as memory protection, sandboxing and virtualization. Some of our methods require only the ability to trigger services that perform encryption or MAC using the unknown key, such as encrypted disk partitions or secure network links. Moreover, we demonstrate an extremely strong type of attack, which requires knowledge of neither the specific plaintexts nor ciphertexts, and works by merely monitoring the effect of the cryptographic process on the cache. We discuss in detail several such attacks on AES, and experimentally demonstrate their applicability to real systems, such as OpenSSL and Linux’s dm-crypt encrypted partitions (in the latter case, the full key can be recovered after just 800 writes to the partition, taking 65 milliseconds). Finally, we describe several countermeasures for mitigating such attacks.

Dag Arne Osvik, Adi Shamir, Eran Tromer

Related-Key Impossible Differential Attacks on 8-Round AES-192

Abstract

In this paper we examine the strength of AES against the related-key impossible differential attack, following the work of Jakimoski and Desmedt [12]. We use several additional observations to substantially improve the data and time complexities of their attacks. Amongst our results, we present a related-key attack on 7-round AES-192 with data complexity of 2⁵⁶ chosen plaintexts (instead of 2¹¹¹). Our attack on 8-round AES-192 has data complexity of 2^68.5 chosen plaintexts (instead of 2⁸⁸). The time complexities of our attacks is also substantially lower than the time complexities of previous attacks.

Eli Biham, Orr Dunkelman, Nathan Keller

Identification

Session Corruption Attack and Improvements on Encryption Based MT-Authenticators

Abstract

Bellare, Canetti and Krawczyk proposed a security model (BCK-model) for authentication and key exchange protocols in 1998. The model not only reasonably captures the power of practical attackers but also provides a modular approach to the design of secure key exchange protocols. One important element in this approach is the MT-authenticator. An MT-authenticator transforms a message transmission protocol for an ideally authenticated network to an equivalent protocol for a real, unauthenticated network such that all attacks that can be launched in the unauthenticated network can also be launched in the authenticated network. In this paper, we show that the proof of the encryption-based MT-authenticator proposed in their paper is flawed, which leads to their encryption-based MT-authenticator insecure. An attack called session corruption attack can be launched successfully against the MT-authenticator in the unauthenticated network but not against the corresponding message transmission protocol in the authenticated network. To thwart this attack, we propose several improved techniques and two new encryption-based MT-authenticators.

Xiaojian Tian, Duncan S. Wong

Fair Identification

Abstract

This paper studies a new problem called fair identification: given two parties, how should they identify each other in a fair manner. More precisely, if both parties are honest then they learn each other’s identity, and if anyone is cheating then either both of them learn each other’s identity or no one learns no information about the identity of the other. We propose a security model and a provably secure optimistic fair identification protocol.

Omkant Pandey, Julien Cathalo, Jean-Jacques Quisquater

Algebra

Efficient Doubling on Genus 3 Curves over Binary Fields

Abstract

The most important and expensive operation in a hyperelliptic curve cryptosystem (HECC) is the scalar multiplication by an integer k, i.e., computing an integer k times a divisor D on the Jacobian. Using some recoding algorithms for the scalar, we can reduce the number of divisor class additions during the process of computing the scalar multiplication. On the other side, the divisor doublings will stay the same for all kinds of scalar multiplication algorithms. In this paper we accelerate the divisor doublings for genus 3 HECC over binary fields by using special types of curves. Depending on the degree of h, our explicit formulae only require 1I + 11M + 11S, 1I + 13M + 13S, 1I + 20M + 12S and 1I + 26M + 11S for divisor doublings in the best case, respectively. Especially, for the case of deg h = 1, our explicit formula improve the recent result in [GKP04] significantly by saving 31M at the cost of extra 7S. In addition, we discuss some cases which are not included in [GKP04].

By constructing birational transformation of variables, we derive explicit doubling formulae for special types of equations of the curve. For each type of curve, we analyze how many field operations are needed. So far no attack on any of the all curves suggested in this paper is known, even though some cases are very special. Our results allow to choose curves from a large variety which have extremely fast doubling needing only one third the time of an addition in the best case. Furthermore, an actual implementation of the new formulae on a Pentium-M processor shows their practical relevance.

Xinxin Fan, Thomas Wollinger, Yumin Wang

Another Look at Small RSA Exponents

Abstract

In this work we consider a variant of RSA whose public and private exponents can be chosen significantly smaller than in typical RSA. In particular, we show that it is possible to have private exponents smaller than N ^1/4 which are resistant to all known small private exponent attacks. This allows for instances of RSA with short CRT-exponents and short public exponents. In addition, the number of bits required to store the private key information can be significantly reduced in this variant.

M. Jason Hinek

Integrity

Collision-Resistant Usage of MD5 and SHA-1 Via Message Preprocessing

Abstract

A series of recent papers have demonstrated collision attacks on popularly used hash functions, including the widely deployed MD5 and SHA-1 algorithm. To assess this threat, the natural response has been to evaluate the extent to which various protocols actually depend on collision resistance for their security, and potentially schedule an upgrade to a stronger hash function. Other options involve altering the protocol in some way. This work suggests a different option. We present several simple message pre-processing techniques and show how the techniques can be combined with MD5 or SHA-1 so that applications are no longer vulnerable to the known collision attacks. For some applications, this may a viable alternative to upgrading the hash function.

Michael Szydlo, Yiqun Lisa Yin

RFID-Tags for Anti-counterfeiting

Abstract

RFID-tags are becoming very popular tools for identification of products. As they have a small microchip on board, they offer functionality that can be used for security purposes. This chip functionality makes it possible to verify the authenticity of a product and hence to detect and prevent counterfeiting. In order to be successful for these security purposes too, RFID-tags have to be resistant against many attacks, in particular against cloning of the tag. In this paper, we investigate how an RFID-tag can be made unclonable by linking it inseparably to a Physical Unclonable Function (PUF). We present the security protocols that are needed for the detection of the authenticity of a product when it is equipped with such a system. We focus on off-line authentication because it is very attractive from a practical point of view. We show that a PUF based solution for RFID-tags is feasible in the off-line case.

Pim Tuyls, Lejla Batina

Public Key Encryption

A “Medium-Field” Multivariate Public-Key Encryption Scheme

Abstract

Electronic commerce fundamentally requires two different public-key cryptographical primitives, for key agreement and authentication. We present the new encryption scheme MFE, and provide a performance and security review. MFE belongs to the \(\mathcal{MQ}\) class, an alternative class of PKCs also termed Polynomial-Based, or multivariate. They depend on multivariate quadratic systems being unsolvable.

The classical trapdoors central to PKC’s are modular exponentiation for RSA and discrete logarithms for ElGamal/DSA/ECC. But they are relatively slow and will be obsoleted by the arrival of QC (Quantum Computers). The argument for \(\mathcal{MQ}\)-schemes is that they are usually faster, and there are no known QC-assisted attacks on them.

There are several \(\mathcal{MQ}\) digital signature schemes being investigated today. But encryption (or key exchange schemes) are another story — in fact, only two other \(\mathcal{MQ}\)-encryption schemes remain unbroken. They are both built along “big-field” lines. In contrast MFE uses medium-sized field extensions, which makes it faster. For security and efficiency, MFE employs an iteratively triangular decryption process which involves rational functions (called by some “tractable rational maps”) and taking square roots. We discuss how MFE avoids previously known pitfalls of this genre while addressing its security concerns.

Lih-Chung Wang, Bo-Yin Yang, Yuh-Hua Hu, Feipei Lai

A New Security Proof for Damgård’s ElGamal

Abstract

We provide a new security proof for a variant of ElGamal proposed by Damgård, showing that it is secure against non-adaptive chosen ciphertext attack. Unlike previous security proofs for this cryptosystem, which rely on somewhat problematic assumptions, our underlying problem is similar to accepted problems such the Gap and Decision Diffie-Hellman problems.

Kristian Gjøsteen

Signatures

Stand-Alone and Setup-Free Verifiably Committed Signatures

Abstract

In this paper, a novel construction of stand-alone and setup-free verifiably committed signatures from RSA – an open problem advertised by Dodis and Reyzin in their speech [16] is presented. The methodology used in this paper is reminiscent of the concept of verifiably encrypted signatures introduced by Asokan et al [1, 2] . We suggest to encrypt only a random salt used to generate a virtual commitment that will be embedded into Cramer-Shoup’s signature scheme and to prove the validity of the signature with respect to this encrypted value. Our construction is provably secure assuming that the underlying Cramer-Shoup’s signature scheme is secure against adaptive chosen-message attack, and Paillier’s encryption is one-way. We thus provide an efficient solution to Dodis-Reyzin’s open problem.

Huafei Zhu, Feng Bao

Toward the Fair Anonymous Signatures: Deniable Ring Signatures

Abstract

Ring signature scheme, proposed by Rivest et al., allows a signer to sign a message anonymously. In the ring signature scheme, the signer who wants to sign a document anonymously first chooses some public keys of entities (signers) and then generates a signature which ensures that one of the signer or entities signs the document. In some situations, however, this scheme allows the signer to shift the blame to victims because of the anonymity. The group signature scheme may be a solution for the problem; however, it needs a group manager (electronic big brother) who can violate the signer anonymity without notification, and a complicated key setting.

This paper introduces a new concept of a signature scheme with signer anonymity, a deniable ring signature scheme ( \(\mathcal{DRS}\)), in which no group manager exists, and the signer should be involved in opening the signer anonymity. We also propose a concrete scheme proven to be secure under the assumption of the DDH (decision Diffie Hellman) problem in the random oracle model.

Yuichi Komano, Kazuo Ohta, Atsushi Shimbo, Shinichi Kawamura

Side-Channel Attacks

Practical Second-Order DPA Attacks for Masked Smart Card Implementations of Block Ciphers

Abstract

In this article we describe an improved concept for second-order differential-power analysis (DPA) attacks on masked smart card implementations of block ciphers. Our concept allows to mount second-order DPA attacks in a rather simple way: a second-order DPA attack consists of a pre-processing step and a DPA step. Therefore, our way of performing second-order DPA attacks allows to easily assess the number of traces that are needed for a successful attack. We give evidence on the effectiveness of our methodology by showing practical attacks on a masked AES smart card implementation. In these attacks we target inputs and outputs of the SubBytes operation in the first encryption round.

Elisabeth Oswald, Stefan Mangard, Christoph Herbst, Stefan Tillich

Higher Order Masking of the AES

Abstract

The development of masking schemes to secure AES implementations against side channel attacks is a topic of ongoing research. Many different approaches focus on the AES S-box and have been discussed in the previous years. Unfortunately, to our knowledge most of these countermeasures only address first-order DPA. In this article, we discuss the theoretical background of higher order DPA. We give the expected measurement costs an adversary has to deal with for different hardware models. Moreover, we present a masking scheme which protects an AES implementation against higher order DPA. We have implemented this masking scheme for various orders and present the corresponding performance details implementors will have to expect.

Kai Schramm, Christof Paar

CCA Encryption

Chosen Ciphertext Secure Public Key Threshold Encryption Without Random Oracles

Abstract

We present a non-interactive chosen ciphertext secure threshold encryption system. The proof of security is set in the standard model and does not use random oracles. Our construction uses the recent identity based encryption system of Boneh and Boyen and the chosen ciphertext secure construction of Canetti, Halevi, and Katz.

Dan Boneh, Xavier Boyen, Shai Halevi

How to Construct Multicast Cryptosystems Provably Secure Against Adaptive Chosen Ciphertext Attack

Abstract

In this paper we present a general framework for constructing efficient multicast cryptosystems with provable security and show that a line of previous work on multicast encryption are all special cases of this general approach. We provide new methods for building such cryptosystems with various levels of security (e.g., IND-CPA, IND-CCA2). The results we obtained enable the construction of a whole class of new multicast schemes with guaranteed security using a broader range of common primitives such as OAEP. Moreover, we show that multicast cryptosystems with high level of security (e.g. IND-CCA2) can be based upon public key cryptosystems with weaker (e.g. CPA) security as long as the decryption can be securely and efficiently “shared”. Our constructions feature truly constant-size decryption keys whereas the lengths of both the encryption key and ciphertext are independent of group size.

Yitao Duan, John Canny

Message Authentication

On the (Im)possibility of Blind Message Authentication Codes

Abstract

Blind signatures allow a signer to digitally sign a document without being able to glean any information about the document. In this paper, we investigate the symmetric analog of blind signatures, namely blind message authentication codes (blind MACs). One may hope to get the same efficiency gain from blind MAC constructions as is usually obtained when moving from asymmetric to symmetric cryptosystems. Our main result is a negative one however: we show that the natural symmetric analogs of the unforgeability and blindness requirements cannot be simultaneously satisfied. Faced with this impossibility, we show that blind MACs do exist (under the one-more RSA assumption in the random oracle model) in a more restrictive setting where users can share common state information. Our construction, however, is only meant to demonstrate the existence; it uses an underlying blind signature scheme, and hence does not achieve the desired performance benefits. The construction of an efficient blind MAC scheme in this restrictive setting is left as an open problem.

Michel Abdalla, Chanathip Namprempre, Gregory Neven

An Optimal Non-interactive Message Authentication Protocol

Abstract

Vaudenay recently proposed a message authentication protocol which is interactive and based on short authenticated strings (SAS). We study here SAS-based non-interactive message authentication protocols (NIMAP). We start by the analysis of two popular non-interactive message authentication protocols. The first one is based on a collision-resistant hash function and was presented by Balfanz et al. The second protocol is based on a universal hash function family and was proposed by Gehrmann, Mitchell, and Nyberg. It uses much less authenticated bits but requires a stronger authenticated channel.

We propose a protocol which can achieve the same security as the first protocol but using less authenticated bits, without any stronger communication model, and without requiring a hash function to be collision-resistant. Finally, we demonstrate the optimality of our protocol.

Sylvain Pasini, Serge Vaudenay

Block Ciphers

A New Criterion for Nonlinearity of Block Ciphers

Abstract

For years, the cryptographic community has searched for good nonlinear functions. Bent functions, almost perfect nonlinear functions, and similar constructions have been suggested as a good base for cryptographic applications due to their highly nonlinear nature. In the first part of this paper we study these functions as block ciphers, and present several distinguishers between almost perfect nonlinear permutations and random permutations. The data complexity of the best distinguisher is O(2^n/3) and its time complexity is O(2^2n/3) for an n-bit block size, independent of the key size.

In the second part of the paper we suggest a criterion to measure the effective linearity of a given block cipher. We devise a distinguisher for general block ciphers based on their effective linearity. Finally, we show that for several constructions, our distinguishing attack is better than previously known techniques.

Orr Dunkelman, Nathan Keller

Block Ciphers Sensitive to Gröbner Basis Attacks

Abstract

We construct and analyze Feistel and SPN ciphers that have a sound design strategy against linear and differential attacks but for which the encryption process can be described by very simple polynomial equations. For a block and key size of 128 bits, we present ciphers for which practical Gröbner basis attacks can recover the full cipher key requiring only a minimal number of plaintext/ciphertext pairs. We show how Gröbner bases for a subset of these ciphers can be constructed with neglegible computational effort. This reduces the key–recovery problem to a Gröbner basis conversion problem. By bounding the running time of a Gröbner basis conversion algorithm, FGLM, we demonstrate the existence of block ciphers resistant against differential and linear cryptanalysis but vulnerable against Gröbner basis attacks.

Johannes Buchmann, Andrei Pyshkin, Ralf-Philipp Weinmann

Multi-party Computation

Universally Composable Oblivious Transfer in the Multi-party Setting

Abstract

We construct efficient universally composable oblivious transfer protocols in the multi-party setting for honest majorities. Unlike previous proposals our protocols are designed in the plain model (i.e., without a common reference string), are secure against malicious adversaries from scratch (i.e., without requiring an expensive compiler), and are based on weaker cryptographic assumptions than comparable two-party protocols. Hence, the active participation of auxiliary parties pays off in terms of complexity. This is particularly true for the construction of one of our building blocks, an efficient universally composable homomorphic commitment scheme. Efficient solutions for this problem in the two-party setting are not known, not even in the common reference string model.

Marc Fischlin

A Round and Communication Efficient Secure Ranking Protocol

Abstract

In this work, we initiate the study of realizing a ranking functionality (m ₁, ⋯, m _n)↦ (r ₁, ⋯, r _n) in the non-adaptive malicious model, where \(r_{i}=+ \sharp \{m_{j}:m_{j} < m_{i}\}\). Generically, it has been solved by a general multi-party computation technique (via a circuit formulation). However, such a solution is inefficient in either round complexity or communication complexity. In this work, we propose an efficient construction without a circuit. Our protocol is constant round and efficient in communication complexity as well. Furthermore, we show it is directly secure in the non-adaptive malicious model (i.e., without a compiler, as is used in many general constructions).

Shaoquan Jiang, Guang Gong

Backmatter

Titel: Topics in Cryptology – CT-RSA 2006
herausgegeben von: David Pointcheval
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-32648-9
Print ISBN: 978-3-540-31033-4
DOI: https://doi.org/10.1007/11605805