Fast Software Encryption

Frontmatter

Introduction

B. Preneel

Clock-controlled pseudorandom generators on finite groups

Abstract

As a generalisation of clock-controlled shift registers, we consider a class of key-stream generators where a clocking sequence is used to control a “pseudorandom” walk on a finite group.

Ulrich Baum, Simon Blackburn

On random mappings and random permutations

W. G. Chambers

Binary cyclotomic generators

Abstract

In this paper a number of binary cyclotomic generators based on cyclotomy are described. A number of cryptographic properties of the generators are controlled. A general approach to control the linear complexity and its stability for periodic sequences over any field is shown. Two bridges between number theory and stream ciphers have been established, and the relations between the design and analysis of some stream ciphers and some number-theoretic problems are shown. A number of cryptographic ideas are pointed out.

Cunsheng Ding

Construction of bent functions and balanced Boolean functions with high nonlinearity

Abstract

A general explicit construction of bent functions is described, which unifies well known constructions due to Maiorana-McFarland and Dillon as two opposite extremal cases. Within this framework we also find new ways to generate bent functions. Then it is shown how the constructed bent functions can be modified in order to obtain highly nonlinear balanced Boolean functions. Although their nonlinearity is the best known so far, it remains open whether this bound can still be improved.

Hans Dobbertin

Additive and linear structures of cryptographic functions

Abstract

In the design and analysis of cryptographic algorithms, exploiting the structures of such algorithms is an important aspect. In this paper, additive and linear structures of functions from GF ⁿ (q) to GF ^m (q) will be considered. A function f is said to have an additive structure if there is a non-zero vector a, such that f(x+a)−f(x) remains invariant for all x. Such a vector a is called an additive translator of the function f. A function f is said to have a linear structure if f has an additive translator a and if f(x+ca)−f(x)=c(f(a)−f(0)) for all c in GF(q). We call this a a linear translator of f. We show how to use such additive and linear structures to simplify the expression of the function f. It is shown that function f has r linearly independent linear translators if and only if there is a non-singular linear transformation such that the composition of this linear transformation with the original function gives a function that is the sum of a linear function of r variables and some function of the other n−r variables. In particular, when q is a prime, then any additive translator is a linear translator, which implies that f becomes a sum of an r-variable linear function and an n−r-variable function if and only if f has r linearly independent additive translators. Moreover, for an invertible function f, there is a one-to-one relationship between the linear translators of f and the linear translators of its inverse function.

Xuejia Lai

The RC5 encryption algorithm

Abstract

This document describes the RC5 encryption algorithm, a fast symmetric block cipher suitable for hardware or software implementations. A novel feature of RC5 is the heavy use of data-dependent rotations. RC5 has a variable word size, a variable number of rounds, and a variable-length secret key. The encryption and decryption algorithms are exceptionally simple.

Ronald L. Rivest

The MacGuffin block cipher algorithm

Abstract

This paper introduces MacGuffin, a 64 bit “codebook” block cipher. Many of its characteristics (block size, application domain, performance and implementation structure) are similar to those of the U.S. Data Encryption Standard (DES). It is based on a Feistel network, in which the cleartext is split into two sides with one side repeatedly modified according to a keyed function of the other. Previous block ciphers of this design, such as DES, operate on equal length sides. MacGuffin is unusual in that it is based on a generalized unbalanced Feistel network (GUFN) in which each round of the cipher modifies only 16 bits according to a function of the other 48. We describe the general characteristics of MacGuffin architecture and implementation and give a complete specification for the 32-round, 128-bit key version of the cipher.

Matt Blaze, Bruce Schneier

S-boxes and round functions with controllable linearity and differential uniformity

Abstract

In this contribution we consider the stability of linearity and differential uniformity of vector Boolean functions under certain constructions and modifications. These include compositions with affine surjections onto the input space and with affine surjections from the output space, inversions, adding coordinate functions, forming direct sums and restrictions to affine subspaces. As examples we consider some true round function and S-box constructions. More theoretical examples are offered by the bent and almost perfect nonlinear functions. We also include some facts about functions with partially bent components.

Kaisa Nyberg

Properties of linear approximation tables

Abstract

Linear cryptanalysis is an attack that derives a linear approximation between bits of the plaintext, ciphertext and key. This global approximation is constructed from the linear approximation tables of the nonlinear mappings used by the cipher, usually the S-boxes, as in the case of DES. In this paper we will describe the distribution of these tables for bijective mappings (permutations), concentrating on the expected value of the largest entry, and use our results to construct Feistel ciphers provably resistant to linear cryptanalysis.

