nach oben

2006 | Buch

Kapitel lesen Erstes Kapitel lesen

Selected Areas in Cryptography

12th International Workshop, SAC 2005, Kingston, ON, Canada, August 11-12, 2005, Revised Selected Papers

herausgegeben von: Bart Preneel, Stafford Tavares

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

SAC 2005 was the 12th in a series of annual workshops on Selected Areas in Cryptography. This was the 5th time the workshop was hosted by Queen’s U- versity in Kingston (the previous workshops were held here in 1994, 1996, 1998 and 1999).Other SAC workshopshave been organizedat Carleton University in Ottawa (1995, 1997 and 2003), the Fields Institute in Toronto (2001), Memorial University of Newfoundland in St. John’s (2002) and the University of Waterloo (2000 and 2004). The workshop provided a relaxed atmosphere in which - searchers in cryptography could present and discuss new work on selected areas of current interest. The themes for SAC 2005 were: – design and analysis of symmetric key cryptosystems; – primitives for symmetric key cryptography, including block and stream - phers, hash functions, and MAC algorithms; – e?cient implementations of symmetric and public key algorithms; – cryptographic algorithms and protocols for ubiquitous computing (sensor networks, RFID). A total of 96 papers were submitted. Three papers were not considered - cause they were identi?ed as being multiple submissions. After an extensive double-blind reviewing process, the program committee accepted 25 papers for presentation at the workshop. We were very fortunate to have two invited speakers at SAC 2005, who both delivered thought-provoking and entertaining talks: – Alfred Menezes: Another Look at Provable Security; – Mike Wiener: The Full Cost of Cryptanalytic Attacks.

Inhaltsverzeichnis

Frontmatter

Stream Ciphers I

Conditional Estimators: An Effective Attack on A5/1

Abstract

Irregularly-clocked linear feedback shift registers (LFSRs) are commonly used in stream ciphers. We propose to harness the power of conditional estimators for correlation attacks on these ciphers. Conditional estimators compensate for some of the obfuscating effects of the irregular clocking, resulting in a correlation with a considerably higher bias. On GSM’s cipher A5/1, a factor two is gained in the correlation bias compared to previous correlation attacks. We mount an attack on A5/1 using conditional estimators and using three weaknesses that we observe in one of A5/1’s LFSRs (known as R2). The weaknesses imply a new criterion that should be taken into account by cipher designers. Given 1500–2000 known-frames (about 4.9–9.2 conversation seconds of known keystream), our attack completes within a few tens of seconds to a few minutes on a PC, with a success rate of about 91%. To complete our attack, we present a source of known-keystream in GSM that can provide the keystream for our attack given 3–4 minutes of GSM ciphertext, transforming our attack to a ciphertext-only attack.

Elad Barkan, Eli Biham

Cryptanalysis of the F-FCSR Stream Cipher Family

Abstract

This paper focuses on F-FCSR, a new family of stream ciphers proposed by Arnault and Berger at FSE 2005. It uses a non-linear primitive called the Feedback with Carry Shift Register (FCSR) as a building block. Its security relies on some properties of the 2-adic numbers. The F-FCSR family contains several stream ciphers, each of them proposing different features.

First, we show a resynchronization attack that breaks algorithms in the family that support initialization vectors. The attack requires at most 2¹⁶ chosen IV’s and a little offline processing to recover the full secret key. We have implemented it with success on a standard PC.

Secondly, we show a time/memory/data trade-off attack which breaks several algorithms in the F-FCSR family, even when initialization vectors are not supported. Its complexity ranges from 2⁶⁴ to 2⁸⁰ operations (depending on which algorithm in the family we consider), while the internal state has size 196 bits at least. Therefore this attack is better than generic attacks.

Éliane Jaulmes, Frédéric Muller

Fault Attacks on Combiners with Memory

Abstract

Fault attacks are powerful cryptanalytic tools that are applicable to many types of cryptosystems. Recently, general techniques have been developed which can be used to attack many standard constructions of stream ciphers based on LFSR’s. Some more elaborated methods have been invented to attack RC4. These fault attacks are not applicable in general to combiners with memory.

