Hash Function Cryptanalysis and Design (I)

Producing Collisions for Panama, Instantaneously

Abstract

We present a practical attack on the Panama hash function that generates a collision in 2⁶ evaluations of the state updating function. Our attack improves that of Rijmen and coworkers that had a complexity 2⁸², too high to produce a collision in practice. This improvement comes mainly from the use of techniques to transfer conditions on the state to message words instead of trying many message pairs and using the ones for which the conditions are satisfied. Our attack works for any arbitrary prefix message, followed by a pair of suffix messages with a given difference. We give an example of a collision and make the collision-generating program available. Our attack does not affect the Panama stream cipher, that is still unbroken to the best of our knowledge.

Joan Daemen, Gilles Van Assche

Cryptanalysis of FORK-256

Abstract

In this paper we present a cryptanalysis of a new 256-bit hash function, FORK-256, proposed by Hong et al. at FSE 2006. This cryptanalysis is based on some unexpected differentials existing for the step transformation. We show their possible uses in different attack scenarios by giving a 1-bit (resp. 2-bit) near collision attack against the full compression function of FORK-256 running with complexity of 2¹²⁵ (resp. 2¹²⁰) and with negligible memory, and by exhibiting a 22-bit near pseudo-collision. We also show that we can find collisions for the full compression function with a small amount of memory with complexity not exceeding 2^126.6 hash evaluations. We further show how to reduce this complexity to 2^109.6 hash computations by using 2⁷³ memory words. Finally, we show that this attack can be extended with no additional cost to find collisions for the full hash function, i.e. with the predefined IV.

Krystian Matusiewicz, Thomas Peyrin, Olivier Billet, Scott Contini, Josef Pieprzyk

The Grindahl Hash Functions

Abstract

In this paper we propose the Grindahl hash functions, which are based on components of the Rijndael algorithm. To make collision search sufficiently difficult, this design has the important feature that no low-weight characteristics form collisions, and at the same time it limits access to the state. We propose two concrete hash functions, Grindahl-256 and Grindahl-512 with claimed security levels with respect to collision, preimage and second preimage attacks of 2¹²⁸ and 2²⁵⁶, respectively. Both proposals have lower memory requirements than other hash functions at comparable speeds and security levels.

Lars R. Knudsen, Christian Rechberger, Søren S. Thomsen

Stream Ciphers Cryptanalysis (I)

Overtaking VEST

Abstract

VEST is a set of four stream cipher families submitted by S. O’Neil, B. Gittins and H. Landman to the eSTREAM call for stream cipher proposals of the European project ECRYPT. The state of any family member is made of three components: a counter, a counter diffusor and a core accumulator. We show that collisions can be found in the counter during the IV Setup. Moreover they can be combined with a collision in the linear counter diffusor to form collisions on the whole cipher. As a consequence, it is possible to retrieve 53 bits of the keyed state of the stream cipher by performing a chosen IV attack. For the default member of a VEST family, we present a “long” IV attack which requires 2^22.24 IV setups, and a “short” IV attack which requires 2^28.73 IV setups on average. The 53 bits retrieved can be used to reduce the complexity of the exhaustive key search. The chosen IV attack can be turned into a chosen message attack on a MAC based on VEST.

Antoine Joux, Jean-René Reinhard

Cryptanalysis of Achterbahn-128/80

Abstract

This paper presents two key-recovery attacks against Achterbahn-128/80, the last version of one of the stream cipher proposals in the eSTREAM project. The attack against the 80-bit variant, Achterbahn-80, has complexity 2⁶¹. The attack against Achterbahn-128 requires 2^80.58 operations and 2⁶⁰ keystream bits. These attacks are based on an improvement of the attack due to Hell and Johansson against Achterbahn version 2. They mainly rely on an algorithm that makes profit of the independence of the constituent registers.

María Naya-Plasencia

Differential-Linear Attacks Against the Stream Cipher Phelix

Abstract

The previous key recovery attacks against Helix obtain the key with about 2⁸⁸ operations using chosen nonces (reusing nonce) and about 1000 adaptively chosen plaintext words (or 2^35.6 chosen plaintext words). The stream cipher Phelix is the strengthened version of Helix. In this paper we apply the differential-linear cryptanalysis to recover the key of Phelix. With 2³⁴ chosen nonces and 2³⁷ chosen plaintext words, the key of Phelix can be recovered with about 2^41.5 operations.

