main-content

## Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the 18th Annual International Workshop on Selected Areas in Cryptography, SAC 2011, held in Toronto, Canada in August 2011. The 23 revised full papers presented together with 2 invited papers were carefully reviewed and selected from 92 submissions. The papers are organized in topical sections on cryptanalysis of hash functions, security in clouds, bits and randomness, cryptanalysis of ciphers, cryptanalysis of public-key crypthography, cipher implementation, new designs and mathematical aspects of applied cryptography.

## Inhaltsverzeichnis

### Boomerang Distinguishers on MD4-Family: First Practical Results on Full 5-Pass HAVAL

Abstract
In this paper, we study a boomerang attack approach on MD4-based hash functions, and present a practical 4-sum distinguisher against the compression function of the full 5-pass HAVAL. Our approach is based on the previous work by Kim et al., which proposed the boomerang distinguisher on the encryption mode of MD4, MD5, and HAVAL in the related-key setting. Firstly, we prove that the differential path for 5-pass HAVAL used in the previous boomerang distinguisher contains a critical flaw and thus the attack cannot work. We then search for new differential paths. Finally, by using the new paths, we mount the distinguisher on the compression function of the full 5-pass HAVAL which generates a 4-sum quartet with a complexity of approximately 211 compression function computations. As far as we know, this is the first result on the full compression function of 5-pass HAVAL that can be computed in practice. We also point out that the 4-sum distinguisher can also be constructed for other MD4-based hash functions such as MD5, 3-pass HAVAL, and 4-pass HAVAL. Our attacks are implemented on a PC and we present a generated 4-sum quartet for each attack target.
Yu Sasaki

### Improved Analysis of ECHO-256

Abstract
ECHO-256 is a second-round candidate of the SHA-3 competition. It is an AES-based hash function that has attracted a lot of interest and analysis. Up to now, the best known attacks were a distinguisher on the full internal permutation and a collision on four rounds of its compression function. The latter was the best known analysis on the compression function as well as the one on the largest number of rounds so far. In this paper, we extend the compression function results to get a distinguisher on 7 out of 8 rounds using rebound techniques. We also present the first 5-round collision attack on the ECHO-256 hash function.
Jérémy Jean, María Naya-Plasencia, Martin Schläffer

### Provable Chosen-Target-Forced-Midfix Preimage Resistance

Abstract
This paper deals with definitional aspects of the herding attack of Kelsey and Kohno, and investigates the provable security of several hash functions against herding attacks.
Firstly, we define the notion of chosen-target-forced-midfix (CTFM) as a generalization of the classical herding (chosen-target-forced-prefix) attack to the cases where the challenge message is not only a prefix but may appear at any place in the preimage. Additionally, we identify four variants of the CTFM notion in the setting where salts are explicit input parameters to the hash function. Our results show that including salts without weakening the compression function does not add up to the CTFM security of the hash function.
Our second and main technical result is a proof of CTFM security of the classical Merkle-Damgård construction. The proof demonstrates in the ideal model that the herding attack of Kelsey and Kohno is optimal (asymptotically) and no attack with lower complexity exists. Our security analysis applies to a wide class of narrow-pipe Merkle-Damgård based iterative hash functions, including enveloped Merkle-Damgård, Merkle-Damgård with permutation, HAIFA, zipper hash and hash-twice hash functions. To our knowledge, this is the first positive result in this field.
Finally, having excluded salts from the possible tool set for improving narrow-pipe designs’ CTFM resistance, we resort to various message modification techniques. Our findings, however, result in the negative and we demonstrate CTFM attacks with complexity of the same order as the Merkle-Damgård herding attack on a broad class of narrow-pipe schemes with specific message modifications.
Elena Andreeva, Bart Mennink

### On CCA-Secure Somewhat Homomorphic Encryption