In this paper, techniques are developed that specifically allow to attack this class of stream ciphers. These methods are expected to work against any LFSR-based construction that uses only a small memory and few input bits in its output function. In particular, efficient attacks are described against the stream cipher E0 used in Bluetooth, either by inducing faults in the memory or in one of its LFSR’s. In both cases, the outputs derived from the faulty runs finally allow to describe the secret key by a system of linear equations. Computer simulations showed that inducing 12 faults sufficed in most cases if about 2500 output bits were available. Another specific fault attack is developed against the stream cipher SNOW 2.0, whose output function has a 64-bit memory. Similar to E ₀, the secret key is finally the solution of a system of linear equations. We expect that one fault is enough if about 2¹² output words are known.

Frederik Armknecht, Willi Meier

Block Ciphers

New Observation on Camellia

Abstract

In this paper, some observations on Camellia are presented, by which the Square attack and the Collision attack are improved. 11-round 256-bit Camellia without FL function is breakable with complexity of 2²⁵⁰ encryptions. 9-round 128-bit Camellia without FL function is breakable with the complexity of 2⁹⁰ encryptions. And 10-round 256-bit Camellia with FL function is breakable with the complexity of 2²¹⁰ encryptions and 9-round 128-bit Camellia with FL function is breakable with the complexity of 2¹²² encryptions. These results are better than any other known results. It concludes that the most efficient attack on Camellia is Square attack.

Duo Lei, Li Chao, Keqin Feng

Proving the Security of AES Substitution-Permutation Network

Abstract

In this paper we study the substitution-permutation network (SPN) on which AES is based. We introduce AES ^*, a SPN identical to AES except that fixed S-boxes are replaced by random and independent permutations. We prove that this construction resists linear and differential cryptanalysis with 4 inner rounds only, despite the huge cumulative effect of multipath characteristics that is induced by the symmetries of AES. We show that the DP and LP terms both tend towards 1/(2¹²⁸− 1) very fast when the number of round increases. This proves a conjecture by Keliher, Meijer, and Tavares. We further show that AES ^*. is immune to any iterated attack of order 1 after 10 rounds only, which substantially improves a previous result by Moriai and Vaudenay.

Thomas Baignères, Serge Vaudenay

Modes of Operation

An Attack on CFB Mode Encryption as Used by OpenPGP

Abstract

This paper describes an adaptive chosen-ciphertext attack on the Cipher Feedback (CFB) mode of encryption as used in OpenPGP. In most circumstances it will allow an attacker to determine 16 bits of any block of plaintext with about 2¹⁵ oracle queries for the initial setup work and 2¹⁵ oracle queries for each block. Standard CFB mode encryption does not appear to be affected by this attack. It applies to a particular variation of CFB used by OpenPGP. In particular it exploits an ad-hoc integrity check feature in OpenPGP which was meant as a “quick check” to determine the correctness of the decrypting symmetric key.

Serge Mister, Robert Zuccherato

Parallelizable Authentication Trees

Abstract

We define a new authentication tree in the symmetric key setting, which has the same computational time, storage and security parameters as the well known Merkle authentication tree, but which unlike the latter, allows for all the cryptographic operations required for an update to be performed in parallel. As in Merkle authentication trees, the cryptographic operations required for verification can also be parallelized. In particular, we show a provably secure scheme for incremental MAC with partial authentication secure against substitution and replay attacks, which on total data of size 2ⁿ blocks, and given n cryptographic engines, can compute incremental MACs and perform individual block authentication with a critical path of only one cryptographic operation

W. Eric Hall, Charanjit S. Jutla

Improved Time-Memory Trade-Offs with Multiple Data

Abstract

