 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Block cipher" – news ·newspapers ·books ·scholar ·JSTOR(April 2012) (Learn how and when to remove this message) |
Incryptography, ablock cipher is adeterministic algorithm that operates on fixed-length groups ofbits, calledblocks. Block ciphers are the elementarybuilding blocks of manycryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated viaencryption.
A block cipher uses blocks as an unvarying transformation. Even a secure block cipher is suitable for the encryption of only a single block of data at a time, using a fixed key. A multitude ofmodes of operation have been designed to allow their repeated use in a secure way to achieve the other security goals of confidentiality andauthenticity. However, block ciphers may also feature as building blocks in other cryptographic protocols, such asuniversal hash functions andpseudorandom number generators.
A block cipher consists of two pairedalgorithms, one for encryption,E, and the other for decryption,D.[1] Both algorithms accept two inputs: an input block of sizen bits and akey of sizek bits; and both yield ann-bit output block. The decryption algorithmD is defined to be theinverse function of encryption, i.e.,D =E−1. More formally,[2][3] a block cipher is specified by an encryption function
which takes as input a keyK, of bit lengthk (called thekey size), and a bit stringP, of lengthn (called theblock size), and returns a stringC ofn bits.P is called theplaintext, andC is termed theciphertext. For eachK, the functionEK(P) is required to be an invertible mapping on{0,1}n. The inverse forE is defined as a function
taking a keyK and a ciphertextC to return a plaintext valueP, such that
For example, a block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit 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 128-bit block of ciphertext together with the secret key, and yields the original 128-bit block of plain text.[4]
For each keyK,EK is apermutation (abijective mapping) over the set of input blocks. Each key selects one permutation from the set of possible permutations.[5]
The modern design of block ciphers is based on the concept of an iteratedproduct cipher. In his seminal 1949 publication,Communication Theory of Secrecy Systems,Claude Shannon analyzed product ciphers and suggested them as a means of effectively improving security by combining simple operations such assubstitutions andpermutations.[6] Iterated product ciphers carry out encryption in multiplerounds, each of which uses a different subkey derived from the original key. One widespread implementation of such ciphers named aFeistel network afterHorst Feistel is notably implemented in theDES cipher.[7] Many other realizations of block ciphers, such as theAES, are classified assubstitution–permutation networks.[8]
The root of allcryptographic block formats used within thePayment Card Industry Data Security Standard (PCI DSS) andAmerican National Standards Institute (ANSI) standards lies with theAtalla Key Block (AKB), which was a key innovation of theAtalla Box, the firsthardware security module (HSM). It was developed in 1972 byMohamed M. Atalla, founder ofAtalla Corporation (nowUtimaco Atalla), and released in 1973. The AKB was a key block, which is required to securely interchangesymmetric keys orPINs with other actors in thebanking industry. This secure interchange is performed using the AKB format.[9] The Atalla Box protected over 90% of allATM networks in operation as of 1998,[10] and Atalla products still secure the majority of the world's ATM transactions as of 2014.[11]
The publication of the DES cipher by the United States National Bureau of Standards (subsequently the U.S.National Institute of Standards and Technology, NIST) in 1977 was fundamental in the public understanding of modern block cipher design. It also influenced the academic development ofcryptanalytic attacks. Bothdifferential andlinear cryptanalysis arose out of studies on DES design. As of 2016[update], there is a palette of attack techniques against which a block cipher must be secure, in addition to being robust againstbrute-force attacks.
Most block cipher algorithms are classified asiterated block ciphers which means that they transform fixed-size blocks ofplaintext into identically sized blocks ofciphertext, via the repeated application of an invertible transformation known as theround function, with each iteration referred to as around.[12]
Usually, the round functionR takes differentround keysKi as a second input, which is derived from the original key:[13]
where is the plaintext and the ciphertext, withr being the number of rounds.
Frequently,key whitening is used in addition to this. At the beginning and the end, the data is modified with key material (often withXOR):
Given one of the standard iterated block cipher design schemes, it is fairly easy to construct a block cipher that is cryptographically secure, simply by using a large number of rounds. However, this will make the cipher inefficient. Thus, efficiency is the most important additional design criterion for professional ciphers. Further, a good block cipher is designed to avoid side-channel attacks, such as branch prediction and input-dependent memory accesses that might leak secret data via the cache state or the execution time. In addition, the cipher should be concise, for small hardware and software implementations.
One important type of iterated block cipher known as asubstitution–permutation network (SPN) takes a block of the plaintext and the key as inputs and applies several alternating rounds consisting of asubstitution stage followed by apermutation stage—to produce each block of ciphertext output.[14] The non-linear substitution stage mixes the key bits with those of the plaintext, creating Shannon'sconfusion. The linear permutation stage then dissipates redundancies, creatingdiffusion.[15][16]
Asubstitution box (S-box) substitutes a small block of input bits with another block of output bits. This substitution must beone-to-one, to ensure invertibility (hence decryption). A secure S-box will have the property that changing one input bit will change about half of the output bits on average, exhibiting what is known as theavalanche effect—i.e. it has the property that each output bit will depend on every input bit.[17]
Apermutation box (P-box) is apermutation of all the bits: it takes the outputs of all the S-boxes of one round, permutes the bits, and feeds them into the S-boxes of the next round. A good P-box has the property that the output bits of any S-box are distributed to as many S-box inputs as possible.[18]
At each round, the round key (obtained from the key with some simple operations, for instance, using S-boxes and P-boxes) is combined using some group operation, typicallyXOR.[citation needed]
Decryption is done by simply reversing the process (using the inverses of the S-boxes and P-boxes and applying the round keys in reversed order).[19]
In aFeistel cipher, the block of plain text to be encrypted is split into two equal-sized halves. The round function is applied to one half, using a subkey, and then the output is XORed with the other half. The two halves are then swapped.[20]
Let be the round function and let be the sub-keys for the rounds respectively.
Then the basic operation is as follows:[20]
Split the plaintext block into two equal pieces, (,)
For each round, compute
Then the ciphertext is.
The decryption of a ciphertext is accomplished by computing for
Then is the plaintext again.
One advantage of the Feistel model compared to asubstitution–permutation network is that the round function does not have to be invertible.[21]
The Lai–Massey scheme offers security properties similar to those of theFeistel structure. It also shares the advantage that the round function does not have to be invertible. Another similarity is that it also splits the input block into two equal pieces. However, the round function is applied to the difference between the two, and the result is then added to both half blocks.
Let be the round function and a half-round function and let be the sub-keys for the rounds respectively.
Then the basic operation is as follows:
Split the plaintext block into two equal pieces, (,)
For each round, compute
where and
Then the ciphertext is.
The decryption of a ciphertext is accomplished by computing for
where and
Then is the plaintext again.
Many modern block ciphers and hashes areARX algorithms—their round function involves only three operations: (A) modular addition, (R)rotation with fixed rotation amounts, and (X)XOR. Examples includeChaCha20[dubious –discuss],Speck,XXTEA, andBLAKE[dubious –discuss]. Many authors draw an ARX network, a kind ofdata flow diagram, to illustrate such a round function.[22]
These ARX operations are popular because they are relatively fast and cheap in hardware and software, their implementation can be made extremely simple, and also because they run in constant time, and therefore are immune totiming attacks. Therotational cryptanalysis technique attempts to attack such round functions.
Other operations often used in block ciphers include data-dependent rotations as inRC5 andRC6, asubstitution box implemented as alookup table as inData Encryption Standard andAdvanced Encryption Standard, apermutation box, and multiplication as inIDEA.
A block cipher by itself allows encryption only of a single data block of the cipher's block length. For a variable-length message, the data must first be partitioned into separate cipher blocks. In the simplest case, known aselectronic codebook (ECB) mode, a message is first split into separate blocks of the cipher's block size (possibly extending the last block withpadding bits), and then each block is encrypted and decrypted independently. However, such a naive method is generally insecure because equal plaintext blocks will always generate equal ciphertext blocks (for the same key), so patterns in the plaintext message become evident in the ciphertext output.[23]
To overcome this limitation, several so-calledblock cipher modes of operation have been designed[24][25] and specified in national recommendations such as NIST 800-38A[26] andBSI TR-02102[27] and international standards such asISO/IEC 10116.[28] The general concept is to userandomization of the plaintext data based on an additional input value, frequently called aninitialization vector, to create what is termedprobabilistic encryption.[29] In the popularcipher block chaining (CBC) mode, for encryption to besecure the initialization vector passed along with the plaintext message must be a random orpseudo-random value, which is added in anexclusive-or manner to the first plaintext block before it is encrypted. The resultant ciphertext block is then used as the new initialization vector for the next plaintext block. In thecipher feedback (CFB) mode, which emulates aself-synchronizing stream cipher, the initialization vector is first encrypted and then added to the plaintext block. Theoutput feedback (OFB) mode repeatedly encrypts the initialization vector to create akey stream for the emulation of asynchronous stream cipher. The newercounter (CTR) mode similarly creates a key stream, but has the advantage of only needing unique and not (pseudo-)random values as initialization vectors; the needed randomness is derived internally by using the initialization vector as a block counter and encrypting this counter for each block.[26]
From asecurity-theoretic point of view, modes of operation must provide what is known assemantic security.[30] Informally, it means that given some ciphertext under an unknown key one cannot practically derive any information from the ciphertext (other than the length of the message) over what one would have known without seeing the ciphertext. It has been shown that all of the modes discussed above, with the exception of the ECB mode, provide this property under so-calledchosen plaintext attacks.
Some modes such as the CBC mode only operate on complete plaintext blocks. Simply extending the last block of a message with zero bits is insufficient since it does not allow a receiver to easily distinguish messages that differ only in the number of padding bits. More importantly, such a simple solution gives rise to very efficientpadding oracle attacks.[31] A suitablepadding scheme is therefore needed to extend the last plaintext block to the cipher's block size. While many popular schemes described in standards and in the literature have been shown to be vulnerable to padding oracle attacks,[31][32] a solution that adds a one-bit and then extends the last block with zero-bits, standardized as "padding method 2" in ISO/IEC 9797-1,[33] has been proven secure against these attacks.[32]
Cryptanalysis is the technique in which ciphers are decrypted without knowledge of the used key. Different attacks can be employed based on the information available to the cryptanalyst, theseAttack models are:
![[icon]](/mt/?noimg=&dark=on&url=https%3a%2f%2fen.wikipedia.org%2fwiki%2fFile%3aWiki_letter_w_cropped.svg) | This sectionneeds expansion with: Impact of key size and block size, discuss time–m to thebirthday attack.. You can help byadding missing information.(January 2019) |
This property results in the cipher's security degrading quadratically, and needs to be taken into account when selecting a block size. There is a trade-off though as large block sizes can result in the algorithm becoming inefficient to operate.[34] Earlier block ciphers such as theDES have typically selected a 64-bit block size, while newer designs such as theAES support block sizes of 128 bits or more, with some ciphers supporting a range of different block sizes.[35]
| This sectionneeds expansion. You can help byadding missing information.(April 2012) |
A linear cryptanalysis is a form of cryptanalysis based on findingaffine approximations to the action of acipher. Linear cryptanalysis is one of the two most widely used attacks on block ciphers; the other beingdifferential cryptanalysis.[36]
The discovery is attributed toMitsuru Matsui, who first applied the technique to theFEAL cipher (Matsui and Yamagishi, 1992).[37]
Integral cryptanalysis is a cryptanalytic attack that is particularly applicable to block ciphers based on substitution–permutation networks. Unlike differential cryptanalysis, which uses pairs of chosen plaintexts with a fixed XOR difference, integral cryptanalysis uses sets or even multisets of chosen plaintexts of which part is held constant and another part varies through all possibilities. For example, an attack might use 256 chosen plaintexts that have all but 8 of their bits the same, but all differ in those 8 bits. Such a set necessarily has an XOR sum of 0, and the XOR sums of the corresponding sets of ciphertexts provide information about the cipher's operation. This contrast between the differences between pairs of texts and the sums of larger sets of texts inspired the name "integral cryptanalysis", borrowing the terminology of calculus.[citation needed]
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, theXSL 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.[38]
When a block cipher is used in a givenmode of operation, the resulting algorithm should ideally be about as secure as the block cipher itself. ECB (discussed above) emphatically lacks this property: regardless of how secure the underlying block cipher is, ECB mode can easily be attacked. On the other hand, CBC mode can be proven to be secure under the assumption that the underlying block cipher is likewise secure. Note, however, that making statements like this requires formal mathematical definitions for what it means for an encryption algorithm or a block cipher to "be secure". This section describes two common notions for what properties a block cipher should have. Each corresponds to a mathematical model that can be used to prove properties of higher-level algorithms, such as CBC.
This general approach to cryptography – proving higher-level algorithms (such as CBC) are secure under explicitly stated assumptions regarding their components (such as a block cipher) – is known asprovable security.
Informally, a block cipher is secure in the standard model if an attacker cannot tell the difference between the block cipher (equipped with a random key) and a random permutation.
To be a bit more precise, letE be ann-bit block cipher. We imagine the following game:
The attacker, which we can model as an algorithm, is called anadversary. The functionf (which the adversary was able to query) is called anoracle.
Note that an adversary can trivially ensure a 50% chance of winning simply by guessing at random (or even by, for example, always guessing "heads"). Therefore, letPE(A) denote the probability that adversaryA wins this game againstE, and define theadvantage ofA as 2(PE(A) − 1/2). It follows that ifA guesses randomly, its advantage will be 0; on the other hand, ifA always wins, then its advantage is 1. The block cipherE is apseudo-random permutation (PRP) if no adversary has an advantage significantly greater than 0, given specified restrictions onq and the adversary's running time. If in Step 2 above adversaries have the option of learningf−1(X) instead off(X) (but still have only small advantages) thenE is astrong PRP (SPRP). An adversary isnon-adaptive if it chooses allq values forX before the game begins (that is, it does not use any information gleaned from previous queries to choose eachX as it goes).
These definitions have proven useful for analyzing various modes of operation. For example, one can define a similar game for measuring the security of a block cipher-based encryption algorithm, and then try to show (through areduction argument) that the probability of an adversary winning this new game is not much more thanPE(A) for someA. (The reduction typically provides limits onq and the running time ofA.) Equivalently, ifPE(A) is small for all relevantA, then no attacker has a significant probability of winning the new game. This formalizes the idea that the higher-level algorithm inherits the block cipher's security.
| This sectionneeds expansion. You can help byadding missing information.(April 2012) |
Block ciphers may be evaluated according to multiple criteria in practice. Common factors include:[39][40]
Lucifer is generally considered to be the first civilian block cipher, developed atIBM in the 1970s based on work done byHorst Feistel. A revised version of the algorithm was adopted as a U.S. governmentFederal Information Processing Standard: FIPS PUB 46Data Encryption Standard (DES).[42] It was chosen by the U.S. National Bureau of Standards (NBS) after a public invitation for submissions and some internal changes byNBS (and, potentially, theNSA). DES was publicly released in 1976 and has been widely used.[citation needed]
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 byEli Biham andAdi Shamir in the late 1980s. The technique is calleddifferential 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 byMitsuru Matsui. DES prompted a large amount of other work and publications in cryptography andcryptanalysis in the open community and it inspired many new cipher designs.[citation needed]
DES has a block size of 64 bits and akey size of 56 bits. 64-bit blocks became common in block cipher designs after DES. Key length depended on several factors, including government regulation. Many observers[who?] in the 1970s commented that the 56-bit key length used for DES was too short. As time went on, its inadequacy became apparent, especially after aspecial-purpose machine designed to break DES was demonstrated in 1998 by theElectronic Frontier Foundation. An extension to DES,Triple DES, triple-encrypts each block with either two independent keys (112-bit key and 80-bit security) or three independent keys (168-bit key and 112-bit security). It was widely adopted as a replacement. As of 2011, the three-key version is still considered secure, though theNational Institute of Standards and Technology (NIST) standards no longer permit the use of the two-key version in new applications, due to its 80-bit security level.[43]
TheInternational Data Encryption Algorithm (IDEA) is a block cipher designed byJames Massey ofETH Zurich andXuejia Lai; it was first described in 1991, as an intended replacement for DES.
IDEA operates on 64-bitblocks using a 128-bit key and consists of a series of eight identical transformations (around) and an output transformation (thehalf-round). The processes for encryption and decryption are similar. IDEA derives much of its security by interleaving operations from differentgroups –modular addition and multiplication, and bitwiseexclusive or (XOR) – which are algebraically "incompatible" in some sense.
The designers analysed IDEA to measure its strength againstdifferential cryptanalysis and concluded that it is immune under certain assumptions. No successfullinear or algebraic weaknesses have been reported. As of 2012[update], the best attack which applies to all keys can break a full 8.5-round IDEA using a narrow-bicliques attack about four times faster than brute force.
RC5 is a block cipher designed byRonald Rivest in 1994 which, unlike many other ciphers, has a variable block size (32, 64, or 128 bits), key size (0 to 2040 bits), and a number of rounds (0 to 255). The original suggested choice of parameters was a block size of 64 bits, a 128-bit key, and 12 rounds.
A key feature of RC5 is the use of data-dependent rotations; one of the goals of RC5 was to prompt the study and evaluation of such operations as a cryptographic primitive. RC5 also consists of a number ofmodular additions and XORs. The general structure of the algorithm is aFeistel-like a network. The encryption and decryption routines can be specified in a few lines of code. The key schedule, however, is more complex, expanding the key using an essentiallyone-way function with the binary expansions of bothe and thegolden ratio as sources of "nothing up my sleeve numbers". The tantalizing simplicity of the algorithm together with the novelty of the data-dependent rotations has made RC5 an attractive object of study for cryptanalysts.
12-round RC5 (with 64-bit blocks) is susceptible to adifferential attack using 244 chosen plaintexts.[44] 18–20 rounds are suggested as sufficient protection.
TheRijndael cipher developed by Belgian cryptographers,Joan Daemen andVincent Rijmen was one of the competing designs to replace DES. It won the5-year public competition to become the AES (Advanced Encryption Standard).
Adopted by NIST in 2001, AES has a fixed block size of 128 bits and a key size of 128, 192, or 256 bits, whereas Rijndael can be specified with block and key sizes in any multiple of 32 bits, with a minimum of 128 bits. The block size has a maximum of 256 bits, but the key size has no theoretical maximum. AES operates on a 4×4column-major order matrix of bytes, termed thestate (versions of Rijndael with a larger block size have additional columns in the state).
Blowfish is a block cipher, designed in 1993 byBruce Schneier and included in a large number of cipher suites and encryption products. Blowfish has a 64-bit block size and a variablekey length from 1 bit up to 448 bits.[45] It is a 16-roundFeistel cipher and uses large key-dependentS-boxes. Notable features of the design include the key-dependentS-boxes and a highly complexkey schedule.
It was designed as a general-purpose algorithm, intended as an alternative to the aging DES and free of the problems and constraints associated with other algorithms. At the time Blowfish was released, many other designs were proprietary, encumbered bypatents, or were commercial/government secrets. Schneier has stated that "Blowfish is unpatented, and will remain so in all countries. The algorithm is hereby placed in thepublic domain, and can be freely used by anyone." The same applies toTwofish, a successor algorithm from Schneier.
| This sectionneeds expansion. You can help byadding missing information.(June 2008) |
M. Liskov, R. Rivest, and D. Wagner have described a generalized version of block ciphers called "tweakable" block ciphers.[46] A tweakable block cipher accepts a second input called thetweak 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. Thedisk encryption theory article describes some of these modes.
Block ciphers traditionally work over a binaryalphabet. That is, both the input and the output are binary strings, consisting ofn zeroes and ones. In some situations, however, one may wish to have a block cipher that works over some other alphabet; for example, encrypting 16-digit credit card numbers in such a way that the ciphertext is also a 16-digit number might facilitate adding an encryption layer to legacy software. This is an example offormat-preserving encryption. More generally, format-preserving encryption requires a keyed permutation on some finitelanguage. This makes format-preserving encryption schemes a natural generalization of (tweakable) block ciphers. In contrast, traditional encryption schemes, such as CBC, are not permutations because the same plaintext can encrypt multiple different ciphertexts, even when using a fixed key.
Block ciphers can be used to build other cryptographic primitives, such as those below. For these other primitives to be cryptographically secure, care has to be taken to build them the right way.
Just as block ciphers can be used to build hash functions, like SHA-1 and SHA-2 are based on block ciphers which are also used independently asSHACAL, hash functions can be used to build block ciphers. Examples of such block ciphers areBEAR and LION.
{{cite journal}}:Cite journal requires|journal= (help)