Hongjun Wu, Bart Preneel

Theory

How to Enrich the Message Space of a Cipher

Abstract

Given (deterministic) ciphers \({\mathcal E}\) and E that can encipher messages of l and n bits, respectively, we construct a cipher \({\mathcal E}^*={XLS}[{\mathcal E},E]\) that can encipher messages of l + s bits for any s < n. Enciphering such a string will take one call to \({\mathcal E}\) and two calls to E. We prove that \({\mathcal E}^*\) is a strong pseudorandom permutation as long as \({\mathcal E}\) and E are. Our construction works even in the tweakable and VIL (variable-input-length) settings. It makes use of a multipermutation (a pair of orthogonal Latin squares), a combinatorial object not previously used to get a provable-security result.

Thomas Ristenpart, Phillip Rogaway

Security Analysis of Constructions Combining FIL Random Oracles

Abstract

We consider the security of compression functions built by combining smaller perfectly secure compression functions modeled as fixed input length random oracles. We give tight security bounds and generic attacks for various parameters of these constructions and apply our results to recent proposals of block cipher-based hash functions.

Yannick Seurin, Thomas Peyrin

Bad and Good Ways of Post-processing Biased Physical Random Numbers

Abstract

Algorithmic post-processing is used to overcome statistical deficiencies of physical random number generators. We show that the quasigroup based approach for post-processing random numbers described in [MGK05] is ineffective and very easy to attack. We also suggest new algorithms which extract considerably more entropy from their input than the known algorithms with an upper bound for the number of input bits needed before the next output is produced.

Markus Dichtl

Fast Talks: Block Cipher Cryptanalysis

Improved Slide Attacks

Abstract

The slide attack is applicable to ciphers that can be represented as an iterative application of the same keyed permutation. The slide attack leverages simple attacks on the keyed permutation to more complicated (and time consuming) attacks on the entire cipher.

In this paper we extend the slide attack by examining the cycle structures of the entire cipher and of the underlying keyed permutation. Our method allows to find slid pairs much faster than was previously known, and hence reduces the time complexity of the entire slide attack significantly. In addition, since our attack finds as many slid pairs as the attacker requires, it allows to leverage all types of attacks on the underlying permutation (and not only simple attacks) to an attack on the entire cipher.

We demonstrate the strength of our technique by presenting an attack on 24-round reduced GOST whose S-boxes are unknown. Our attack retrieves the unknown S-boxes as well as the secret key with a time complexity of about 2⁶³ encryptions. Thus, this attack allows an easier attack on other instances of GOST that use the same S-boxes. When the S-boxes are known to the attacker, our attack can retrieve the secret key of 30-round GOST (out of the 32 rounds).

Eli Biham, Orr Dunkelman, Nathan Keller

A New Class of Weak Keys for Blowfish

Abstract

The reflection attack is a recently discovered self similarity analysis which is usually mounted on ciphers with many fixed points. In this paper, we describe two reflection attacks on r-round Blowfish which is a fast, software oriented encryption algorithm with a variable key length k. The attacks work successfully on approximately 2^{k + 32 − 16r} number of keys which we call reflectively weak keys. We give an almost precise characterization of these keys. One interesting result is that 2³⁴ known plaintexts are enough to determine if the unknown key is a reflectively weak key, for any key length and any number of rounds. Once a reflectively weak key is identified, a large amount of subkey information is revealed with no cost. Then, we recover the key in roughly r·2^16r + 22 steps. Furthermore, it is possible to improve the attack for some key lengths by using memory to store all reflectively weak keys in a table in advance. The pre-computation phase costs roughly r·2^k − 11 steps. Then the unknown key can be recovered in 2^{(k + 32 − 16r)/64} steps. As an independent result, we improve Vaudenay’s analysis on Blowfish for reflectively weak keys. Moreover, we propose a new success criterion for an attack working on some subset of the key space when the key generator is random.

Orhun Kara, Cevat Manap

Fast Talks: Block Cipher Design

The 128-Bit Blockcipher CLEFIA (Extended Abstract)

Abstract

