Block cipher: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Sandy Harris
mNo edit summary
 
Line 1: Line 1:
{{subpages}}
{{PropDel}}<br><br>{{subpages}}
{{main|Cryptography}}
{{TOC|right}}
{{TOC-right}}
In [[cryptography]], '''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 cipher]]s, which generate a continuous stream of keying material to be mixed with messages.


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 symmetric cipher is a [[stream cipher]], which generates a stream of keying material to be mixed with messages. Block ciphers can be used in various [[#Block cipher modes|modes]] when multiple blocks are to be encrypted.
The basic function of block ciphers is to keep messages or stored data [[Information_security#Content_confidentiality | secret]]; the intent is that an unauthorised person be completely unable to read the enciphered material. Block ciphers therefore use a [[Key (cryptography)|key]] and are designed to be hard to read without that key. Of course an attacker's intent is exactly the opposite; he wants to read the material without authorisation, and often without the key. See [[cryptanalysis]] for his methods.


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. Widely used references include "Applied Cryptography" <ref name="schneier">{{citation
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 competition. Fifteen ciphers were entered, five finalists selected, and eventually AES chosen. Text below gives an overview; for details of the process and the criteria, and descriptions of all fifteen candidates, see the [[AES competition]] article.
| first = Bruce | last = Schneier
| title = Applied Cryptography
| date = 2nd edition, 1996,  
| publisher = John Wiley & Sons
|ISBN =0-471-11709-9}}</ref> and "Handbook of Applied Cryptography" <ref name=HAC>{{citation
| first1 = AJ | last1 = Menezes | first2 = PC | last2= van Oorschot | first3= SA | last3 = Vanstone 
| url=http://www.cacr.math.uwaterloo.ca/hac/
| title = Handbook of Applied Cryptography
| date = Fifth Edition, 2001
| ISBN=0-8493-8523-7}}</ref>, each with a large section on block ciphers. A useful web index of current work is the [http://www2.mat.dtu.dk/people/Lars.R.Knudsen/bc.html Block Cipher Lounge].  


Among the best-known and most widely used block ciphers are two US government standards. The [[#DES | Data Encryption Standard]] from the 1970s is now considered obsolete; the [[#AES | Advanced Encryption Standard]] replaced it in 2002. Both of these ciphers, and others, are discussed in more detail below.
These standards greatly influenced the design of other block ciphers, and the latter part of this article is divided into sections based on that. [[#DES and alternatives | DES and alternatives]] describes 20th century block ciphers, all with the 64-bit block size of DES. [[#The AES generation | The AES generation]] describes the next generation, the first 21st century ciphers, all with the 128-bit block size of AES. [[#Large-block ciphers | Large-block ciphers]] covers a few special cases that do not fit in the other sections.


== Principles and techniques ==
== 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. This section gives an overview of the rest of the story; it aims to provide a context for the rest of the article by mentioning some issues that, while outside the study of the ciphers themselves, are crucially important in understanding and using these ciphers.


Most of the principles discussed here for block ciphers also apply to other cryptographic primitives. [[Hash]] algorithms generally use iteration and require avalanche. In both hashes and [[stream cipher]]s, non-linearity is an important design criterion, and s-boxes can be used in either.  
Any cipher is worthless without a good key. Keys must be kept secure, they should be large enough and sufficiently random that searching for the key (a [[brute force attack]]) is effectively impossible, and in any application which encrypts large volumes of data, the key must be changed from time to time. See the [[cryptography#Keying | cryptography]] article for discussion.


=== Iterated block ciphers ===
It is hard to design any system that must withstand adversaries; see [[Cryptography#Cryptography_is_difficult|cryptography is difficult]]. In particular, block ciphers must withstand [[cryptanalysis]]; it is impossible to design a good block cipher, or to evaluate the security of one, without a thorough understanding of the available attack methods. Also, [[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 either ignored or mocked by most experts.


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 using the round key for the current round.
A block cipher defines how a single block is encrypted; a [[block cipher modes of operation| mode of operation]] 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. A block cipher can be used to build another cryptographic function such as a [[random number generator]], a [[stream cipher]], or a [[cryptographic hash]]. These are primarily a matter of choosing the correct mode, but there are more general design issues as well; see the linked articles for details.


Some ciphers have an additional step called  '''whitening'''; additional material derived from the key is mixed into the plaintext before the first round, or into the ciphertext after the last, or both. [[#Variations on DES | DES-X]] is an example.
Block ciphers are often used as components in [[hybrid cryptosystem]]s; these combine [[public key]] (asymmetric) cryptography with [[symmetric key cryptography | secret key]] (symmetric) techniques such as block ciphers or [[stream cipher]]s. Typically, the symmetric cipher is the workhorse that encrypts large amounts of data; the public key mechanism manages keys for the symmetric cipher and provides [[Information_security#Source_authentication|authentication]]. Generally other components such as [[cryptographic hash]]es and a cryptographically strong [[random number generator]] are required as well. Such a 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 [[hybrid cryptosystem]] for how the components fit together, and [[information security]] for broader issues.


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 | GOST]] uses 32 rounds. A more complex round function might allow fewer rounds; for example, [[#IDEA | 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.
That said, we turn to the block ciphers themselves.


In choosing the number of rounds, a safety margin is often applied. If the cipher appears to be secure after n rounds, the designer may specify m rounds for actual use with m considerably greater than n.
== Size parameters ==
   
One could say there are only three things to worry about in designing a block cipher:
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. In effect, this is one extreme of the trade-off described in the previous paragraph; if the round function is itself cryptographically secure, then only one round is needed.
* make the '''block size large enough''' that an enemy cannot create a [[code book attack | 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


In [[cryptanalysis]] it is common to attack '''reduced round''' versions of a cipher. For example, instead of full 16-round DES, the analyst might start by trying to break a two-round or four-round version. Such attacks are easier and success there 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. In the best possible case for the cryptanalyst, a break of the two-round system might lead to an attack on a four-round system which in turn might break the eight-round version and finally all 16 rounds.
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 | Principles and techniques]] covers ideas and methods for that.


=== Avalanche ===
Later on, we describe two generations of actual ciphers. The [[#DES and alternatives | 20th century ciphers]] use 64-bit blocks and key sizes from 56 bits up. The [[#The AES generation | 21st century ciphers]] use 128-bit blocks and 128-bit or larger keys.


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. Ideally, x would be 1; certainly it 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.
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.


This was named the avalanche effect in a paper <ref>{{ cite paper | author = Horst Feistel | title = Cryptography and Computer Privacy | journal = Scientific American | date = 1973 | url = http://www3.edgenet.net/dcowley/docs.html }}</ref> 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.
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 ciphers, 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. Striking some sort of balance with a few strong ciphers is probably the best policy.


The '''strict avalanche criterion''' <ref name=strictav> {{cite paper | author = A. F. Webster and [[Stafford E. Tavares]] | title = On the design of S-boxes | journal = Advances in Cryptology - Crypto '85 (Lecture Notes in Computer Science) | date = 1985 }} </ref> is a strong version of the requirement for good avalanche properties. Complementing any single bit of input should give a 50% chance of a change in any given bit of output.
=== 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 attack]]s.


=== Feistel structure ===
DES and the [[#DES and alternatives | generation of ciphers]] that followed it all used a 64-bit block size. To weaken such a cipher significantly the attacker must build up a code book with 2<sup>32</sup> 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.


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<sub>n</sub>, even numbered rounds are then:
However, with [[Moore's Law]] making larger code books more practical, [[NIST]] chose to play it safe in their [[#The AES generation|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 (cipher)|Camellia]], [[SEED (cipher)|SEED]] and [[ARIA (cipher)|ARIA]] also use 128 bits.


left<sub>n</sub> = left<sub>n-1</sub> ^ F(right<sub>n-1</sub>, k<sub>n</sub>)
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|large-block ciphers]] for details.
right<sub>n</sub> = right<sub>n-1</sub>


and odd-numbered rounds are
=== Key size ===
In theory, any cipher except a [[one-time pad]] 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. If the key uses <math>n</math> bits, there are 2<sup>n</sup> possible keys and on average the attacker must test half of them, so the average cost of the attack is 2<sup>n-1</sup> encryptions.


right<sub>n</sub> = right<sub>n-1</sub> ^ F(left<sub>n-1</sub>, k<sub>n</sub>)
'''Current block ciphers all use at least 128-bit keys''', which makes brute force attacks utterly impractical. Suppose an attacker has a billion processors in a monster parallel machine (several orders of magnitude more than any current machine) and each processor can test a billion keys a second (also a generous estimate; if the clock is ''k'' GHz, the processor must do an encryption in ''k'' cycles to achieve this). This amazingly powerful attacker can test about 2<sup>60</sup> keys a second, so he needs 2<sup>67</sup> seconds against a 128-bit key. There are about 2<sup>25</sup> seconds in a year, so that is about 2<sup>42</sup> years. This is over 4,000,000,000,000 (four trillion) years so the cipher is clearly secure against brute force.
left<sub>n</sub> = left<sub>n-1</sub>


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. For example, the decryption step matching the first example above is:
Many ciphers support larger keys as well; the reasons are discussed in the [[Brute_force#Choosing_key_sizes|brute force attack]] article.


left<sub>n-1</sub> = left<sub>n</sub> ^ F(right<sub>n</sub>, k<sub>n</sub>)
== Principles and techniques ==
right<sub>n-1</sub> = right<sub>n</sub>
This section introduces the main principles of block cipher design, defines standard terms, and describes common techniques.


In some ciphers, all operations must be reversible so that decryption can work. In a Feistel cipher, 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.
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 cipher]]s and [[cryptographic hash]] algorithms.


A single round in a Feistel cipher has less than ideal avalanche properties. In our first example above, half the output bits (on the right) are unchanged and the left<sub>n-1</sub> input bits each affect only one output; this falls well short of the ideal in which every input bit affects every output bit. However, the other half is changed in the next round and the F function can be designed so that small changes in its inputs (half-block or round key) produce large output changes. Within a few rounds, a Feistel cipher can have excellent overall avalanche properties.
=== 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, a number of '''round keys''' or '''subkeys''' are computed from the '''primary key'''; the method used is called the cipher's '''key schedule'''. 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.


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.
Three common ways to design iterated block ciphers &mdash; [[#SP networks|SP networks]], [[#Feistel structures|Feistel structures]] and the [[#Lai-Massey scheme|Lai-Massey construction]] &mdash; and two important ways to look at the complexity requirements  &mdash; [[#Avalanche|avalanche]] and [[#Nonlinearity|nonlinearity]] &mdash; are covered in following sections.


=== Non-linearity ===
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.


To be secure, every block cipher must contain some non-linear operations. If all operations in a cipher were linear &mdash; in any algebraic system, with the attacker making the choice of system and allowed to try as many as he likes &mdash; 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.
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 cipher| GOST]] and [[Tiny Encryption Algorithm| TEA]] both use 32 rounds. A more complex round function might allow fewer rounds; for example, [[International Data Encryption Algorithm| 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.


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 a known plaintext/ciphertext pair and only the key bits remain as variables. 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 with the same 128 key bits as 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.
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.


The attacker can also try [[linear cryptanalysis]]; if he can find a good linear ''approximation'' for the round function and has enough known plaintext/ciphertext pairs, then this will break the 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.


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.
'''Whitening''' involves mixing additional material derived from the key into the plaintext before the first round, or into the ciphertext after the last round, or both. The technique was introduced by [[Ron Rivest]] in [[Data Encryption Standard#Variations on DES|DES-X]] and has since been used in other ciphers such as [[Rivest ciphers#RC6|RC6]], [[Blowfish (cipher)| 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 [[Data Encryption Standard#Variations on DES | DES-X]].


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.
A recent development is the '''tweakable''' block cipher
<ref>{{citation
| title=Tweakable Block Ciphers
| author=M. Liskov, R. Rivest, and D. Wagner
| journal=LNCS, Crypto 2002
| publisher=Springer Verlag
| date=2002
| url=http://www.eecs.berkeley.edu/~daw/papers/tweak-crypto02.pdf
}}</ref>.
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.


Other operations can also be used, albeit at higher costs. [[#IDEA | IDEA]] uses multiplication modulo 2<sup>16</sup>+1 and [[#AES | AES]] does matrix multiplications in a field.  
If changing tweaks is sufficiently lightweight, compared to the key scheduling operation which is often fairly expensive, then some new [[Block_cipher_modes_of_operation#Tweakable_modes|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.


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]].
The [[Hasty Pudding (cipher)|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".


A general operation for introducing non-linearity is the substitution box or s-box; see following section.
=== Avalanche ===
The designer wants changes to quickly propagate through the cipher. This was named the '''avalanche effect''' in a paper <ref>{{ citation | author = Horst Feistel | title = Cryptography and Computer Privacy | journal = Scientific American | date = 1973 | url = http://www3.edgenet.net/dcowley/docs.html }}</ref> by [[Horst Feistel]]. The idea is that changes should build up like an avalanche, so that a tiny initial change (consider a snowball tossed onto a mountain) 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.


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


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.
The '''strict avalanche criterion''' <ref name=SAC> {{citation | author = A. F. Webster and [[Stafford E. Tavares]] | title = On the design of S-boxes | journal = Advances in Cryptology - Crypto '85 (Lecture Notes in Computer Science) | date = 1985 }} </ref> 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.


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 this online [http://www.ciphersbyritter.com/RES/SBOXDESN.HTM  literature survey] and references below.
=== Cipher structures ===
In [[Claude Shannon]]'s  
<ref>{{citation
| author = C. E. Shannon
| title = Communication Theory of Secrecy Systems
| journal = Bell Systems Technical Journal
| volume = 28
| date = 1949
| pages = pp.656-715
| url = http://www.prism.net/user/dcowley/docs.html }}</ref>
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 [[Cipher#Classical_cipher_components | classical ciphers]] from before the advent of computers. All modern block ciphers are product ciphers.


S-boxes are described as n*m or n by m with n representing the number of input bits and m the number of output bits. For example, DES uses 6 by 4 s-boxes. The storage requirement for an n*m s-box is 2<sup>n</sup>*m bits, so large values of n are problematic. Values up to eight are common; going much beyond that would be expensive.
Two structures are very commonly used in building block ciphers &mdash; SP networks and the Feistel structure. The Lai-Massey construction is a third alternative, less common than the other two. In Shannon's terms, all of these are product ciphers. Any of these structures is a known quantity for a cipher designer, part of the toolkit. He or she gets big chunks of a design &mdash; an overall cipher structure with a well-defined hole for the  round function to fit into &mdash; from the structure, This leaves him or her free to concentrate on the hard part, designing the actual round function. None of these structures gives ideal avalanche in a single round but, with any reasonable round function, all give excellent avalanche after a few rounds.


A common use of s-boxes in block cipher design is in the F function of a Feistel cipher. The F function, and therefore the cipher as a whole, will be highly non-linear if the s-boxes are. Since the F function need not be reversible, there is no need to construct an inverse s-box for decryption.
Not all block ciphers use one of these structures, but most do. This section describes these common structures.


Early block ciphers of this type, [[#DES | DES]] and [[#GOST | GOST]], 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 in the next round, so that good avalanche is achieved after a few rounds.
==== 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.


Later ciphers, such as [[#Blowfish | Blowfish]] and [[#CAST | CAST-128]], use four 8*32 s-boxes. The 32-bit input is XORed with the round key then split into four bytes and each byte is passed through a different s-box, giving four 32-bit results. Those results are then combined (non-linearly) to get the 32-bit F function output. Such an F function has ideal avalanche properties &mdash; all output bits depend on all input bits and all key bits. No output transformation is required.
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 [[#S-boxes | section]] below.


==== S-boxes as a model of other things ====
The '''P-layer''' permutes the resulting bits, providing diffusion or in Feistel's terms helping to ensure avalanche.
S-boxes may be used in analysis even when they are not actually used in the cipher. 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 multiplication in [[#IDEA | IDEA]] has two inputs and one output, all 16-bit, so it can be modeled as a 32*16 s-box. In an academic paper, one might look at this as an s-box in order to apply standard tools for measuring non-linearity, or to compare it with other ciphers that do use s-boxes. A well-funded cryptanalyst might actually build the s-box (8 gigabytes of memory) either as a step in analysis or to speed up an attack.
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.


In theory, larger components, or even the whole cipher, can be modeled in the same way. For the F function in a Feistel cipher, the inputs are only half a block and a round key; this gives an 80*32 s-box or 64*32 s-box, much too big for an attacker to actually build but perhaps usable in theoretical work. Try to model anything bigger &mdash; a whole cipher, a round of a non-Feistel cipher, or multiple rounds of a Feistel cipher &mdash; and s-box dimensions become astronomical. Consider [[#AES | AES]] with 128-bit blocks and (the minimum) 128-bit key size; this can be modeled as a 256*128 s-box, an array with 2<sup>256</sup> entries, but the  model is unlikely to be useful.
==== 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|DES]]. Such ciphers are known as '''Feistel ciphers''' or '''Feistel networks'''. In Shannon's terms, they are another class of product cipher.


== Block cipher modes ==
Feistel ciphers are sometimes referred to as '''Luby-Rackoff''' ciphers after the authors of a theoretical paper
<ref>{{citation
| author = M. Luby and C. Rackoff
| title = How to Construct Pseudorandom Permutations and Pseudorandom Functions
| journal = SIAM J. Comput
| date - 1988
}}</ref>
analyzing some of their properties. Later work
<ref>{{citation
| author = Jacques Patarin
| title = Luby-Rackoff: 7 Rounds Are Enough for Security
| journal = Lecture Notes in Computer Science
| volume = 2729
| date = Oct 2003
| pages = 513 - 529
}}</ref>
based on that shows that a Feistel cipher with seven rounds can be secure.


Various '''modes of operation''' for block cipher usage were originally defined for DES in a US [[Federal Information Processing Standard]] (FIPS) <ref>{{cite paper | title = FIPS 81: DES Modes of Operation | date = December 1980 | url = http://www.itl.nist.gov/fipspubs/fip81.htm}}</ref>. The most recent [[NIST]] recommendations are in "Recommendation for Block Cipher Modes of Operation" <ref>{{cite paper | title = Recommendation for Block Cipher Modes of Operation | publisher = National Institute for Standards & Technology | date = 2001 | url = http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf }}</ref>
In a Feistel 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 XOR-ed into the other half-block of text. The rounds alternate direction &mdash; 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.  


These modes can be applied to any block cipher.
Showing the half-blocks as left and right, bitwise XOR as <math>\oplus</math> (each bit of the output word is the XOR of the corresponding bits of the two input words) and round key for round <math>n</math> as k<sub>n</sub>, even numbered rounds are then:


=== Electronic Code Book, ECB ===
: <math> \text{left}_n = \text{left}_{n-1} \oplus F( \text{right}_{n-1}, k_n ) </math>
: <math> \text{right}_n = \text{right}_{n-1} </math>


In '''Electronic Code Book''' mode, the cipher is just applied to each block of plaintext independently.
and odd-numbered rounds are


The disadvantage is that the same plaintext block always encrypts to the same ciphertext; this gives an enemy some information. ECB is therefore '''generally not used'''.
: <math> \text{right}_n = \text{right}_{n-1} \oplus F( \text{left}_{n-1}, k_n ) </math>
: <math> \text{left}_n = \text{left}_{n-1} </math>


=== Cipher Block Chaining, CBC ===
Since XOR is its own inverse (a<math>\oplus</math>b<math>\oplus</math>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:


In '''cipher block chaining''' mode, the ciphertext output from the previous block is XORed into the plaintext before encryption. Encryption of block n is then:
: <math> \text{left}_{n-1} = \text{left}_n \oplus F( \text{right}_n, k_n ) </math>
: <math> \text{right}_{n-1} = \text{right}_n </math>


  c<sub>n</sub> = encrypt( p<sub>n</sub> XOR c<sub>n-1</sub>)
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 changes all of it in a single round.


For this to work for n=1, an '''initialisation vector''' (IV) must be provided to act as c<sub>0</sub>. This need not be secret, but it should be different for each message. If the same IV is repeatedly used, then if two or more messages start with the same text, they will encrypt identically for the first block or the first few blocks. This is an unnecessary weakness; using unique IVs is therefore standard practice.
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. It is possible to design a Feistel cipher so that the F-function itself has ideal avalanche properties &mdash; every output bit depends nonlinearly on every input bit and every key bit &mdash; details are in a [[#Large_S-boxes|later section]].


=== Cipher feedback, CFB ===
There is a variant called an unbalanced Feistel cipher in which the block is split into two unequal-sized pieces rather than two equal halves. [[Skipjack]] was a well-known example. There are also variations which treat the text as four blocks rather than just two; [[MARS (cipher)|MARS]] and [[CAST (cipher)#CAST-256|CAST-256]] are examples.


=== Output Feedback, OFB ===
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 nonlinear. All other operations in a Feistel cipher are linear and a cipher without enough nonlinearity is weak; see below.


=== Counter, CTR ===
==== Lai-Massey scheme ====
This structure was introduced in a thesis by [[Xuejia Lai]], supervised by [[James Massey]], in a cipher which later became the [[International Data Encryption Algorithm]], IDEA.<ref name=idea>{{citation
| author = X. Lai
| title = On the Design and Security of Block Ciphers
| journal = ETH Series in Information Processing, v. 1
| publisher = Hartung-Gorre Verlag
| date = 1992
}}</ref> It has since been used in other ciphers such as [[FOX (cipher)|FOX]], later renamed [[IDEA NXT]]. Perhaps the best-known analysis is by [[Serge Vaudenay]], one of the designers of FOX. <ref>{{citation
| author = S. Vaudenay
| title = On the Lai-Massey Scheme
| conference = Asiacrypt 99
| publisher = Springer-Verlag, LCNS
| date = 1999
}}</ref>


One paper <ref>{{citation
| title = Lai-Massey Scheme and Quasi-Feistel Networks
| author = Aaram Yun, Je Hong Park and Jooyoung Lee
| url = http://eprint.iacr.org/2007/347
| date = 2007
}}</ref>
proposes a general class of "quasi-Feistel networks", with the Lai-Massey scheme as one instance, and shows that several of the well-known results on Feistel networks (such as the Luby-Rackoff and Patarin papers referenced above) can be generalised to the whole class. Another <ref>{{citation
| title = Pseudorandomness Analysis of the Lai-Massey Scheme
| author = Yiyuan Luo, [[Xuejia Lai]], Zheng Gong and Zhongming Wu
| url = http://eprint.iacr.org/2009/266
| date = 2009
}}</ref> gives some specific results for the Lai-Massey scheme.


Counter mode is used in the Yarrow [http://www.schneier.com/yarrow.html] random number generator.
=== Nonlinearity ===
To be secure, '''every cipher must contain nonlinear operations'''. If all operations in a cipher were linear then the cipher could be reduced to a system of linear equations and be broken by an [[algebraic attack]]. The attacker can choose which algebraic system to use; for example, against one cipher he might treat the text as a vector of bits and use Boolean algebra while for another he might choose to treat it as a vector of bytes and use arithmetic modulo 2<sup>8</sup>. 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]].


== Well-known block ciphers ==
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 nonlinearity 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 ''nonlinear'' systems of equations is far harder, so the cipher designer strives to introduce nonlinearity to the system, preferably to have at least some components that are ''not even close to linear''. Combined with good avalanche properties and enough rounds, this makes both direct algebraic analysis and linear cryptanalysis prohibitively difficult.


=== DES ===
There are several ways to add nonlinearity; some ciphers rely on only one while others use several.


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; see next section.
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 nonlinear whichever way he tries it.


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.
For example, in the [[Blowfish (cipher)| Blowfish]] F-function, it is necessary to combine four 32-bit words into one. This is not done with just addition, x = a+b+c+d or just Boolean operations x = a<math>\oplus</math>b<math>\oplus</math>c<math>\oplus</math>d but instead with a mixture, x = ((a+b)<math>\oplus</math>c)+d. On most computers this costs no more, but it makes the analyst's job harder.


DES uses eight S-boxes, each 6 bits in and 4 out. The F function works as follows:
Other operations can also be used, albeit at higher costs. [[International Data Encryption Algorithm | IDEA]] uses multiplication modulo 2<sup>16</sup>+1 and [[#AES | AES]] does matrix multiplications with polynomials in a [[Galois field]].  
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.


Every new [[cryptanalysis | cryptanalytic]] technique invented since DES became a standard has been tested against DES. None of them have broken it completely, but two &mdash; [[differential cryptanalysis]] and [[linear cryptanalysis]] &mdash; give attacks theoretically significantly better than brute force. This does not appear to have much practical importance since both require enormous numbers of known plaintexts and since DES has been repeatedly broken by brute force anyway. All the older publicly known cryptanalytic techniques have also been tried, or at least considered, for use against DES; none of them work.
'''Rotations''', also called '''circular shifts''', on words or registers are nonlinear in normal algebra, though they are easily described in Boolean algebra. [[GOST cipher| GOST]] uses rotations by a constant amount, [[CAST (cipher)#CAST-128 | CAST-128]] and [[CAST (cipher)#CAST-256 | CAST-256]] use a key-dependent rotation in the F-function, and [[Rivest ciphers#RC5 | RC5]], [[Rivest ciphers#RC6 | RC6]] and [[#MARS | MARS]] all use data-dependent rotations.


The generation of block ciphers which followed DES in the 80s and 90s &mdash; such as GOST, Blowfish, CAST-128 and IDEA (see below for all) &mdash; nearly all 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 some of the design principles came from analysis of DES.
A general operation for introducing nonlinearity is the substitution box or '''S-box'''; see following section.


==== DES is not secure ====
Nonlinearity is also an important consideration in the design of [[stream cipher]]s 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.


DES can no longer be considered secure because its 56-bit key is simply too short. It is vulnerable to a [[brute force]] search of the whole key space, either by large collections of general-purpose machines or even more quickly by specialized hardware. Of course this also applies to any other cipher with only a 56-bit key.
=== 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.
In 1998, the [http://www.eff.org Electronic Frontier Foundation] built a DES-cracking machine. It can find a DES key in an average of a few days' search. The details of all this, including complete code listings and complete plans for the machine, have been published in "Cracking DES" <ref> name-crack {{cite book
| author = Electronic Frontier Foundation
| title = Cracking DES: Secrets of Encryption Research, Wiretap Politics, and Chip Design
| publisher = Electronic Frontier Foundation
| url = http://cryptome.org/cracking-des/cracking-des.htm
| isbn = ISBN: 1-56592-520-3 
| date = 1998 }}</ref>


That machine cost just over $200,000 to design and build in 1998. [[Moore's Law]] is that machines get faster (or cheaper, for the same speed) by roughly a factor of two every 18 months. At that rate, the cost in 2007, 9 years later, should be down to $200,000/2<sup>9/1.5</sup> = $3125, and a quarter of that by 2010. Such estimates are far from exact; we cannot say with any precision what such a cracker would cost today. However, we can say with certainty that DES should no longer be used to protect valuable data.
S-boxes are described as <math>m</math> by <math>n</math>, with <math>m</math> representing the number of input bits and <math>n</math> the number of output bits. For example, [[#DES|DES]] uses 6 by 4 S-boxes. The storage requirement for an <math>m</math> by <math>n</math> S-box is 2<sup>m</sup>''n'' bits, so large values of <math>m</math> (many input bits) are problematic. Values up to eight are common and [[MARS (cipher)| MARS]] has a 9 by 32 S-box; going much beyond that would be expensive. Large values of <math>n</math> (many output bits) are not a problem; 32 is common and at least one system, the Tiger hash algorithm
<ref>{{citation
| title=Tiger: a fast new hash function
| author=Ross Anderson & Eli Biham
| journal=Fast Software Encryption, Third International Workshop Proceedings
| date= 1996
| url=http://www.cs.technion.ac.il/~biham/Reports/Tiger/}}</ref>,
uses 64.


Before the definitive EFF effort, DES had been cracked several times by people using many machines. See this [http://www.distributed.net/pressroom/DESII-1-PR.html press release] for example. A major corporation, university, or government department could break DES by using spare cycles on their existing collection of computers, by dedicating a group of otherwise surplus machines to the problem, or by combining the two approaches. It might take them weeks or months, rather than the days required for the EFF machine, but they could do it.
S-boxes are often used in the S-layer of an [[#Substitution-permutation networks | 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 <math>n</math> by <math>n</math> S-boxes can be used. For example, [[#AES|AES]] is an SP network with a single 8 by 8 S-box and [[#Serpent|Serpent]] is one with eight 4 by 4 S-boxes. Another common application is in the F-function of a [[#Feistel structure | 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.


==== Variations on DES ====
With either an SP network or a Feistel construction, '''nonlinear S-boxes and enough rounds give a highly nonlinear cipher'''.


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.
==== Large S-boxes ====
The first generation of Feistel ciphers used relatively small S-boxes, 6 by 4 for [[Data Encryption Standard|DES]] and 4 by 4 for [[GOST cipher|GOST]]. In these ciphers the F-function is essentially one round of an [[#Substitution-permutation networks | SP Network]]. The eight S-boxes give 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 (a bit permutation in DES, a rotation in GOST) 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.


[[Ron Rivest]] proposed '''DES-X''' or DESX [http://www.rsa.com/rsalabs/node.asp?id=2232], 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 <ref>{{cite paper
Later Feistel ciphers use larger S-boxes; [[CAST (cipher)| CAST-128 or CAST-256]] and [[Blowfish (cipher) | Blowfish]] all use four 8 by 32 S-boxes. They do not use S-box bits directly as F-function output. Instead, they take a 32-bit word from each  S-box, then combine them to form a 32-bit output. This gives an F-function with '''ideal avalanche properties'''; every bit of input and every bit of round key affects every bit of outputNo output transformation is required in such an F-function, and Blowfish has none. However, one may be used anyway; the CAST ciphers add a key-dependent rotation.
  | author = Joe Kilian and Phillip Rogaway
| title = How to protect DES against exhaustive key search
| journal = Advances in Cryptology - Crypto '96
| publisher = Springer-Verlag
| date = 1996
| pages = 252–267
| url = http://wwwcsif.cs.ucdavis.edu/~rogaway/papers/desx.ps }}</ref> of resistance to [[linear cryptanalysis]] and [[differential cryptanalysis]] shows that it is better than DES against these attacks, but not hugely so.


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 <ref name="gdes">{{ cite paper
With the Feistel structure and such an F-function, complete avalanche &mdash; all 64 output bits depend on all 64 input bits &mdash; is achieved in three rounds, and the cipher meets the '''strict avalanche criterion''' <ref name="SAC" />; complementing any input bit has a 50% chance of changing any given output bit.
| author = Andreas Pfitzmann and Ralf Amann
| title = More Efficient Software Implementations of Generalized DES
| journal = Computers & Security,
| year = 1990
| volume = 12
| pages = 477-500 }}</ref>. However, Schneier at al. [http://www.schneier.com/paper-key-schedule.pdf] demonstrate that the technique has weaknesses.


=== Triple DES ===
These ciphers 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 by 32 S-box takes one K byte of storage; several can be used on a modern machine without difficulty. They need only four S-box lookups, rather than the eight in DES or GOST, so the F-function and therefore the whole cipher can be reasonably efficient.
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, one might expect an attacker to have to do 2<sup>112</sup> work to break it. In fact, only 2<sup>57</sup> work is required with a  [[meet-in-the-middle attack]], though a large amount of memory is also required. That is, double DES is only four times stronger that DES, which can be broken by [[brute force]] with 2<sup>55</sup> encryptions.
==== S-box design ====
There is an extensive literature on the design of good S-boxes, much of it emphasizing achieving high nonlinearity though other criteria are also used. See [[Block_cipher/External_Links#Literature_surveys| external links]].


'''Triple DES''', sometimes written 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<sup>112</sup>. That provides adequate protection for many applications, and no better attack is known.
The CAST S-boxes use [[bent function]]s (the most highly nonlinear Boolean functions) as their columns. That is, the mapping from all the input bits to any single output bit is a bent function. A paper on generating the S-boxes is Mister & Adams "Practical S-box Design"
<ref name="sbox">{{citation
| author = S. Mister, C. Adams
| title = Practical S-Box Design
| journal = Selected Areas in Cryptography (SAC '96)
| date = August, 1996
| url=http://adonis.ee.queensu.ca:8000/sac/sac96/papers/paper7.ps
| pages = 61-76 }}</ref>.
Bent functions are combined to get additional desirable traits &mdash; a balanced S-box (equal probability of 0 and 1 output), minimum correlation among output bits, and high overall S-box nonlinearity.


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 | AES]] will generally be both faster and more secure; Triple DES provides only 2<sup>112</sup> strength against the best known attack, meet-in-the-middle. AES is resistant to that attack and gives 2<sup>128</sup> or more against the best known attack on it, brute force.
[[Blowfish (cipher) | Blowfish]] uses a different approach, generating random S-boxes as part of the key scheduling operation at cipher setup time. Such S-boxes are not as nonlinear as the carefully constructed CAST ones, but they are nonlinear enough and, unlike the CAST S-boxes, they are unknown to an attacker.


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.
In '''perfectly nonlinear S-boxes'''
<ref>{{citation
| author = [[Kaisa Nyberg]]
| title = Perfect nonlinear S-boxes
| journal = Eurocrypt'91, LNCS 547
| publisher = Springer-Verlag
| date = 1991 }}</ref>,
not only are all columns [[bent function]]s (the most nonlinear possible Boolean functions), but all linear combinations of columns are bent functions as well. This is possible only if <math>m \ge 2n</math>, there are at least twice as many input bits as output bits. Such S-boxes are therefore not much used.


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.
==== S-boxes in analysis ====
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 [[International Data Encryption Algorithm | IDEA]] cipher uses a multiplication operation with two 16-bit inputs and one 16-bit output; it can be modeled as a 32 by 16 S-box. In an academic paper, one might use such a model in order to apply standard tools for measuring S-box nonlinearity. 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.


The three-key variant is widely used; for example RFC 2451 specifies it for use in [[IPsec]].
=== Resisting linear & differential attacks ===
Two very powerful [[cryptanalysis | cryptanalytic]] methods of attacking block ciphers are [[linear cryptanalysis]] and [[differential cryptanalysis]]. The former works by finding linear approximations for the nonlinear components of a cipher, then combining them using the [[piling-up lemma]] to attack the whole cipher. The latter looks at how small changes in the input affect the output, and how such changes propagate through multiple rounds. These are the only known attacks that break [[Data Encryption Standard|DES]] with less effort than brute force, and they are completely general attacks that apply to any block cipher..


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. This is not significant in most applications. 3DES with three keys has only 2<sup>112</sup> strength against a meet-in-the-middle attack, so it is possible that the two key version, with 2<sup>112</sup> against either brute force or meet-in-the-middle, is just as strong.
Both these attacks, 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.


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 for doing this would be if one of the communicating systems only supported DES while the other had only triple DES. By using single-key triple DES on one end, you could get the two to encrypt their communications, albeit not securely.
Techniques introduced for [[CAST (cipher)|CAST]] go 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 round function (for CAST, from [[bent function]]s in the S-boxes)
# derive a limit <math>m</math>, the maximum possible quality of any linear approximation to a single round
# consider the number of rounds, <math>r</math>, as a variable
# derive an expression for <math>e</math>, the effort required to break the cipher by LC, in terms of <math>r</math> and <math>m</math>
# find the minimum <math>r</math> such that <math>e</math> exceeds the effort required for brute force, making LC ''impractical''
# derive an expression for <math>c</math>, the number of chosen plaintexts required for LC, also in terms of <math>r</math> and <math>m</math> (LC with only known plaintext requires more texts, so it can be ignored)
# find the minimum <math>r</math> such that <math>c</math> exceeds the number of ''possible'' plaintexts, 2<sup>blocksize</sup>, making LC ''impossible''
A similar approach applied to differentials gives values for <math>r</math> 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. There are other methods of constructing ciphers provably immune to these attacks. [[Serge Vaudenay]]'s work on [[decorrelation theory]] gives one <ref>{{citation
| author = Serge Vaudenay
| title=  Decorrelation: A Theory for Block Cipher Security
| journal = Journal of Cryptology
| publisher = Springer
|date= 2003
}}</ref>
and Knudsen-Nyberg ciphers are another. <ref>{{citation
| author = Kaissa Nyberg and Lars Knudsen
| title = Provable security against a differential attack
| journal =Journal of Cryptology
| date = 1995
}}</ref>


=== GOST ===
This type of analysis is now a standard part of the cryptographer's toolkit. Many of the [[#The_AES_generation|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.


The GOST cipher, and the related GOST hash algorithm, were standards in the [[Soviet Union]].
== DES and alternatives ==
The [[Data Encryption Standard]], DES, is among 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 attack]]s if the opponents have recent technology.


The GOST cipher <ref> schneier </ref> 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.
The DES standard marked the beginning of an era in [[cryptography]]. Of course, much work continued to be done in secret by military and intelligence organisations of various nations, but from the time of DES cryptography also developed as an open academic discipline complete with journals, conferences, courses and textbooks. In particular, there was a lot of 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.


GOST also uses a 256-bit key which makes it, unlike DES, thoroughly resistant to [[brute force]] attacks.
Every new [[cryptanalysis|cryptanalytic]] technique invented since DES became a standard has been tested against DES. None of them have broken it completely, but two &mdash; [[differential cryptanalysis]] and [[linear cryptanalysis]] &mdash; 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, all encrypted with the same key, so reasonably frequent key changes provide an effective defense. All the older publicly known cryptanalytic techniques have also been tried, or at least considered, for use against DES; none of them work.


=== CAST ===
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 most used 128-bit or longer keys for better resistance to brute force attacks.


==== The original algorithm ====
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.
* [[Rivest ciphers#RC2|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.
* [[Rivest ciphers#RC5|RC5]], a Feistel cipher from [[RSA security]]. This was fairly widely deployed, often replacing RC2 in applications.
* [[CAST cipher#CAST-128|CAST-128]], a widely used 16-round Feistel cipher, with 8 by 32 S-boxes.
* [[Blowfish (cipher)| 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.
* [[SAFER (cipher)|SAFER]] and [[LOKI (cipher)|LOKI]], two families of ciphers which each included an original version against which [[Lars Knudsen]] found an attack and a revised version to block that attack. Each had a descendant which was an [[#The_AES_generation|AES candidate]].
* [[Triple DES]], applying DES three times with different keys


==== CAST 128 ====
Many of the techniques used in these ciphers came from DES and many of the design principles came from analysis of DES. However, there were also new design ideas. The [[CAST cipher|CAST]] ciphers were the first to use [[#large S-boxes|large S-boxes]] which allow the F-function of a [[Feistel cipher]] to have ideal [[#Avalanche|avalanche]] properties, and to use [[bent function]]s in the S-box columns. [[Blowfish (cipher)| Blowfish]] introduced key-dependent S-boxes. Several introduced new ways to achieve nonlinearity:  data-dependent rotations in [[Rivest ciphers#RC5|RC5]], key-dependent rotations in [[CAST cipher#CAST-128|CAST-128]], a clever variant on multiplication in [[International Data Encryption Algorithm|IDEA]], and the [[pseudo-Hadamard transform]] in [[SAFER (cipher)|SAFER]].


RFC 2144
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.


==== CAST 256 ====
== The AES generation ==
By the 90s, the [[Data Encryption Standard]] was clearly obsolete; its small key size made it more and more vulnerable to [[brute force attack]]s as computers became faster. The US [[National Institute of Standards and Technology]] (NIST) therefore began work on an [[Advanced Encryption Standard]], '''AES''', a block cipher to replace DES in government applications and in regulated industries.


=== Blowfish ===
To do this, they ran a very open international AES competition, starting in 1998. Their requirements specified a block cipher with 128-bit [[#Block_size | block size]] and support for 128, 192 or 256-bit [[#Key size | 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.


=== IDEA ===
Fifteen submissions meeting basic criteria were received. All were [[#Iterated block ciphers|iterated block ciphers]]; in Shannon's terms all were [[#Cipher_structures|product ciphers]]. Most used an [[#SP network | SP network]] or [[#Feistel structure|Feistel structure]], or variations of those. Several had [[#Resisting_linear_.26_differential_attacks|proofs of resistance]] to various attacks. The [[AES competition]] article covers all candidates and many have their own articles as well. Here we give only a summary.


IDEA <ref name=idea>{{cite paper
After much analysis and testing, and two conferences, the field was narrowed to five finalists:
| author = X. Lai
* [[Twofish]], a cipher with key-dependent S-boxes, from a team at [[Bruce Schneier]]'s company Counterpane
| title = On the Design and Security of Block Ciphers
* [[MARS (cipher)| MARS]], a variant of Feistel cipher using data-dependent rotations, from [[IBM]]
| journal = ETH Series in Information Processing, v. 1
* [[Serpent (cipher)| Serpent]], an SP network, from an international group of well-known players
| publisher = Hartung-Gorre Verlag
* [[Rivest ciphers#RC6 | RC6]], a cipher using data-dependent rotations, from a team led by [[Ron Rivest]]
| date = 1992
* [[Advanced Encryption Standard | Rijndael]]. an SP network, from two Belgian designers
}}</ref> 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<sup>16</sup>. The third is basically multiplication, modulo 2<sup>16</sup>+1, but with some additional code so the "x*0 yields zero for all x" case does not weaken the cipher.
After another year of analysis and testing, they chose a winner. In October 2002, Rijndael was chosen to become the [[Advanced Encryption Standard]] or AES. See [[Block_cipher/External_Links#AES_links | external links]] for the official standard.


To see how this works, consider this multiplication table modulo 5:
An entire [[#DES_and_alternatives|generation]] of block ciphers used the 64-bit block size of DES, but since AES many new designs use a 128-bit block size.


    0  1  2  3  4
As discussed under [[#Size parameters|size parameters]], if two or more ciphers have the same block and key sizes, then they are effectively interchangeable; replacing one cipher with another requires no other changes in an application. When asked to implement AES, the implementer might include the other finalists &mdash; [[Twofish]], [[Serpent (cipher)| Serpent]]. [[Rivest ciphers#RC5|RC6]] and [[MARS (cipher)| MARS]] &mdash; as well. This provides useful insurance against the (presumably unlikely) risk of someone finding a good attack on AES. Little extra effort is required since open source implementations of all these ciphers are readily available, see [[Block_cipher/External_Links#AES_links|external links]]. All except RC6 have completely open licenses.


0  0  0  0  0  0
There are also many other ciphers that might be used. There were ten AES candidates that did not make it into the finals:
1  0  1  2  3  4
* [[CAST (cipher)#CAST-256|CAST-256]], based on CAST-128 and with the same theoretical advantages
2  0  2  4  1  3
* [[DFC (cipher)| DFC]], based on another theoretical analysis proving resistance to various attacks.
3  0  3  1  4  2
* [[Hasty Pudding (cipher)|Hasty Pudding]], a variable block size [[#Whitening_and_tweaking|tweakable]] cipher
4  0  4  3  2  1
* [[DEAL (cipher)|DEAL]], a Feistel cipher using DES as the round function
* [[FROG (cipher)| FROG]], an innovative cipher; interesting but weak
* [[E2 (cipher)| E2]], from Japan
* [[CRYPTON (cipher)| CRYPTON]], a Korean cipher with some design similarities to AES
* [[MAGENTA (cipher)|MAGENTA]], Deutsche Telekom's candidate, quickly broken
* '''LOKI97''', one of the [[LOKI (cipher)|LOKI]] family of ciphers, from Australia
* '''SAFER+''', one of the [[SAFER (cipher)|SAFER]] family of ciphers, from Cylink Corporation


Note that, ignoring multiplications by zero, every column and every row is a permutation of the set (1,2,3,4). This is true for any prime modulus.
Some should not be considered. Magenta and FROG have been broken, DEAL is slow, and E2 has been replaced by its descendant Camellia.


If our inputs are 2-bit numbers (0,1,2,3), we can map them to (4,1,2,3) so that all multiplications use the interesting part of the table. Results are in (1,2,3,4), which we map back to (1,2,3,0) so we get 2-bit output.
There are also some newer 128-bit ciphers that are widely used in certain countries:


C code for IDEA multiplication of 2-bit numbers (range 0-3) would be:
* [[Camellia (cipher)|Camellia]], an 18-round Feistel cipher widely used in Japan and one of the standard ciphers for the [[NESSIE]] (New European Schemes for Signatures, Integrity and Encryption) project.
* [[SEED (cipher)|SEED]], developed by the [[Korean Information Security Agency]] (KISA) and widely used in Korea.


#define NBITS 2
== Large-block ciphers ==
#define MAX (1<<NBITS)
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 [[Block cipher modes of operation|mode of operation]].
#define MOD (MAX+1)


unsigned idea_multiply( unsigned x, unsigned y)
For nearly all ciphers, the block size is a power of two. [[Joan Daemen]]'s PhD thesis, though, had two exceptions: [[3-Way]] uses 96 bits (three 32-bit words) and [[BaseKing]] 192 (three 64-bit words). Neither cipher was widely used, but they did influence later designs. Daemen was one of the designers of [[Square (cipher)|Square]] and of Rijndael which became the [[Advanced Encryption Standard]].
{
    unsigned z ;


    // make sure inputs are in range
A few ciphers supporting larger block sizes do exist; this section discusses them.
    x %= MAX ;
    y %= MAX ;


    // adjust the range
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.
    // avoid multiplying by zero
    if( x == 0 ) x = MAX ;
    if( y == 0 ) y = MAX ;


    // calculate the result
Some block ciphers, such as [[Tiny Encryption Algorithm| Block TEA]] and [[Hasty Pudding (cipher)|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 [[Block_cipher_modes_of_operation#Electronic_Code_Book.2C_ECB | 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 [[#Whitening_and_tweaking|tweakable]] cipher such as Hasty Pudding with the block number or other object identifier as the tweak. Another is to use [[Block_cipher_modes_of_operation#Cipher_Block_Chaining.2C_CBC |CBC mode]] with an initialisation vector derived from an object identifier.
    // see table above
    z = (x*y) % MOD ;


    // adjust it
[[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''
    // avoid returning MAX
<ref name="schneier">{{citation
    if( z == MAX ) z = 0 ;
| first = Bruce | last = Schneier
 
| title = Applied Cryptography
    return( z ) ;
| date = 2nd edition, 1996,
  }
| publisher = John Wiley & Sons
 
  |ISBN =0-471-11709-9}}</ref>
Change NBITS to 16 and you have real IDEA multiplication, operating on 16-bit quantities. This works correctly because MOD is then the prime 2<sup>16</sup>+1. On a 32-bit processor, you need to add a bit of extra code to avoid having MAX*MAX overflow a 32-bit register, but that is the only special case.
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 [[Hash_(cryptography)#Whirlpool|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 [[Hash_(cryptography)#The_Advanced_Hash_Standard|Advanced Hash Standard]] candidate [[Hash_(cryptography)#Skein|Skein]] which uses a [[#Whitening_and_tweaking| 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.
 
This operation is not nearly as cheap as addition or XOR; in many environments it will also be more expensive than s-box lookups. However, it is highly non-linear and reasonably fast on a modern 32-bit or larger CPU. In some environments, such as an embedded processor with limited cache, it might even be cheaper than s-box lookups. In any case, IDEA uses only 8 rounds so it can afford a moderately expensive operation in the round function.
 
=== 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 [http://www.nist.gov/public_affairs/releases/g00-176.htm] the winner &mdash; '''Rijndael''' (pronounced approximately "rhine doll"), from two Belgian designers. The NIST page on AES [http://csrc.nist.gov/archive/aes/rijndael/wsdindex.html] has much detail.
 
=== Twofish ===
 
=== Serpent ===
 
=== RC6 ===
 
'''RC6''' was an AES finalist cipher designed by [[Ron Rivest]].
 
=== MARS ===


'''MARS'''  was an AES finalist cipher from [[IBM]].
It is possible to go the other way and use any [[cryptographic hash]] to build a block cipher; again  ''Applied Cryptography'' <ref name="schneier" /> 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.


=== TEA ===
The hash-to-cipher technique was, however, important in one legal proceeding, the [[Cryptography_controversy#Export_Controls|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.


The '''Tiny Encryption Algorithm''' is a cipher designed for small size and easy software implementation.
It is also possible to use a [[public key]] operation as a block cipher. For example, one might use the [[RSA algorithm]] 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]].


==References==
==References==
{{reflist|2}}
{{reflist|2}}[[Category:Suggestion Bot Tag]]

Latest revision as of 17:00, 19 July 2024

This article may be deleted soon.
To oppose or discuss a nomination, please go to CZ:Proposed for deletion and follow the instructions.

For the monthly nomination lists, see
Category:Articles for deletion.


In cryptography, 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.

The basic function of block ciphers is to keep messages or stored data secret; the intent is that an unauthorised person be completely unable to read the enciphered material. Block ciphers therefore use a key and are designed to be hard to read without that key. Of course an attacker's intent is exactly the opposite; he wants to read the material without authorisation, and often without the key. See cryptanalysis for his methods.

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 competition. Fifteen ciphers were entered, five finalists selected, and eventually AES chosen. Text below gives an overview; for details of the process and the criteria, and descriptions of all fifteen candidates, see the AES competition article.

These standards greatly influenced the design of other block ciphers, and the latter part of this article is divided into sections based on that. DES and alternatives describes 20th century block ciphers, all with the 64-bit block size of DES. The AES generation describes the next generation, the first 21st century ciphers, all with the 128-bit block size of AES. Large-block ciphers covers a few special cases that do not fit in the other sections.

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. This section gives an overview of the rest of the story; it aims to provide a context for the rest of the article by mentioning some issues that, while outside the study of the ciphers themselves, are crucially important in understanding and using these ciphers.

Any cipher is worthless without a good key. Keys must be kept secure, they should be large enough and sufficiently random that searching for the key (a brute force attack) is effectively impossible, and in any application which encrypts large volumes of data, the key must be changed from time to time. See the cryptography article for discussion.

It is hard to design any system that must withstand adversaries; see cryptography is difficult. In particular, block ciphers must withstand cryptanalysis; it is impossible to design a good block cipher, or to evaluate the security of one, without a thorough understanding of the available attack methods. Also, 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 either ignored or mocked by most experts.

A block cipher defines how a single block is encrypted; a mode of operation 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. A block cipher can be used to build another cryptographic function such as a random number generator, a stream cipher, or a cryptographic hash. These are primarily a matter of choosing the correct mode, but there are more general design issues as well; see the linked articles for details.

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. Typically, the symmetric cipher is the workhorse that encrypts large amounts of data; the public key mechanism manages keys for the symmetric cipher and provides authentication. Generally other components such as cryptographic hashes and a cryptographically strong random number generator are required as well. Such a 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 hybrid cryptosystem for how the components fit together, and information security for broader 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 ciphers, 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. Striking some sort of balance with a few strong ciphers is probably the best policy.

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 build up a code book with 232 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, SEED and ARIA 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 except a one-time pad 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. If the key uses bits, there are 2n possible keys and on average the attacker must test half of them, so the average cost of the attack is 2n-1 encryptions.

Current block ciphers all use at least 128-bit keys, which makes brute force attacks utterly impractical. Suppose an attacker has a billion processors in a monster parallel machine (several orders of magnitude more than any current machine) and each processor can test a billion keys a second (also a generous estimate; if the clock is k GHz, the processor must do an encryption in k cycles to achieve this). This amazingly powerful attacker can test about 260 keys a second, so he needs 267 seconds against a 128-bit key. There are about 225 seconds in a year, so that is about 242 years. This is over 4,000,000,000,000 (four trillion) years so the cipher is clearly secure against brute force.

Many ciphers support larger keys as well; the reasons are discussed in the brute force attack article.

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, a number of round keys or subkeys are computed from the primary key; the method used is called the cipher's key schedule. 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.

Three common ways to design iterated block ciphers — SP networks, Feistel structures and the Lai-Massey construction — and two important ways to look at the complexity requirements — avalanche and nonlinearity — 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, or 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 [1]. 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 [2] by Horst Feistel. The idea is that changes should build up like an avalanche, so that a tiny initial change (consider a snowball tossed onto a mountain) 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 or of the round key is changed at round , that should affect all bits of the ciphertext by round for some reasonably small . Ideally, would be 1, but this is not generally achieved in practice. Certainly must be much less than the total number of rounds; if is large, then the cipher will need more rounds to be secure.

The strict avalanche criterion [3] 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 [4] 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. The Lai-Massey construction is a third alternative, less common than the other two. In Shannon's terms, all of these are product ciphers. Any of these structures 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. None of these structures gives ideal avalanche in a single round but, with any reasonable round function, all give excellent avalanche after a few rounds.

Not all block ciphers use one of these structures, but most do. This section describes these 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 or Feistel networks. In Shannon's terms, they are another class of product cipher.

Feistel ciphers are sometimes referred to as Luby-Rackoff ciphers after the authors of a theoretical paper [5] analyzing some of their properties. Later work [6] based on that shows that a Feistel cipher with seven rounds can be secure.

In a Feistel 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 XOR-ed 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, bitwise XOR as (each bit of the output word is the XOR of the corresponding bits of the two input words) and round key for round as kn, even numbered rounds are then:

and odd-numbered rounds are

Since XOR is its own inverse (abb=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:

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 changes 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. It is possible to design a Feistel cipher so that the F-function itself has ideal avalanche properties — every output bit depends nonlinearly on every input bit and every key bit — details are in a later section.

There is a variant called an unbalanced Feistel cipher in which the block is split into two unequal-sized pieces rather than two equal halves. Skipjack was a well-known example. There are also variations which treat the text as four blocks rather than just two; MARS and CAST-256 are examples.

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 nonlinear. All other operations in a Feistel cipher are linear and a cipher without enough nonlinearity is weak; see below.

Lai-Massey scheme

This structure was introduced in a thesis by Xuejia Lai, supervised by James Massey, in a cipher which later became the International Data Encryption Algorithm, IDEA.[7] It has since been used in other ciphers such as FOX, later renamed IDEA NXT. Perhaps the best-known analysis is by Serge Vaudenay, one of the designers of FOX. [8]

One paper [9] proposes a general class of "quasi-Feistel networks", with the Lai-Massey scheme as one instance, and shows that several of the well-known results on Feistel networks (such as the Luby-Rackoff and Patarin papers referenced above) can be generalised to the whole class. Another [10] gives some specific results for the Lai-Massey scheme.

Nonlinearity

To be secure, every cipher must contain nonlinear operations. If all operations in a cipher were linear then the cipher could be reduced to a system of linear equations and be broken by an algebraic attack. The attacker can choose which algebraic system to use; for example, against one cipher he might treat the text as a vector of bits and use Boolean algebra while for another he might choose to treat it as a vector of bytes and use arithmetic modulo 28. 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.

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 nonlinearity 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 nonlinear systems of equations is far harder, so the cipher designer strives to introduce nonlinearity to the system, preferably to have at least some components that are not even close to linear. 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 nonlinearity; 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 nonlinear 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 just addition, x = a+b+c+d or just Boolean operations x = abcd but instead with a mixture, 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 216+1 and AES does matrix multiplications with polynomials in a Galois field.

Rotations, also called circular shifts, on words or registers are nonlinear 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 nonlinearity is the substitution box or S-box; see following section.

Nonlinearity 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.

S-boxes are described as by , with representing the number of input bits and the number of output bits. For example, DES uses 6 by 4 S-boxes. The storage requirement for an by S-box is 2mn bits, so large values of (many input bits) are problematic. Values up to eight are common and MARS has a 9 by 32 S-box; going much beyond that would be expensive. Large values of (many output bits) are not a problem; 32 is common and at least one system, the Tiger hash algorithm [11], 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 by S-boxes can be used. For example, AES is an SP network with a single 8 by 8 S-box and Serpent is one with eight 4 by 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.

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

Large S-boxes

The first generation of Feistel ciphers used relatively small S-boxes, 6 by 4 for DES and 4 by 4 for GOST. In these ciphers the F-function is essentially one round of an SP Network. The eight S-boxes give 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 (a bit permutation in DES, a rotation in GOST) 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.

Later Feistel ciphers use larger S-boxes; CAST-128 or CAST-256 and Blowfish all use four 8 by 32 S-boxes. They do not use S-box bits directly as F-function output. Instead, they take a 32-bit word from each S-box, then combine them to form a 32-bit output. This gives an F-function with ideal avalanche properties; every bit of input and every bit of round key affects every bit of output. No output transformation is required in such an F-function, and Blowfish has none. However, one may be used anyway; the CAST ciphers add a key-dependent rotation.

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, and the cipher meets the strict avalanche criterion [3]; complementing any input bit has a 50% chance of changing any given output bit.

These ciphers 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 by 32 S-box takes one K byte of storage; several can be used on a modern machine without difficulty. They need only four S-box lookups, rather than the eight in DES or GOST, so the F-function and therefore the whole cipher can be reasonably efficient.

S-box design

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

The CAST S-boxes use bent functions (the most highly nonlinear Boolean functions) as their columns. That is, the mapping from all the input bits to any single output bit is a bent function. A paper on generating the S-boxes is Mister & Adams "Practical S-box Design" [12]. Bent functions are combined to get additional desirable traits — a balanced S-box (equal probability of 0 and 1 output), minimum correlation among output bits, and high overall S-box nonlinearity.

Blowfish uses a different approach, generating random S-boxes as part of the key scheduling operation at cipher setup time. Such S-boxes are not as nonlinear as the carefully constructed CAST ones, but they are nonlinear enough and, unlike the CAST S-boxes, they are unknown to an attacker.

In perfectly nonlinear S-boxes [13], not only are all columns bent functions (the most nonlinear possible Boolean functions), but all linear combinations of columns are bent functions as well. This is possible only if , there are at least twice as many input bits as output bits. Such S-boxes are therefore not much used.

S-boxes in analysis

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 by 16 S-box. In an academic paper, one might use such a model in order to apply standard tools for measuring S-box nonlinearity. 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.

Resisting linear & differential attacks

Two very powerful cryptanalytic methods of attacking block ciphers are linear cryptanalysis and differential cryptanalysis. The former works by finding linear approximations for the nonlinear components of a cipher, then combining them using the piling-up lemma to attack the whole cipher. The latter looks at how small changes in the input affect the output, and how such changes propagate through multiple rounds. These are the only known attacks that break DES with less effort than brute force, and they are completely general attacks that apply to any block cipher..

Both these attacks, 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.

Techniques introduced for CAST go 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:

  1. start from properties of the round function (for CAST, from bent functions in the S-boxes)
  2. derive a limit , the maximum possible quality of any linear approximation to a single round
  3. consider the number of rounds, , as a variable
  4. derive an expression for , the effort required to break the cipher by LC, in terms of and
  5. find the minimum such that exceeds the effort required for brute force, making LC impractical
  6. derive an expression for , the number of chosen plaintexts required for LC, also in terms of and (LC with only known plaintext requires more texts, so it can be ignored)
  7. find the minimum such that exceeds the number of possible plaintexts, 2blocksize, making LC impossible

A similar approach applied to differentials gives values for 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. There are other methods of constructing ciphers provably immune to these attacks. Serge Vaudenay's work on decorrelation theory gives one [14] and Knudsen-Nyberg ciphers are another. [15]

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.

DES and alternatives

The Data Encryption Standard, DES, is among 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 cryptography. Of course, much work continued to be done in secret by military and intelligence organisations of various nations, but from the time of DES cryptography also developed as an open academic discipline complete with journals, conferences, courses and textbooks. In particular, there was a lot of 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, all encrypted with the same key, so reasonably frequent key changes provide an effective defense. 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 most used 128-bit or longer keys for better resistance to brute force attacks.

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.
  • SAFER and LOKI, two families of ciphers which each included an original version against which Lars Knudsen found an attack and a revised version to block that attack. Each had a descendant which was an AES candidate.
  • Triple DES, applying DES three times with different keys

Many of the techniques used in these ciphers came from DES and many of the design principles came from analysis of DES. However, there were also 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. Several introduced new ways to achieve nonlinearity: data-dependent rotations in RC5, key-dependent rotations in CAST-128, a clever variant on multiplication in IDEA, and the pseudo-Hadamard transform in SAFER.

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.

The AES generation

By the 90s, the Data Encryption Standard was clearly obsolete; its small key size made it more and more vulnerable to brute force attacks as computers became faster. The US National Institute of Standards and Technology (NIST) therefore began work on an Advanced Encryption Standard, AES, a block cipher to replace DES in government applications and in regulated industries.

To do this, they ran a very open international AES competition, starting in 1998. Their 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. All 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. The AES competition article covers all candidates and many have their own articles as well. Here we give only a summary.

After much analysis and testing, and two conferences, the field was narrowed to five finalists:

  • Twofish, a cipher with key-dependent S-boxes, from a team at Bruce Schneier's company Counterpane
  • MARS, a variant of Feistel cipher using data-dependent rotations, from IBM
  • Serpent, an SP network, from an international group of well-known players
  • RC6, a cipher using data-dependent rotations, from a team led by Ron Rivest
  • Rijndael. an SP network, from two Belgian designers

After another year of analysis and testing, they chose a winner. In October 2002, Rijndael was chosen to become the Advanced Encryption Standard or AES. See external links for the official standard.

An entire generation of block ciphers used the 64-bit block size of DES, but since AES many new designs use a 128-bit block size.

As discussed under size parameters, if two or more ciphers have the same block and key sizes, then they are effectively interchangeable; replacing one cipher with another requires no other changes in an application. When asked to implement AES, the implementer might include the other finalists — Twofish, Serpent. RC6 and MARS — as well. This provides useful insurance against the (presumably unlikely) risk of someone finding a good attack on AES. Little extra effort is required since open source implementations of all these ciphers are readily available, see external links. All except RC6 have completely open licenses.

There are also many other ciphers that might be used. There were ten AES candidates that did not make it into the finals:

  • CAST-256, based on CAST-128 and with the same theoretical advantages
  • DFC, based on another theoretical analysis proving resistance to various attacks.
  • Hasty Pudding, a variable block size tweakable cipher
  • DEAL, a Feistel cipher using DES as the round function
  • FROG, an innovative cipher; interesting but weak
  • E2, from Japan
  • CRYPTON, a Korean cipher with some design similarities to AES
  • MAGENTA, Deutsche Telekom's candidate, quickly broken
  • LOKI97, one of the LOKI family of ciphers, from Australia
  • SAFER+, one of the SAFER family of ciphers, from Cylink Corporation

Some should not be considered. Magenta and FROG have been broken, DEAL is slow, and E2 has been replaced by its descendant Camellia.

There are also some newer 128-bit ciphers that are widely used in certain countries:

  • Camellia, an 18-round Feistel cipher widely used in Japan and one of the standard ciphers for the NESSIE (New European Schemes for Signatures, Integrity and Encryption) project.
  • SEED, developed by the Korean Information Security Agency (KISA) and widely used in Korea.

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.

For nearly all ciphers, the block size is a power of two. Joan Daemen's PhD thesis, though, had two exceptions: 3-Way uses 96 bits (three 32-bit words) and BaseKing 192 (three 64-bit words). Neither cipher was widely used, but they did influence later designs. Daemen was one of the designers of Square and of Rijndael which became the Advanced Encryption Standard.

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 [16] 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 [16] 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 the RSA algorithm 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.

References

  1. M. Liskov, R. Rivest, and D. Wagner (2002), "Tweakable Block Ciphers", LNCS, Crypto 2002
  2. Horst Feistel (1973), "Cryptography and Computer Privacy", Scientific American
  3. 3.0 3.1 A. F. Webster and Stafford E. Tavares (1985), "On the design of S-boxes", Advances in Cryptology - Crypto '85 (Lecture Notes in Computer Science)
  4. C. E. Shannon (1949), "Communication Theory of Secrecy Systems", Bell Systems Technical Journal 28: pp.656-715
  5. M. Luby and C. Rackoff, "How to Construct Pseudorandom Permutations and Pseudorandom Functions", SIAM J. Comput
  6. Jacques Patarin (Oct 2003), "Luby-Rackoff: 7 Rounds Are Enough for Security", Lecture Notes in Computer Science 2729: 513 - 529
  7. X. Lai (1992), "On the Design and Security of Block Ciphers", ETH Series in Information Processing, v. 1
  8. S. Vaudenay (1999), On the Lai-Massey Scheme, Springer-Verlag, LCNS
  9. Aaram Yun, Je Hong Park and Jooyoung Lee (2007), Lai-Massey Scheme and Quasi-Feistel Networks
  10. Yiyuan Luo, Xuejia Lai, Zheng Gong and Zhongming Wu (2009), Pseudorandomness Analysis of the Lai-Massey Scheme
  11. Ross Anderson & Eli Biham (1996), "Tiger: a fast new hash function", Fast Software Encryption, Third International Workshop Proceedings
  12. S. Mister, C. Adams (August, 1996), "Practical S-Box Design", Selected Areas in Cryptography (SAC '96): 61-76
  13. Kaisa Nyberg (1991), "Perfect nonlinear S-boxes", Eurocrypt'91, LNCS 547
  14. Serge Vaudenay (2003), "Decorrelation: A Theory for Block Cipher Security", Journal of Cryptology
  15. Kaissa Nyberg and Lars Knudsen (1995), "Provable security against a differential attack", Journal of Cryptology
  16. 16.0 16.1 Schneier, Bruce (2nd edition, 1996,), Applied Cryptography, John Wiley & Sons, ISBN 0-471-11709-9