Cryptanalysis (from theGreekkryptós, "hidden", andanalýein, "to analyze") refers to the process of analyzinginformation systems in order to understand hidden aspects of the systems.[1] Cryptanalysis is used to breachcryptographic security systems and gain access to the contents ofencrypted messages, even if thecryptographic key is unknown.
In addition to mathematical analysis of cryptographic algorithms, cryptanalysis includes the study ofside-channel attacks that do not target weaknesses in the cryptographic algorithms themselves, but instead exploit weaknesses in their implementation.
Even though the goal has been the same, the methods and techniques of cryptanalysis have changed drastically through the history of cryptography, adapting to increasing cryptographic complexity, ranging from the pen-and-paper methods of the past, through machines like the BritishBombes andColossus computers atBletchley Park inWorld War II, to themathematically advanced computerized schemes of the present. Methods for breaking moderncryptosystems often involve solving carefully constructed problems inpure mathematics, the best-known beinginteger factorization.
Inencryption, confidential information (called the"plaintext") is sent securely to a recipient by the sender first converting it into an unreadable form ("ciphertext") using anencryption algorithm. The ciphertext is sent through an insecure channel to the recipient. The recipientdecrypts the ciphertext by applying an inversedecryption algorithm, recovering the plaintext. To decrypt the ciphertext, the recipient requires a secret knowledge from the sender, usually a string of letters, numbers, orbits, called acryptographic 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 incomputer networking to protect email and internet communication.
The goal of cryptanalysis is for a third party, acryptanalyst, 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.[2] A mathematical technique to do this is called acryptographic attack. Cryptographic attacks can be characterized in a number of ways:
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 generalalgorithm is known; this isShannon's Maxim "the enemy knows the system"[3] – in its turn, equivalent toKerckhoffs's principle.[4] This is a reasonable assumption in practice – throughout history, there are countless examples of secret algorithms falling into wider knowledge, variously throughespionage,betrayal andreverse engineering. (And on occasion, ciphers have been broken through pure deduction; for example, the GermanLorenz cipher and the JapanesePurple code, and a variety of classical schemes):[5]
Attacks can also be characterised by the resources they require. Those resources include:[6]
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 estimatedorder of magnitude of their attacks' difficulty, saying, for example, "SHA-1 collisions now 252."[7]
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 2128 encryptions; an attack requiring 2110 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."[8]
The results of cryptanalysis can also vary in usefulness. CryptographerLars Knudsen (1998) classified various types of attack onblock ciphers according to the amount and quality of secret information that was discovered:
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,[9] 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 onDES,MD5, andSHA-1 were all preceded by attacks on weakened versions.
In academic cryptography, aweakness or abreak 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 thesecret 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.[8]
Cryptanalysis hascoevolved together with cryptography, and the contest can be traced through thehistory of cryptography—newciphers 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.[citation needed]
Although the actual word "cryptanalysis" is relatively recent (it was coined byWilliam Friedman in 1920), methods for breakingcodes andciphers are much older.David Kahn notes inThe Codebreakers thatArab scholars were the first people to systematically document cryptanalytic methods.[10]
The first known recorded explanation of cryptanalysis was given byAl-Kindi (c. 801–873, also known as "Alkindus" in Europe), a 9th-century Arabpolymath,[11][12] inRisalah fi Istikhraj al-Mu'amma (A Manuscript on Deciphering Cryptographic Messages). This treatise contains the first description of the method offrequency analysis.[13] Al-Kindi is thus regarded as the first codebreaker in history.[14] His breakthrough work was influenced byAl-Khalil (717–786), who wrote theBook of Cryptographic Messages, which contains the first use ofpermutations and combinations to list all possibleArabic words with and without vowels.[15]
Frequency analysis is the basic tool for breaking mostclassical ciphers. In natural languages, certain letters of thealphabet appear more often than others; inEnglish, "E" is likely to be the most common letter in any sample ofplaintext. Similarly, thedigraph "TH" is the most likely pair of letters in English, and so on. Frequency analysis relies on a cipher failing to hide thesestatistics. For example, in asimple substitution cipher (where each letter is simply replaced with another), the most frequent letter in theciphertext 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.[16]
Al-Kindi's invention of the frequency analysis technique for breaking monoalphabeticsubstitution ciphers[17][18] was the most significant cryptanalytic advance until World War II. Al-Kindi'sRisalah fi Istikhraj al-Mu'amma described the first cryptanalytic techniques, including some forpolyalphabetic ciphers, cipher classification, Arabic phonetics and syntax, and most importantly, gave the first descriptions on frequency analysis.[19] He also covered methods of encipherments, cryptanalysis of certain encipherments, andstatistical analysis of letters and letter combinations in Arabic.[20][13] An important contribution ofIbn Adlan (1187–1268) was onsample size for use of frequency analysis.[15]
In Europe,Italian scholarGiambattista della Porta (1535–1615) was the author of a seminal work on cryptanalysis,De Furtivis Literarum Notis.[21]
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 fortreason as a result of her involvement in three plots to assassinateElizabeth I of England. The plans came to light after her coded correspondence with fellow conspirators was deciphered byThomas Phelippes.
In Europe during the 15th and 16th centuries, the idea of apolyalphabetic substitution cipher was developed, among others by the French diplomatBlaise de Vigenère (1523–96).[22] For some three centuries, theVigenè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.[23] DuringWorld War I, inventors in several countries developedrotor cipher machines such asArthur Scherbius'Enigma, in an attempt to minimise the repetition that had been exploited to break the Vigenère system.[24]
InWorld War I, the breaking of theZimmermann Telegram was instrumental in bringing the United States into the war. InWorld War II, theAllies benefitted enormously from their joint success cryptanalysis of the German ciphers – including theEnigma machine and theLorenz cipher – and Japanese ciphers, particularly'Purple' andJN-25.'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' intelligence.[25]
Cryptanalysis of enemy messages played a significant part in theAllied victory in World War II.F. W. Winterbotham, quoted the western Supreme Allied Commander,Dwight D. Eisenhower, at the war's end as describingUltra intelligence as having been "decisive" to Allied victory.[26]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.[27]
In practice, frequency analysis relies as much onlinguistic 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 duringWorld War II, where efforts to crackAxis ciphers required new levels of mathematical sophistication. Moreover, automation was first applied to cryptanalysis in that era with the PolishBomba device, the BritishBombe, the use ofpunched card equipment, and in theColossus computers – the first electronic digital computers to be controlled by a program.[28][29]
With reciprocal machine ciphers such as theLorenz cipher and theEnigma machine used byNazi Germany duringWorld 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 theindicator, as it indicates to the receiving operator how to set his machine to decipher the message.[30]
Poorly designed and implemented indicator systems allowed firstPolish cryptographers[31] and then the British cryptographers atBletchley Park[32] to break the Enigma cipher system. Similar poor indicator systems allowed the British to identifydepths that led to the diagnosis of theLorenz SZ40/42 cipher system, and the comprehensive breaking of its messages without the cryptanalysts seeing the cipher machine.[33]
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."[34][35] This may be detected by the messages having the sameindicator by which the sending operator informs the receiving operator about thekey generator initial settings for the message.[36]
Generally, the cryptanalyst may benefit from lining up identical enciphering operations among a set of messages. For example, theVernam cipher enciphers by bit-for-bit combining plaintext with a long key using the "exclusive or" operator, which is also known as "modulo-2 addition" (symbolized by ⊕ ):
Deciphering combines the same key bits with the ciphertext to reconstruct the 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:
The individual plaintexts can then be worked out linguistically by tryingprobable 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:
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:
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.[33]
Governments have long recognized the potential benefits of cryptanalysis forintelligence, both military and diplomatic, and established dedicated organizations devoted to breaking the codes and ciphers of other nations, for example,GCHQ and theNSA, organizations which are still very active today.
Even though computation was used to great effect in thecryptanalysis of the Lorenz cipher and other systems during World War II, it also made possible new methods of cryptographyorders 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] The historianDavid Kahn notes:[37]
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 achosen 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 attacks, andquantum 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."[38]
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:[39]
Thus, while the best modern ciphers may be far more resistant to cryptanalysis than theEnigma, cryptanalysis and the broader field ofinformation security remain quite active.[40]
Asymmetric cryptography (orpublic-key cryptography) is cryptography that relies on using two (mathematically related) keys; one private, and one public. Such ciphers invariably rely on "hard"mathematical problems as the basis of their security, so an obvious point of attack is to develop methods for solving the problem. The security of two-key cryptography depends on mathematical questions in a way that single-key cryptography generally does not, and conversely links cryptanalysis to wider mathematical research in a new way.[citation needed]
Asymmetric schemes are designed around the (conjectured) difficulty of solving various mathematical problems. If an improved algorithm can be found to solve the problem, then the system is weakened. For example, the security of theDiffie–Hellman key exchange scheme depends on the difficulty of calculating thediscrete logarithm. In 1983,Don Coppersmith found a faster way to find discrete logarithms (in certain groups), and thereby requiring cryptographers to use larger groups (or different types of groups).RSA's security depends (in part) upon the difficulty ofinteger factorization – a breakthrough in factoring would impact the security of RSA.[41]
In 1980, one could factor a difficult 50-digit number at an expense of 1012 elementary computer operations. By 1984 the state of the art in factoring algorithms had advanced to a point where a 75-digit number could be factored in 1012 operations. Advances in computing technology also meant that the operations could be performed much faster.Moore's law predicts that computer speeds will continue to increase. Factoring techniques may continue to do so as well, but will most likely depend on mathematical insight and creativity, neither of which has ever been successfully predictable. 150-digit numbers of the kind once used in RSA have been factored. The effort was greater than above, but was not unreasonable on fast modern computers. By the start of the 21st century, 150-digit numbers were no longer considered a large enoughkey size for RSA. Numbers with several hundred digits were still considered too hard to factor in 2005, though methods will probably continue to improve over time, requiring key size to keep pace or other methods such aselliptic curve cryptography to be used.[citation needed]
Another distinguishing feature of asymmetric schemes is that, unlike attacks on symmetric cryptosystems, any cryptanalysis has the opportunity to make use of knowledge gained from thepublic key.[42]
![[icon]](/mt/?noimg=&dark=on&url=https%3a%2f%2fen.wikipedia.org%2fwiki%2fFile%3aWiki_letter_w_cropped.svg) | This sectionneeds expansion. You can help byadding to it.(April 2012) |
| This sectionneeds expansion. You can help byadding to it.(April 2012) |
Quantum computers, which are still in the early phases of research, have potential use in cryptanalysis. For example,Shor's Algorithm could factor large numbers inpolynomial time, in effect breaking some commonly used forms of public-key encryption.[43]
By usingGrover's algorithm on a quantum computer, brute-force key search can be made quadratically faster. However, this could be countered by doubling the key length.[44]
 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Cryptanalysis" – news ·newspapers ·books ·scholar ·JSTOR(April 2012) (Learn how and when to remove this message) |
Al-Kindi is considered the first code breaker
Authority control databases: National |
|---|
