Block cipher

Block ciphers are one of the two main types of symmetric cipher; they operate on fixed-size blocks of plaintext, giving a block of ciphertext for each. The other main type are stream ciphers, which generate a continuous stream of keying material to be mixed with messages.

There is an extensive literature both on the design of block ciphers and on methods of attacking them. For the design, see below and articles on specific ciphers. For the attacks, see cryptanalysis and articles on specific attacks. The standard references Applied Cryptography and Handbook of Applied Cryptography , each have a large section on block ciphers.

Among the best-known and most widely used block ciphers are two US government standards. The Data Encryption Standard (DES) from the 1970s is now considered obsolete; the Advanced Encryption Standard (AES) replaced it in 2002.

To choose the new standard, the National Institute of Standards and Technology ran an AES contest. Fifteen ciphers were entered, five finalists selected, and eventually AES chosen. Text below covers all five finalists — Rijndael which became AES, Twofish, Mars, RC6 and Serpent — and some other candidates.

Context

Block ciphers are essential components in many security systems. However, just having a good block cipher does not give you security, much as just having good tires does not give you transportation. It may not even help; good tires are of little use if you need a boat. Even in systems where block ciphers are needed, they are never the whole story.

Most of this article deals with block ciphers themselves. The major sections are:

• Size parameters describes how block size and key size are chosen
• Principles and techniques defines terms and introduces major ideas and methods
• DES and alternatives describes 20th century block ciphers, from the 70s into the 90s
• The AES generation describes the next generation, the first 21st century ciphers
• Large-block ciphers covers a few special cases that do not fit in the other sections

This section aims to provide a context for those by mentioning some issues that, while outside the study of the ciphers themselves, are crucially important in understanding and using these ciphers.

• It is hard to design any system that must withstand adversaries; see cryptography is difficult and information security.
• Block ciphers must withstand cryptanalysis. It is impossible to design a good block cipher, or evaluate the security of one, without a thorough understanding of the available attack methods.
• Kerckhoffs' Principle applies to block ciphers. No cipher can be considered secure unless it can resist an attacker who knows all its details except the key in use. Analysis of security claims cannot even begin until all internal details of a cipher are published, so anyone making security claims without publishing those details will be laughed at.
• Any cipher is worthless without a good key. In any application which encrypts large volumes of data, the key must be changed from time to time. See the cryptography article for discussion and random number for the methods used to generate keys which an opponent cannot guess.
• Various block cipher modes of operation are used when multiple blocks are to be encrypted. The block cipher defines how a single block is encrypted; the mode defines how multiple block encryptions are combined to achieve some larger goal. Using a mode that is inappropriate for the application at hand may lead to insecurity, even if the cipher itself is secure.

Block ciphers are often used as components in hybrid cryptosystems. These combine public key (asymmetric) cryptography with secret key (symmetric) techniques such as block ciphers or stream ciphers; generally other components such as cryptographic hashes and a cryptographically strong random number generator are used as well. Such a hybrid system can only be as strong as its weakest link, and it may not even be that strong. Using secure components including good block ciphers is certainly necessary, but just having good components does not guarantee that the system will be secure. See information security for the system issues.

That said, we turn to the block ciphers themselves.

Size parameters

One could say there are only three things to worry about in designing a block cipher:

• make the block size large enough that an enemy cannot create a code book, collecting so many known plaintext/ciphertext pairs that the cipher is broken.
• make the key size large enough that he cannot use a brute force attack, trying all possible keys
• then design the cipher well enough that no other attack is effective

Getting adequate block size and key size is the easy part; just choose large enough numbers. This section describes how those choices are made. Making ciphers that resist attacks that are cleverer than brute force (see cryptanalysis) is far more difficult. The following section, Principles and techniques covers ideas and methods for that.

Later on, we describe two generations of actual ciphers. The 20th century ciphers use 64-bit blocks and key sizes from 56 bits up. The 21st century ciphers use 128-bit blocks and 128-bit or larger keys.

If two or more ciphers use the same block and key sizes, they are effectively interchangeable. One can replace another in almost any application without requiring any other change to the application. This might be done to comply with a particular government's standards, to replace a cipher against which some new attack had been discovered, to provide efficiency in a particular environment, or simply to suit a preference.

Nearly all cryptographic libraries give a developer a choice of components, and some protocols such as IPsec allow a network administrator to select ciphers. This may be a good idea if all the available ciphers are strong, but if some are weak it just gives the developer or administrator, neither of whom is likely to be an expert on cipher internals, an opportunity to get it wrong. There is an argument that supporting multiple ciphers is an unnecessary complication. On the other hand, being able to change ciphers easily if one is broken provides a valuable safety mechanism.

Block size

The block size of a cipher is chosen partly for implementation convenience; using a multiple of 32 bits makes software implementations simpler. However, it must also be large enough to guard against code book attacks.

DES and the generation of ciphers that followed it all used a 64-bit block size. To weaken such a cipher significantly the attacker must buld up a code book with 2³² blocks, 32 gigabytes of data, all encrypted with the same key, As long as the cipher user changes keys reasonably often, a code book attack is not a threat. Procedures and protocols for block cipher usage therefore always include a re-keying policy.

However, with Moore's Law making larger code books more practical, NIST chose to play it safe in their AES specifications; they used a 128-bit block size. This was a somewhat controversial innovation at the time (1998), since it meant changes to a number of applications and it was not absolutely clear that the larger size was necessary. However, it has since become common practice; later ciphers such as Camellia and SEED also use 128 bits.

There are also a few ciphers which either support variable block size or have a large fixed block size. See the section on large-block ciphers for details.

Key size