In this paper we study time/memory/data trade-off attacks from two points of view. We show that Time-Memory trade-off (TMTO) by Hellman may be extended to Time/Memory/Key trade-off. For example, AES with 128-bit key has only 85-bit security if 2⁴³ encryptions of an arbitrary fixed text under different keys are available to the attacker. Such attacks are generic and are more practical than some recent high complexity chosen related-key attacks on round-reduced versions of AES. They constitute a practical threat for any cipher with 80-bit or shorter keys and are marginally practical for 128-bit key ciphers. We show that UNIX password scheme even with carefully generated passwords is vulnerable to practical trade-off attacks. Our second contribution is to present a unifying framework for the analysis of multiple data trade-offs. Both Babbage-Golic (BG) and Biryukov-Shamir (BS) formulas can be obtained as special cases of this framework. Moreover we identify a new class of single table multiple data trade-offs which cannot be obtained either as BG or BS trade-off. Finally we consider the analysis of the rainbow method of Oechslin and show that for multiple data, the TMTO curve of the rainbow method is inferior to the TMTO curve of the Hellman method.

Alex Biryukov, Sourav Mukhopadhyay, Palash Sarkar

Public Key Cryptography

A Space Efficient Backdoor in RSA and Its Applications

Abstract

In this paper we present an RSA backdoor that, for example, can be used for a hardware-based RSA key recovery system. The system is robust in the sense that a successful reverse-engineer is not able to obtain previous nor future RSA private keys that have been/will be generated within the key generation device. The construction employs the notion of two elliptic curves in which one is the “twist” of the other. We present a proof in the random oracle model that the generated RSA key pairs that are produced by the cryptographic black-box are computationally indistinguishable (under ECDDH) from “normal” RSA key pairs, thus ensuring the integrity of the outputs. Furthermore, the security level of the key recovery mechanism is nearly identical to that of the key pair being generated. Thus, the solution provides an “equitable” level of security for the end user. This solution also gives a number of new kleptographic applications.

Adam Young, Moti Yung

An Efficient Public Key Cryptosystem with a Privacy Enhanced Double Decryption Mechanism

Abstract

A clue of double decryption mechanism was introduced at Eurocrypt ’02 by Cramer and Shoup, and it was revisited at Asiacrypt ’03 by Bresson, Catalano and Pointcheval. Previous double decryption schemes are designed based on $\mathbb{Z}_{n^{2}}$ where n = pq for two primes, p and q. Note that, they use the Paillier’s scheme as a primitive scheme to design a double decryption mechanism. In this paper, we propose an efficient public key scheme with double decryption mechanism based on $\mathbb{Z}_{p^{2}q}$. Our scheme is more efficient than the previous schemes. Moreover, we review the previous schemes in a privacy point of view and propose a privacy enhanced double decryption scheme.

Taek-Young Youn, Young-Ho Park, Chang Han Kim, Jongin Lim

Stream Ciphers II

On the (Im)Possibility of Practical and Secure Nonlinear Filters and Combiners

Abstract

A vast amount of literature on stream ciphers is directed to the cryptanalysis of LFSR-based filters and combiners, resulting in various cryptanalytic attacks. In this paper, we present a unified framework for the security of a design against these attacks based on the properties of the LFSR(s) and the Boolean function used. It is explained why building nonlinear filters seems more practical than building nonlinear combiners. We also investigate concrete building blocks that offer a good trade-off in their resistance against these various attacks, and can at the same time be used to build a low-cost synchronous stream cipher for hardware applications.

An Braeken, Joseph Lano

Rekeying Issues in the MUGI Stream Cipher

Abstract

MUGI [15] is a word-based stream cipher designed for 64-bit architectures. It uses a 128-bit master key and a 128-bit initialization vector to populate a large non-linear feedback shift register (NLFSR) and additional non-linear state (NLS). In standard benchmarks on 32-bit processors, MUGI suffers from poor key agility because it is implemented on an architecture for which it is not designed, and because its NLFSR is too large relative to the size of its master key. This paper proposes a variant of MUGI, entitled MUGI-M, to enhance key agility, and concludes with an analysis of its security and performance characteristics.

Matt Henricksen, Ed Dawson

Key Establishment Protocols and Access Control

Tree-Based Key Distribution Patterns

Abstract

We revisit a key agreement scheme presented by Leighton and Micali [11], generalize the scheme, and present a new framework of tree-based key distribution pattern (TKDP). We presents a method of constructing TKDPs from cover-free families. We show the existence of TKDPs by probabilistic method. We can reduce the upper bounds on the minimum number of rows of ($t,w, \mathcal{T}$)-TKDPs, which are obtained from probabilistic methods, asymptotically by a factor of w as compared to Leighton and Micali’s schemes by choosing optimal trees $\mathcal{T}$ instead of chains.