Abstract
It is well known that any encryption scheme which supports any form of homomorphic operation cannot be secure against adaptive chosen ciphertext attacks. The question then arises as to what is the most stringent security definition which is achievable by homomorphic encryption schemes. Prior work has shown that various schemes which support a single homomorphic encryption scheme can be shown to be IND-CCA1, i.e. secure against lunchtime attacks. In this paper we extend this analysis to the recent fully homomorphic encryption scheme proposed by Gentry, as refined by Gentry, Halevi, Smart and Vercauteren. We show that the basic Gentry scheme is not IND-CCA1; indeed a trivial lunchtime attack allows one to recover the secret key. We then show that a minor modification to the variant of the somewhat homomorphic encryption scheme of Smart and Vercauteren will allow one to achieve IND-CCA1, indeed PA-1, in the standard model assuming a lattice based knowledge assumption. We also examine the security of the scheme against another security notion, namely security in the presence of ciphertext validity checking oracles; and show why CCA-like notions are important in applications in which multiple parties submit encrypted data to the “cloud” for secure processing.
Jake Loftus, Alexander May, Nigel P. Smart, Frederik Vercauteren

### Efficient Schemes for Anonymous Yet Authorized and Bounded Use of Cloud Resources

Abstract
In this paper we introduce anonymous yet authorized and bounded cloud resource schemes. Contrary to many other approaches to security and privacy in the cloud, we aim at hiding behavioral information, i.e. consumption patterns, of users consuming their cloud resources, e.g. CPU time or storage space, from a cloud provider. More precisely, users should be able to purchase a contingent of resources from a cloud provider and be able to anonymously and unlinkably consume their resources till their limit (bound) is reached. Furthermore, they can also reclaim these resources back anonymously, e.g. if they delete some stored data. We present a definition of such schemes along with a security model and present an instantiation based on Camenisch-Lysyanskaya signatures. Then, we extend the scheme to another scheme providing even more privacy for users, i.e. by even hiding the issued resource limit (bound) during interactions and thus providing full anonymity to users, and present some useful extensions for both schemes. We also support our theoretical claims with experimental results obtained from an implementation that show the practicality of our schemes.
Daniel Slamanig

### Group Law Computations on Jacobians of Hyperelliptic Curves

Abstract
We derive an explicit method of computing the composition step in Cantor’s algorithm for group operations on Jacobians of hyperelliptic curves. Our technique is inspired by the geometric description of the group law and applies to hyperelliptic curves of arbitrary genus. While Cantor’s general composition involves arithmetic in the polynomial ring $$\mathbb{F}_q[x]$$, the algorithm we propose solves a linear system over the base field which can be written down directly from the Mumford coordinates of the group elements.
We apply this method to give more efficient formulas for group operations in both affine and projective coordinates for cryptographic systems based on Jacobians of genus 2 hyperelliptic curves in general form.
Craig Costello, Kristin Lauter

### Cryptographic Analysis of All 4 × 4-Bit S-Boxes

Abstract
We present cryptanalytic results of an exhaustive search of all 16! bijective 4-bit S-Boxes. Previously affine equivalence classes have been exhaustively analyzed in 2007 work by Leander and Poschmann. We extend on this work by giving further properties of the optimal S-Box linear equivalence classes. In our main analysis we consider two S-Boxes to be cryptanalytically equivalent if they are isomorphic up to the permutation of input and output bits and a XOR of a constant in the input and output. We have enumerated all such equivalence classes with respect to their differential and linear properties. These equivalence classes are equivalent not only in their differential and linear bounds but also have equivalent algebraic properties, branch number and circuit complexity. We describe a “golden” set of S-boxes that have ideal cryptographic properties. We also present a comparison table of S-Boxes from a dozen published cryptographic algorithms.
Markku-Juhani O. Saarinen

### The Cryptographic Power of Random Selection

