Editing Cryptanalysis (section)

==Overview==
In [[encryption]], confidential information (called the ''"[[plaintext]]"'') is sent securely to a recipient by the sender first converting it into an unreadable form (''"[[ciphertext]]"'') using an [[encryption algorithm]].  The ciphertext is sent through an insecure channel to the recipient.  The recipient [[decryption|decrypts]] the ciphertext by applying an inverse [[decryption|decryption algorithm]], recovering the plaintext.  To decrypt the ciphertext, the recipient requires a secret knowledge from the sender, usually a string of letters, numbers, or [[binary digit|bits]], called a ''[[cryptographic key]]''.  The concept is that even if an unauthorized person gets access to the ciphertext during transmission, without the secret key they cannot convert it back to plaintext.

Encryption has been used throughout history to send important military, diplomatic and commercial messages, and today is very widely used in [[computer networking]] to protect email and internet communication.

The goal of cryptanalysis is for a third party, a [[cryptanalyst]], to gain as much information as possible about the original (''"[[plaintext]]"''), attempting to "break" the encryption to read the ciphertext and learning the secret key so future messages can be decrypted and read.<ref>{{Cite book|last=Dooley|first=John F.|title=History of Cryptography and Cryptanalysis: Codes, Ciphers, and Their Algorithms|date=2018|publisher=Springer International Publishing|isbn=978-3-319-90442-9|series=History of Computing|location=Cham|doi=10.1007/978-3-319-90443-6|s2cid=18050046}}</ref>  A mathematical technique to do this is called a ''cryptographic attack''. Cryptographic attacks can be characterized in a number of ways:

===Amount of information available to the attacker===
{{main|Attack model}}
[[Attack model|Cryptanalytical attacks]] can be classified based on what type of information the attacker has available. As a basic starting point it is normally assumed that, for the purposes of analysis, the general [[algorithm]] is known; this is [[Claude Shannon|Shannon's Maxim]] "the enemy knows the system"<ref>{{cite journal|last1=Shannon|first1=Claude|title=Communication Theory of Secrecy Systems|journal=Bell System Technical Journal|date=4 October 1949|volume=28|issue=4|page=662|doi=10.1002/j.1538-7305.1949.tb00928.x|url=https://archive.org/stream/bstj28-4-656#page/n5/mode/2up|access-date=20 June 2014|ref=Shannon}}</ref> – in its turn, equivalent to [[Kerckhoffs's principle]].<ref>{{citation |first = David |last = Kahn |title = The Codebreakers: the story of secret writing  |year = 1996 |edition=second |publisher = Scribners |page=235}}</ref> This is a reasonable assumption in practice – throughout history, there are countless examples of secret algorithms falling into wider knowledge, variously through [[espionage]], [[betrayal]] and [[reverse engineering]]. (And on occasion, ciphers have been broken through pure deduction; for example, the German [[Lorenz cipher]] and the Japanese [[Purple code]], and a variety of classical schemes):<ref>{{cite book|author=Schmeh, Klaus|title=Cryptography and public key infrastructure on the Internet|publisher=John Wiley & Sons|year=2003|isbn=978-0-470-84745-9|page=45|url=https://books.google.com/books?id=9NqidkUqHdgC&pg=PA45}}</ref>
* ''[[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.

===Computational resources required===
{{See also|Time/memory/data tradeoff attack}}
Attacks can also be characterised by the resources they require. Those resources include:<ref>{{Cite journal|last=Hellman|first=M.|date=July 1980|title=A cryptanalytic time-memory trade-off|journal=IEEE Transactions on Information Theory|language=en-US|volume=26|issue=4|pages=401–406|doi=10.1109/tit.1980.1056220|s2cid=552536 |issn=0018-9448|url=http://www-ee.stanford.edu/~hellman/publications/36.pdf |archive-url=https://ghostarchive.org/archive/20221010/http://www-ee.stanford.edu/~hellman/publications/36.pdf |archive-date=2022-10-10 |url-status=live}}</ref>
* Time – the number of ''computation steps'' (e.g., test encryptions) which must be performed.
* Memory – the amount of ''storage'' required to perform the attack.
* Data – the quantity and type of ''plaintexts and ciphertexts'' required for a particular approach.

It is sometimes difficult to predict these quantities precisely, especially when the attack is not practical to actually implement for testing. But academic cryptanalysts tend to provide at least the estimated ''order of magnitude'' of their attacks' difficulty, saying, for example, "SHA-1 collisions now 2<sup>52</sup>."<ref>{{Citation | last1 = McDonald | first1 = Cameron | last2 = Hawkes | first2 = Philip | last3 = Pieprzyk | first3 = Josef | author3-link = Josef Pieprzyk | title =SHA-1 collisions now 2<sup>52</sup> | url = http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf | access-date = 4 April 2012}}</ref>

[[Bruce Schneier]] notes that even computationally impractical attacks can be considered breaks: "Breaking a cipher simply means finding a weakness in the cipher that can be exploited with a complexity less than brute force. Never mind that brute-force might require 2<sup>128</sup> encryptions; an attack requiring 2<sup>110</sup> encryptions would be considered a break...simply put, a break can just be a certificational weakness: evidence that the cipher does not perform as advertised."<ref name="schneier"/><!-- Birthday attacks; man in the middle / time-memory tradeoff -->

===Partial breaks===
The results of cryptanalysis can also vary in usefulness. Cryptographer [[Lars Knudsen]] (1998) classified various types of attack on [[block cipher]]s according to the amount and quality of secret information that was discovered:
* ''Total break'' – the attacker deduces the secret [[key (cryptography)|key]].
* ''Global deduction'' – the attacker discovers a functionally equivalent [[algorithm]] for encryption and decryption, but without learning the key.
* ''Instance (local) deduction'' – the attacker discovers additional plaintexts (or ciphertexts) not previously known.
* ''Information deduction'' – the attacker gains some [[Information entropy|Shannon information]] about plaintexts (or ciphertexts) not previously known.
* ''Distinguishing algorithm'' – the attacker can distinguish the cipher from a random [[permutation]].

Academic attacks are often against weakened versions of a cryptosystem, such as a block cipher or hash function with some rounds removed. Many, but not all, attacks become exponentially more difficult to execute as rounds are added to a cryptosystem,<ref>For an example of an attack that cannot be prevented by additional rounds, see [[slide attack]].</ref> so it's possible for the full cryptosystem to be strong even though reduced-round variants are weak. Nonetheless, partial breaks that come close to breaking the original cryptosystem may mean that a full break will follow; the successful attacks on [[Data Encryption Standard|DES]], [[MD5]], and [[SHA-1]] were all preceded by attacks on weakened versions.

In academic cryptography, a ''weakness'' or a ''break'' in a scheme is usually defined quite conservatively: it might require impractical amounts of time, memory, or known plaintexts. It also might require the attacker be able to do things many real-world attackers can't: for example, the attacker may need to choose particular plaintexts to be encrypted or even to ask for plaintexts to be encrypted using several keys related to the [[secret key]]. Furthermore, it might only reveal a small amount of information, enough to prove the cryptosystem imperfect but too little to be useful to real-world attackers. Finally, an attack might only apply to a weakened version of cryptographic tools, like a reduced-round block cipher, as a step towards breaking the full system.<ref name=schneier>{{Harvnb|Schneier|2000}}</ref>