In theory, any cipher can be broken by a brute force attack; the enemy just has to try keys until he finds the right one. However, the attack is practical only if the cipher's key size is inadequate. Current block ciphers all use at least 128-bit keys to protect against brute force attacks; many support larger keys as well. If the key uses n-bits, there are 2ⁿ possible keys and on average the attacker must test half of them, so the average cost of the attack is 2^n-1 encryptions.

Key size is critical in stream ciphers as well as block ciphers, for the same reasons. In many applications of cryptographic hash algorithms, no key is used. However in applications where a key is used, such as hashed message authentication codes, key size is naturally an issue.

Principles and techniques

This section introduces the main principles of block cipher design, defines standard terms, and describes common techniques.

All of the principles and many of the terms and techniques discussed here for block ciphers also apply to other cryptographic primitives such as stream ciphers and cryptographic hash algorithms.

Iterated block ciphers

Nearly all block ciphers are iterated block ciphers; they have multiple rounds, each applying the same transformation to the output of the previous round. At setup time the primary key undergoes key scheduling giving a number of round keys. In the actual encryption or decryption, each round uses its own round key. This allows the designer to define some relatively simple transformation, called a round function, and apply it repeatedly to create a cipher with enough overall complexity to thwart attacks.

Two common ways to design iterated block ciphers — SP networks and Feistel structures — and two important ways to look at the complexity requirements — avalanche and non-linearity — are covered in following sections.

Any iterated cipher can be made more secure by increasing the number of rounds or made faster by reducing the number. In choosing the number of rounds, the cipher designer tries to strike a balance that achieves both security and efficiency simultaneously. Often a safety margin is applied; if the cipher appears to be secure after a certain number of rounds, the designer specifies a somewhat larger number for actual use.

There is a trade-off that can be made in the design. With a simple fast round function, many rounds may be required to achieve adequate security; for example, GOST and TEA both use 32 rounds. A more complex round function might allow fewer rounds; for example, IDEA uses only 8 rounds. Since the ciphers with fast round functions generally need more rounds and the ones with few rounds generally need slower round functions, neither strategy is clearly better. Secure and reasonably efficient ciphers can be designed either way, and compromises are common.

In cryptanalysis it is common to attack reduced round versions of a cipher. For example, in attacking a 16-round cipher, the analyst might start by trying to break a two-round or four-round version. Such attacks are much easier. Success against the reduced round version may lead to insights that are useful in work against the full cipher, or even to an attack that can be extended to break the full cipher.

Whitening and tweaking

Nearly all block ciphers use the same basic design, an iterated block cipher with multiple rounds. However, some have additional things outside that basic structure.

Whitening involves mixing additional material derived from the key into the plaintext before the first round, or into the ciphertext after the last round. The most common practice is to do both. The technique was introduced by Ron Rivest in DES-X and has since been used in other ciphers such as RC6, Blowfish and Twofish. If the whitening material uses additional key bits, as in DES-X, then this greatly increases resistance to brute force attacks because of the larger key. If the whitening material is derived from the primary key during key scheduling, then resistance to brute force is not increased since the primary key remains the same size. However, using whitening is generally much cheaper than adding a round, and it does increase resistance to other attacks; see papers cited for DES-X.

A recent development is the tweakable block cipher . Where a normal block cipher has only two inputs, plaintext and key, a tweakable block cipher has a third input called the tweak. The tweak, along with the key, controls the operation of the cipher. Whitening can be seen as one form of tweaking, but many others are possible.

If changing tweaks is sufficiently lightweight, compared to the key scheduling operation which is often fairly expensive, then some new modes of operation become possible. Unlike the key, the tweak need not always be secret, though it should be somewhat random and in some applications it should change from block to block. Tweakable ciphers and the associated modes are an active area of current research.

The Hasty Pudding Cipher was one of the first tweakable ciphers, pre-dating the Tweakable Block Ciphers paper and referring to what would now be called the tweak as "spice".

Avalanche

The designer wants changes to quickly propagate through the cipher. 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.

If a single bit of input is changed at round $n$, that should affect all bits of the ciphertext by round $n+x$ for some reasonably small $x$. Ideally, $x$ would be 1, but this is not generally achieved in practice. Certainly $x$ must be much less than the total number of rounds; if $x$ is large, then the cipher will need more rounds to be secure.

The strict avalanche criterion is a strong version of the requirement for good avalanche properties. Complementing any single bit of the input or the key should give exactly a 50% chance of a change in any given bit of output.

Cipher structures

In Claude Shannon's . terms, a cipher needs both confusion and diffusion, and a general design principle is that of the product cipher which combines several operations to achieve both goals. This goes back to the combination of substitution and transposition in various classical ciphers from before the advent of computers. All modern block ciphers are product ciphers.

Two structures are very commonly used in building block ciphers — SP networks and the Feistel structure. In Shannon's terms, both are product ciphers. Either structure is a known quantity for a cipher designer, part of the toolkit. He or she gets big chunks of a design — an overall cipher structure with a well-defined hole for the round function to fit into — from the structure, This leaves him or her free to concentrate on the hard part, designing the actual round function. Neither structure gives ideal avalanche in a single round but, with any reasonable round function, both give excellent avalanche after a few rounds.

Not all block ciphers use one of these structures, but most do. This section describes these two common structures.

SP networks

A substitution-permutation network or SP network or SPN is Shannon's own design for a product cipher. It uses two layers in each round: a substitution layer provides confusion, then a permutation layer provides diffusion.

The S-layer typically uses look-up tables called substitution boxes or S-boxes, though other mechanisms are also possible. The input is XOR-ed with a round key, split into parts and each part used as an index into an S-box. The S-box output then replaces that part so the combined S-box outputs become the S-layer output. S-boxes are discussed in more detail in their own section below.

