Block cipher

A block cipher is a symmetric cipher that operates on fixed-size blocks of plaintext, giving a block of ciphertext for each. The other main type of cipher is a stream cipher, which generates a stream of keying material to be mixed with messages. Block ciphers can be used in various modes when multiple block are to be encrypted.

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. However, it is now considered obsolete; its 56-bit key size makes it highly vulnerable to a brute force attack, given modern computers. Some applications still use Triple DES, a variant which applies DES three times with two or three different keys.

The generation of block ciphers which followed DES in the 80s and 90s -- such as Blowfish, CAST-128 and IDEA -- nearly all used 64-bit blocks, like DES, but all used 128-bit or longer keys for better resistance to brute force. Some of their design principles came from analysis of DES.

The Advanced Encryption Standard, AES, is the block cipher which replaced DES as a US government standard in 2000. It uses 128-bit blocks and supports key sizes up to 256 bits. NIST, the National Institute of Standards and Technology, ran a contest to find the right cipher for their new standard; there were entries from all over the world and an extensive analysis process. The winner, Rijndael, from two Belgian designers, became AES.

The Block Cipher Lounge [1] web site has more information.

Common techniques

Iterated block ciphers

Nearly all block ciphers use iteration; define some relatively simple transformation and apply it repeatedly to create the cipher. At setup time the primary key undergoes key scheduling giving a number of round keys. The actual cipher then has multiple rounds, each applying the same transformation to the output of the previous round and the round key for the current round. Some ciphers have an additional step before or after the set of rounds, exclusive-ORing additional key material into the plaintext or ciphertext; this is known as whitening.

There are exceptions; when a block cipher is constructed from another cryptographic primitive, there may be no need to iterate because the other primitive provides adequate security. For example, RSA can be used as a block cipher with block size equal to the RSA modulus, and other public key techniques can be used in the same way.

Feistel structure

Many block ciphers use the Feistel structure, devised by Horst Feistel of IBM and used in DES. Such ciphers are known as Feistel ciphers. Each round uses a function F whose input and output are each half a block. Splitting the block into right and left halves and showing XOR as ^ and round key for round n as k_n, even numbered rounds are then:

leftn = leftn-1 ^ F(rightn-1, kn)
rightn = rightn-1

and odd-numbered rounds are

rightn = rightn-1 ^ F(leftn-1, kn)
leftn = leftn-1

Since XOR is its own inverse and the half-block that is used in the F function is unchanged in each round, reversing this is straightforward. The F function itself need not be reversible. In fact, it generally is not; the main criterion in choosing an F-function is that it be highly non-linear since all other parts of the cipher are linear and a cipher without enough non-linearity is weak.

Well-known block ciphers

DES

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. However, it is now considered obsolete; its 56-bit key size makes it highly vulnerable to a brute force attack, given modern computers. Some applications still use Triple DES, a variant which applies DES three times with two or three different keys.

DES operates on 64-bit blocks and takes a 64-bit key. It is a Feistel cipher with 16 rounds and a 48-bit round key for each round, To generate the round keys, the 56-bit key is split into two 28-bit halves and those halves are circularly shifted after each round by one or two bits. Then 48 bits from them are selected and permuted to form the round key.

DES uses eight S-boxes, each 6 bits in and 4 out. The F function works as follows:

expand the 32-bit input to 48 bits, simply by copying some bits twice
XOR with the 48-bit round key
split the result into 8 6-bit chunks
pass each chunk through a different s-box, giving 32 output bits
permute the output bits

The permutation ensures rapid avalanche; a one-bit change in key affects one s-box; a one-bit change in the input block affects one or two s-boxes. With the permutation, changing the output of one s-box affects several in the next round. After a few rounds, the effect spreads to the entire output.

The generation of block ciphers which followed DES in the 80s and 90s -- such as the GOST cipher, Blowfish, CAST-128 and IDEA -- nearly all used 64-bit blocks, like DES, but all used 128-bit or longer keys for better resistance to brute force. Some of their design principles came from analysis of DES.

IDEA

IDEA Is the International Data Encryption Algorithm, a European standard.

AES

In the late 90s, the US National Institute of Standards and Technology ran a contest to find a block cipher to replace DES. The result is the Advanced Encryption Standard. AES.

In October 299, they announced [2] the winner — Rijndael (pronounced approximately "rhine doll"), from two Belgian designers. The NIST page on AES [3] has much detail.