We propose a new 128-bit blockcipher CLEFIA supporting key lengths of 128, 192 and 256 bits, which is compatible with AES. CLEFIA achieves enough immunity against known attacks and flexibility for efficient implementation in both hardware and software by adopting several novel and state-of-the-art design techniques. CLEFIA achieves a good performance profile both in hardware and software. In hardware using a 0.09 μm CMOS ASIC library, about 1.60 Gbps with less than 6 Kgates, and in software, about 13 cycles/byte, 1.48 Gbps on 2.4 GHz AMD Athlon 64 is achieved. CLEFIA is a highly efficient blockcipher, especially in hardware.

Taizo Shirai, Kyoji Shibutani, Toru Akishita, Shiho Moriai, Tetsu Iwata

New Lightweight DES Variants

Abstract

In this paper we propose a new block cipher, DESL (DES Lightweight), which is based on the classical DES (Data Encryption Standard) design, but unlike DES it uses a single S-box repeated eight times. On this account we adapt well-known DES S-box design criteria, such that they can be applied to the special case of a single S-box. Furthermore, we show that DESL is resistant against certain types of the most common attacks, i.e., linear and differential cryptanalyses, and the Davies-Murphy attack. Our hardware implementation results of DESL are very promising (1848 GE), therefore DESL is well suited for ultra-constrained devices such as RFID tags.

Gregor Leander, Christof Paar, Axel Poschmann, Kai Schramm

Block Cipher Cryptanalysis

A New Attack on 6-Round IDEA

Abstract

IDEA is a 64-bit block cipher with 128-bit keys introduced by Lai and Massey in 1991. IDEA is one of the most widely used block ciphers, due to its inclusion in several cryptographic packages, such as PGP. Since its introduction in 1991, IDEA has withstood extensive cryptanalytic effort, but no attack was found on the full (8.5-round) variant of the cipher.

In this paper we present the first known attack on 6-round IDEA faster than exhaustive key search. The attack exploits the weak key-schedule algorithm of IDEA, and combines Square-like techniques with linear cryptanalysis to increase the number of rounds that can be attacked. The attack is the best known attack on IDEA. We also improve previous attacks on 5-round IDEA and introduce a 5-round attack which uses only 16 known plaintexts.

Eli Biham, Orr Dunkelman, Nathan Keller

Related-Key Rectangle Attacks on Reduced AES-192 and AES-256

Abstract

This paper examines the security of AES-192 and AES-256 against a related-key rectangle attack. We find the following new attacks: 8-round reduced AES-192 with 2 related keys, 10-round reduced AES-192 with 64 or 256 related keys and 9-round reduced AES-256 with 4 related keys. Our attacks reduce the complexity of earlier attacks presented at FSE 2005 and Eurocrypt 2005: for reduced AES-192 with 8 rounds, we decrease the required number of related keys from 4 to 2 at the cost of a higher data and time complexity; we present the first shortcut attack on AES-192 reduced to 10 rounds; for reduced AES-256 with 9 rounds, we decrease the required number of related keys from 256 to 4 and both the data and time complexity at the cost of a smaller number of attacked rounds. Furthermore, we point out some flaw in the 9-round AES-192 attack presented at Eurocrypt 2005, show how to fix it and enhance the attack in terms of the number of related keys.

Jongsung Kim, Seokhie Hong, Bart Preneel

An Analysis of XSL Applied to BES

Abstract

Currently, the only plausible attack on the Advanced Encryption System (AES) is the XSL attack over F ₂₅₆ through the Big Encryption System (BES) embedding. In this paper, we give an analysis of the XSL attack when applied to BES and conclude that the complexity estimate is too optimistic. For example, the complexity of XSL on BES-128 should be at least 2⁴⁰¹ instead of the value of 2⁸⁷ from current literature. Our analysis applies to the eprint version of the XSL attack, which is different from the compact XSL attack studied by Cid and Leurent at Asiacrypt 2005. Moreover, we study the attack on the BES embedding of AES, while Cid and Leurent studies the attack on AES itself. Thus our analysis can be considered as a parallel work, which together with Cid and Leurent’s study, disproves the effectiveness of both versions of the XSL attack against AES.

Chu-Wee Lim, Khoongming Khoo

Stream Cipher Cryptanalysis (II)

On the Security of IV Dependent Stream Ciphers

Abstract

