Fast Software Encryption

Frontmatter

Attacks on the HKM / HFX cryptosystem

Abstract

The HKM / HFX cryptosystem is proposed for standardization at the ITU Telecommunication Standardization Sector Study Group 8. It is designed to provide authenticity and confidentiality of FAX messages at a commercial level of security. In addition, the HKM / HFX cryptosystem is designed for unrestricted export.

This paper contains the results of an analysis of the HKM / HFX cryptosystem. Eleven attacks and their complexities are described in full detail. The analytic results show that the security provided by the HKM / HFX cryptosystem is not high enough to meet the requirements for an international standard of the ITU, even with the additional feature of free exportability.

Xuejia Lai, Rainer A. Rueppel

Truncated differentials of SAFER

Abstract

In this paper we do differential cryptanalysis of SAFER. We consider “truncated differentials” and apply them in an attack on 5-round SAFER, which finds the secret key in time much faster than by exhaustive search.

Lars R. Knudsen, Thomas A. Berson

On the weak keys of blowfish

Abstract

Blowfish is a sixteen-rounds Feistel cipher in which the F function is a part of the private key. In this paper, we show that the disclosure of F allows to perform a differential cryptanalysis which can recover all the rest of the key with 2⁴⁸ chosen plaintexts against a number of rounds reduced to eight. Moreover, for some weak F function, this attack only needs 2²³ chosen plaintexts against eight rounds, and 3×2⁵¹ chosen plaintexts against sixteen-rounds. When the F function is safely kept private, one can detect whether it is weak or not with a differential attack using 2²² plaintexts against eight rounds.

Serge Vaudenay

High-bandwidth encryption with low-bandwidth smartcards

Abstract

This paper describes a simple protocol, the Remotely Keyed Encryption Protocol (RKEP), that enables a secure, but bandwidthlimited, cryptographic smartcard to function as a high-bandwidth secretkey encryption and decryption engine for an insecure, but fast, host processor. The host processor assumes most of the computational and bandwidth burden of each cryptographic operation without ever learning the secret key stored on the card. By varying the parameters of the protocol, arbitrary size blocks can be processed by the host with only a single small message exchange with the card and minimal card computation. RKEP works with any conventional block cipher and requires only standard ECB mode block cipher operations on the smartcard, permitting its implementation with off-the-shelf components. There is no storage overhead. Computational overhead is minimal, and includes the calculation of a cryptographic hash function as well as a conventional cipher function on the host processor.

Matt Blaze

ISAAC

Abstract

A sequence of new pseudorandom number generators are developed: IA, IBAA, and ISAAC. No efficient method is known for deducing their internal states. ISAAC requires an amortized 18.75 instructions to produce a 32-bit value. There are no cycles in ISAAC shorter than 2⁴⁰ values. The expected cycle length is 2⁸²⁹⁵ values. Tests show that scaled-down versions of IBAA are unbiased for their entire cycle length. No proofs of security are given.

Robert J. Jenkins Jr.

A note on the hash function of Tillich and zémor

Willi Geiselmann

Cryptanalysis of MD4

Abstract

In 1990 Rivest introduced the hash function MD4. Two years later RIPEMD, a European proposal, was designed as a stronger mode of MD4. Recently we have found an attack against two of three rounds of RIPEMD. As we shall show in the present note, the methods developed to attack RIPEMD can be modified and supplemented such that it is possible to break the full MD4, while previously only partial attacks were known. An implementation of our attack allows to find collisions for MD4 in a few seconds on a PC. An example of a collision is given demonstrating that our attack is of practical relevance.

Hans Dobbertin

RIPEMD-160: A strengthened version of RIPEMD

Abstract

Cryptographic hash functions are an important tool in cryptography for applications such as digital fingerprinting of messages, message authentication, and key derivation. During the last five years, several fast software hash functions have been proposed; most of them are based on the design principles of Ron Rivest's MD4. One such proposal was RIPEMD, which was developed in the framework of the EU project RIPE (Race Integrity Primitives Evaluation). Because of recent progress in the cryptanalysis of these hash functions, we propose a new version of RIPEMD with a 160-bit result, as well as a plug-in substitute for RIPEMD with a 128-bit result. We also compare the software performance of several MD4-based algorithms, which is of independent interest.

Hans Dobbertin, Antoon Bosselaers, Bart Preneel

Fast accumulated hashing

Abstract

A new non-trapdoor accumulator for cumulative hashing is introduced. It can be efficiently realized in practise using existing cryptographic hash algorithms and pseudorandom sequence generators. The memory requirement is less than in comparable signature-based solutions.