The P-layer permutes the resulting bits, providing diffusion or in Feistel's terms helping to ensure avalanche.

A single round of an SP network does not provide ideal avalanche; output bits are affected only by inputs to their S-box, not by all input bits. However, the P-layer ensures that the output of one S-box in one round will affect several S-boxes in the next round so, after a few rounds, overall avalanche properties can be very good.

Feistel structure

Another way to build an iterated block cipher is to use the Feistel structure. This technique was devised by Horst Feistel of IBM and used in DES. Such ciphers are known as Feistel ciphers. In Shannon's terms, they are another class of product cipher.

Each round uses an operation called the F function whose input is half a block and a round key; the output is a half-block of scrambled data which is XORed into the other half block of text. The rounds alternate direction — in one data from the left half-block is input and the right half-block is changed, and in the next round that is reversed.

Showing the half-blocks as left and right, XOR as ^ and round key for round n as k_n, even numbered rounds are then:

left_n = left_n-1 ^ F(right_n-1, k_n)

right_n = right_n-1

and odd-numbered rounds are

right_n = right_n-1 ^ F(left_n-1, k_n)

left_n = left_n-1

Since XOR is its own inverse (a^b^b=a for any a,b) and the half-block that is used as input to the F function is unchanged in each round, reversing a Feistel round is straightforward. Just calculate the F function again with the same inputs and XOR the result into the ciphertext to cancel out the previous XOR. For example, the decryption step matching the first example above is:

left_n-1 = left_n ^ F(right_n, k_n)

right_n-1 = right_n

In some ciphers, including those based on SP networks, all operations must be reversible so that decryption can work. The main advantage of a Feistel cipher over an SP network is that the F function itself need not be reversible, only repeatable. This gives the designer extra flexibility; almost any operation he can think up can be used in the F function. On the other hand, in the Feistel construction, only half the output changes in each round while an SP network can change all of it in a single round.

A single round in a Feistel cipher has less than ideal avalanche properties; only half the output is changed. However, the other half is changed in the next round so, with a good F function, a Feistel cipher can have excellent overall avalanche properties within a few rounds.

The hard part of Feistel cipher design is of course the F function. Design goals include efficiency, easy implementation, and good avalanche properties. Also, it is critically important that the F-function be highly non-linear. All other operations in a Feistel cipher are linear and a cipher without enough non-linearity is weak; see the next section.

Non-linearity

To be secure, every cipher must contain non-linear operations. If all operations in a cipher were linear — in any algebraic system, with the attacker making the choice of system and perhaps trying more than one — 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. Therefore, any cipher that uses only linear operations can be broken by an algebraic attack.

The attacker can also try linear cryptanalysis. If he can find a good enough linear approximation for the round function and has enough known plaintext/ciphertext pairs, then this will break the cipher. Defining "enough" in the two places where it occurs in the previous sentence is tricky; see linear cryptanalysis. Simplifying outrageously, a good rule for the cipher designer is the more non-linearity the better; have at least some components that are not even close to linear.

What makes these attacks impractical is a combination of the sheer size of the system of equations used (large block size, whitening, and more rounds all increase this) and non-linearity in the relations involved. In any algebra, solving a system of linear equations is more-or-less straightforward provided there are more equations than variables. However, 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 and enough rounds, this makes both direct algebraic analysis and linear cryptanalysis prohibitively difficult. There are several ways to 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 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 x = ((a+b)^c)+d. On most computers this costs no more, but it makes 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 with polynomials in a Galois field.

Rotations, also called circular shifts, on words or registers are non-linear in normal algebra, though they are easily described in Boolean algebra. GOST uses rotations by a constant amount, CAST-128 and CAST-256 use a key-dependent rotation in the F function, and RC5, RC6 and MARS all use data-dependent rotations.

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

Non-linearity is also an important consideration in the design of stream ciphers and cryptographic hash algorithms. For hashes, much of the mathematics and many of the techniques used are similar to those for block ciphers. For stream ciphers, rather different mathematics and methods apply (see Berlekamp-Massey algorithm for example), but the basic principle is the same.

S-boxes

S-boxes or substitution boxes are look-up tables. The basic operation involved is a = sbox[b] which, at least for reasonable sizes of a and b, is easily done on any computer.

There is an extensive literature on the design of good S-boxes, much of it emphasizing achieving high non-linearity though other criteria are also used. See external links and references below.

S-boxes are described as $m*n$ or $m$ by $n$, with $m$ representing the number of input bits and $n$ the number of output bits. For example, DES uses 6 by 4 S-boxes. The storage requirement for an $m*n$ S-box is 2^m*n bits, so large values of $m$ (many input bits) are problematic. Values up to eight are common; going much beyond that would be expensive. Large values of $n$ (many output bits) are not a problem; 32 is common and at least one system, the Tiger hash algorithm , uses 64.

S-boxes are often used in the S-layer of an SP Network. In this application, the S-box must have an inverse to be used in decryption. It must therefore have the same number of bits for input and output; only $n*n$ S-boxes can be used. For example, AES is an SP network with a single $8*8$ S-box and Serpent is one with eight $4*4$ S-boxes.

Another common application is in the F function of a Feistel cipher. Since the F function need not be reversible, there is no need to construct an inverse S-box for decryption and S-boxes of any size may be used. The first generation of Feistel ciphers used relatively small S-boxes, $6*4$ for DES and $4*4$ for GOST. Later Feistel ciphers use larger ones, $8*32$ for both CAST and Blowfish; the reasons for this are discussed in the CAST S-boxes section.

With either an SP network or a Feistel construction, non-linear S-boxes and enough rounds give a highly non-linear cipher.