Almost all the existing stream ciphers are using two inputs: a secret key and an initial value (IV). However recent attacks indicate that designing a secure IV-dependent stream cipher and especially the key and IV setup component of such a cipher remains a difficult task. In this paper we first formally establish the security of a well known generic construction for deriving an IV-dependent stream cipher, namely the composition of a key and IV setup pseudo-random function (PRF) with a keystream generation pseudo-random number generator (PRNG). We then present a tree-based construction allowing to derive a IV-dependent stream cipher from a PRNG for a moderate cost that can be viewed as a subcase of the former generic construction. Finally we show that the recently proposed stream cipher quad [3] uses this tree-based construction and that consequently the security proof for quad’s keystream generation part given in [3] can be extended to incorporate the key and IV setup.

Côme Berbain, Henri Gilbert

Two General Attacks on Pomaranch-Like Keystream Generators

Abstract

Two general attacks that can be applied to all versions and variants of the Pomaranch stream cipher are presented. The attacks are demonstrated on all versions and succeed with complexity less than exhaustive keysearch. The first attack is a distinguisher which needs keystream from only one or a few IVs to succeed. The attack is not only successful on Pomaranch Version 3 but has also less computational complexity than all previously known distinguishers for the first two versions of the cipher. The second attack is an attack which requires keystream from an amount of IVs exponential in the state size. It can be used as a distinguisher but it can also be used to predict future keystream bits corresponding to an IV if the first few bits are known. The attack will succeed on all versions of Pomaranch with complexities much lower than previously known attacks.

Håkan Englund, Martin Hell, Thomas Johansson

Analysis of QUAD

Abstract

In a Eurocrypt 2006 article entitled “QUAD: A Practical Stream Cipher with Provable Security,” Berbain, Gilbert, and Patarin introduced QUAD, a parametrized family of stream ciphers. The article stated that “the security of the novel stream cipher is provably reducible to the intractability of the MQ problem”; this reduction deduces the infeasibility of attacks on QUAD from the hypothesized infeasibility (with an extra looseness factor) of attacks on the well-known hard problem of solving systems of multivariate quadratic equations over finite fields. The QUAD talk at Eurocrypt 2006 reported speeds for QUAD instances with 160-bit state and output block over the fields GF(2), GF(16), and GF(256).

This paper discusses both theoretical and practical aspects of attacking QUAD and of attacking the underlying hard problem. For example, this paper shows how to use XL-Wiedemann to break the GF(256) instance QUAD(256,20,20) in approximately 2⁶⁶ Opteron cycles, and to break the underlying hard problem in approximately 2⁴⁵ cycles. For each of the QUAD parameters presented at Eurocrypt 2006, this analysis shows the implications and limitations of the security proofs, pointing out which QUAD instances are not secure, and which ones will never be proven secure. Empirical data backs up the theoretical conclusions; in particular, the 2⁴⁵-cycle attack was carried out successfully.

Bo-Yin Yang, Owen Chia-Hsin Chen, Daniel J. Bernstein, Jiun-Ming Chen

Cryptanalysis of Hash Functions (II)

Message Freedom in MD4 and MD5 Collisions: Application to APOP

Abstract

In Wang’s attack, message modifications allow to deterministically satisfy certain sufficient conditions to find collisions efficiently. Unfortunately, message modifications significantly change the messages and one has little control over the colliding blocks. In this paper, we show how to choose small parts of the colliding messages. Consequently, we break a security countermeasure proposed by Szydlo and Yin at CT-RSA ’06, where a fixed padding is added at the end of each block.

Furthermore, we also apply this technique to recover part of the passwords in the Authentication Protocol of the Post Office Protocol (POP). This shows that collision attacks can be used to attack real protocols, which means that finding collisions is a real threat.

Gaëtan Leurent

New Message Difference for MD4

Abstract

This paper proposes several approaches to improve the collision attack on MD4 proposed by Wang et al. First, we propose a new local collision that is the best for the MD4 collision attack. Selection of a good message difference is the most important step in achieving effective collision attacks. This is the first paper to introduce an improvement to the message difference approach of Wang et al., where we propose a new local collision. Second, we propose a new algorithm for constructing differential paths. While similar algorithms have been proposed, they do not support the new local collision technique.Finally, we complete a collision attack, and show that the complexity is smaller than the previous best work.