Abstract
The principle of random selection and the principle of adding biased noise are new paradigms used in several recent papers for constructing lightweight RFID authentication protocols. The cryptographic power of adding biased noise can be characterized by the hardness of the intensively studied Learning Parity with Noise (LPN) Problem. In analogy to this, we identify a corresponding learning problem for random selection and study its complexity. Given L secret linear functions $$f_1,\ldots,f_L:\mbox{\{0,1\}}^n\longrightarrow\mbox{\{0,1\}}^a$$, $$RandomSelect\left(L,n,a\right)$$ denotes the problem of learning f 1,…,f L from values $$\left(u,f_l\left(u\right)\right)$$, where the secret indices l ∈ {1,…,L} and the inputs $$u\in\mbox{\{0,1\}^n}$$ are randomly chosen by an oracle. We take an algebraic attack approach to design a nontrivial learning algorithm for this problem, where the running time is dominated by the time needed to solve full-rank systems of linear equations over $$O\left(n^L\right)$$ unknowns. In addition to the mathematical findings relating correctness and average running time of the suggested algorithm, we also provide an experimental assessment of our results.
Matthias Krause, Matthias Hamann

### Proof of Empirical RC4 Biases and New Key Correlations

Abstract
In SAC 2010, Sepehrdad, Vaudenay and Vuagnoux have reported some empirical biases between the secret key, the internal state variables and the keystream bytes of RC4, by searching over a space of all linear correlations between the quantities involved. In this paper, for the first time, we give theoretical proofs for all such significant empirical biases. Our analysis not only builds a framework to justify the origin of these biases, it also brings out several new conditional biases of high order. We establish that certain conditional biases reported earlier are correlated with a third event with much higher probability. This gives rise to the discovery of new keylength-dependent biases of RC4, some as high as 50/N, where N is the size of the RC4 permutation. The new biases in turn result in successful keylength prediction from the initial keystream bytes of the cipher.
Sourav Sen Gupta, Subhamoy Maitra, Goutam Paul, Santanu Sarkar

### Combined Differential and Linear Cryptanalysis of Reduced-Round PRINTcipher

Abstract
In this paper we analyze the security of PRINTcipher using a technique that combines differential and linear cryptanalysis. This technique is different from differential-linear cryptanalysis. We use linear approximations to increase the probability of differential characteristics. We show that specific choices of some of the key bits give rise to a certain differential characteristic probability, which is far higher than the best characteristic probability claimed by the designers. We give the underlying mechanism of this probability increase. We have developed attacks on 29 and 31 rounds of PRINTcipher-48 for 4.54% and 0.036% of the keys, respectively. Moreover, we have implemented the proposed attack algorithm on 20 rounds of the cipher.
Ferhat Karakoç, Hüseyin Demirci, A. Emre Harmancı

### Practical Attack on the Full MMB Block Cipher

Abstract
Modular Multiplication based Block Cipher (MMB) is a block cipher designed by Daemen et al. as an alternative to the IDEA block cipher. In this paper, we give a practical sandwich attack on MMB with adaptively chosen plaintexts and ciphertexts. By constructing a 5-round sandwich distinguisher of the full 6-round MMB with probability 1, we recover the main key of MMB with text complexity 240 and time complexity 240 MMB encryptions. We also present a chosen plaintexts attack on the full MMB by employing the rectangle-like sandwich attack, which the complexity is 266.5 texts, 266.5 MMB encryptions and 270.5 bytes of memory. In addition, we introduce an improved differential attack on MMB with 296 chosen plaintexts, 296 encryptions and 266 bytes of memory. Especially, even if MMB is extended to 7 rounds, the improved differential attack is applicable with the same complexity as that of the full MMB.
Keting Jia, Jiazhe Chen, Meiqin Wang, Xiaoyun Wang

### Conditional Differential Cryptanalysis of Trivium and KATAN

Abstract
The concept of conditional differential cryptanalysis has been applied to NLFSR-based cryptosystems at ASIACRYPT 2010. We improve the technique by using automatic tools to find and analyze the involved conditions. Using these improvements we cryptanalyze the stream cipher Trivium and the KATAN family of lightweight block ciphers. For both ciphers we obtain new cryptanalytic results. For reduced variants of Trivium we obtain a class of weak keys that can be practically distinguished up to 961 of 1152 rounds. For the KATAN family we focus on its security in the related-key scenario and obtain practical key-recovery attacks for 120, 103 and 90 of 254 rounds of KATAN32, KATAN48 and KATAN64, respectively.
Simon Knellwolf, Willi Meier, María Naya-Plasencia