In perfectly non-linear S-boxes , not only are all columns bent functions (the most non-linear possible Boolean functions), but all linear combinations of columns are bent functions as well. This is possible only if $m>=2n$, there are at least twice as many input bits as output bits. Such S-boxes are therefore not much used.

S-boxes are sometimes used as an analytic tool even for operations that are not actually implemented as S-boxes. Any operation whose output is fully determined by its inputs can be described by an S-box; concatenate all inputs into an index, look that index up, get the output. For example, the IDEA cipher uses a multiplication operation with two 16-bit inputs and one 16-bit output; it can be modeled as a 32*16 S-box. In an academic paper, one might use such a model in order to apply standard tools for measuring S-box non-linearity. A well-funded cryptanalyst might actually build the S-box (8 gigabytes of memory) either to use in his analysis or to speed up an attack.

DES and alternatives

The Data Encryption Standard, DES, was made a US government standard block cipher in the late 70s. That 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.

This section covers 20th century block ciphers, DES and the ciphers which followed DES in the 80s and 90s. DES served as a sort of baseline for cipher design in this era; the design goal for all these ciphers was to replace DES in some of its many applications with something faster, more secure, or both. All of the followers — GOST, Blowfish, CAST-128, IDEA and others — 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.

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. We cover them in the next section.

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. DES operates on 64-bit blocks and takes a 56-bit key.

DES is now considered obsolete; its small key size makes it vulnerable to a brute force attack, given modern computers. In 2002, DES was replaced as a US government standard by the Advanced Encryption Standard which uses 128-bit blocks and takes 128, 192 or 256-bit keys.

Some applications still use Triple DES, a variant which applies DES three times with two or three different keys; see next section.

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 internals

DES operates on 64-bit blocks and takes a 56-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 S-boxes in the next round. After a few rounds, the effect spreads to the entire output.

DES was originally designed for hardware implementation and includes some operations, such as the bit permutations used in both key scheduling and the F function, which are inconvenient to do in software. There have been many software implementations of DES, many of them provide acceptable performance, and some have been widely used, but later ciphers designed with software implementation in mind are generally faster.

DES's Achilles' heel: key length

DES can no longer be considered secure in any application where there is significant risk that an adversary will deploy large resources.

DES uses a 56-bit key. That is simply too small to resist a brute force attack, an exhaustive search in which the enemy just tries keys until he finds the right one. If an enemy either has money to spend on specialised hardware or has access to many general-purpose computers, then DES is not secure against that enemy. Of course this also applies to any other cipher with a small key.

In 1998, the Electronic Frontier Foundation built a $200,000 machine that finds a DES key in a few days; details are in Cracking DES . In 2006, two German universities built a €9,000 "Cost-Optimized Parallel COde Breaker" or Copacobana machine based on Field programmable gate arrays that breaks DES in just under a week on average. That machine is commercially available.

Many computing tasks are quite difficult to parallelize. Cipher-cracking is one of the few exceptions; adding more hardware just makes it faster without raising any tricky communication problems. One Copacobana machine breaks DES in a week, so an attacker using seven of them can do it in a day and so on. On an intelligence agency budget, using 168 of them to crack a key an hour, or 10,000 to crack a key a minute, would be feasible if any worthwhile target still used DES.

DES has also been cracked by people using many general-purpose computers. In 1998 RSA Laboratories ran a "DES Challenge" offering a cash prize to crack a DES key. The winners used many machines connected by the Internet, "a peak of about 14,000 unique hosts within a single 24-hour period"; it took them three months to find one key. Today, the machines are much faster, according to Moore's Law roughly 100 times faster. Presumably a network of comparable size today could break DES in about a day and a smaller network could do it in a few weeks or months. Many large organisations — business, government, criminal, ... — have enough computing power for this.

Even today, it would still take decades for an attacker with a single machine to find a DES key. However, a lone attacker might be able to do it fairly quickly by using machines at an employer or a university.

Despite this, DES is still moderately widely deployed in legacy applications. In some cases — depending on the value of the information, the threats, the costs of changing to a stronger cipher, and the risks of changing a working system — keeping it in service may be reasonable. However, against serious threats it must be considered insecure; certainly there is no reason to even consider it for new applications.

Variations on DES

DES is vulnerable to brute force attack because of its small key. However, it has withstood decades of intensive analysis with no catastrophic flaws found, so it appears to be basically a remarkably solid design. Various people have therefore sought ways to achieve larger key size while retaining the basic DES algorithm.

Ron Rivest proposed DESX or DES-X, essentially DES with whitening. 64 bits of key material are XORed into the plaintext before encryption, and 64 more into the ciphertext afterward. With the 56 bits of DES key, the gives 184 total keys bits so the cipher is safe from brute force attacks. Encryption overheads are only a tiny bit more than DES; the cost of the XORs. Analysis of resistance to linear cryptanalysis and differential cryptanalysis shows that it is better than DES against these attacks, but not hugely so.

Biham and Biryukov proposed techniques in which additional key bits are used to alter the S-boxes before encryption. This increases setup cost somewhat, but the overheads per block encrypted or decrypted are identical to those for DES. It is resistant to brute force and somewhat better than DES against other attacks. The technique can be used with some hardware encryption devices that DESX could not be used on.

Another approach is to use independent round keys. DES has 16 48-bit round keys, a total of 768 bits of keying material, but in normal DES they are all derived from the 56-bit main key. Use 768 independent key bits and the cipher is obviously resistant to brute force, one proposal was G-DES or Generalised DES . However, Schneier at al. demonstrate that the technique has weaknesses.

Triple DES

Another way to derive a stronger cipher from DES is to apply DES multiple times with different keys.

