main-content

## Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the 19th International Conference on Selected Areas in Cryptography, SAC 2012, held in Windsor, Ontario, Canada, in August 2012. The 24 papers presented were carefully reviewed and selected from 87 submissions. They are organized in topical sections named: cryptanalysis, digital signatures, stream ciphers, implementations, block cipher cryptanalysis, lattices, hashfunctions, blockcipher constructions, and miscellaneous.

## Inhaltsverzeichnis

### An All-In-One Approach to Differential Cryptanalysis for Small Block Ciphers

Abstract
We present a framework that unifies several standard differential techniques. This unified view allows us to consider many, potentially all, output differences for a given input difference and to combine the information derived from them in an optimal way. We then propose a new attack that implicitly mounts several standard, truncated, impossible, improbable and possible future variants of differential attacks in parallel and hence allows to significantly improve upon known differential attacks using the same input difference. To demonstrate the viability of our techniques, we apply them to KATAN-32. In particular, our attack allows us to break 115 rounds of KATAN-32. For this, our attack exploits the non-uniformity of the difference distribution after 91 rounds which is 20 rounds more than the previously best known differential characteristic.
Martin R. Albrecht, Gregor Leander

### A New Method for Solving Polynomial Systems with Noise over $\mathbb{F}_2$ and Its Applications in Cold Boot Key Recovery

Abstract
The family of Max-PoSSo problems is about solving polynomial systems with noise, and is analogous to the well-known Max-SAT family of problems when the ground field is $$\mathbb{F}_2$$. In this paper, we present a new method called ISBS for solving the family of Max-PoSSo problems over $$\mathbb{F}_2$$. This method is based on the ideas of incrementally solving polynomial system and searching the values of polynomials with backtracking. The ISBS method can be combined with different algebraic methods for solving polynomial systems, such as the Gröbner Basis method or the Characteristic Set(CS) method. By combining with the CS method, we implement ISBS and apply it in Cold Boot attacks. A Cold Boot attack is a type of side channel attack in which an attacker recover cryptographic key material from DRAM relies on the data remanence property of DRAM. Cold Boot key recovery problems of block ciphers can be modeled as Max-PoSSo problems over $$\mathbb{F}_2$$. We apply the ISBS method to solve the Cold Boot key recovery problems of AES and Serpent, and obtain some experimental results which are better than the existing ones.
Zhenyu Huang, Dongdai Lin

### Cryptanalysis of the Xiao – Lai White-Box AES Implementation

Abstract
In the white-box attack context, i.e., the setting where an implementation of a cryptographic algorithm is executed on an untrusted platform, the adversary has full access to the implementation and its execution environment. In 2002, Chow et al. presented a white-box AES implementation which aims at preventing key-extraction in the white-box attack context. However, in 2004, Billet et al. presented an efficient practical attack on Chow et al.’s white-box AES implementation. In response, in 2009, Xiao and Lai proposed a new white-box AES implementation which is claimed to be resistant against Billet et al.’s attack. This paper presents a practical cryptanalysis of the white-box AES implementation proposed by Xiao et al. The linear equivalence algorithm presented by Biryukov et al. is used as a building block. The cryptanalysis efficiently extracts the AES key from Xiao et al.’s white-box AES implementation with a work factor of about 232.
Yoni De Mulder, Peter Roelse, Bart Preneel

### A Practical Leakage-Resilient Signature Scheme in the Generic Group Model

Abstract
We propose a leakage-resilient signature scheme in the continual leakage model that is based on a well-known identity-based encryption scheme by Boneh and Boyen (Eurocrypt 2004). The proposed signature scheme is the most efficient among the existing schemes that allow for continual leakage. Its efficiency is close to that of non leakage-resilient pairing-based signature schemes. It tolerates leakage of almost half of the bits of the secret key at every new signature invocation. We prove the security of the new scheme in the generic bilinear group model.
David Galindo, Srinivas Vivek

### Forward Secure Signatures on Smart Cards