### Some Instant- and Practical-Time Related-Key Attacks on KTANTAN32/48/64

Abstract
The hardware-attractive block cipher family KTANTAN was studied by Bogdanov and Rechberger who identified flaws in the key schedule and gave a meet-in-the-middle attack. We revisit their result before investigating how to exploit the weakest key bits. We then develop several related-key attacks, e.g., one on KTANTAN32 which finds 28 key bits in time equivalent to 23.0 calls to the full KTANTAN32 encryption. The main result is a related-key attack requiring 228.44 time (half a minute on a current CPU) to recover the full 80-bit key. For KTANTAN48, we find three key bits in the time of one encryption, and give several other attacks, including full key recovery. For KTANTAN64, the attacks are only slightly more expensive, requiring 210.71 time to find 38 key bits, and 232.28 for the entire key. For all attacks, the requirements on related-key material are modest as in the forward and backward directions, we only need to flip a single key bit. All attacks succeed with probability one. Our attacks directly contradict the designers’ claims. We discuss why this is, and what can be learnt from this.
Martin Ågren

### Analysis of the Initial and Modified Versions of the Candidate 3GPP Integrity Algorithm 128-EIA3

Abstract
In this paper we investigate the security of the two most recent versions of the message authentication code 128-EIA3, which is considered for adoption as a third integrity algorithm in the emerging 3GPP standard LTE. We first present an efficient existential forgery attack against the June 2010 version of the algorithm. This attack allows, given any message and the associated MAC value under an unknown integrity key and an initial vector, to predict the MAC value of a related message under the same key and the same initial vector with a success probability 1/2. We then briefly analyse the tweaked version of the algorithm that was introduced in January 2011 to circumvent this attack. We give some evidence that while this new version offers a provable resistance against similar forgery attacks under the assumption that (key, IV) pairs are never reused by any legitimate sender or receiver, some of its design features limit its resilience against IV reuse.
Thomas Fuhr, Henri Gilbert, Jean-René Reinhard, Marion Videau

### New Insights on Impossible Differential Cryptanalysis

Abstract
Since its introduction, impossible differential cryptanalysis has been applied to many ciphers. Besides the specific application of the technique in various instances, there are some very basic results which apply to generic structures of ciphers, e.g., the well known 5-round impossible differential of Feistel ciphers with bijective round functions.
In this paper we present a new approach for the construction and the usage of impossible differentials for Generalized Feistel structures. The results allow to extend some of the previous impossible differentials by one round (or more), answer an open problem about the ability to perform this kind of analysis, and tackle, for the first time the case of non-bijective round functions.
Charles Bouillaguet, Orr Dunkelman, Pierre-Alain Fouque, Gaëtan Leurent

### A Unified Framework for Small Secret Exponent Attack on RSA

Abstract
We address a lattice based method on small secret exponent attack on RSA scheme. Boneh and Durfee reduced the attack into finding small roots of a bivariate modular equation: $$x(N+1+y)+1 \equiv 0 (\bmod\; e)$$, where N is an RSA moduli and e is the RSA public key. Boneh and Durfee proposed a lattice based algorithm for solving the problem. When the secret exponent d is less than N 0.292, their method breaks RSA scheme. Since the lattice used in the analysis is not full-rank, the analysis is not easy. Blömer and May gave an alternative algorithm. Although their bound d ≤ N 0.290 is worse than Boneh–Durfee result, their method used a full rank lattice. However, the proof for their bound is still complicated. Herrmann and May gave an elementary proof for the Boneh–Durfee’s bound: d ≤ N 0.292. In this paper, we first give an elementary proof for achieving the bound of Blömer–May: d ≤ N 0.290. Our proof employs unravelled linearization technique introduced by Herrmann and May and is rather simpler than Blömer–May’s proof. Then, we provide a unified framework to construct a lattice that are used for solving the problem, which includes two previous method: Herrmann–May and Blömer–May methods as a special case. Furthermore, we prove that the bound of Boneh–Durfee: d ≤ N 0.292 is still optimal in our unified framework.
Noboru Kunihiro, Naoyuki Shinohara, Tetsuya Izu