Luke O'Connor

Searching for the optimum correlation attack

Abstract

We present some new ideas on attacking stream ciphers based on regularly clocked shift registers. The nonlinear filter functions used in such systems may leak information if they interact with shifted copies of themselves, and this gives us a systematic way to search for correlations between a keystream and the underlying shift register sequence.

Ross Anderson

A known plaintext attack on the PKZIP stream cipher

Abstract

The PKZIP program is one of the more widely used archive/ compression programs on personal computers. It also has many compatible variants on other computers, and is used by most BBS's and ftp sites to compress their archives. PKZIP provides a stream cipher which allows users to scramble files with variable length keys (passwords).

In this paper we describe a known plaintext attack on this cipher, which can find the internal representation of the key within a few hours on a personal computer using a few hundred bytes of known plaintext. In many cases, the actual user keys can also be found from the internal representation. We conclude that the PKZIP cipher is weak, and should not be used to protect valuable data.

Eli Biham, Paul C. Kocher

Linear cryptanalysis of stream ciphers

Abstract

Starting from recent results on a linear statistical weakness of keystream generators and on linear correlation properties of combiners with memory, linear cryptanalysis of stream ciphers based on the linear sequential circuit approximation of finite-state machines is introduced as a general method for assessing the strength of stream ciphers. The statistical weakness can be used to reduce the uncertainty of unknown plaintext and also to reconstruct the unknown structure of a keystream generator, regardless of the initial state. The linear correlations in arbitrary keystream generators can be used for divide and conquer correlation attacks on the initial state based on known plaintext or ciphertext only. Linear cryptanalysis of irregularly clocked shift registers as well as of arbitrary shift register based binary keystream generators proves to be feasible. In particular, the direct stream cipher mode of block ciphers, the basic summation generator, the shrinking generator, the clock-controlled cascade generator, and the modified linear congruential generators are analyzed. It generally appears that simple shift register based keystream generators are potentially vulnerable to linear cryptanalysis. A proposal of a novel, simple and secure keystream generator is also presented.

Jovan Dj. Golić

Feedback with carry shift registers over finite fields

Extended abstract

Andrew Klapper

A free energy minimization framework for inference problems in modulo 2 arithmetic

Abstract

This paper studies the task of inferring a binary vector s given noisy observations of the binary vector t=As modulo 2, where A is an M×N binary matrix. This task arises in correlation attack on a class of stream ciphers and in the decoding of error correcting codes.

The unknown binary vector is replaced by a real vector of probabilities that are optimized by variational free energy minimization. The derived algorithms converge in computational time of order between w _A and Nw _A , where w _A is the number of 1s in the matrix A, but convergence to the correct solution is not guaranteed.

Applied to error correcting codes based on sparse matrices A, these algorithms give a system with empirical performance comparable to that of BCH and Reed-Muller codes.

Applied to the inference of the state of a linear feedback shift register given the noisy output sequence, the algorithms offer a principled version of Meier and Staffelbach's (1989) algorithm B, thereby resolving the open problem posed at the end of their paper. The algorithms presented here appear to give superior performance.

David J. C. MacKay

Truncated and higher order differentials

Abstract

In [6] higher order derivatives of discrete functions were considered and the concept of higher order differentials was introduced. We introduce the concept of truncated differentials and present attacks on ciphers presumably secure against differential attacks, but vulnerable to attacks using higher order and truncated differentials. Also we give a differential attack using truncated differentials on DES reduced to 6 rounds using only 46 chosen plaintexts with an expected running time of about the time of 3,500 encryptions. Finally it is shown how to find a minimum nonlinear order of a block cipher using higher order differentials.

Lars R. Knudsen

SAFER K-64: One year later

James L. Massey

Improved characteristics for differential cryptanalysis of hash functions based on block ciphers

Abstract

In this paper we present an improvement of the differential attack on hash functions based on block ciphers. By using the specific properties of the collision attack on hash functions, we can greatly reduce the work factor to find a pair that follows the characteristic. We propose a new family of differential characteristics that is especially useful in combination with our improvement. Attacks on a hash function based on DES variants reduced to 12, 13 or 15 rounds become faster than brute force collision attacks.

Vincent Rijmen, Bart Preneel

Linear cryptanalysis using multiple approximations and FEAL

Abstract

We describe the results of experiments on the use of multiple approximations in a linear cryptanalytic attack on FEAL; we pay particular attention to FEAL-8. While these attacks on FEAL are interesting in their own right, many important and intriguing issues in the use of multiple approximations are brought to light.

