Industry News

Cryptanalysis

Cryptanalysis (from the Greek kryptós, "hidden", and analýein, "to loosen" or "to untie") is the study of methods for obtaining the meaning of encrypted information without access to the secret information which is normally required to do so. Typically, this involves finding the secret key. In non-technical language, this is the practice of codebreaking or cracking the code, although these phrases also have a specialised technical meaning.

"Cryptanalysis" is also used to refer to any attempt to circumvent the security of other types of cryptographic algorithms and protocols in general, and not just encryption. However, cryptanalysis usually excludes attacks that do not primarily target weaknesses in the actual cryptography; methods such as bribery, physical coercion, burglary, keylogging, and so forth, although these latter types of attack are an important concern in computer security, and are increasingly becoming more effective than traditional cryptanalysis.
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 Enigma in World War II, to the computer-based schemes of the present. Even the results of cryptanalysis have changed — it is no longer possible to have unlimited success in codebreaking, and there is a hierarchical classification of what constitutes a rare practical attack. In the mid-1970s, a new class of cryptography was introduced: asymmetric cryptography. Methods for breaking these cryptosystems are typically radically different from before, and usually involve solving a carefully-constructed problem in pure mathematics, the most well-known being integer factorization.

History of Cryptanalysis

Cryptanalysis has coevolved together with cryptography, and the contest can be traced through the history of cryptography — new ciphers 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: in order to create secure cryptography, you have to design against possible cryptanalysis.

Classical Cryptanalysis

Although the actual word "cryptanalysis" is relatively recent (it was coined by William Friedman in 1920), methods for breaking codes and ciphers are much older. The first known recorded explanation of cryptanalysis was given by 9th century Arabic polymath Abu Yusuf Yaqub ibn Ishaq al-Sabbah Al-Kindi in A Manuscript on Deciphering Cryptographic Messages. This treatise includes a description of the method of frequency analysis (Ibraham, 1992). Frequency analysis is the basic tool for breaking classical ciphers. In natural languages, certain letters of the alphabet appear more frequently than others; in English, "E" is likely to be the most common letter in any given sample of text. Similarly, the digraph "TH" is the most likely pair of letters, 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 relies as much on linguistic knowledge as it does on statistics, but as ciphers became more complex, mathematics gradually became the predominant approach to cryptanalysis. This change was particularly evident during World War II, where efforts to crack Axis ciphers required new levels of mathematical sophistication. Moreover, automation was for the first time applied to cryptanalysis with the Bombe device and the Colossus - one of the earliest computers.

Modern Cryptanalysis

Even though computation was used to great effect in cryptanalysis in 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. The historian David Kahn notes, "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, in which a selected plaintext is matched against its ciphertext, cannot yield the key that unlock 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." (Remarks on the 50th Anniversary of the National Security Agency, 1 November 2002). Kahn goes on to mention increased opportunities for interception, bugging, side channel attacks and quantum computers as replacements for the traditional means of cryptanalysis. Kahn may have been premature in his cryptanalysis postmortem; weak ciphers are not yet extinct. In academia, new designs are regularly presented, and are also frequently broken: the 1984 block cipher Madryga was found to be susceptible to ciphertext-only attacks in 1998; FEAL-4, proposed as a replacement for the DES standard encryption algorithm, was demolished by a spate of attacks from the academic community, many of which are entirely practical. In industry, too, ciphers are not free from flaws: for example, the A5/1, A5/2 and CMEA algorithms, used in mobile phone technology, can all be broken in hours, minutes or even in real-time using widely-available computing equipment. Wi-Fi's Wired Equivalent Privacy was broken in 2001 by a related key attack.

Historically, cryptography was split into a dichotomy of codes and ciphers, and coding had its own terminology, analogous to that for ciphers: "encoding, codetext, decoding" and so on. However, codes have a variety of drawbacks, including susceptibilty to cryptanalysis and the difficulty of managing a cumbersome codebook. Because of this, codes have fallen into disuse in modern cryptography, and ciphers are the dominant paradigm.

The Results of Cryptanalysisr

Successful cryptanalysis has undoubtably influenced history; the ability to read the presumed-secret thoughts and plans of others can be a decisive advantage, and never more so than during wartime. For example, 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 cryptanalysis of the German ciphers - including the Enigma machine and the Lorenz cipher - has been credited with everything between shortening the end of the European war by a few months to determining the eventual result (see ULTRA). The United States also benefited from the cryptanalysis of the Japanese PURPLE code (see MAGIC). Governments have long recognised the potential benefits of cryptanalysis for intelligence, both military and diplomatic, and established dedicated organisations devoted to breaking the codes and ciphers of other nations, for example, GCHQ and the NSA, organisations which are still very active today. Even as of 2004, it was reported that the United States had broken Iranian ciphers. (It is unknown, however, whether this was pure cryptanalysis, or whether other factors were involved.)o mix my metaphors - more than one way to skin a cat." (Remarks on the 50th Anniversary of the National Security Agency, 1 November 2002). Kahn goes on to mention increased opportunities for interception, bugging, side channel attacks and quantum computers as replacements for the traditional means of cryptanalysis.\par Kahn may have been premature in his cryptanalysis postmortem; weak ciphers are not yet extinct. In academia, new designs are regularly presented, and are also frequently broken: the 1984 block cipher Madryga was found to be susceptible to ciphertext-only attacks in

Cryptanalysis of Asymmetric Cryptography

Asymmetric cryptography (or public key cryptography) is cryptography that relies on using two 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. 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 the Diffie-Hellman key exchange scheme depends on the difficulty of calculating the discrete logarithm. In 1983, Don Coppersmith found a computationally feasible way to find discrete logarithms, and thereby gave to the cryptanalyst a tool with which to break the Diffie-Hellman cryptosystems. Another scheme, the popular RSA algorithm, remains unbroken. Its security depends (in part) upon the difficulty of integer factorisation - a breakthrough in factoring would impact the security of RSA. 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, too. Moore's law predicts that computer speeds will continue to increase. Factoring techniques may continue 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 enough key size for RSA. Numbers with several hundred digits are still considered too hard to factor in 2004, though methods will probably continue to improve over time, requiring key size to keep pace or new algorithms to be used. 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 the public key.