Editing Cryptanalysis (section)

==History==
{{Main|History of cryptography}}

Cryptanalysis has [[coevolution|coevolved]] together with cryptography, and the contest can be traced through the [[history of cryptography]]—new [[cipher]]s being designed to replace old broken designs, and new cryptanalytic techniques invented to crack the improved schemes. In practice, they are viewed as two sides of the same coin: secure cryptography requires design against possible cryptanalysis.{{cn|date=November 2023}}

===Classical ciphers===
[[Image:Al-kindi-cryptanalysis.png|thumb|right|First page of [[Al-Kindi]]'s 9th century ''Manuscript on Deciphering Cryptographic Messages.'']]
{{See also|Frequency analysis|Index of coincidence|Kasiski examination}}

Although the actual word "''cryptanalysis''" is relatively recent (it was coined by [[William Friedman]] in 1920), methods for breaking [[code (cryptography)|codes]] and [[cipher]]s are much older. [[David Kahn (writer)|David Kahn]] notes in ''[[The Codebreakers]]'' that [[Arab scholars]] were the first people to systematically document cryptanalytic methods.<ref>{{cite book|last1=Kahn|first1=David|title=The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet|date=1996|publisher=Simon and Schuster|isbn=9781439103555|url=https://books.google.com/books?id=3S8rhOEmDIIC&q=david+kahn+the+codebreakers}}</ref>

The first known recorded explanation of cryptanalysis was given by [[Al-Kindi]] (c. 801–873, also known as "Alkindus" in Europe), a 9th-century Arab [[polymath]],<ref>{{Cite book|url=https://books.google.com/books?id=3xJjNG5CNdwC&dq=Al+Kindi+Arab%2F&pg=PA199|title=History of Islamic Philosophy: With View of Greek Philosophy and Early History of Islam|first=I. M. N.|last=Al-Jubouri|date=February 22, 2004|publisher=Authors On Line Ltd|isbn=9780755210114|via=Google Books}}</ref><ref>{{Cite book|url=https://books.google.com/books?id=2wS2CAAAQBAJ&dq=al+kindi+Arab%2F&pg=PA279|title=The Biographical Encyclopedia of Islamic Philosophy|first=Oliver|last=Leaman|date=July 16, 2015|publisher=Bloomsbury Publishing|isbn=9781472569455|via=Google Books}}</ref> in ''Risalah fi Istikhraj al-Mu'amma'' (''A Manuscript on Deciphering Cryptographic Messages''). This treatise contains the first description of the method of [[frequency analysis]].<ref name=Kadi>Ibrahim A. Al-Kadi (April 1992), "The origins of cryptology: The Arab contributions", ''[[Cryptologia]]'' '''16''' (2): 97–126</ref> Al-Kindi is thus regarded as the first codebreaker in history.<ref name="Sahinaslan">{{cite journal |last1=Sahinaslan |first1=Ender |last2=Sahinaslan |first2=Onder |title=Cryptographic methods and development stages used throughout history |journal=AIP Conference Proceedings |date=2 April 2019 |volume=2086 |issue=1 |pages=030033 |doi=10.1063/1.5095118 |bibcode=2019AIPC.2086c0033S |issn=0094-243X |quote=Al-Kindi is considered the first code breaker|doi-access=free }}</ref> His breakthrough work was influenced by [[Al-Khalil ibn Ahmad al-Farahidi|Al-Khalil]] (717–786), who wrote the ''Book of Cryptographic Messages'', which contains the first use of [[wikt:permutation|permutations and combinations]] to list all possible [[Arabic language|Arabic]] words with and without vowels.<ref name="LB">{{cite journal|last=Broemeling|first=Lyle D.|title=An Account of Early Statistical Inference in Arab Cryptology|journal=The American Statistician|date=1 November 2011|volume=65|issue=4|pages=255–257|doi=10.1198/tas.2011.10191|s2cid=123537702}}</ref>

Frequency analysis is the basic tool for breaking most [[classical cipher]]s. In natural languages, certain letters of the [[alphabet]] appear more often than others; in [[English language|English]], "[[E]]" is likely to be the most common letter in any sample of [[plaintext]]. Similarly, the [[Digraph (orthography)|digraph]] "TH" is the most likely pair of letters in English, and so on. Frequency analysis relies on a cipher failing to hide these [[statistics]]. For example, in a [[simple substitution cipher]] (where each letter is simply replaced with another), the most frequent letter in the [[ciphertext]] would be a likely candidate for "E". Frequency analysis of such a cipher is therefore relatively easy, provided that the ciphertext is long enough to give a reasonably representative count of the letters of the alphabet that it contains.<ref>{{Harvnb|Singh|1999|p=17}}</ref>

Al-Kindi's invention of the frequency analysis technique for breaking monoalphabetic [[substitution cipher]]s<ref>{{cite book|url=https://books.google.com/books?id=2wS2CAAAQBAJ&q=al+kindi+Arab&pg=PA279|title=The Biographical Encyclopedia of Islamic Philosophy|first=Oliver|last=Leaman|date=16 July 2015|publisher=Bloomsbury Publishing|access-date=19 March 2018|via=Google Books|isbn=9781472569455}}</ref><ref>{{cite book|url=https://books.google.com/books?id=3xJjNG5CNdwC&q=Al+Kindi+Arab&pg=PA199|title=History of Islamic Philosophy: With View of Greek Philosophy and Early History of Islam|first=I. M. N.|last=Al-Jubouri|date=19 March 2018|publisher=Authors On Line Ltd|access-date=19 March 2018|via=Google Books|isbn=9780755210114}}</ref> was the most significant cryptanalytic advance until World War II. Al-Kindi's ''Risalah fi Istikhraj al-Mu'amma'' described the first cryptanalytic techniques, including some for [[polyalphabetic cipher]]s, cipher classification, Arabic phonetics and syntax, and most importantly, gave the first descriptions on frequency analysis.<ref>[[Simon Singh]], ''[[The Code Book]]'', pp. 14–20</ref> He also covered methods of encipherments, cryptanalysis of certain encipherments, and [[statistical analysis]] of letters and letter combinations in Arabic.<ref>{{cite web | url = http://www.muslimheritage.com/topics/default.cfm?ArticleID=372 | title = Al-Kindi, Cryptgraphy<!--sic?-->, Codebreaking and Ciphers | access-date = 12 January 2007 | archive-date = 5 February 2014 | archive-url = https://web.archive.org/web/20140205102439/http://www.muslimheritage.com/topics/default.cfm?ArticleID=372 | url-status = dead }}</ref><ref name=Kadi/> An important contribution of [[Ibn Adlan]] (1187–1268) was on [[sample size]] for use of frequency analysis.<ref name="LB"/>

In Europe, [[Italy|Italian]] scholar [[Giambattista della Porta]] (1535–1615) was the author of a seminal work on cryptanalysis, ''[[De Furtivis Literarum Notis]]''.<ref>{{Cite web|url=http://www.cryptool.org/content/view/28/54/lang,english/|archiveurl=https://web.archive.org/web/20080828190150/http://www.cryptool.org/content/view/28/54/lang%2Cenglish/|url-status=dead|title=Crypto History|archivedate=August 28, 2008}}</ref>

Successful cryptanalysis has undoubtedly influenced history; the ability to read the presumed-secret thoughts and plans of others can be a decisive advantage. For example, in England in 1587, [[Mary, Queen of Scots]] was tried and executed for [[treason]] as a result of her involvement in three plots to assassinate [[Elizabeth I of England]]. The plans came to light after her coded correspondence with fellow conspirators was deciphered by [[Thomas Phelippes]].

In Europe during the 15th and 16th centuries, the idea of a [[Polyalphabetic cipher|polyalphabetic substitution cipher]] was developed, among others by the French diplomat [[Blaise de Vigenère]] (1523–96).<ref>{{Harvnb|Singh|1999|pp=45–51}}</ref> For some three centuries, the [[Vigenère cipher]], which uses a repeating key to select different encryption alphabets in rotation, was considered to be completely secure (''le chiffre indéchiffrable''—"the indecipherable cipher"). Nevertheless, [[Charles Babbage]] (1791–1871) and later, independently, [[Friedrich Kasiski]] (1805–81) succeeded in breaking this cipher.<ref>{{Harvnb|Singh|1999|pp=63–78}}</ref> During [[World War I]], inventors in several countries developed [[rotor cipher machine]]s such as [[Arthur Scherbius]]' [[Enigma machine|Enigma]], in an attempt to minimise the repetition that had been exploited to break the Vigenère system.<ref>{{Harvnb|Singh|1999|p=116}}</ref>

===Ciphers from World War I and World War II===
{{See also|Cryptanalysis of the Enigma|Cryptanalysis of the Lorenz cipher}}
[[Image:Zimmermann-telegramm-offen.jpg|thumb|right|The decrypted [[Zimmermann Telegram]].]]

In [[World War I]], the breaking of the [[Zimmermann Telegram]] was instrumental in bringing the United States into the war. In [[World War II]], the [[Allies of World War II|Allies]] benefitted enormously from their joint success cryptanalysis of the German ciphers – including the [[Enigma machine]] and the [[Lorenz cipher]] – and Japanese ciphers, particularly [[Purple (cipher machine)|'Purple']] and [[JN-25]]. [[Ultra (cryptography)|'Ultra']] intelligence has been credited with everything between shortening the end of the European war by up to two years, to determining the eventual result. The war in the Pacific was similarly helped by [[Magic (cryptography)|'Magic']] intelligence.<ref>{{Harvnb|Smith|2000|p=4}}</ref>

Cryptanalysis of enemy messages played a significant part in the [[Allies of World War II|Allied]] victory in World War II. [[F. W. Winterbotham]], quoted the western Supreme Allied Commander, [[Dwight D. Eisenhower]], at the war's end as describing [[Ultra (cryptography)|Ultra]] intelligence as having been "decisive" to Allied victory.{{sfn|Winterbotham|2000|p=229}} [[Harry Hinsley|Sir Harry Hinsley]], official historian of British Intelligence in World War II, made a similar assessment about Ultra, saying that it shortened the war "by not less than two years and probably by four years"; moreover, he said that in the absence of Ultra, it is uncertain how the war would have ended.{{sfn|Hinsley|1993}}

In practice, frequency analysis relies as much on [[linguistics|linguistic]] knowledge as it does on statistics, but as ciphers became more complex, [[mathematics]] became more important in cryptanalysis. This change was particularly evident before and during [[World War II]], where efforts to crack [[Axis Powers|Axis]] ciphers required new levels of mathematical sophistication. Moreover, automation was first applied to cryptanalysis in that era with the Polish [[Bomba (cryptography)|Bomba]] device, the British [[Bombe]], the use of [[punched card]] equipment, and in the [[Colossus computers]] – the first electronic digital computers to be controlled by a program.<ref>{{Harvnb|Copeland|2006|p=1}}</ref><ref>{{Harvnb|Singh|1999|p=244}}</ref>

====Indicator====
With reciprocal machine ciphers such as the [[Lorenz cipher]] and the [[Enigma machine]] used by [[Nazi Germany]] during [[World War II]], each message had its own key. Usually, the transmitting operator informed the receiving operator of this message key by transmitting some plaintext and/or ciphertext before the enciphered message. This is termed the ''indicator'', as it indicates to the receiving operator how to set his machine to decipher the message.<ref>{{Harvnb|Churchhouse|2002|pp=33, 34}}</ref>

Poorly designed and implemented indicator systems allowed first [[Biuro Szyfrów|Polish cryptographers]]<ref>{{Harvnb|Budiansky|2000|pp=97–99}}</ref> and then the British cryptographers at [[Bletchley Park]]<ref>{{Harvnb|Calvocoressi|2001|p=66}}</ref> to break the Enigma cipher system. Similar poor indicator systems allowed the British to identify ''depths'' that led to the diagnosis of the [[Lorenz cipher|Lorenz SZ40/42]] cipher system, and the comprehensive breaking of its messages without the cryptanalysts seeing the cipher machine.<ref name="Tutte 1998">{{Harvnb|Tutte|1998}}</ref>

====Depth====
Sending two or more messages with the same key is an insecure process. To a cryptanalyst the messages are then said to be ''"in depth."''<ref>{{Harvnb|Churchhouse|2002|p=34}}</ref><ref>The [[Bletchley Park]] 1944 Cryptographic Dictionary defined a depth as <br /> 1. A series of code messages reciphered with the same, or the same part of a, reciphering key especially when written under one another so that all the groups (usually one in each message) that are reciphered with the same group of the subtractor lie under each other and form a 'column'.<br /> (b) two or more messages in a transposition cipher that are of the same length and have been enciphered on the same key;<br /> (c) two or more messages in a machine or similar cipher that have been enciphered on the same machine-setting or on the same key.<br /> 2. be in depth: (of messages). Stand to each other in any of the relationships described above.<br />{{Citation |title=The Bletchley Park 1944 Cryptographic Dictionary formatted by Tony Sale (c) 2001 |page=27 |url=https://www.codesandciphers.org.uk/documents/cryptdict/cryptxtt.pdf}}</ref> This may be detected by the messages having the same ''[[Enigma machine#Indicator|indicator]]'' by which the sending operator informs the receiving operator about the [[Key (cryptography)|key generator initial settings]] for the message.<ref>{{Harvnb|Churchhouse|2002|pp= 33, 86}}</ref>

Generally, the cryptanalyst may benefit from lining up identical enciphering operations among a set of messages. For example, the [[Gilbert Vernam|Vernam cipher]] enciphers by bit-for-bit combining plaintext with a long key using the "[[exclusive or]]" operator, which is also known as "[[Modular arithmetic|modulo-2 addition]]" (symbolized by ⊕ ):
::::Plaintext ⊕ Key = Ciphertext
Deciphering combines the same key bits with the ciphertext to reconstruct the plaintext:
::::Ciphertext ⊕ Key = Plaintext
(In modulo-2 arithmetic, addition is the same as subtraction.) When two such ciphertexts are aligned in depth, combining them eliminates the common key, leaving just a combination of the two plaintexts:
::::Ciphertext1 ⊕ Ciphertext2 = Plaintext1 ⊕ Plaintext2
The individual plaintexts can then be worked out linguistically by trying ''probable words'' (or phrases), also known as ''"cribs,"'' at various locations; a correct guess, when combined with the merged plaintext stream, produces intelligible text from the other plaintext component:
::::Cyphertext1 ⊕ Cyphertext2 ⊕ Plaintext1 = Plaintext2
The recovered fragment of the second plaintext can often be extended in one or both directions, and the extra characters can be combined with the merged plaintext stream to extend the first plaintext. Working back and forth between the two plaintexts, using the intelligibility criterion to check guesses, the analyst may recover much or all of the original plaintexts. (With only two plaintexts in depth, the analyst may not know which one corresponds to which ciphertext, but in practice this is not a large problem.) When a recovered plaintext is then combined with its ciphertext, the key is revealed:
::::Plaintext1 ⊕ Ciphertext1 = Key
Knowledge of a key then allows the analyst to read other messages encrypted with the same key, and knowledge of a set of related keys may allow cryptanalysts to diagnose the system used for constructing them.<ref name="Tutte 1998"/>

===Development of modern cryptography===
Governments have long recognized the potential benefits of cryptanalysis for [[Military espionage|intelligence]], both military and diplomatic, and established dedicated organizations devoted to breaking the codes and ciphers of other nations, for example, [[GCHQ]] and the [[National Security Agency|NSA]], organizations which are still very active today.

[[Image:TuringBombeBletchleyPark.jpg|thumb|The [[Bombe]] replicated the action of several [[Enigma machine]]s wired together. Each of the rapidly rotating drums, pictured above in a [[Bletchley Park]] museum mockup, simulated the action of an Enigma rotor.]]

Even though computation was used to great effect in the [[cryptanalysis of the Lorenz cipher]] and other systems during World War II, it also made possible new methods of cryptography [[orders of magnitude]] more complex than ever before. Taken as a whole, modern cryptography has become much more impervious to cryptanalysis than the pen-and-paper systems of the past, and now seems to have the upper hand against pure cryptanalysis.{{Citation needed|date=April 2012}} The historian [[David Kahn (writer)|David Kahn]] notes:<ref>[[David Kahn (writer)|David Kahn]] [https://fas.org/irp/eprint/kahn.html Remarks on the 50th Anniversary of the National Security Agency], November 1, 2002.</ref>

{{blockquote|text=Many are the cryptosystems offered by the hundreds of commercial vendors today that cannot be broken by any known methods of cryptanalysis. Indeed, in such systems even a [[Chosen-plaintext attack|chosen plaintext attack]], in which a selected plaintext is matched against its ciphertext, cannot yield the key that unlock[s] other messages. In a sense, then, cryptanalysis is dead. But that is not the end of the story. Cryptanalysis may be dead, but there is – to mix my metaphors – more than one way to skin a cat.}}

Kahn goes on to mention increased opportunities for interception, [[bugging]], [[side channel attack]]s, and [[quantum cryptography|quantum computers]] as replacements for the traditional means of cryptanalysis. In 2010, former NSA technical director Brian Snow said that both academic and government cryptographers are "moving very slowly forward in a mature field."<ref>Tim Greene, Network World, [http://www.networkworld.com/news/2010/030410-rsa-cloud-security-warning.html Former NSA tech chief: I don't trust the cloud] {{webarchive|url=https://web.archive.org/web/20100308105556/http://www.networkworld.com/news/2010/030410-rsa-cloud-security-warning.html |date=2010-03-08 }}. Retrieved March 14, 2010.</ref>

However, any postmortems for cryptanalysis may be premature. While the effectiveness of cryptanalytic methods employed by intelligence agencies remains unknown, many serious attacks against both academic and practical cryptographic primitives have been published in the modern era of computer cryptography:<ref>{{Cite book |url=https://nap.nationalacademies.org/read/26168/chapter/2 |title=Read "Cryptography and the Intelligence Community: The Future of Encryption" at NAP.edu |date=2022 |publisher=National Academies Press |doi=10.17226/26168 |isbn=978-0-309-49135-8 |language=en}}</ref>
* The [[block cipher]] [[Madryga]], proposed in 1984 but not widely used, was found to be susceptible to [[ciphertext-only attack]]s in 1998.
* [[FEAL|FEAL-4]], proposed as a replacement for the [[Data Encryption Standard|DES]] standard encryption algorithm but not widely used, was demolished by a spate of attacks from the academic community, many of which are entirely practical.
* The [[A5/1]], [[A5/2]], [[CMEA (cipher)|CMEA]], and [[DECT Standard Cipher|DECT]] systems used in [[mobile phone|mobile]] and wireless phone technology can all be broken in hours, minutes or even in real-time using widely available computing equipment.
* [[Brute-force search|Brute-force keyspace search]] has broken some real-world ciphers and applications, including single-DES (see [[EFF DES cracker]]), [[Cryptography#Export controls|40-bit "export-strength" cryptography]], and the [[Content Scrambling System|DVD Content Scrambling System]].
* In 2001, [[Wired Equivalent Privacy]] (WEP), a protocol used to secure [[Wi-Fi]] [[wireless network]]s, was shown to be breakable in practice because of a weakness in the [[RC4]] cipher and aspects of the WEP design that made [[related-key attack]]s practical. WEP was later replaced by [[Wi-Fi Protected Access]].
* In 2008, researchers conducted a proof-of-concept break of [[Transport Layer Security|SSL]] using weaknesses in the [[MD5]] [[Cryptographic hash function|hash function]] and certificate issuer practices that made it possible to exploit [[collision attack]]s on hash functions. The certificate issuers involved changed their practices to prevent the attack from being repeated.

Thus, while the best modern ciphers may be far more resistant to cryptanalysis than the [[Enigma machine|Enigma]], cryptanalysis and the broader field of [[information security]] remain quite active.<ref>{{Cite web|url=https://www.garykessler.net/library/crypto.html|title=An Overview of Cryptography|website=www.garykessler.net|access-date=2019-06-03}}</ref>