Burton S. Kaliski Jr., M. J. B. Robshaw

Problems with the linear cryptanalysis of DES using more than one active S-box per round

Abstract

Matsui introduced the concept of linear cryptanalysis. Originally only one active S-box per round was used. Later he and Biham proposed linear cryptanalysis with more than one active S-box per round. They combine equations with the Piling-up Lemma which requires independent random input variables. This requirement is not met for neighbouring S-boxes, because they share input bits. In this paper we study the error resulting from this application of the Piling-up Lemma. We give statistical evidence that the errors are severe. On the other hand we show that the Piling-up Lemma gives the correct probabilities for Matsui's Type II approximation.

Uwe Blöcher, Markus Dichtl

Correlation matrices

Abstract

In this paper we introduce the correlation matrix of a Boolean mapping, a useful concept in demonstrating and proving properties of Boolean functions and mappings. It is argued that correlation matrices are the “natural” representation for the proper understanding and description of the mechanisms of linear cryptanalysis [4]. It is also shown that the difference propagation probabilities and the table consisting of the squared elements of the correlation matrix are linked by a scaled Walsh-Hadamard transform.

Joan Daemen, René Govaerts, Joos Vandewalle

On the need for multipermutations: Cryptanalysis of MD4 and SAFER

Abstract

Cryptographic primitives are usually based on a network with boxes. At EUROCRYPT'94, Schnorr and the author of this paper claimed that all boxes should be multipermutations. Here, we investigate a few combinatorial properties of multipermutations. We argue that boxes which fail to be multipermutations can open the way to unsuspected attacks. We illustrate this statement with two examples.

Firstly, we show how to construct collisions to MD4 restricted to its first two rounds. This allows one to forge digests close to each other using the full compression function of MD4. Secondly, we show that variants of SAFER are subject to attack faster than exhaustive search in 6.1% cases. This attack can be implemented if we decrease the number of rounds from 6 to 4.

Serge Vaudenay

How to exploit the intractability of exact TSP for cryptography

Abstract

We outline constructions for both pseudo-random generators and one-way hash functions. These constructions are based on the exact TSP (XTSP), a special variant of the well known traveling salesperson problem. We prove that these constructions are secure if the XTSP is infeasible. Our constructions are easy to implement, appear to be fast, but require a large amount of memory.

Stefan Lucks

How to reverse engineer an EES device

Michael Roe

A fast homophonic coding algorithm based on arithmetic coding

Abstract

We present a practical algorithm for the homophonic coding of a message source, as required for cryptographic purposes. The purpose of homophonic coding is to transform the output of a non-uniformly distributed message source into a sequence of uniformly distributed symbols. This is achieved by randomly mapping each source symbol into one of a set of homophones. The selected homophones are then encoded by means of arithmetic coding, after which they can be encrypted with a suitable cryptographic algorithm. The advantage of homophonic coding above source coding is that source coding merely protects against a ciphertext-only attack, whereas homophonic coding provides additional protection against known-plaintext and chosen-plaintext attacks. This paper introduces a fast algorithm for homophonic coding based on arithmetic coding, termed the shift-and-add algorithm, which makes use of the fact that the set of homophones are chosen according to a dyadic probability distribution. This leads to a particularly simple, efficient implementation, requiring no multiplications but only shifts and additions. The usefulness of the algorithm is demonstrated by the homophonic coding of an ASCII textfile. The simulation results show that homophonic coding increases the entropy by less than 2 bits per symbol, and also provides source encoding (data compression).

W. T. Penzhorn

On Fibonacci keystream generators

Abstract

A number of keystream generators have been proposed which are based on Fibonacci sequences, and at least one has been fielded. They are attractive in that they can use some of the security results from the theory of shift register based keystream generators, while running much more quickly in software. However, new designs bring new risks, and we show how a system proposed at last year's workshop, the Fibonacci Shrinking Genertor (FISH), can be broken by an opponent who knows a few thousand words of keystream. We then discuss how such attacks can be avoided, and present a new algorithm, PIKE, which is based on the A5 algorithm used in GSM telephones.

Ross Anderson

Cryptanalysis of McGuffin

Abstract

This paper shows that the actual proposal for an unbalanced Feistel network by Schneier and Blaze is as vulnerable to differential cryptanalysis as the DES.

Vincent Rijmen, Bart Preneel

Performance of block ciphers and hash functions — One year later

Michael Roe

TEA, a tiny encryption algorithm

Abstract

We give a short routine which is based on a Feistel iteration and uses a large number of rounds to get security with simplicity.

David J. Wheeler, Roger M. Needham

Backmatter