Yu Sasaki, Lei Wang, Kazuo Ohta, Noboru Kunihiro

Algebraic Cryptanalysis of 58-Round SHA-1

Abstract

In 2004, a new attack against SHA-1 has been proposed by a team leaded by Wang [15]. The aim of this article is to sophisticate and improve Wang’s attack by using algebraic techniques. We introduce new notions, namely semi-neutral bit and adjuster and propose then an improved message modification technique based on algebraic techniques. In the case of the 58-round SHA-1, the experimental complexity of our improved attack is 2³¹ SHA-1 computations, whereas Wang’s method needs 2³⁴ SHA-1 computations. We have found many new collisions for the 58-round SHA-1. We also study the complexity of our attack for the full SHA-1.

Makoto Sugita, Mitsuru Kawazoe, Ludovic Perret, Hideki Imai

Theory of Stream Ciphers

Algebraic Immunity of S-Boxes and Augmented Functions

Abstract

In this paper, the algebraic immunity of S-boxes and augmented functions of stream ciphers is investigated. Augmented functions are shown to have some algebraic properties that are not covered by previous measures of immunity. As a result, efficient algebraic attacks with very low data complexity on certain filter generators become possible. In a similar line, the algebraic immunity of the augmented function of the eSTREAM candidate Trivium is experimentally tested. These tests suggest that Trivium has some immunity against algebraic attacks on augmented functions.

Simon Fischer, Willi Meier

Generalized Correlation Analysis of Vectorial Boolean Functions

Abstract

We investigate the security of n-bit to m-bit vectorial Boolean functions in stream ciphers. Such stream ciphers have higher throughput than those using single-bit output Boolean functions. However, as shown by Zhang and Chan at Crypto 2000, linear approximations based on composing the vector output with any Boolean functions have higher bias than those based on the usual correlation attack. In this paper, we introduce a new approach for analyzing vector Boolean functions called generalized correlation analysis. It is based on approximate equations which are linear in the input x but of free degree in the output z = F(x). Based on experimental results, we observe that the new generalized correlation attack gives linear approximation with much higher bias than the Zhang-Chan and usual correlation attacks. Thus it can be more effective than previous methods.

First, the complexity for computing the generalized nonlinearity for this new attack is reduced from \(2^{2^m \times n+n}\) to 2²ⁿ. Second, we prove a theoretical upper bound for generalized nonlinearity which is much lower than the unrestricted nonlinearity (for Zhang-Chan’s attack) or usual nonlinearity. This again proves that generalized correlation attack performs better than previous correlation attacks. Third, we introduce a generalized divide-and-conquer correlation attack and prove that the usual notion of resiliency is enough to protect against it. Finally, we deduce the generalized nonlinearity of some known secondary constructions for secure vector Boolean functions.

Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe

Side Channel Attacks

An Analytical Model for Time-Driven Cache Attacks

Abstract

Cache attacks exploit side-channel information that is leaked by a microprocessor’s cache. There has been a significant amount of research effort on the subject to analyze and identify cache side-channel vulnerabilities since early 2002. Experimental results support the fact that the effectiveness of a cache attack depends on the particular implementation of the cryptosystem under attack and on the cache architecture of the device this implementation is running on. Yet, the precise effect of the mutual impact between the software implementation and the cache architecture is still an unknown. In this manuscript, we explain the effect and present an analytical model for time-driven cache attacks that accurately forecasts the strength of a symmetric key cryptosystem based on 3 simple parameters: (1) the number of lookup tables; (2) the size of the lookup tables; (3) and the length of the microprocessor’s cache line. The accuracy of the model has been experimentally verified on 3 different platforms with different implementations of the AES algorithm attacked by adversaries with different capabilities.

Kris Tiri, Onur Acıiçmez, Michael Neve, Flemming Andersen

MACs and Small Block Ciphers

Improving the Security of MACs Via Randomized Message Preprocessing

Abstract

“Hash then encrypt” is an approach to message authentication, where first the message is hashed down using an ε-universal hash function, and then the resulting k-bit value is encrypted, say with a block-cipher. The security of this scheme is proportional to εq ², where q is the number of MACs the adversary can request. As ε is at least 2^− k, the best one can hope for is O(q ²/2^k) security. Unfortunately, such small ε is not achieved by simple hash functions used in practice, such as the polynomial evaluation or the Merkle-Damgård construction, where ε grows with the message length L.