Just applying DES twice, double DES, is ineffective. Using two 56-bit keys gives 112 total key bits, so a brute force attack needs 2¹¹¹ encryptions. However, brute force is not the best attack. A meet-in-the-middle attack needs only 2⁵⁷ DES operations, though a large amount of memory is also required. That is, double DES is only four times stronger than DES, which can be broken by brute force with an average of 2⁵⁵ encryptions.

Triple DES or 3DES is effective. Apply DES three times with two or three different keys. This is also vulnerable to a meet-in-the-middle attack, but the work factor for that attack is 2¹¹². That provides adequate protection for many applications, and no better attack is known.

Triple DES can be somewhat slow compared to other ciphers. It requires three DES encryptions per block. DES was designed for hardware implementation and includes some operations which are difficult in software. For new applications, a newer cipher such as AES will generally be both faster and more secure. Triple DES provides only 2¹¹² strength against the best known attack, meet-in-the-middle. AES is completely resistant to that attack and gives at least 2¹²⁷ strength against the best known attack on it, brute force.

Triple DES is, however, still widely deployed in legacy applications. Consider a bank with several thousand ATM machines, with built-in hardware or well-tested software for triple DES. Changing those will certainly be expensive and will entail some risk of bugs in the new system; it may not be worth it.

Triple DES can be done with three keys, two keys or just one key, though the one-key variant should never be used. In all cases, the order of operations is EDE or encrypt-decrypt-encrypt.

The three-key variant is widely used; for example RFC 2451 specifies it for use in IPsec.

In the two-key variant the first and third keys are the same. This gives a saving in key storage and key transmission overheads — only 112 bits are required rather than 168 — but this is not significant in most applications. Either two-key or three-key 3DES has 2¹¹² strength against a meet-in-the-middle attack, and that is the best known attack against either. The three-key variant is stronger against brute force, but that does not matter much since a better attack is known. Overall, it appears the two-key variant is just as strong.

The one-key variant is a "worst of both worlds" solution, the overheads of triple DES (three times those of DES) with the security of DES (inadequate against brute force attacks). The only possible reason to use this would be to make two systems communicate when one can only do DES and the other only Triple DES. Using one-key Triple DES on one end would allow encrypted communication, but it would only be as secure as DES.

GOST

The GOST cipher, and the related GOST hash algorithm, were standards in the Soviet Union.

The GOST cipher resembles DES in many ways; it is an iterated block cipher with a Feistel structure using eight s-boxes in the F function; each s-box produces four bits of output and these are combined to produce the 32-bit output. However, it differs from DES in other ways. There is no expansion from 32 bits to 48, so s-box inputs are only four bits rather than six, and there is no permutation of the output bits, only an 11-bit circular shift; these differences make GOST easier to implement in software than DES. However, they may also weaken the cipher; GOST compensates by increasing the number of rounds to 32 rather than DES's 16.

GOST also uses a 256-bit key which makes it, unlike DES, thoroughly resistant to brute force attacks.

Moreover, each implementation of GOST can use different S-boxes; an organisation can have its own implementation with its own S-boxes. If those S-boxes are kept secret, the total secret information is about 610 bits ,

CAST

The original work on CAST was in Carlisle Adams' PhD thesis . A well-known paper is "Constructing Symmetric Ciphers using the CAST Design Procedure". . There is also a US patent on some of the techniques.

"CAST" is a general procedure for constructing a family of ciphers; individual ciphers have names like "CAST-128".

F function and S-boxes

CAST ciphers are Feistel ciphers using large S-boxes, 8*32 rather than the 6*4 of DES. They are primarily designed for software implementation, rather than the 1970s hardware DES was designed for, so looking up a full computer word at a time makes sense. An 8*32 S-box takes one K byte of storage; several can be used on a modern machine without difficulty.

In earlier Feistel ciphers, DES and GOST, the F function is essentially one round of an SP Network. These ciphers use eight 6*4 or 4*4 S-boxes to get 32 bits of S-box output. Those bits, reordered by a simple transformation, become the 32-bit output of the F function. Avalanche properties are less than ideal since each output bit depends only on the inputs to one S-box. The output transformation compensates for this, ensuring that the output from one S-box in one round affects several S-boxes in the next round so that good avalanche is achieved after a few rounds.

CAST ciphers, and Blowfish, use bigger S-boxes and do not use S-box bits directly as F function output. Instead, they take 32-bit words from several S-boxes and combine them to form a 32-bit output, so that the F function has ideal avalanche properties — every output bit depends on all S-box output words, and therefore on all input bits and all key bits. With the Feistel structure and such an F function, complete avalanche — all 64 output bits depend on all 64 input bits — is achieved in three rounds. This also requires fewer S-box lookups than the eight in DES or GOST so the F function, and therefore the whole cipher, can be reasonably efficient.

No output transformation is required in such an F function, but one may be used anyway; CAST-128 has a key-dependent rotation.

The CAST S-boxes use bent functions (the most highly non-linear Boolean functions) as their columns. That is, the mapping from all the input bits to any single output bit is a bent function. Such S-boxes meet the strict avalanche criterion ; not only does every every bit of round input and every bit of round key affect every bit of round output, but complementing any input bit has exactly a 50% chance of changing any given output bit. A paper on generating the S-boxes is Mister & Adams "Practical S-box Design" . Bent functions are combined to get additional desirable traits — a balanced S-box (equal probability of 0 and 1 output), miniumum correlation among output bits, and high overall S-box non-linearity.