Preliminary version
Abstract
We introduce the forward secure signature scheme XMSS +  and present an implementation for smart cards. It is based on the hash-based signature scheme XMSS. In contrast to the only previous implementation of a hash-based signature scheme on smart cards by Rohde et al., we solve the problem of on-card key generation. Compared to XMSS, we reduce the key generation time from $$\mathcal{O}(n)$$ to $$\mathcal{O}(\sqrt{n})$$, where n is the number of signatures that can be created with one key pair. To the best of our knowledge this is the first implementation of a forward secure signature scheme and the first full implementation of a hash-based signature scheme on smart cards. The resulting runtimes are comparable to those of RSA and ECDSA on the same device. This shows the practicality of forward secure signature schemes, even on constrained devices.
Andreas Hülsing, Christoph Busold, Johannes Buchmann

### Extracts from the SHA-3 Competition

The Start of the Competition
The story of the SHA-3 competition starts with the presentation of surprisingly efficient attacks on several modern hash functions at Eurocrypt 2005 [1, 2] and at Crypto 2005 [3, 4]. Collisions were given for the hash functions MD4, MD5, RIPEMD and SHA-0. An algorithm was shown that can produce collisions for SHA-1 with a complexity that is much lower than previously thought. Before 2005, there were already partial attacks known for several of these hash functions, but only MD4 was really broken [5]. Soon the results were furthere improved and extended to other hash functions. These developments caused NIST to start an effort to develop and standardize a new Secure Hashing Algorithm. This effort was going to be an open competition, similar to the AES competition which it had run from 1998 until 2000.
Vincent Rijmen

### Cryptanalysis of the “Kindle” Cipher

Abstract
In this paper we study a 128-bit-key cipher called PC1 which is used as part of the DRM system of the Amazon Kindle e-book reader. This is the first academic cryptanalysis of this cipher and it shows that PC1 is a very weak stream cipher, and can be practically broken in a known-plaintext and even in a ciphertext-only scenario.
A hash function based on this cipher has also been proposed and is implemented in the binary editor WinHex. We show that this hash function is also vulnerable to a practical attack, which can produce meaningful collisions or second pre-images.
Alex Biryukov, Gaëtan Leurent, Arnab Roy

### Cryptographically Strong de Bruijn Sequences with Large Periods

Abstract
In this paper we first refine Mykkeltveit et al.’s technique for producing de Bruijn sequences through compositions. We then conduct an analysis on an approximation of the feedback functions that generate de Bruijn sequences. The cycle structures of the approximated feedback functions and the linear complexity of a sequence produced by an approximated feedback function are determined. Furthermore, we present a compact representation of an (n + 16)-stage nonlinear feedback shift register (NLFSR) and a few examples of de Bruijn sequences of period 2 n ,  35 ≤ n ≤ 40, which are generated by the recursively constructed NLFSR together with the evaluation of their implementation.
Kalikinkar Mandal, Guang Gong

### Cryptanalysis of the Loiss Stream Cipher

Abstract
Loiss is a byte-oriented stream cipher designed by Dengguo Feng et al. Its design builds upon the design of the SNOW family of ciphers. The algorithm consists of a linear feedback shift register (LFSR) and a non-linear finite state machine (FSM). Loiss utilizes a structure called Byte-Oriented Mixer with Memory (BOMM) in its filter generator, which aims to improve resistance against algebraic attacks, linear distinguishing attacks and fast correlation attacks. In this paper, by exploiting some differential properties of the BOMM structure during the cipher initialization phase, we provide an attack of a practical complexity on Loiss in the related-key model. As confirmed by our experimental results, our attack recovers 92 bits of the 128-bit key in less than one hour on a PC with 3 GHz Intel Pentium 4 processor. The possibility of extending the attack to a resynchronization attack in a single-key model is discussed. We also show that Loiss is not resistant to slide attacks.
Alex Biryukov, Aleksandar Kircanski, Amr M. Youssef

### Efficient Arithmetic on Elliptic Curves over Fields of Characteristic Three