The main insight of this work comes from the fact that, by using randomized message preprocessing via a short random salt p (which must then be sent as part of the authentication tag), we can use the “hash then encrypt” paradigm with suboptimal “practical” ε-universal hash functions, and still improve its exact security to optimal O(q ²/2^k). Specifically, by using at most an O(logL)-bit salt p, one can always regain the optimal exact security O(q ²/2^k), even in situations where ε grows polynomially with L. We also give very simple preprocessing maps for popular “suboptimal” hash functions, namely polynomial evaluation and the Merkle-Damgård construction.

Our results come from a general extension of the classical Carter-Wegman paradigm, which we believe is of independent interest. On a high level, it shows that public randomization allows one to use the potentially much smaller “average-case” collision probability in place of the “worst-case” collision probability ε.

Yevgeniy Dodis, Krzysztof Pietrzak

New Bounds for PMAC, TMAC, and XCBC

Abstract

We provide new security proofs for PMAC, TMAC, and XCBC message authentication modes. The previous security bounds for these modes were σ ²/2ⁿ, where n is the block size in bits and σ is the total number of queried message blocks. Our new bounds are ℓq ²/2ⁿ for PMAC and ℓq ²/2ⁿ + ℓ⁴ q ²/2²ⁿ for TMAC and XCBC, where q is the number of queries and ℓ is the maximum message length in n-bit blocks. This improves the previous results under most practical cases, e.g., when no message is exceptionally long compared to other messages.

Kazuhiko Minematsu, Toshiyasu Matsushima

Perfect Block Ciphers with Small Blocks

Abstract

Existing symmetric encryption algorithms target messages consisting of elementary binary blocks of at least 64 bits. Some applications need a block cipher which operates over smaller and possibly non-binary blocks, which can be viewed as a pseudo-random permutation of n elements. We present an algorithm for selecting such a random permutation of n elements and evaluating efficiently the permutation and its inverse over arbitrary inputs. We use an underlying deterministic RNG (random number generator). Each evaluation of the permutation uses O(logn) space and O((logn)³) RNG invocations. The selection process is “perfect”: the permutation is uniformly selected among the n! possibilities.

Louis Granboulan, Thomas Pornin

Springer Professional

Table of Contents

Frontmatter

Hash Function Cryptanalysis and Design (I)

Producing Collisions for Panama, Instantaneously

Cryptanalysis of FORK-256

The Grindahl Hash Functions

Stream Ciphers Cryptanalysis (I)

Overtaking VEST

Cryptanalysis of Achterbahn-128/80

Differential-Linear Attacks Against the Stream Cipher Phelix

Theory

How to Enrich the Message Space of a Cipher

Security Analysis of Constructions Combining FIL Random Oracles

Bad and Good Ways of Post-processing Biased Physical Random Numbers

Fast Talks: Block Cipher Cryptanalysis

Improved Slide Attacks

A New Class of Weak Keys for Blowfish

Fast Talks: Block Cipher Design

The 128-Bit Blockcipher CLEFIA (Extended Abstract)

New Lightweight DES Variants

Block Cipher Cryptanalysis

A New Attack on 6-Round IDEA

Related-Key Rectangle Attacks on Reduced AES-192 and AES-256

An Analysis of XSL Applied to BES

Stream Cipher Cryptanalysis (II)

On the Security of IV Dependent Stream Ciphers

Two General Attacks on Pomaranch-Like Keystream Generators

Analysis of QUAD

Cryptanalysis of Hash Functions (II)

Message Freedom in MD4 and MD5 Collisions: Application to APOP

New Message Difference for MD4

Algebraic Cryptanalysis of 58-Round SHA-1

Theory of Stream Ciphers

Algebraic Immunity of S-Boxes and Augmented Functions

Generalized Correlation Analysis of Vectorial Boolean Functions

Side Channel Attacks

An Analytical Model for Time-Driven Cache Attacks

MACs and Small Block Ciphers

Improving the Security of MACs Via Randomized Message Preprocessing

New Bounds for PMAC, TMAC, and XCBC

Perfect Block Ciphers with Small Blocks

Backmatter

Premium Partner