Jooyoung Lee, Douglas R. Stinson

Provably Secure Tripartite Password Protected Key Exchange Protocol Based on Elliptic Curves

Abstract

Joux’s tripartite key agreement protocol is one of the most prominent developments in the area of key agreement. Although certificate-based and ID-based authentication schemes have been proposed to provide authentication for Joux’s protocol, no provably secure password-based one round tripartite key agreement protocol has been proposed yet. We propose a secure one round password-based tripartite key agreement protocol that builds on Joux’s protocol and adapts PAK-EC scheme for password-based authentication, and present a proof of its security.

Sanggon Lee, Yvonne Hitchcock, Youngho Park, Sangjae Moon

An Access Control Scheme for Partially Ordered Set Hierarchy with Provable Security

Abstract

In a hierarchical structure, an entity has access to another if and only if the former is a superior of the later. The access control scheme for a hierarchy represented by a partially ordered set (poset) has been researched intensively in the past years. In this paper, we propose a new scheme that achieves the best performance of previous schemes and is provably secure under a comprehensive security model.

Jiang Wu, Ruizhong Wei

Hash Functions

Breaking a New Hash Function Design Strategy Called SMASH

Abstract

We present a collision attack on SMASH. SMASH was proposed as a new hash function design strategy that does not rely on the structure of the MD4 family. The presented attack method allows us to produce almost any desired difference in the chaining variables of the iterated hash function. Due to the absence of a secret key, we are able to construct differences with probability 1. Furthermore, we get only few constraints on the colliding messages, which allows us to construct meaningful collisions. The presented collision attack uses negligible resources and we conjecture that it works for all hash functions built following the design strategy of SMASH.

Norbert Pramstaller, Christian Rechberger, Vincent Rijmen

Analysis of a SHA-256 Variant

Abstract

SHA-256 is a cryptographic hash function which was proposed in 2000 as a new generation of SHA functions and was adopted as FIPS standard in 2002. In this paper we will consider a SHA-256 variant and a SHACAL-2 variant in which every arithmetic addition is replaced by XOR operation. We call the SHA-256 variant SHA-2-XOR and the SHACAL-2 variant SHACAL-2-XOR respectively. We will present a differential attack on these constructions by using one-round iterative differential characteristics with probability 2^− 8 we identified. Our result shows that SHACAL-2-XOR with up to 31 rounds out of 64 has a weakness of randomness and that SHA-2-XOR with up to 34 rounds has a weakness of pseudo-collision resistance. Using the 31-round distinguisher, we present an attack on SHACAL-2-XOR with up to 32 rounds. We also show that no 2-round iterative patterns with probability higher than 2^− 16 exist.

Hirotaka Yoshida, Alex Biryukov

Impact of Rotations in SHA-1 and Related Hash Functions

Abstract

SHA-1 uses a single set of rotation constants within the compression function. However, most other members of the MD4 family of hash functions use multiple sets of rotation constants, i.e. the rotation amounts change with the step being processed.

To our knowledge, no design rationales on the choice of rotation constants are given on any of these hash functions. This is the first paper that analyzes rotations in iterated hash functions. We focus on SHA-1-like hash functions and use recent developments in the analysis of these hash functions to evaluate the security implications of using multiple sets of rotation constants in the compression function instead of a single set. Additionally, we give some observations on the set of constants used in SHA-0 and SHA-1.

Norbert Pramstaller, Christian Rechberger, Vincent Rijmen

Protocols for RFID Tags

A Scalable, Delegatable Pseudonym Protocol Enabling Ownership Transfer of RFID Tags

(Extended Abstract)

Abstract

The ability to link two different sightings of the same Radio Frequency Identification (RFID) tag enables invasions of privacy. The problem is aggravated when an item, and the tag attached to it, changes hands during the course of its lifetime. After such an ownership transfer, the new owner should be able to read the tag but the old owner should not.