Abstract
This paper presents new explicit formulae for the point doubling, tripling and addition for ordinary Weierstraß elliptic curves with a point of order 3 and their equivalent Hessian curves over finite fields of characteristic three. The cost of basic point operations is lower than that of all previously proposed ones. The new doubling, mixed addition and tripling formulae in projective coordinates require 3M + 2C, 8M + 1C + 1D and 4M + 4C + 1D respectively, where M, C and D is the cost of a field multiplication, a cubing and a multiplication by a constant. Finally, we present several examples of ordinary elliptic curves in characteristic three for high security levels.
Reza R. Farashahi, Hongfeng Wu, Chang-An Zhao

### Efficient Implementation of Bilinear Pairings on ARM Processors

Abstract
As hardware capabilities increase, low-power devices such as smartphones represent a natural environment for the efficient implementation of cryptographic pairings. Few works in the literature have considered such platforms despite their growing importance in a post-PC world. In this paper, we investigate the efficient computation of the Optimal-Ate pairing over Barreto-Naehrig curves in software at different security levels on ARM processors. We exploit state-of-the-art techniques and propose new optimizations to speed up the computation in the tower field and curve arithmetic. In particular, we extend the concept of lazy reduction to inversion in extension fields, analyze an efficient alternative for the sparse multiplication used inside the Miller’s algorithm and reduce further the cost of point/line evaluation formulas in affine and projective homogeneous coordinates. In addition, we study the efficiency of using M-type sextic twists in the pairing computation and carry out a detailed comparison between affine and projective coordinate systems. Our implementations on various mass-market smartphones and tablets significantly improve the state-of-the-art of pairing computation on ARM-powered devices, outperforming by at least a factor of 3.7 the best previous results in the literature.
Gurleen Grewal, Reza Azarderakhsh, Patrick Longa, Shi Hu, David Jao

### Towards Faster and Greener Cryptoprocessor for Eta Pairing on Supersingular Elliptic Curve over $\mathbb{F}_{2^{1223}}$

Abstract
At the CHES workshop last year, Ghosh et al. presented an FPGA based cryptoprocessor, which for the first time ever makes it possible to compute an eta pairing at the 128-bit security level in less than one milli-second. The high performance of their cryptoprocessor comes largely from the use of the Karatsuba method for field multiplication. In this article, for the same type of pairing we propose hybrid sequential/parallel multipliers based on the Toeplitz matrix-vector products and present some optimizations for the final exponentiation, resulting in high performance cryptoprocessors. On the same kind of FPGA devices, our cryptoprocessor performs pairing faster than that of [12] while requiring less hardware resources. We also present ASIC implementations and report that the three-way split multiplier based cryptoprocessor consumes less energy than the two-way.
Jithra Adikari, M. Anwar Hasan, Christophe Negre

### Feasibility and Practicability of Standardized Cryptography on 4-bit Micro Controllers

Abstract
Myriads of ultra-constrained 4-bit micro controllers (MCUs) are deployed in (mostly) legacy devices, some in security sensitive applications, such as remote access and control systems or all sort of sensors. Yet the feasibility and practicability of standardized cryptography on 4-bit MCUs has been mostly neglected. In this work we close this gap and provide, to the best of our knowledge, the first implementations of ECC and SHA-1, and the fastest implementation of AES on a 4-bit MCU. Though it is not the main focus of this paper, we have investigated the SCA resistance trade-offs for ECC by implementing a variety of countermeasures. We hope that our comprehensive, highly energy-efficient crypto library—that even outperforms all previously published implementations on low-power 8-bit MCUs—will give rise to a variety of security functionalities, previously thought to be too demanding for these ultra-constrained devices.
Nisha Jacob, Sirote Saetang, Chien-Ning Chen, Sebastian Kutzner, San Ling, Axel Poschmann

### All Subkeys Recovery Attack on Block Ciphers: Extending Meet-in-the-Middle Approach

