Block cipher: Difference between revisions
Jump to navigation
Jump to search
| [unchecked revision] | [unchecked revision] |
imported>Rebestalic →Modes of operation: in case people suppose that the likeness of a penguin is a product of secure image encryption |
|||
| Line 3: | Line 3: | ||
In [[cryptography]], a '''block cipher''' is a [[deterministic algorithm]] that operates on fixed-length groups of [[bit]]s, called ''blocks''. Block ciphers are the elementary [[cryptographic primitive|building blocks]] of many [[cryptographic protocol]]s. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via [[encryption]]. | In [[cryptography]], a '''block cipher''' is a [[deterministic algorithm]] that operates on fixed-length groups of [[bit]]s, called ''blocks''. Block ciphers are the elementary [[cryptographic primitive|building blocks]] of many [[cryptographic protocol]]s. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via [[encryption]]. | ||
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 of [[block cipher modes of operation|modes of operation]] have been designed to allow their repeated use in a secure way to achieve the security goals of confidentiality and [[authentication|authenticity]]. However, block ciphers may also feature as building blocks in other cryptographic protocols, such as [[universal hash function]]s and [[pseudorandom number generator]]s. | 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 of [[block cipher modes of operation|modes of operation]] have been designed to allow their repeated use in a secure way to achieve the other security goals of confidentiality and [[authentication|authenticity]]. However, block ciphers may also feature as building blocks in other cryptographic protocols, such as [[universal hash function]]s and [[pseudorandom number generator]]s. | ||
==Definition== | ==Definition== | ||
| Line 19: | Line 19: | ||
==History== | ==History== | ||
The modern design of block ciphers is based on the concept of an iterated [[product 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 as [[substitution cipher|substitution]]s and [[transposition cipher|permutation]]s.<ref name="shannon">{{cite journal|last1= Shannon|first1= Claude|title= Communication Theory of Secrecy Systems|journal= [[Bell System Technical Journal]]|volume= 28|issue= 4|pages= 656–715|year= 1949|doi= 10.1002/j.1538-7305.1949.tb00928.x|url= http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf|access-date= 2012-04-09|archive-date= 2007-06-05|archive-url= https://web.archive.org/web/20070605092733/http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf|url-status= dead}}</ref> Iterated product ciphers carry out encryption in multiple [[Round (cryptography)|rounds]], each of which uses a different subkey derived from the original key. One widespread implementation of such ciphers named a [[Feistel network]] after [[Horst Feistel]] is notably implemented in the [[Data Encryption Standard|DES]] cipher.<ref name="tilborg">{{cite book|editor1-last= van Tilborg|editor1-first= Henk C. A.|editor2-last= Jajodia|editor2-first= Sushil|title= Encyclopedia of Cryptography and Security|publisher= Springer|year= 2011|isbn= 978-1-4419-5905-8|url= https://books.google.com/books?id=UuNKmgv70lMC&pg=PA455}}, p. 455.</ref> Many other realizations of block ciphers, such as the [[Advanced Encryption Standard|AES]], are classified as [[substitution–permutation network]]s.{{sfn|van Tilborg|Jajodia|2011|p=1268}} | The modern design of block ciphers is based on the concept of an iterated [[product 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 as [[substitution cipher|substitution]]s and [[transposition cipher|permutation]]s.<ref name="shannon">{{cite journal|last1= Shannon|first1= Claude|title= Communication Theory of Secrecy Systems|journal= [[Bell System Technical Journal]]|volume= 28|issue= 4|pages= 656–715|year= 1949|doi= 10.1002/j.1538-7305.1949.tb00928.x|bibcode= 1949BSTJ...28..656S|url= http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf|access-date= 2012-04-09|archive-date= 2007-06-05|archive-url= https://web.archive.org/web/20070605092733/http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf|url-status= dead}}</ref> Iterated product ciphers carry out encryption in multiple [[Round (cryptography)|rounds]], each of which uses a different subkey derived from the original key. One widespread implementation of such ciphers named a [[Feistel network]] after [[Horst Feistel]] is notably implemented in the [[Data Encryption Standard|DES]] cipher.<ref name="tilborg">{{cite book|editor1-last= van Tilborg|editor1-first= Henk C. A.|editor2-last= Jajodia|editor2-first= Sushil|title= Encyclopedia of Cryptography and Security|publisher= Springer|year= 2011|isbn= 978-1-4419-5905-8|url= https://books.google.com/books?id=UuNKmgv70lMC&pg=PA455}}, p. 455.</ref> Many other realizations of block ciphers, such as the [[Advanced Encryption Standard|AES]], are classified as [[substitution–permutation network]]s.{{sfn|van Tilborg|Jajodia|2011|p=1268}} | ||
The root of all [[cryptographic]] block formats used within the [[Payment Card Industry Data Security Standard]] (PCI DSS) and [[American National Standards Institute]] (ANSI) standards lies with the [[Atalla Key Block]] (AKB), which was a key innovation of the [[Atalla Box]], the first [[hardware security module]] (HSM). It was developed in 1972 by [[Mohamed M. Atalla]], founder of [[Atalla Corporation]] (now [[Utimaco Atalla]]), and released in 1973. The AKB was a key block, which is required to securely interchange [[Symmetric-key algorithm|symmetric keys]] or [[Personal identification number|PINs]] with other actors in the [[banking industry]]. This secure interchange is performed using the AKB format.<ref>{{cite web |last1=Rupp |first1=Martin |title=The Benefits of the Atalla Key Block |url=https://content.hsm.utimaco.com/blog/the-benefits-of-atalla-key-block |website=[[Utimaco]] |date=16 August 2019 |access-date=10 September 2019 |archive-date=17 October 2020 |archive-url=https://web.archive.org/web/20201017215047/https://content.hsm.utimaco.com/blog/the-benefits-of-atalla-key-block |url-status=dead }}</ref> The Atalla Box protected over 90% of all [[Automated teller machine|ATM]] networks in operation as of 1998,<ref>{{cite web |last1=Hamscher |first1=Walter |year=1998 |title=Electronic Business without Fear: The Tristrata Security Architecture |url=http://www.standardadvantage.com/docs/fear.pdf |archive-url=https://web.archive.org/web/20050529185702/http://www.standardadvantage.com/docs/fear.pdf |archive-date=29 May 2005 |citeseerx=10.1.1.123.2371 }}{{self-published inline|date=January 2022}}</ref> and Atalla products still secure the majority of the world's ATM transactions as of 2014.<ref name="Stiennon">{{cite web |last1=Stiennon |first1=Richard |title=Key Management a Fast Growing Space |url=https://securitycurrent.com/key-management-a-fast-growing-space/ |website=SecurityCurrent |publisher=IT-Harvest |access-date=21 August 2019 |date=17 June 2014}}</ref> | The root of all [[cryptographic]] block formats used within the [[Payment Card Industry Data Security Standard]] (PCI DSS) and [[American National Standards Institute]] (ANSI) standards lies with the [[Atalla Key Block]] (AKB), which was a key innovation of the [[Atalla Box]], the first [[hardware security module]] (HSM). It was developed in 1972 by [[Mohamed M. Atalla]], founder of [[Atalla Corporation]] (now [[Utimaco Atalla]]), and released in 1973. The AKB was a key block, which is required to securely interchange [[Symmetric-key algorithm|symmetric keys]] or [[Personal identification number|PINs]] with other actors in the [[banking industry]]. This secure interchange is performed using the AKB format.<ref>{{cite web |last1=Rupp |first1=Martin |title=The Benefits of the Atalla Key Block |url=https://content.hsm.utimaco.com/blog/the-benefits-of-atalla-key-block |website=[[Utimaco]] |date=16 August 2019 |access-date=10 September 2019 |archive-date=17 October 2020 |archive-url=https://web.archive.org/web/20201017215047/https://content.hsm.utimaco.com/blog/the-benefits-of-atalla-key-block |url-status=dead }}</ref> The Atalla Box protected over 90% of all [[Automated teller machine|ATM]] networks in operation as of 1998,<ref>{{cite web |last1=Hamscher |first1=Walter |year=1998 |title=Electronic Business without Fear: The Tristrata Security Architecture |url=http://www.standardadvantage.com/docs/fear.pdf |archive-url=https://web.archive.org/web/20050529185702/http://www.standardadvantage.com/docs/fear.pdf |archive-date=29 May 2005 |citeseerx=10.1.1.123.2371 }}{{self-published inline|date=January 2022}}</ref> and Atalla products still secure the majority of the world's ATM transactions as of 2014.<ref name="Stiennon">{{cite web |last1=Stiennon |first1=Richard |title=Key Management a Fast Growing Space |url=https://securitycurrent.com/key-management-a-fast-growing-space/ |website=SecurityCurrent |publisher=IT-Harvest |access-date=21 August 2019 |date=17 June 2014}}</ref> | ||
| Line 49: | Line 49: | ||
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 166–167.</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 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 | 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 | 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}} | 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}} | ||
| Line 114: | Line 114: | ||
====ARX (add–rotate–XOR)==== | ====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. | 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]]{{Dubious|date=November 2025|reason=ChaCha20 is a stream cipher, this section seems to imply it is a stream cipher.}}, [[Speck (cipher)|Speck]], [[XXTEA]], and [[BLAKE (hash function)|BLAKE]]{{Dubious|date=November 2025|reason=Blake is a hash function, article implies it is a block cipher.}}. 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> | |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> | ||
| Line 133: | Line 133: | ||
==Padding== | ==Padding== | ||
{{Main|Padding (cryptography)}} | {{Main|Padding (cryptography)}} | ||
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 efficient [[padding oracle attack]]s.<ref name="padding-attack">{{cite book|author=Serge Vaudenay|title=Advances in Cryptology — EUROCRYPT 2002 |chapter=Security Flaws Induced by CBC Padding — Applications to SSL, IPSEC, WTLS |series=Lecture Notes in Computer Science |volume | 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 efficient [[padding oracle attack]]s.<ref name="padding-attack">{{cite book|author=Serge Vaudenay|title=Advances in Cryptology — EUROCRYPT 2002 |chapter=Security Flaws Induced by CBC Padding — Applications to SSL, IPSEC, WTLS |series=Lecture Notes in Computer Science |volume=2332 |pages=534–545|publisher=Springer Verlag|year=2002 |doi=10.1007/3-540-46035-7_35 |isbn=978-3-540-43553-2 |url=http://infoscience.epfl.ch/record/99410 }}</ref> A suitable [[padding (cryptography)|padding 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,<ref name="padding-attack"/><ref name="oz-pad">{{cite book|author1=Kenneth G. Paterson|author2=Gaven J. Watson|title=Security and Cryptography for Networks |chapter=Immunising CBC Mode Against Padding Oracle Attacks: A Formal Security Treatment |series=Lecture Notes in Computer Science |volume=5229|pages=340–357|publisher=Springer Verlag|year=2008|doi=10.1007/978-3-540-85855-3_23|isbn=978-3-540-85854-6 }}</ref> 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,<ref name="iso-iec 9797-1">{{citation|title=ISO/IEC 9797-1: Information technology – Security techniques – Message Authentication Codes (MACs) – Part 1: Mechanisms using a block cipher|publisher=ISO/IEC|year=2011|url=http://www.iso.org/iso/iso_catalogue/catalogue_ics/catalogue_detail_ics.htm?csnumber=50375}}</ref> has been proven secure against these attacks.<ref name="oz-pad"/> | ||
==Cryptanalysis== | ==Cryptanalysis== | ||
{{ | {{main|Cryptanalysis}} | ||
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, these [[Attack model|Attack models]] are: | |||
* ''[[Ciphertext-only attack|Ciphertext-only]]'': the cryptanalyst has access only to a collection of [[ciphertext]]s or [[codetext]]s. | |||
* ''[[Known-plaintext attack|Known-plaintext]]'': the attacker has a set of ciphertexts to which they know the corresponding [[plaintext]]. | |||
* ''[[Chosen plaintext attack|Chosen-plaintext]]'' (''[[chosen-ciphertext attack|chosen-ciphertext]]''): the attacker can obtain the ciphertexts (plaintexts) corresponding to an arbitrary set of plaintexts (ciphertexts) of their own choosing. | |||
* ''[[Adaptive chosen plaintext attack|Adaptive chosen-plaintext]]'': like a chosen-plaintext attack, except the attacker can choose subsequent plaintexts based on information learned from previous encryptions, similarly to the ''[[Adaptive chosen ciphertext attack]]''. | |||
* ''[[Related-key attack]]'': Like a chosen-plaintext attack, except the attacker can obtain ciphertexts encrypted under two different keys. The keys are unknown, but the relationship between them is known; for example, two keys that differ in the one bit. | |||
===Brute-force attacks=== | ===Brute-force attacks=== | ||
| Line 158: | Line 165: | ||
===Other techniques=== | ===Other techniques=== | ||
[[File:Attaque boomerang.png|thumb|right|200px|The development of the [[boomerang attack]] enabled [[differential cryptanalysis]] techniques to be applied to many ciphers that had previously been deemed secure against differential attacks]] | [[File:Attaque boomerang.png|thumb|right|200px|The development of the [[boomerang attack]] enabled [[differential cryptanalysis]] techniques to be applied to many ciphers that had previously been deemed secure against differential attacks]] | ||
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 attack]]s, [[boomerang attack]]s, 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.<ref>{{Citation | | 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 attack]]s, [[boomerang attack]]s, 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.<ref>{{Citation |last1=Wu |first1=Shengbao |title=Security Evaluation against Differential Cryptanalysis for Block Cipher Structures |date=2011 |url=https://eprint.iacr.org/2011/551 |access-date=2025-01-01 |last2=Wang |first2=Mingsheng}}</ref> | ||
==Provable security== | ==Provable security== | ||
| Line 232: | Line 239: | ||
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 by [[patent]]s, 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 the [[public domain]], and can be freely used by anyone." The same applies to [[Twofish]], a successor algorithm from Schneier. | 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 by [[patent]]s, 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 the [[public domain]], and can be freely used by anyone." The same applies to [[Twofish]], a successor algorithm from Schneier. | ||
=== Additional National Block Ciphers === | |||
Several block ciphers exist that are generally only used in certain localities or jurisdictions, some of the more well known ones include: | |||
* [[SM4 (cipher)|SM4]] — China | |||
* [[Kuznyechik]] (GOST R 34.12-2015) — Russia | |||
* [[GOST (block cipher)|GOST 28147-89]] — Soviet Union / Russia (deprecated) | |||
* [[ARIA (cipher)|ARIA]] — South Korea | |||
* [[SEED]] — South Korea | |||
* [[Camellia (cipher)|Camellia]] — Japan, also used internationally to an extent. | |||
* [[Kalyna (cipher)|Kalyna]] — Ukraine | |||
==Generalizations== | ==Generalizations== | ||