We address these issues through an RFID pseudonym protocol. Each time it is queried, the RFID tag emits a different pseudonym using a pseudo-random function. Without consent of a special Trusted Center that shares secrets with the tag, it is infeasible to map the pseudonym to the tag’s real identity. We present a scheme for RFID pseudonyms that works with legacy, untrusted readers, requires only one message from tag to reader, and is scalable: decoding tag pseudonyms takes work logarithmic in the number of tags. Our scheme further allows for time-limited delegation, so that we can give an RFID reader the power to disambiguate a limited number of pseudonyms without further help from the Trusted Center. We show how RFID pseudonyms facilitate the transfer of ownership of RFID tags between mutually distrustful parties.

Our scheme requires only limited cryptographic functionality from the tag: we need a pseudo-random function (PRF) and the ability to update tag state or to generate random numbers. Tag storage and communication requirements are modest: we give example parameters for a deployment of one million tags in which each tag stores only 128 bits, makes 6 PRF evaluations, and sends 158 bits each time it is read.

David Molnar, Andrea Soppera, David Wagner

Reducing Time Complexity in RFID Systems

Abstract

Radio frequency identification systems based on low-cost computing devices is the new plaything that every company would like to adopt. Its goal can be either to improve the productivity or to strengthen the security. Specific identification protocols based on symmetric challenge-response have been developed in order to assure the privacy of the device bearers. Although these protocols fit the devices’ constraints, they always suffer from a large time complexity. Existing protocols require O(n) cryptographic operations to identify one device among n.

Molnar and Wagner suggested a method to reduce this complexity to O(log n). We show that their technique could degrade the privacy if the attacker has the possibility to tamper with at least one device. Because low-cost devices are not tamper-resistant, such an attack could be feasible. We give a detailed analysis of their protocol and evaluate the threat. Next, we extend an approach based on time-memory trade-offs whose goal is to improve Ohkubo, Suzuki, and Kinoshita’s protocol. We show that in practice this approach reaches the same performances as Molnar and Wagner’s method, without degrading privacy.

Gildas Avoine, Etienne Dysli, Philippe Oechslin

Efficient Implementations

Accelerated Verification of ECDSA Signatures

Abstract

Verification of ECDSA signatures is considerably slower than generation of ECDSA signatures. This paper describes a method that can be used to accelerate verification of ECDSA signatures by more than 40% with virtually no added implementation complexity. The method can also be used to accelerate verification for other ElGamal-like signature algorithms, including DSA.

Adrian Antipa, Daniel Brown, Robert Gallant, Rob Lambert, René Struik, Scott Vanstone

Pairing-Friendly Elliptic Curves of Prime Order

Abstract

Previously known techniques to construct pairing-friendly curves of prime or near-prime order are restricted to embedding degree $k \leqslant 6 $. More general methods produce curves over ${\mathbb F}_{p}$ where the bit length of p is often twice as large as that of the order r of the subgroup with embedding degree k; the best published results achieve ρ ≡ log(p)/log(r) ~ 5/4. In this paper we make the first step towards surpassing these limitations by describing a method to construct elliptic curves of prime order and embedding degree k = 12. The new curves lead to very efficient implementation: non-pairing operations need no more than ${\mathbb F}_{p^4}$ arithmetic, and pairing values can be compressed to one third of their length in a way compatible with point reduction techniques. We also discuss the role of large CM discriminants D to minimize ρ; in particular, for embedding degree k = 2q where q is prime we show that the ability to handle log(D)/log(r) ~ (q–3)/(q–1) enables building curves with ρ ~ q/(q–1).

Paulo S. L. M. Barreto, Michael Naehrig

Minimality of the Hamming Weight of the τ-NAF for Koblitz Curves and Improved Combination with Point Halving

Abstract

In order to efficiently perform scalar multiplications on elliptic Koblitz curves, expansions of the scalar to a complex base associated with the Frobenius endomorphism are commonly used. One such expansion is the τ-adic NAF, introduced by Solinas. Some properties of this expansion, such as the average weight, are well known, but in the literature there is no proof of its optimality, i.e. that it always has minimal weight. In this paper we provide the first proof of this fact.

