 Block cipher

In cryptography, a block cipher is a symmetric key cipher operating on fixedlength groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take (for example) a 128bit block of plaintext as input, and output a corresponding 128bit block of ciphertext. The exact transformation is controlled using a second input — the secret key. Decryption is similar: the decryption algorithm takes, in this example, a 128bit block of ciphertext together with the secret key, and yields the original 128bit block of plain text.
A message longer than the block size (128 bits in the above example) can still be encrypted with a block cipher by breaking the message into blocks and encrypting each block individually. However, in this method all blocks are encrypted with the same key, which degrades security (because each repetition in the plaintext becomes a repetition in the ciphertext). To overcome this issue, modes of operation are used to make encryption probabilistic. Some modes of operation, despite the fact that their underlying implementation is a block cipher, allow the encryption of individual bits. The resulting cipher is called a stream cipher.
An early and highly influential block cipher design was the Data Encryption Standard (DES), developed at IBM and published as a standard in 1977. A successor to DES, the Advanced Encryption Standard (AES), was adopted in 2001.
Contents
Generalities
A block cipher consists of two paired algorithms, one for encryption, E, and the other for decryption, E^{−1}. Both algorithms accept two inputs: an input block of size n bits and a key of size k bits, yielding an nbit output block. For any one fixed key, decryption is the inverse function of encryption, so that
for any block M and key K. M is termed the plaintext and C the ciphertext.
For each key K, E_{K} is a permutation (a bijective mapping) over the set of input blocks. Each key selects one permutation from the possible set of (2^{n})!.
The block size, n, is typically 64 or 128 bits, although some ciphers have a variable block size. 64 bits was the most common length until the mid1990s, when new designs began to switch to the longer 128bit length. One of several modes of operation is generally used along with a padding scheme to allow plaintexts of arbitrary lengths to be encrypted. Each mode has different characteristics in regard to error propagation, ease of random access and vulnerability to certain types of attack. Typical key sizes (k) include 40,^{[1]} 56,^{[1]} 64, 80, 128,^{[1]} 192 and 256, 512, 1024, 2048, 4096 bits. As of 2011^{[update]}, 128 bits is normally taken as the minimum key length needed to prevent brute force attacks. For creating ciphers with arbitrary block sizes (or on domains that aren't powers of two) see Formatpreserving encryption.
Iterated block ciphers
Most block ciphers are constructed by repeatedly applying a simpler function. This approach is known as iterated block cipher (see also product cipher). Each iteration is termed a round, and the repeated function is termed the round function; anywhere between 4 to 32 rounds are typical.
Usually, the round function R takes different round keys K_{i} as second input, which are derived from the original key:
where M_{0} is the plaintext and M_{r} the ciphertext, with r being the round number.
Frequently, key whitening is used in addition to this. At the beginning and the end, the data is modified with key material (often with XOR, but simple arithmetic operations like adding and subtracting are also used):
Many block ciphers can be categorised as Feistel networks, or, as more general substitutionpermutation networks. Arithmetic operations, logical operations (especially XOR), Sboxes and various permutations are all frequently used as components.
History
Lucifer is generally considered to be the first civilian block cipher, developed at IBM in the 1970s based on work done by Horst Feistel. A revised version of the algorithm was adopted as a US government FIPS standard, the DES. It was chosen by the US National Bureau of Standards (NBS) after a public invitation for submissions and some internal changes by NBS (and, potentially, the NSA). DES was publicly released in 1976 and has been widely used.
DES was designed to, among other things, resist a certain cryptanalytic attack known to the NSA and rediscovered by IBM, though unknown publicly until rediscovered again and published by Eli Biham and Adi Shamir in the late 1980s. The technique is called differential cryptanalysis and remains one of the few general attacks against block ciphers; linear cryptanalysis is another, but may have been unknown even to the NSA, prior to its publication by Mitsuru Matsui. DES prompted a large amount of other work and publications in cryptography and cryptanalysis in the open community and it inspired many new cipher designs.
DES has a block size of 64 bits and a key size of 56 bits. 64bit blocks became common in block cipher designs after DES. Key length depended on several factors, including government regulation. Many observers in the 1970s commented that the 56bit key length used for DES was too short. As time went on, its inadequacy became apparent, especially after a special purpose machine designed to break DES was demonstrated in 1998 by the Electronic Frontier Foundation. A variant of DES, Triple DES, tripleencrypts blocks with either two different keys (2 key TDES, resulting in a 112bit keys and 80bit security) or three keys (3 key TDES, resulting in a 168bit key and 112bit security). It was widely adopted as a replacement. As of 2011, the threekey version is still considered secure, though National Institute of Standards and Technology(NIST) standards no longer permit the use of the twokey version in new applications, due to its 80 bit security level.
DES has been superseded as a United States Federal Standard by the AES, adopted by National Institute of Standards and Technology (NIST) in 2001 after a 5year public competition. The cipher was developed by two Belgian cryptographers, Joan Daemen and Vincent Rijmen, and submitted under the name Rijndael. AES has a block size of 128 bits and three possible key sizes, 128, 192 and 256 bits. The US Government permits the use of AES to protect classified information in systems approved by NSA.
Cryptanalysis
In addition to linear and differential cryptanalysis, there is a growing catalog of attacks: truncated differential cryptanalysis, partial differential cryptanalysis, integral cryptanalysis, which encompasses square and integral attacks, slide attacks, boomerang attacks, the XSL attack, impossible differential cryptanalysis and algebraic attacks. For a new block cipher design to have any credibility, it must demonstrate evidence of security against known attacks.
Tweakable block ciphers
M. Liskov, R. Rivest, and D. Wagner have described a generalized version of block ciphers called "tweakable" block ciphers. A tweakable block cipher accepts a second input called the tweak along with its usual plaintext or ciphertext input. The tweak, along with the key, selects the permutation computed by the cipher. If changing tweaks is sufficiently lightweight (compared with a usually fairly expensive key setup operation), then some interesting new operation modes become possible. The disk encryption theory article describes some of these modes.
Block ciphers and other cryptographic primitives
Block ciphers can be used to build other cryptographic primitives. For these other primitives to be cryptographically secure care has to be taken to build them the right way.
Stream ciphers can be built using block ciphers. OFBmode and CTR mode are block modes that turn a block cipher into a stream cipher.
Cryptographic hash functions can be built using block ciphers. See oneway compression function for descriptions of several such methods. The methods resemble the block cipher modes of operation usually used for encryption.
Just as block ciphers can be used to build hash functions, hash functions can be used to build block ciphers. Examples of such block ciphers are SHACAL, BEAR and LION.
Cryptographically secure pseudorandom number generators (CSPRNGs) can be built using block ciphers.
Secure pseudorandom permutations of arbitrarily sized finite sets can be constructed with block ciphers; see FormatPreserving Encryption.
Message authentication codes (MACs) are often built from block ciphers. CBCMAC, OMAC and PMAC are such MACs.
Authenticated encryption is also built from block ciphers. It means to both encrypt and MAC at the same time. That is to both provide confidentiality and authentication. CCM, EAX, GCM and OCB are such authenticated encryption modes.
See also
 Block cipher security summary
 Confusion and diffusion
 Topics in cryptography
 Disk encryption
References
 ^ ^{a} ^{b} ^{c} Blaze, Matt; Diffie, Whitefield; Rivest, Ronald L.; Schneier, Bruce; Shimomura, Tsutomu; Thompson, Eric; Wiener, Michael (January 19996). "Minimal key lengths for symmetric ciphers to provide adequate commercial security". Fortify. http://www.fortify.net/related/cryptographers.html. Retrieved 14 October 2011.
 M. Liskov, R. Rivest, and D. Wagner, "Tweakable Block Ciphers", Crypto 2002 PDF.
External links
 A list of many symmetric algorithms, the majority of which are block ciphers.
 The block cipher lounge
 What is a block cipher? from RSA FAQ
Categories: Block ciphers
Wikimedia Foundation. 2010.