### Very Compact Hardware Implementations of the Blockcipher CLEFIA

Abstract
The 128-bit blockcipher CLEFIA is known to be highly efficient in hardware implementations. This paper proposes very compact hardware implementations of CLEFIA-128. Our implementations are based on novel serialized architectures in the data processing block. Three types of hardware architectures are implemented and synthesized using a 0.13 μm standard cell library. In the smallest implementation, the area requirements are only 2,488 GE, which are about half of the previous smallest implementation as far as we know. Furthermore, only additional 116 GE enable to support decryption.
Toru Akishita, Harunaga Hiwatari

### Another Look at Tightness

Abstract
We examine a natural, but non-tight, reductionist security proof for deterministic message authentication code (MAC) schemes in the multi-user setting. If security parameters for the MAC scheme are selected without accounting for the non-tightness in the reduction, then the MAC scheme is shown to provide a level of security that is less than desirable in the multi-user setting. We find similar deficiencies in the security assurances provided by non-tight proofs when we analyze some protocols in the literature including ones for network authentication and aggregate MACs. Our observations call into question the practical value of non-tight reductionist security proofs. We also exhibit attacks on authenticated encryption schemes, disk encryption schemes, and stream ciphers in the multi-user setting.
Sanjit Chatterjee, Alfred Menezes, Palash Sarkar

### Duplexing the Sponge: Single-Pass Authenticated Encryption and Other Applications

Abstract
This paper proposes a novel construction, called duplex, closely related to the sponge construction, that accepts message blocks to be hashed and–at no extra cost–provides digests on the input blocks received so far. It can be proven equivalent to a cascade of sponge functions and hence inherits its security against single-stage generic attacks. The main application proposed here is an authenticated encryption mode based on the duplex construction. This mode is efficient, namely, enciphering and authenticating together require only a single call to the underlying permutation per block, and is readily usable in, e.g., key wrapping. Furthermore, it is the first mode of this kind to be directly based on a permutation instead of a block cipher and to natively support intermediate tags. The duplex construction can be used to efficiently realize other modes, such as a reseedable pseudo-random bit sequence generators and a sponge variant that overwrites part of the state with the input block rather than to XOR it in.
Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche

### Blockcipher-Based Double-Length Hash Functions for Pseudorandom Oracles

Abstract
PRO (Pseudorandom Oracle) is an important security of hash functions because it ensures that the PRO hash function inherits all properties of a random oracle in single stage games up to the PRO bound (e.g., collision resistant security, preimage resistant security and so on). In this paper, we propose new blockcipher-based double-length hash functions, which are PROs up to $$\mathcal{O}(2^n)$$ query complexity in the ideal cipher model. Our hash functions use a single blockcipher, which encrypts an n-bit string using a 2n-bit key, and maps an input of arbitrary length to an n-bit output. Since many blockciphers supports a 2n-bit key (e.g. AES supports a 256-bit key), the assumption to use the 2n-bit key length blockcipher is acceptable. To our knowledge, this is the first time double-length hash functions based on a single (practical size) blockcipher with birthday PRO security.
Yusuke Naito

### ASC-1: An Authenticated Encryption Stream Cipher

Abstract
The goal of the modes of operation for authenticated encryption is to achieve faster encryption and message authentication by performing both the encryption and the message authentication in a single pass as opposed to the traditional encrypt-then-mac approach, which requires two passes. Unfortunately, the use of a block cipher as a building block limits the performance of the authenticated encryption schemes to at most one message block per block cipher evaluation.
In this paper, we propose the authenticated encryption scheme ASC-1 (Authenticating Stream Cipher One). Similarly to LEX, ASC-1 uses leak extraction from different AES rounds to compute the key material that is XOR-ed with the message to compute the ciphertext. Unlike LEX, the ASC-1 operates in a CFB fashion to compute an authentication tag over the encrypted message. We argue that ASC-1 is secure by reducing its (IND-CCA , INT-CTXT) security to the problem of distinguishing the case when the round keys are uniformly random from the case when the round keys are generated by a key scheduling algorithm.
Goce Jakimoski, Samant Khajuria