The first CAST cipher (in the thesis) was a Feistel cipher with 64-bit blocks, a 64-bit key, 8 rounds with 16-bit round keys, a very simple key schedule, and six 8*32 S-boxes. For the F function, split the 32-bit input into 4 bytes and the round key into 2 bytes. Run each of the 6 bytes through a different S-box to get 6 32-bit outputs and combine those outputs using XOR. This cipher was not much used; when people mention "CAST", they almost always mean the widely deployed CAST-128.

Resisting linear & differential attacks

One objective of the CAST design procedure is to produce ciphers that are not vulnerable to either linear cryptanalysis or differential cryptanalysis . These are the only known attacks that break DES with less effort than brute force. More generally, they are the most powerful known cryptanalytic methods of attacking block ciphers. Both, however, require large numbers of known or chosen plaintexts, so a simple defense against them is to re-key often enough that the enemy cannot collect sufficient texts.

CAST goes further, building a cipher that is provably immune to linear or differential analysis with any number of texts. The method, taking linear cryptanalysis as our example and abbreviating it LC, is as follows:

start from properties of the F function, particularly the bent functions in the S-boxes

derive a limit m, the maximum possible quality of any linear approximation to a single round

consider the number of rounds, r, as a variable

derive an expression for e, the effort required to break the cipher by LC, in terms of r and m

find the minimum r such that e exceeds the effort required for brute force, making LC impractical

derive an expression for c, the number of chosen plaintexts required for LC, also in terms of r and m

(LC with only known plaintext requires more texts, so it can be ignored)

find the minimum r such that c exceeds the number of possible plaintexts, 2^blocksize, making LC impossible

A similar approach applied to differentials gives values for r that make differential cryptanalysis impractical or impossible. Choose the actual number of rounds so that, at a minimum, both attacks are impractical. Ideally, make both impossible, then add a safety factor.

This type of analysis is now a standard part of the cryptographer's toolkit. Many of the AES candidates, for example, included proofs along these lines in their design documentation, and AES itself uses such a calculation to determine the number of rounds required for various key sizes.

CAST-128

CAST-128, also called CAST5, is the best-known and most widely used CAST cipher. It replaced IDEA in PGP in version 3.0 and is specified in all versions of the Open PGP standard . Nortel and their spin-off Entrust also used it in several products; Adams worked for both companies.

CAST-128 is a Feistel cipher with 64-bit blocks and 16 rounds. Key sizes from 40 to 128 bits are supported; 128 is almost invariably used. There are eight 8*32 S-boxes, four used in the key schedule and the other four in actual encryption. Round keys are 37 bits.

The F function XORs the input with 32 bits of round key, splits the result into bytes and runs each byte through a different S-box to get four 32-bit results. Those are combined non-linearly, using different combining functions in different rounds. Finally, the output is given a rotation controlled by the other 5 round key bits.

The cipher is freely available for any use. There is an RFC describing it; see external links. A descendant named CAST-256 was an AES candidate; there is also an RFC for that.

The RFCs provide a set of standard S-boxes that are normally used in any implementation of either CAST-128 or CAST-256. However, it would be possible for a large organisation to have its own version of either cipher, by generating its own S-boxes using the Mister & Adams paper as a guide.

Blowfish

Blowfish was designed by Bruce Schneier. It is a Feistel cipher with 64-bit blocks and 16 rounds. Supported key sizes are 32 to 576 bits; at least 128 is recommended.

The F function XORs the input with the 32-bit round key, splits the result into bytes and runs each byte through a different S-box to get four 32-bit results. Those are combined non-linearly with x = ((a+b)^c)+d. As for CAST, the F function has ideal avalanche properties — every output bit depends non-linearly on all input bits and all key bits. Complete avalanche — all 64 output bits depend on all 64 input bits — is achieved in three rounds.

Blowfish S-boxes are key-dependent, randomly generated at cipher setup time. Start with a round key array of 18 32-bit entries (16 actual round keys plus 64 bits for whitening) and four S-boxes, all initialised with apparently random bits derived from an expansion of pi. XOR the primary key into the round key array; the key can be any size up to the 576 bits of that array, Then run the cipher repeatedly and use the output to change both the round keys and the S-boxes; this takes 521 cipher iterations.

For some applications, this key setup is inconveniently expensive; Blowfish may not be the best choice if keys need to be changed often. However, the actual encryption and decryption are fast.

The cipher is freely available for any use. It has a home page; see external links.

IDEA

IDEA is the International Data Encryption Algorithm, a European standard. It is a iterated block cipher, but does not have a Feistel structure. Block size is 64 bits, key 128. No S-boxes are used.

IDEA achieves non-linearity by mixing operations from three different algebraic systems. All operations have 16-bit words as both input and output. Two are just bitwise XOR and addition modulo 2¹⁶. The third is basically multiplication modulo the prime number 2¹⁶+1, but modified so that the "x*0 yields zero for all x" case does not weaken the cipher.

The IDEA multiplication operation is highly non-linear and has good avalanche properties; every output bit depends on all input bits. It requires both a multiplication and a remainder operation, so it is not nearly as cheap as addition or XOR, but it is reasonably fast on a modern 32-bit or larger CPU. In most environments it will be more expensive than S-box lookups but in some, such as an embedded processor with limited cache, it may be cheaper.

In any case, IDEA uses only 8 rounds so it can afford a moderately expensive operation in the round function.

RC5

RC5, Rivest Cipher 5 was from Ron Rivest. It was the first well-known cipher to make extensive use of data-dependent rotations to achieve non-linearity. It is a Feistel cipher.

There is an RFC giving an RC5 specification for Internet use; see external links.

Its descendant RC6, also using data-dependent rotations, was an AES finalist. RSA Laboratories have a page describing both ciphers; see external links.

TEA