Abstract
We revisit meet-in-the-middle (MITM) attacks on block ciphers. Despite recent significant improvements of the MITM attack, its application is still restrictive. In other words, most of the recent MITM attacks work only on block ciphers consisting of a bit permutation based key schedule such as KTANTAN, GOST, IDEA, XTEA, LED and Piccolo. In this paper, we extend the MITM attack so that it can be applied to a wider class of block ciphers. In our approach, MITM attacks on block ciphers consisting of a complex key schedule can be constructed. We regard all subkeys as independent variables, then transform the game that finds the user-provided key to the game that finds all independent subkeys. We apply our approach called all subkeys recovery (ASR) attack to block ciphers employing a complex key schedule such as CAST-128, SHACAL-2, KATAN, FOX128 and Blowfish, and present the best attacks on them with respect to the number of attacked rounds in literature. Moreover, since our attack is simple and generic, it is applied to the block ciphers consisting of any key schedule functions even if the key schedule is an ideal function.
Takanori Isobe, Kyoji Shibutani

### Improved Cryptanalysis of the Block Cipher KASUMI

Abstract
KASUMI is a block cipher which consists of eight Feistel rounds with a 128-bit key. Proposed more than 10 years ago, the confidentiality and integrity of 3G mobile communications systems depend on the security of KASUMI. In the practically interesting single key setting, only up to 6 rounds have been attacked so far. In this paper we use some observations on the FL and FO functions. Combining these observations with a key schedule weakness, we select some special input and output values to refine the general 5-round impossible differentials and propose the first 7-round attack on KASUMI with time and data complexities similar to the previously best 6-round attacks. This leaves now only a single round of security margin.
The new impossible differential attack on the last 7 rounds needs 2114.3 encryptions with 252.5 chosen plaintexts. For the attack on the first 7 rounds, the data complexity is 262 known plaintexts and the time complexity is 2115.8 encryptions.
Keting Jia, Leibo Li, Christian Rechberger, Jiazhe Chen, Xiaoyun Wang

### Meet-in-the-Middle Technique for Integral Attacks against Feistel Ciphers

Abstract
In this paper, an improvement for integral attacks against Feistel ciphers is discussed. The new technique can reduce the complexity of the key recovery phase. This possibly leads to an extension of the number of attacked rounds. In the integral attack, an attacker guesses a part of round keys and performs the partial decryption. The correctness of the guess is judged by examining whether the XOR sum of the results becomes 0 or not. In this paper, it is shown that the computation of the XOR sum of the partial decryptions can be divided into two independent parts if the analysis target adopts the Feistel network or its variant. Then, correct key candidates are efficiently obtained with the meet-in-the-middle approach. The effect of our technique is demonstrated for several Feistel ciphers. Improvements on integral attacks against LBlock, HIGHT, and CLEFIA are presented. Particularly, the number of attacked rounds with integral analysis is extended for LBlock.
Yu Sasaki, Lei Wang

### Attacking (EC)DSA Given Only an Implicit Hint

Abstract
We describe a lattice attack on DSA-like signature schemes under the assumption that implicit information on the ephemeral keys is known. Inspired by the implicit oracle of May and Ritzenhofen presented in the context of RSA (PKC2009), we assume that the ephemeral keys share a certain amount of bits without knowing the value of the shared bits. This work also extends results of Leadbitter, Page and Smart (CHES2004) which use a very similar type of partial information leakage. By eliminating the shared blocks of bits between the ephemeral keys, we provide lattices of small dimension (e.g. equal to the number of signatures) and thus obtain an efficient attack. More precisely, by using the LLL algorithm, the complexity of the attack is polynomial. We show that this method can work when ephemeral keys share certain amount of MSBs and/or LSBs, as well as contiguous blocks of shared bits in the middle. Under the Gaussian heuristic assumption, theoretical bounds on the number of shared bits in function of the number of signed messages are proven. Experimental results show that we are often able to go a few bits beyond the theoretical bound. For instance, if only 2 shared LSBs on each ephemeral keys of 200 signed messages (with no knowledge about the secret key) then the attack reveals the secret key. The success rate of this attack is about 90% when only 1 LSB is shared on each ephemeral keys associated with about 400 signed messages.
Jean-Charles Faugère, Christopher Goyet, Guénaël Renault

### Lattice Reduction for Modular Knapsack

