Serpent is a 128-bit block cipher designed by Ross Anderson, Eli Biham and Lars Knudsen as a candidate for the Advanced Encryption Standard. Serpent provides users with the highest practical level of assurance that no shortcut attack will be found. To achieve this, we limited ourselves to well understood mechanisms, so that we could rely on the wide experience of block cipher cryptanalysis. We also used twice as many rounds as are necessary to block all currently known shortcut attacks. We believe that this is prudent practice for a cipher that may have a service life of 50 years and continue to protect legacy data for a further 50 years beyond that.

The authors survey a number of attacks based on unwise choices of the parameters of discrete log based public key cryptosystems, and present some new attacks as well. Many of these involve the choice of a generator g whose order is not prime; others involve malicious choices of message key, and/or an interaction between the message key and the public parameters. The US Digital Signature Standard appears to have taken some (but not all) of these attacks into account: it is described as ElGamal with most of the bugs fixed. There are also attacks on some systems that combine knapsacks with discrete log.

The authors show how to turn any stream cipher into one with reduced key diffusion, but without compromising security. The effect is that a single broadcast ciphertext is decrypted to slightly different plaintexts by users with slightly different keys. Thus users who re-sell their copy of the plaintext in contravention of a licence agreement can be traced. It also supports a canonical 3-resilient traitor tracing scheme.

The authors propose a fast new hash function optimised for 64 bit processors such as the DEC Alpha series, but that still runs reasonably fast on 32 bit machines. It is based on three rounds of a block cipher that operates on 192 bit blocks with a 512 bit

Two block ciphers are presented, based on the Luby-Rackoff construction but with one large and one small half block. The first uses a keyed hash function then a stream cipher and then another keyed hash function, while the second uses a stream cipher

The authors introduce a new compression technique: blocks of text are sorted to maximise their accessible redundancy, and then more conventional techniques are applied. A number of variants are possible, but the basic algorithm gets compression of 2.43 bits per character on the Calgary Compression Corpus (which is as good as the better statistical coders) while using cpu resources comparable to those needed for much less efficient schemes.

The author shows that the Fibonacci shrinking generator can be broken with effort about 2^40 depending on the amount of keystream available. This works because the recurrence relations are sparse and the nonlinear processing leaks the least significant bits and half of the other bits of every other keystream word, allowing a correlation attack that reconstructs the initial state. An improved Fibonacci generator called PIKE is then presented; it is based on the GSM A5 stream cipher.

The author presents a new attack on the nonlinear filter generator. Nonlinear Boolean functions such as those used in filters possess mutual information with shifted copies of themselves; thus for example if k successive bits of a shift register sequence are input to a filter function to calculate the next keystream bit, one expects to find correlations between k-tuples of keystream and (2k-1)-tuples of underlying shift register sequence. In fact one finds even more: the set of (2k-1)-tuples that could have generated an observed output may possess parity checks that may halve the search space.

The authors present a block cipher designed to have very small code size and to be easy to program in many languages. It uses 64 rounds of a simple Feistel structure with a round function that mixes addition with exclusive or and shifting. It gets its nonlinearity from carry propagation, and runs several times faster than DES. There is also a paper on extended versions of TEA.

The author updates his league table of the software performance of various block ciphers, stream ciphers and hash functions to include ciphers such as RC4, RC5, Blowfish, WAKE and SEAL.

The author proposes a stream cipher in which a shift register turns three rotors, each of which is a 256-byte permutation. Ho points out that the classical attacks on both rotor and shift register systems fail against this combination, and sets a challenge in cryptanalysis.

The author tested the speed of MD2, MD4, MD5, SHA, RIPE-MD, DES, GOST-28147 and SAFER on both Sparc and Alpha processors, and for both short and long messages. He also tested five possible triple encryption modes of DES. He suggests ways in which such algorithms can be strengthened with no performance penalty.

The author describes a very fast algorithm, WAKE, which takes only about 20 machine instructions per 20-bit word. It is based on a 256 byte permutation which serves as the key and is used with register operations and 128 bits of internal state to encrypt the data. A number of modes are possible, from an arbitrary length block cipher to a keyed hash function. C source code is included in the paper.

The use of low weight connection polynomials in shift-register based stream ciphers not only makes them more vulnerable to correlation attacks, but can make faster reconstruction attacks possible as well. This is shown using the multiplexer generator as an example.