Kaisa Nyberg

Tiger: A fast new hash function

Abstract

Among those cryptographic hash function which are not based on block ciphers, MD4 and Snefru seemed initially quite attractive for applications requiring fast software hashing. However collisions for Snefru were found in 1990, and recently a collision of MD4 was also found. This casts doubt on how long these functions' variants, such as RIPE-MD, MD5, SHA, SHA1 and Snefru-8, will remain unbroken. Furthermore, all these functions were designed for 32-bit processors, and cannot be implemented efficiently on the new generation of 64-bit processors such as the DEC Alpha. We therefore present a new hash function which we believe to be secure; it is designed to run quickly on 64-bit processors, without being too slow on existing machines.

Ross Anderson, Eli Biham

The cipher SHARK

Abstract

We present the new block cipher SHARK. This cipher combines highly non-linear substitution boxes and maximum distance separable error correcting codes (MDS-codes) to guarantee a good diffusion. The cipher is resistant against differential and linear cryptanalysis after a small number of rounds. The structure of SHARK is such that a fast software implementation is possible, both for the encryption and the decryption. Our C-implementation of SHARK runs more than four times faster than SAFER and IDEA on a 64-bit architecture.

Vincent Rijmen, Joan Daemen, Bart Preneel, Antoon Bosselaers, Erik De Win

Two practical and provably secure block ciphers: BEAR and LION

Abstract

In this paper we suggest two new provably secure block ciphers, called BEAR and LION. They both have large block sizes, and are based on the Luby-Rackoff construction. Their underlying components are a hash function and a stream cipher, and they are provably secure in the sense that attacks which find their keys would yield attacks on one or both of the underlying components. They also have the potential to be much faster than existing block ciphers in many applications.

Ross Anderson, Eli Biham

Unbalanced Feistel networks and block cipher design

Abstract

We examine a generalization of the concept of Feistel networks, which we call Unbalanced Feistel Networks (UFNs). Like conventional Feistel networks, UFNs consist of a series of rounds in which one part of the block operates on the rest of the block. However, in a UFN the two parts need not be of equal size. Removing this limitation on Feistel networks has interesting implications for designing ciphers secure against linear and differential attacks. We describe UFNs and a terminology for discussing their properties, present and analyze some UFN constructions, and make some initial observations about their security.

Bruce Schneier, John Kelsey

A comparison of fast correlation attacks

Abstract

A comparison of two different approaches to fast correlation attacks on stream ciphers is conducted. One is based on standard or modified iterative probabilistic decoding algorithms, and the other is a recent, so-called free energy minimisation approach. Two different comparisons are presented: one based on the Hamming distance and the other on error-free information sets. The results indicate that a modified iterative probabilistic decoding attack outperforms the free energy minimisation attack in high noise probability regions.

Andrew Clark, Jovan Dj. Golić, Ed Dawson

Correlation attacks on stream ciphers: Computing low-weight parity checks based on error-correcting codes

Abstract

The fast correlation attack described by Meier and Staffelbach

W T Penzhorn

On the security of nonlinear filter generators

Abstract

By regarding a nonlinear filter keystream generator as a finite input memory combiner, it is observed that a recent, important attack introduced by Anderson can be viewed as a conditional correlation attack. Necessary and sufficient conditions for the output sequence to be purely random given than the input sequence is such are pointed out and a new, so-called inversion attack is introduced, which may work for larger input memory sizes in comparison with the Anderson's attack. Large input memory size and use of full positive difference sets and correlation immune nonlinear filter functions are proposed as new design criteria to ensure the security against the considered attacks.

Jovan Dj. Golić

Faster Luby-Rackoff ciphers

Abstract

This paper deals with a generalization of Luby's and Rackoff's results [9] on the construction of block ciphers and their consequences for block cipher implementations. Based on dedicated hash functions, block ciphers are proposed which are more efficient and operate on larger blocks than their original Luby-Rackoff counterparts.

Stefan Lucks

New structure of block ciphers with provable security against differential and linear cryptanalysis

Abstract

We introduce a methodology for designing block ciphers with provable security against differential and linear cryptanalysis. It is based on three new principles: change of the location of round functions, round functions with recursive structure, and substitution boxes of different sizes. The first realizes parallel computation of the round functions without losing provable security, and the second reduces the size of substitution boxes; moreover, the last is expected to make algebraic attacks difficult. We also give specific examples of practical block ciphers that are provably secure under an independent subkey assumption and are reasonably fast in hardware as well as in software implementation.

Mitsuru Matsui

Backmatter