Point halving, being faster than doubling, is also used to perform fast scalar multiplications on generic elliptic curves over binary fields. Since its computation is more expensive than that of the Frobenius, halving was thought to be uninteresting for Koblitz curves. At PKC 2004, Avanzi, Ciet, and Sica combined Frobenius operations with one point halving to compute scalar multiplications on Koblitz curves using on average 14% less group additions than with the usual τ-and-add method without increasing memory usage. The second result of this paper is an improvement over their expansion. The new representation, called the wide-double-NAF, is not only simpler to compute, but it is also optimal in a suitable sense. In fact, it has minimal Hamming weight among all τ-adic expansions with digits {0,±1} that allow one halving to be inserted in the corresponding scalar multiplication algorithm. The resulting scalar multiplication requires on average 25% less group operations than the Frobenius method, and is thus 12.5% faster than the previously known combination.

Roberto Maria Avanzi, Clemens Heuberger, Helmut Prodinger

SPA Resistant Left-to-Right Integer Recodings

Abstract

We present two left-to-right integer recodings which can be used to perform scalar multiplication with a fixed sequence of operations. These recodings make it possible to have a simple power analysis resistant implementation of a group-based cryptosystem without using unified formulas or introducing dummy operations. This approach is very useful for groups in which the doubling step are less expensive than the addition step, for example with hyperelliptic curves over binary fields or elliptic curves with mixed coordinates.

Nicolas Thériault

Efficient FPGA-Based Karatsuba Multipliers for Polynomials over ${\mathbb F}_{2}$

Abstract

We study different possibilities of implementing the Karatsuba multiplier for polynomials over ${\mathbb F}_{2}$ on FPGAs.

This is a core task for implementing finite fields of characteristic 2. Algorithmic and platform dependent optimizations yield efficient hardware designs. The resulting structure is hybrid in two different aspects. On the one hand, a combination of the classical and the Karatsuba methods decreases the number of bit operations. On the other hand, a mixture of sequential and combinational circuit design techniques includes pipelining and can be adapted flexibly to time-area constraints. The approach—both theory and implementation—can be viewed as a further step towards taming the machinery of fast algorithmics for hardware applications.

Joachim von zur Gathen, Jamshid Shokrollahi

Backmatter

Titel: Selected Areas in Cryptography
herausgegeben von: Bart Preneel
Stafford Tavares
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-33109-4
Print ISBN: 978-3-540-33108-7
DOI: https://doi.org/10.1007/11693383

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Stream Ciphers I

Conditional Estimators: An Effective Attack on A5/1

Cryptanalysis of the F-FCSR Stream Cipher Family

Fault Attacks on Combiners with Memory

Block Ciphers

New Observation on Camellia

Proving the Security of AES Substitution-Permutation Network

Modes of Operation

An Attack on CFB Mode Encryption as Used by OpenPGP

Parallelizable Authentication Trees

Improved Time-Memory Trade-Offs with Multiple Data

Public Key Cryptography

A Space Efficient Backdoor in RSA and Its Applications

An Efficient Public Key Cryptosystem with a Privacy Enhanced Double Decryption Mechanism

Stream Ciphers II

On the (Im)Possibility of Practical and Secure Nonlinear Filters and Combiners

Rekeying Issues in the MUGI Stream Cipher

Key Establishment Protocols and Access Control

Tree-Based Key Distribution Patterns

Provably Secure Tripartite Password Protected Key Exchange Protocol Based on Elliptic Curves

An Access Control Scheme for Partially Ordered Set Hierarchy with Provable Security

Hash Functions

Breaking a New Hash Function Design Strategy Called SMASH

Analysis of a SHA-256 Variant

Impact of Rotations in SHA-1 and Related Hash Functions

Protocols for RFID Tags

A Scalable, Delegatable Pseudonym Protocol Enabling Ownership Transfer of RFID Tags

Reducing Time Complexity in RFID Systems

Efficient Implementations

Accelerated Verification of ECDSA Signatures

Pairing-Friendly Elliptic Curves of Prime Order

Minimality of the Hamming Weight of the τ-NAF for Koblitz Curves and Improved Combination with Point Halving

SPA Resistant Left-to-Right Integer Recodings

Efficient FPGA-Based Karatsuba Multipliers for Polynomials over ${\mathbb F}_{2}$

Backmatter

Premium Partner