Block cipher

DES and alternatives

The Data Encryption Standard, DES, is among the the best known and most thoroughly analysed block ciphers. It was invented by IBM, and was made a US government standard for non-classified government data and for regulated industries such as banking, in the late 70s. From then until about the turn of the century, it was very widely used. It is now considered obsolete because its 56-bit key is too short to resist brute force attacks if the opponents have recent technology.

The DES standard marked the beginning of an era in work related to block ciphers. For an entire generation, every student of cryptanalysis tried to find a way to break DES and every student of cryptography tried to devise a cipher that was demonstrably better than DES. Very few succeeded.

Every new cryptanalytic technique invented since DES became a standard has been tested against DES. None of them have broken it completely, but two — differential cryptanalysis and linear cryptanalysis — give attacks theoretically significantly better than brute force. This does not appear to have much practical importance since both require enormous numbers of known or chosen plaintexts and DES can be broken by brute force with one known plaintext. All the older publicly known cryptanalytic techniques have also been tried, or at least considered, for use against DES; none of them work.

DES served as a sort of baseline for cipher design through the 80s and 90s; the design goal for almost any 20th century block cipher was to replace DES in some of its many applications with something faster, more secure, or both. All these ciphers used 64-bit blocks, like DES, but all used 128-bit or longer keys for better resistance to brute force. Many of the techniques used came from DES and many of the design principles came from analysis of DES.

Ciphers of this generation include:

• The Data Encryption Standard itself, the first well-known Feistel cipher, using 16 rounds and eight 6 by 4 S-boxes.
• The GOST cipher, a Soviet standard similar in design to DES, a 32-round Feistel cipher using eight 4 by 4 S-boxes.
• IDEA, the International Data Encryption Algorithm, a European standard, not a Feistel cipher, with only 8 rounds and no S-boxes.
• RC2, a Feistel cipher from RSA Security which was approved for easy export from the US (provided it was used with only a 40-bit key), so widely deployed.
• RC5, a Feistel cipher from RSA security. This was fairly widely deployed, often replacing RC2 in applications.
• CAST-128, a widely used 16-round Feistel cipher, with 8 by 32 S-boxes.
• Blowfish, another widely used 16-round Feistel cipher with 8 by 32 S-boxes.
• The Tiny Encryption Algorithm, or TEA, designed to be very small and fast but still secure, a 32-round Feistel cipher without S-boxes.
• Skipjack, an algorithm designed by the NSA for use in the Clipper chip, a 32-round unbalanced Feistel cipher.

Several of these ciphers introduced interesting new design ideas. The CAST ciphers were the first to use large S-boxes which allow the F function of a Feistel cipher to have ideal avalanche properties, and to use bent functions in the S-box columns. Blowfish introduced key-dependent S-boxes. RC5 was the first well-known cipher to use data-dependent rotations to achieve nonlinearity. IDEA uses a clever variant on multiplication to achieve nonlinearity.

The era effectively ended when the US government began working on a new cipher standard to replace their Data Encryption Standard, the Advanced Encryption Standard or AES. A whole new generation of ciphers arose, the first 21st century block ciphers. Of course these designs still drew on the experience gained in the post-DES generation, but overall these ciphers are quite different. In particular, they all use 128-bit blocks and most support key sizes up to 256 bits.