The Tiny Encryption Algorithm, or TEA is a cipher designed for small size and easy software implementation. It is a Feistel cipher with 64-bit blocks, a 128-bit key, 32 rounds and a very simple round function using only 32-bit operations — addition, bitwise XOR and shift. In C, the encryption and decryption routines are under 10 lines each. No S-boxes are used, so the data space required is also tiny.

TEA has some weaknesses. Equivalent keys are one problem; each key is equivalent to three others, so the effective key size is only 126 bits. As a result, TEA is weak if used to build a cryptographic hash. This weakness led to a method for hacking Microsoft's Xbox game console, where the cipher was used as a hash function. TEA is also susceptible to a related-key attack which requires 2²³ chosen plaintexts under a related-key pair, with 2³² time complexity .

Partly because of these weaknesses, a number of revisions of TEA have been designed. Block TEA or XTEA extends TEA to build a variable block size cipher. XXTEA is a later revision.

The cipher is freely available for any use. It has a home page; see external links.

The AES generation

Starting in the late 90s, the US National Institute of Standards and Technology (NIST) ran a contest to find a block cipher to replace DES. They were very careful about complying with Kerckhoffs' Principle, perhaps partly to avoid some of the criticisms that had been made of the secrecy in the DES standardisation process. The entire process was completely open; even their requirements document was published and comment or criticism invited before a final version was written, and all of the later work toward the choice of a standard was public as well.

The final requirements specified a block cipher with 128-bit block size and support for 128, 192 or 256-bit key sizes. Evaluation criteria included security, performance on a range of platforms from 8-bit CPUs (e.g. in smart cards) up, and ease of implementation in both software and hardware.

Fifteen submissions meeting basic criteria were received, not just from the US but from many other countries as well. All of the entries were iterated block ciphers; in Shannon's terms all were product ciphers. Most used an SP network or Feistel structure, or variations of those. Several had proofs of resistance to various attacks. After about a year of analysis and testing, and two conferences, the field was narrowed to five finalists — Twofish, MARS, Serpent, RC6, and Rjindael. All finalists and some other candidates are described below.

In October 2002, they announced the winner — Rijndael. Rijndael then became the Advanced Encryption Standard or AES.

The contest was open and international and extensive work was done on testing and comparing the various candidates. To facilitate this, NIST defined some standard interfaces which everybody used. For almost all candidate ciphers, implementations with these interfaces are readily available; see external links. Many, though not all, of these ciphers have open licenses. This means that anyone implementing AES has the option of adding other ciphers at minimum cost, in particular the other three finalists with open licenses — Twofish, MARS, and Serpent. This gives a cheap insurance policy against the (presumably remote) chance of someone finding a good attack on AES.

Because of the birthday attack, a cryptographic hash needs to provide output of 2n bits to resist attacks as well as a cipher with an n-bit key. NIST has therefore issued standards for the SHA-2 family of hashes — SHA-256, SHA-384 and SHA-512 to match the strength of AES, plus SHA-224 to match the 112-bit strength of Triple DES. However, those hashes are all derived from SHA and weaknesses have been shown in that, so in 2008 NIST started a contest similar to the AES contest to design an Advanced Hash Standard which can (if it proves necessary) replace SHA-2 as AES replaced DES.

AES

The Advanced Encryption Standard or AES is the algorithm formerly known as Rijndael (pronounced approximately "rhine doll"). It was designed by two Belgians, Joan Daemen and Vincent Rijmen.

It is an iterated block cipher, but not a Feistel cipher; the overall structure is an SP network. Non-linearity is obtained by mixing operations from different algebraic groups. There are four operations.

Two give confusion:

AddRoundKey: bitwise XOR of 128-bit state and 128-bit round key

SubBytes: run individual bytes through an 8*8 S-box

The other two give diffusion, treating the 128-bit block as a four by four matrix of bytes:

ShiftRows: cyclicly shift each row by a fixed amount

MixColumns: treat each column as a polynomial over the Galois field GF(2⁸); multiply it by one constant polynomial modulo another

It encrypts 128-bit blocks with a 128, 192 or 256-bit key. The number of rounds varies with key size: 10 for 128-bit keys, 12 for 192-bit keys and 14 for 256-bit keys. The numbers of rounds were chosen based on an analysis showing that they are enough to give resistance to linear cryptanalysis and differential cryptanalysis.

The cipher is freely available for any use. See external links for much more information.

Twofish

Twofish was an AES finalist cipher from Bruce Schneier's company Counterpane. Except for the name, it has little relationship to Blowfish; Twofish was a new design.

Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits. It is a 16-round Feistel cipher using four key-dependent 8*8 S-boxes.

The cipher is freely available for any use. It has a home page; see external links.

It has a successor named "Threefish", used in the Skein hash algorithm, a candidate in the Advanced Hash Standard contest.

Serpent

Serpent was an AES finalist cipher from an international team of well-known researchers — Ross Anderson (UK), Eli Biham (Israel), and Lars Knudsen (Norway). Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits.

Serpent is an SP network with 32 rounds. It uses eight 4 by 4 S-boxes, but unlike other ciphers it does not use them all in each round. Instead each round uses eight copies of the same S-box, so that 32-bit computer instructions can do eight 4-bit operations in parallel. Each of the eight S-boxes is used in four different rounds,

The cipher is freely available for any use. It has a home page; see external links.

RC6

RC6 was an AES finalist cipher designed by Ron Rivest. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits.

Like RC5, RC6 made extensive use of data-dependent rotations. RSA Laboratories have a page describing both ciphers; see external links. .

RC6 is the only one of the five finalists which does not have a completely open license; it is still proprietary to RSA Laboratories.

MARS

MARS was an AES finalist cipher from IBM. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits.