Abstract
In this paper, we present a new methodology to adapt any kind of lattice reduction algorithms to deal with the modular knapsack problem. In general, the modular knapsack problem can be solved using a lattice reduction algorithm, when its density is low. The complexity of lattice reduction algorithms to solve those problems is upper-bounded in the function of the lattice dimension and the maximum norm of the input basis. In the case of a low density modular knapsack-type basis, the weight of maximum norm is mainly from its first column. Therefore, by distributing the weight into multiple columns, we are able to reduce the maximum norm of the input basis. Consequently, the upper bound of the time complexity is reduced.
To show the advantage of our methodology, we apply our idea over the floating-point LLL (L2) algorithm. We bring the complexity from O(d 3 + ε β 2 + d 4 + ε β) to O(d 2 + ε β 2 + d 4 + ε β) for ε < 1 for the low density knapsack problem, assuming a uniform distribution, where d is the dimension of the lattice, β is the bit length of the maximum norm of knapsack-type basis.
We also provide some techniques when dealing with a principal ideal lattice basis, which can be seen as a special case of a low density modular knapsack-type basis.
Thomas Plantard, Willy Susilo, Zhenfei Zhang

### The Boomerang Attacks on the Round-Reduced Skein-512

Abstract
The hash function Skein is one of the five finalists of the NIST SHA-3 competition. It is based on the block cipher Threefish which only uses three primitive operations: modular addition, rotation and bitwise XOR (ARX). This paper studies the boomerang attacks on Skein-512. Boomerang distinguishers on the compression function reduced to 32 and 36 rounds are proposed, with time complexities 2104.5 and 2454 hash computations respectively. Examples of the distinguishers on 28 and 31 rounds are also given. In addition, the boomerang distinguishers are applicable to the key-recovery attacks on reduced Threefish-512. The time complexities for key-recovery attacks reduced to 32-/33-/34-round are about 2181, 2305 and 2424 encryptions. Because the previous boomerang distinguishers for Threefish-512 are in fact not compatible [14], our attacks are the first valid boomerang attacks for the reduced-round Skein-512.
Hongbo Yu, Jiazhe Chen, Xiaoyun Wang

### Boomerang and Slide-Rotational Analysis of the SM3 Hash Function

Abstract
SM3 is a hash function, designed by Xiaoyun Wang et al. and published by the Chinese Commercial Cryptography Administration Office for the use of electronic authentication service system. The design of SM3 builds upon the design of the SHA-2 hash function, but introduces additional strengthening features. In this paper, we present boomerang distinguishers for the SM3 compression function reduced to 32 steps out of 64 steps with complexity 214.4, 33 steps with complexity 232.4, 34 steps with complexity 253.1 and 35 steps with complexity 2117.1. Examples of zero-sum quartets for the 32-step and 33-step SM3 compression function are provided. We also point out a slide-rotational property of SM3-XOR, which exists due to the fact that constants used in the steps are not independent.
Aleksandar Kircanski, Yanzhao Shen, Gaoli Wang, Amr M. Youssef

### Provable Security of BLAKE with Non-ideal Compression Function

Abstract
We analyze the security of the SHA-3 finalist BLAKE. The BLAKE hash function follows the HAIFA design methodology, and as such it achieves optimal preimage, second preimage and collision resistance, and is indifferentiable from a random oracle up to approximately 2 n/2 assuming the underlying compression function is ideal.
In our work we show, however, that the compression function employed by BLAKE exhibits a non-random behavior and is in fact differentiable in only 2 n/4 queries. Our attack undermines the provable security strength of BLAKE in the ideal compression function model, not only with respect to its overall indifferentiability but also its collision and (second) preimage security. Our next contribution is the restoration of the security results for BLAKE in the ideal model by refining the level of modularity and assuming that BLAKE’s underlying block cipher is an ideal cipher. We prove that BLAKE is optimally collision, second preimage, and preimage secure (up to a constant). We go on to show that BLAKE is still indifferentiable from a random oracle up to the old bound of 2 n/2 queries, albeit under a weaker assumption: the ideality of its block cipher.
Elena Andreeva, Atul Luykx, Bart Mennink