### On Various Families of Twisted Jacobi Quartics

Abstract
We provide several results on some families of twisted Jacobi quartics. We give new addition formulæ for two models of twisted Jacobi quartic elliptic curves, which represent respectively 1/6 and 2/3 of all elliptic curves, with respective costs 7M + 3S + D a and 8M + 3 S + D a . These formulæ allow addition and doubling of points, except for points differing by a point of order two.
Furthermore, we give an intrinsic characterization of elliptic curves represented by the classical Jacobi quartic, by the action of the Frobenius endomorphism on the 4-torsion subgroup. This allows us to compute the exact proportion of elliptic curves representable by various models (the three families of Jacobi quartics, plus Edwards and Huff curves) from statistics on this Frobenius action.
Jérôme Plût

### Improved Three-Way Split Formulas for Binary Polynomial Multiplication

Abstract
In this paper we deal with 3-way split formulas for binary field multiplication with five recursive multiplications of smaller sizes. We first recall the formula proposed by Bernstein at CRYPTO 2009 and derive the complexity of a parallel multiplier based on this formula. We then propose a new set of 3-way split formulas with five recursive multiplications based on field extension. We evaluate their complexities and provide a comparison.
Murat Cenk, Christophe Negre, M. Anwar Hasan

### Sublinear Scalar Multiplication on Hyperelliptic Koblitz Curves

Abstract
Recently, Dimitrov et. al. [5] proposed a novel algorithm for scalar multiplication of points on elliptic Koblitz curves that requires a provably sublinear number of point additions in the size of the scalar. Following some ideas used by this article, most notably double-base expansions for integers, we generalize their methods to hyperelliptic Koblitz curves of arbitrary genus over any finite field, obtaining a scalar multiplication algorithm requiring a sublinear number of divisor additions.
Hugo Labrande, Michael J. Jacobson

### Faster Hashing to ${\mathbb G}_2$

Abstract
An asymmetric pairing $$e\colon{\mathbb{G}}_2\times{\mathbb{G}}_1\to{\mathbb{G}}_T$$ is considered such that $${\mathbb{G}}_1=E({\mathbb F}_p)[r]$$ and $${\mathbb{G}}_2=\tilde E({\mathbb F}_{p^{k/d}})[r]$$, where k is the embedding degree of the elliptic curve $$E/{\mathbb F}_p$$, r is a large prime divisor of $$\# E({\mathbb F}_p)$$, and $$\tilde E$$ is the degree-d twist of E over $${\mathbb F}_{p^{k/d}}$$ with $$r \mid \tilde E ({\mathbb F}_{p^{k/d}} )$$. Hashing to $${\mathbb{G}}_1$$ is considered easy, while hashing to $${\mathbb{G}}_2$$ is done by selecting a random point Q in $$\tilde E({\mathbb F}_{p^{k/d}})$$ and computing the hash value cQ, where c·r is the order of $$\tilde E({\mathbb F}_{p^{k/d}})$$. We show that for a large class of curves, one can hash to $${\mathbb{G}}_2$$ in $$\textup{O}(1/\varphi (k)\log c)$$ time, as compared with the previously fastest-known $$\textup{O}(\log p)$$. In the case of BN curves, we are able to double the speed of hashing to $${\mathbb{G}}_2$$. For higher-embedding-degree curves, the results can be more dramatic. We also show how to reduce the cost of the final-exponentiation step in a pairing calculation by a fixed number of field multiplications.
Laura Fuentes-Castañeda, Edward Knapp, Francisco Rodríguez-Henríquez

### Backmatter

Weitere Informationen