Editing Block cipher (section)

==Design==

===Iterated block ciphers===
Most block cipher algorithms are classified as ''iterated block ciphers'' which means that they transform fixed-size blocks of [[plaintext]] into identically sized blocks of [[ciphertext]], via the repeated application of an invertible transformation known as the ''round function'', with each iteration referred to as a ''round''.<ref>{{cite book|author1=Junod, Pascal |author2=Canteaut, Anne|author2-link=Anne Canteaut |name-list-style=amp |title=Advanced Linear Cryptanalysis of Block and Stream Ciphers|publisher=IOS Press|year=2011|isbn=9781607508441|page=2|url=https://books.google.com/books?id=pMnRhjStTZoC&pg=PA2}}</ref>

Usually, the round function ''R'' takes different ''round keys'' ''K<sub>i</sub>'' as a second input, which is derived from the original key:<ref>{{cite book | first1 = Jean-Philippe | last1 = Aumasson | date = 6 November 2017 | title = Serious Cryptography: A Practical Introduction to Modern Encryption | publisher = No Starch Press | pages = 56 | isbn = 978-1-59327-826-7 | oclc = 1012843116 | url = https://books.google.com/books?id=W1v6DwAAQBAJ&pg=PA56}}</ref>
:<math>M_i = R_{K_i}(M_{i-1})</math>
where <math>M_0</math> is the plaintext and <math>M_r</math> the ciphertext, with ''r'' 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 with [[Exclusive or|XOR]]):
:<math> M_0 = M \oplus K_0 </math>
:<math>M_i = R_{K_i}(M_{i-1})\; ; \; i = 1 \dots r</math>
:<math>C = M_r \oplus K_{r+1}</math>

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.

===Substitution–permutation networks===
[[Image:SubstitutionPermutationNetwork-en.svg|thumb|200px|right|A sketch of a substitution–permutation network with 3 rounds, encrypting a plaintext block of 16 bits into a ciphertext block of 16 bits. The S-boxes are the ''S<sub>i</sub>'', the P-boxes are the same ''P'', and the round keys are the ''K<sub>i</sub>''.]]
{{Main|Substitution–permutation network}}

One important type of iterated block cipher known as a ''[[substitution–permutation network]] (SPN)'' takes a block of the plaintext and the key as inputs and applies several alternating rounds consisting of a [[Substitution box|substitution stage]] followed by a [[Permutation box|permutation stage]]—to produce each block of ciphertext output.<ref>{{cite book|last=Keliher|first=Liam|chapter=Modeling Linear Characteristics of Substitution–Permutation Networks|editor-last1=Hays|editor-first1=Howard |editor-last2=Carlisle|editor-first2=Adam|title=Selected areas in cryptography: 6th annual international workshop, SAC'99, Kingston, Ontario, Canada, August 9–10, 1999 : proceedings|publisher=Springer|year=2000|isbn=9783540671855|page=[https://archive.org/details/springer_10.1007-3-540-46513-8/page/n87 79]|url=https://archive.org/details/springer_10.1007-3-540-46513-8|display-authors=etal}}</ref> The non-linear substitution stage mixes the key bits with those of the plaintext, creating Shannon's ''[[confusion (cryptography)|confusion]]''. The linear permutation stage then dissipates redundancies, creating ''[[diffusion (cryptography)|diffusion]]''.<ref>{{cite book|last1=Baigneres|first1=Thomas|last2=Finiasz|first2=Matthieu|chapter=Dial 'C' for Cipher|editor-last1=Biham|editor-first1=Eli |editor-last2=Yousseff|editor-first2=Amr|title=Selected areas in cryptography: 13th international workshop, SAC 2006, Montreal, Canada, August 17–18, 2006 : revised selected papers|publisher=Springer|year=2007|isbn=9783540744610|page=77|chapter-url=https://books.google.com/books?id=yb99g5G7FS4C&pg=PA77}}</ref><ref>{{cite book|last1=Cusick|first1=Thomas W.|last2=Stanica|first2=Pantelimon|title=Cryptographic Boolean functions and applications|publisher=Academic Press|year=2009|isbn=9780123748904|page=164|url=https://books.google.com/books?id=OAkhkLSxxxMC&pg=PA164}}</ref>

A ''[[substitution box]] (S-box)'' substitutes a small block of input bits with another block of output bits. This substitution must be [[Bijection|one-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 the [[avalanche effect]]—i.e. it has the property that each output bit will depend on every input bit.<ref>{{cite book|last1=Katz|first1=Jonathan|last2=Lindell|first2=Yehuda|title=Introduction to modern cryptography|publisher=CRC Press|year=2008|isbn=9781584885511|url=https://archive.org/details/Introduction_to_Modern_Cryptography|page=[https://archive.org/details/Introduction_to_Modern_Cryptography/page/n184 166]}}, pages&nbsp;166–167.</ref>

A ''[[permutation box]] (P-box)'' is a [[permutation]] 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.<ref>{{cite book | chapter-url=https://ieeexplore.ieee.org/document/6575944 | doi=10.1109/AICERA-ICMiCR.2013.6575944 | chapter=Key based S-box selection and key expansion algorithm for substitution-permutation network cryptography | title=2013 Annual International Conference on Emerging Research Areas and 2013 International Conference on Microelectronics, Communications and Renewable Energy | date=2013 | last1=Nayaka | first1=Raja Jitendra | last2=Biradar | first2=R. C. | pages=1–6 | isbn=978-1-4673-5149-2 }}</ref>

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, typically [[XOR]].{{citation needed|date=April 2012}}

[[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).<ref>{{cite book | title=Block Cipher Cryptanalysis: An Overview | publisher=Indian Statistical Institute | author=Subhabrata Samajder | year=2017 | location=Kolkata | pages=5/52}}</ref>

===Feistel ciphers===
[[File:Feistel cipher diagram en.svg|thumb|right|265px|Many block ciphers, such as DES and Blowfish utilize structures known as ''[[Feistel cipher]]s'']]
{{Main|Feistel cipher}}
In a ''[[Feistel 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.{{sfn|Katz|Lindell|2008|pp=170–172}}

Let <math>{\rm F}</math> be the round function and let
<math>K_0,K_1,\ldots,K_{n}</math> be the sub-keys for the rounds <math>0,1,\ldots,n</math> respectively.

Then the basic operation is as follows:{{sfn|Katz|Lindell|2008|pp=170–172}}

Split the plaintext block into two equal pieces, (<math>L_0</math>, <math>R_0</math>)

For each round <math>i =0,1,\dots,n</math>, compute

:<math>L_{i+1} = R_i\,</math>
:<math>R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)</math>.

Then the ciphertext is <math>(R_{n+1}, L_{n+1})</math>.

The decryption of a ciphertext <math>(R_{n+1}, L_{n+1})</math> is accomplished by computing for <math>i=n,n-1,\ldots,0</math>

:<math>R_{i} = L_{i+1}\,</math>
:<math>L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})</math>.

Then <math>(L_0,R_0)</math> is the plaintext again.

One advantage of the Feistel model compared to a [[substitution–permutation network]] is that the round function <math>{\rm F}</math> does not have to be invertible.{{sfn|Katz|Lindell|2008|p=171}}

===Lai–Massey ciphers===
[[File:Lai Massey scheme diagram en.svg|thumb|right|265px|The Lai–Massey scheme. The archetypical cipher utilizing it is [[International Data Encryption Algorithm|IDEA]].]]
{{main|Lai–Massey scheme}}

The Lai–Massey scheme offers security properties similar to those of the [[Feistel structure]]. It also shares the advantage that the round function <math>\mathrm F</math> 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 <math>\mathrm F</math> be the round function and <math>\mathrm H</math> a half-round function and let <math>K_0,K_1,\ldots,K_n</math> be the sub-keys for the rounds <math>0,1,\ldots,n</math> respectively.

Then the basic operation is as follows:

Split the plaintext block into two equal pieces, (<math>L_0</math>, <math>R_0</math>)

For each round <math>i =0,1,\dots,n</math>, compute

:<math>(L_{i+1}',R_{i+1}') = \mathrm H(L_i' + T_i,R_i' + T_i),</math>

where <math>T_i = \mathrm F(L_i' - R_i', K_i)</math> and <math>(L_0',R_0') = \mathrm H(L_0,R_0)</math>

Then the ciphertext is <math>(L_{n+1}, R_{n+1}) = (L_{n+1}',R_{n+1}')</math>.

The decryption of a ciphertext <math>(L_{n+1}, R_{n+1})</math> is accomplished by computing for <math>i=n,n-1,\ldots,0</math>

:<math>(L_i',R_i') = \mathrm H^{-1}(L_{i+1}' - T_i, R_{i+1}' - T_i)</math>

where <math>T_i = \mathrm F(L_{i+1}' - R_{i+1}',K_i)</math> and <math>(L_{n+1}',R_{n+1}')=\mathrm H^{-1}(L_{n+1},R_{n+1})</math>

Then <math>(L_0,R_0) = (L_0',R_0')</math> is the plaintext again.

===Operations===

====ARX (add–rotate–XOR)====
Many modern block ciphers and hashes are '''ARX''' algorithms—their round function involves only three operations: (A) modular addition, (R) [[circular shift|rotation]] with fixed rotation amounts, and (X) [[exclusive or|XOR]]. Examples include [[ChaCha20]], [[Speck (cipher)|Speck]], [[XXTEA]], and [[BLAKE (hash function)|BLAKE]]. Many authors draw an ARX network, a kind of [[data flow diagram]], to illustrate such a round function.<ref>{{cite book |last1=Aumasson |first1=Jean-Philippe |last2=Bernstein |first2=Daniel J.
|author-link2=Daniel J. Bernstein |chapter=SipHash: a fast short-input PRF |doi=10.1007/978-3-642-34931-7_28 |chapter-url=https://131002.net/siphash/siphash.pdf |editor1-last=Galbraith |editor1-first=Steven |editor2-last=Nandi |editor2-first=Mridul |title=Progress in cryptology-- INDOCRYPT 2012 : 13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012, proceedings |date=2012 |publisher=Springer |location=Berlin |isbn=978-3-642-34931-7 |page=494|archive-url=https://web.archive.org/web/20200312053222/https://131002.net/siphash/siphash.pdf |archive-date=2020-03-12 }}</ref>

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 to [[timing attack]]s. The [[rotational cryptanalysis]] technique attempts to attack such round functions.

====Other operations====
Other operations often used in block ciphers include data-dependent rotations as in [[RC5]] and [[RC6]], a [[substitution box]] implemented as a [[lookup table]] as in [[Data Encryption Standard]] and [[Advanced Encryption Standard]], a [[permutation box]], and multiplication as in [[IDEA (cipher)|IDEA]].