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.

Avalanche

The designer wants changes to propagate through the cipher so that, for example, a single-bit change at round n affects all bits of the ciphertext by round n+x for some reasonably small x. Certainly x must be much less than the total number of rounds. If the round function design gives a large x then the cipher will need more rounds to be secure.

This was named the avalanche effect in a paper by Horst Feistel. The idea is that changes should build up like an avalanche, so that a tiny initial change quickly creates large effects. The term and its exact application were new, but the basic concept was not; avalanche is a variant of Claude Shannon's diffusion and that in turn is a formalisation of ideas that were already in use.

The strict avalanche criterion formalises this. Complementing any single bit of input should give a 50% chance of a change any given bit of output.

Non-linearity

To be secure, every block cipher must contain some non-linear operations. If all operations in a cipher were linear — in any algebraic system, with the attacker making the choice of system and allowed to try as many as he likes — then the cipher could be reduced to a system of linear equations. Any system of simultaneous linear equations, in any algebra, can be solved straightforwardly if the number of equations matches or exceeds the number of variables. The attacker need only plug in known plaintext/ciphertext pairs until that condition holds, then solve for the key.

For example, for a cipher with 64-bit blocks and a 128-bit key,the attacker could write 64 equations each expressing one output bit in terms of 64 inputs and 128 key bits. Plug in one known plaintext/ciphertext pair and he has 64 equations in 128 variables, not a soluble system. However, if he has a second known pair, that gives him a different set of 64 equations in the same 128 key variables. The total system is now 128 equations in 128 variables. If the equations are all linear, this is soluble by standard techniques. However, he also has the option of plugging in a third known pair to get a system with 192 equations in 128 variables if that is easier to solve, or going even further if that helps.

Solving non-linear systems of equations is far harder so the cipher designer strives to introduce non-linearity to the system. Combined with good avalanche properties, this makes algebraic analysis prohibitively difficult. There are several ways to do add non-linearity; some ciphers rely on only one while others use several.

One method is mixing operations from different algebras. If the cipher relies only on Boolean operations, the cryptanalyst can try to attack using Boolean algebra; if it uses only arithmetic operations, he can try normal algebra. If it uses both, he has a problem. Of course arithmetic operations can be expressed in Boolean algebra or vice versa, but the expressions are inconveniently (for the cryptanalyst!) complex and non-linear whichever way he tries it. For example, in the CAST-128 or Blowfish F function, it is necessary to combine four 32-bit words into one. This is not done with a straightforward x = a+b+c+d or x=a^b^c^d but instead with something like x = (a+b)^(c-d) in one round and x = (a^b)+(c^d) in another. On most computers, this costs no more but it may make the analyst's job harder.

Other operations can also be used, albeit at higher costs. IDEA uses multiplication modulo 2¹⁶+1 and AES does matrix multiplications in a field.

Rotations, also called circular shifts, on words or registers are non-linear in normal algebra, though they are easily described in Boolean algebra. Some ciphers such as GOST use the same rotation by a constant amount in every round; it would be possible to use different constant rotations in different rounds. CAST-128 uses a key-dependent rotation in the F function. Ron Rivest used data-dependent rotations in RC-5 and RC-6.

A general operation for introducing non-linearity is the substitution box or s-box; see following section.

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.