It uses a variant of the Feistel structure which they call a "type 3 Feistel network"; the 128-bit block is treated as four 32-bit sub-blocks; each round uses one sub-block as input and modifies all of the other three sub-blocks. Like RC6, it uses data-dependent rotations. One 9*32 S-box is used; for some operations it is treated as two 8*32 S-boxes.

The cipher is now freely available. It has a home page; see external links.

CAST 256

CAST-256 was an AES candidate cipher; it did not make it into the finals. Like all AES candidates, it uses 128-bit blocks and supports key sizes of 128, 192 or 256 bits.

It is a Feistel-like cipher extended to four 32-bit sub-blocks instead of the two sub-blocks used in CAST-128 for 64-bit blocks. In the terms used by the MARS team, it is a "type one Feistel network"; each round takes one 32-bit sub-block as input and alters one 32-bit sub-block; 48 rounds are used. The F function and S-boxes are from CAST-128.

It is freely available for any use. There is an RFC describing it; see external links.

Hasty Pudding

The Hasty Pudding cipher (HPC), from Rich Schroeppel was, in some ways, the most interesting of the AES candidates. It did not make it into the finals.

Hasty Pudding is a variable size block cipher; blocks can be any size the application requires. It therefore might be ideal for things like encrypting disk blocks; see large block ciphers. Also, quoting the home page "Arbitrary sets, such as dates, or the printable subset of ascii, or the 20-bit primes, can be encrypted to themselves." Key size is also variable; any integer number of bits.

Hasty Pudding is also a tweakable block cipher, though it was designed before that term came into use. What is now called the "tweak" is called "spice" in Hasty Pudding.

The cipher is freely available for any use. It has a home page; see external links.

Camellia

Camellia is a cipher from Mitsubshi and Nippon Telephone and Telegraph. It was not an AES candidate, but has the same 128-bit block size so it could be used as a drop-in replacement for AES in many applications. It is one of the standard ciphers for the NESSIE (New European Schemes for Signatures, Integrity and Encryption) project. It is an 18-round Feistel cipher.

The cipher is freely available for any use. It has a home page; see external links.

SEED

SEED is a block cipher developed by the Korean Information Security Agency (KISA) and widely used in Korea. It was not an AES candidate. It is a 16-round Feistel cipher using two 8 by 8 S-boxes. It uses 128-bit blocks and takes a 128-bit key, so it could be used as a drop-in replacement for AES-128 in many applications

It has a home page; see external links.

Large-block ciphers

For most applications a 64-bit or 128-bit block size is a fine choice; nearly all common block ciphers use one or the other. Such ciphers can be used to encrypt objects larger than their block size; just choose an appropriate mode of operation.

However, a few ciphers supporting larger block sizes do exist; this section discusses them.

A block cipher with larger blocks may be more efficient; it takes fewer block operations to encrypt a given amount of data. It may also be more secure in some ways; diffusion takes place across a larger block size, so data is more thoroughly mixed, and large blocks make a code book attack more difficult. On the other hand, great care must be taken to ensure adequate diffusion within a block so a large-block cipher may need more rounds, larger blocks require more padding, and there is not a great deal of literature on designing and attacking such ciphers so it is hard to know if one is secure. Large-block ciphers are inconvenient for some applications and simply do not fit in some protocols.

Some block ciphers, such as Block TEA and Hasty Pudding, support variable block sizes. They may therefore be both efficient and convenient in applications that need to encrypt many items of a fixed size, for example disk blocks or database records. However, just using the cipher in ECB mode to encrypt each block under the same key is unwise, especially if encrypting many objects. With ECB mode, identical blocks will encrypt to the same ciphertext and give the enemy some information. One solution is to use a tweakable cipher such as Hasty Pudding with the block number or other object identifier as the tweak. Another is to use CBC mode with an initialisation vector derived from an object identifier.

Cryptographic hash algorithms can be built using a block cipher as a component. There are general-purpose methods for this that can use existing block ciphers; Applied Cryptography gives a long list and describes weaknesses in many of them. However, some hashes include a specific-purpose block cipher as part of the hash design. One example is Whirlpool, a 512-bit hash using a block cipher similar in design to AES but with 512-bit blocks and a 512-bit key. Another is the Advanced Hash Standard candidate Skein which uses a tweakable block cipher called Threefish. Threefish has 256-bit, 512-bit and 1024-bit versions; in each version block size and key size are both that number of bits.

It is possible to go the other way and use any cryptographic hash to build a block cipher; again Applied Cryptography has a list of techniques and describes weaknesses. The simplest method is to make a Feistel cipher with double the hash's block size; the F function is then just to hash text and round key together. This technique is rarely used, partly because a hash makes a rather expensive round function and partly because the block cipher block size would have to be inconveniently large; for example using a 160-bit bit hash such as SHA-1 would give a 320-bit block cipher.

The hash-to-cipher technique was, however, important in one legal proceeding, the Bernstein case. At the time, US law strictly controlled export of cryptography because of its possible military uses, but hash functions were allowed because they are designed to provide authentication rather than secrecy. Bernstein's code built a block cipher from a hash, effectively circumventing those regulations. Moreover, he sued the government over his right to publish his work, claiming the export regulations were an unconstitutional restriction on freedom of speech. The courts agreed, effectively striking down the export controls.

It is also possible to use a public key operation as a block cipher. For example, one might use RSA with 1024-bit keys as a block cipher with 1024-bit blocks. Since the round function is itself cryptographically secure, only one round is needed. However, this is rarely done; public key techniques are expensive so this would give a very slow block cipher. A much more common practice is to use public key methods, block ciphers, and cryptographic hashes together in a hybrid cryptosystem.