### $\textnormal{\textsc{TWINE}}$ : A Lightweight Block Cipher for Multiple Platforms

Abstract
This paper presents a 64-bit lightweight block cipher $$\textnormal{\textsc{TWINE}}$$ supporting 80 and 128-bit keys. $$\textnormal{\textsc{TWINE}}$$ realizes quite small hardware implementation similar to the previous lightweight block cipher proposals, yet enables efficient software implementations on various CPUs, from micro-controllers to high-end CPUs. This characteristic is obtained by the use of generalized Feistel combined with an improved block shuffle, introduced at FSE 2010.
Tomoyasu Suzaki, Kazuhiko Minematsu, Sumio Morioka, Eita Kobayashi

### Recursive Diffusion Layers for (Lightweight) Block Ciphers and Hash Functions

Abstract
Diffusion layers with maximum branch numbers are widely used in block ciphers and hash functions. In this paper, we construct recursive diffusion layers using Linear Feedback Shift Registers (LFSRs). Unlike the MDS matrix used in AES, whose elements are limited in a finite field, a diffusion layer in this paper is a square matrix composed of linear transformations over a vector space. Perfect diffusion layers with branch numbers from 5 to 9 are constructed. On the one hand, we revisit the design strategy of PHOTON lightweight hash family and the work of FSE 2012, in which perfect diffusion layers are constructed by one bundle-based LFSR. We get better results and they can be used to replace those of PHOTON to gain smaller hardware implementations. On the other hand, we investigate new strategies to construct perfect diffusion layers using more than one bundle-based LFSRs. Finally, we construct perfect diffusion layers by increasing the number of iterations and using bit-level LFSRs. Since most of our proposals have lightweight examples corresponding to 4-bit and 8-bit Sboxes, we expect that they will be useful in designing (lightweight) block ciphers and (lightweight) hash functions.
Shengbao Wu, Mingsheng Wang, Wenling Wu

### Private Stream Search at Almost the Same Communication Cost as a Regular Search

Abstract
Private Stream Search allows keyword-based search queries to be performed on streaming data (or on a database) without revealing any information about the keywords being searched. Using homomorphic encryption, Ostrovsky and Skeith proposed a solution to this problem in 2005. However, their solution requires the server to send an answer of size O(mSlogm) bits when m documents of S bits match the query, while a regular (non-private) query only requires mS bits. Following this work, some improved schemes have been proposed with the aim of keeping the reply from the server linear in mS. In this work we propose two new communication optimal constructions: both allow communication linear in mS, but they also offer an expansion factor (compared to a non-private query) asymptotically equal to 1 when m and S increase. More precisely, our first scheme requires m(S + O(logt)) bits (where t is the size of the database) and our second scheme m(S + C) where C is a constant depending only on the chosen computational security level.
Matthieu Finiasz, Kannan Ramchandran

### An Optimal Key Enumeration Algorithm and Its Application to Side-Channel Attacks

Abstract
Methods for enumerating cryptographic keys based on partial information obtained on key bytes are important tools in cryptanalysis. This paper discusses two contributions related to the practical application and algorithmic improvement of such tools. On the one hand, we observe that the evaluation of leaking devices is generally based on distinguishers with very limited computational cost, such as Kocher’s Differential Power Analysis. By contrast, classical cryptanalysis usually considers large computational costs (e.g. beyond 280 for present ciphers). Trying to bridge this gap, we show that allowing side-channel adversaries some computing power has major consequences for the security of leaking devices. For this purpose, we first propose a Bayesian extension of non-profiled side-channel attacks that allows us to rate key candidates according to their respective probabilities. Then we provide a new deterministic algorithm that allows us to optimally enumerate key candidates from any number of (possibly redundant) lists of any size, given that the subkey information is provided as probabilities, at the cost of limited (practically tractable) memory requirements. Finally, we investigate the impact of key enumeration taking advantage of this Bayesian formulation, and quantify the resulting reduction in the data complexity of various side-channel attacks.
Nicolas Veyrat-Charvillon, Benoît Gérard, Mathieu Renauld, François-Xavier Standaert

### Backmatter

Weitere Informationen