—By: R Manoj, 'InfoSecurity' Bureau.

In this world of cyber security, the need to break the cryptographic code has become the norm of every cryptanalysts. As the practice of code breaking is used by the cryptanalysts the world over, it is imperative for us to know the concept cryptanalysis in brief. This article deals with the basics of cryptanalysis and the various techniques used by the cryptanalysts.

In this article, we present the basic principles and techniques of cryptanalysis. Before we understand what cryptanalysis is about, let us first understand the relation of cryptanalysis with respect to cryptography.

Cryptography concerns the various ways of protecting messages from being understood by anyone except those for whom the messages are intended. Cryptographers are the people who create and use codes and ciphers. Cryptanalysis is the art and science of solving unknown codes and ciphers. In simple terms, Cryptanalysts try to break the codes and ciphers created and used by cryptographers.

Cryptanalysis has coevolved together with cryptography and the contest can be traced through the history of cryptography. New ciphers are being designed to replace the old broken designs and new cryptanalytic techniques are 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.

The Term

Cryptanalysis refers to the study of ciphers, ciphertext, or cryptosystems which is related to secret code systems) with a view to finding weaknesses in them that will permit retrieval of the plaintext from the ciphertext, without necessarily knowing the key or the algorithm. This process is known as cryptosystem, it is also known as breaking the cipher or ciphertext.

It can also be defined as 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 a secret key. In general terms, cryptanalysis is the practice of codebreaking or cracking the code. Cryptanalysis is derived from the two Greek words kryptós meaning "hidden" and analýein which means "to loosen" or "to untie".

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 methods of attack that do not primarily target weaknesses in the actual cryptography, such as bribery, physical coercion, burglary, keystroke logging, and social engineering, although these types of attack are an important concern and are often more effective than traditional cryptanalysis.

The Concept

Breaking of codes is sometimes used interchangeably with weakening. This refers to finding a property or fault in the design or implementation of the cipher that reduces the number of keys required in a brute force attack. In other words it is like simply trying every possible key until the correct one is found. For example, assume that a symmetric cipher implementation uses a key length of 2^128 bits (2 to the power of 128). This means that a brute force attack would need to try up to all 2^128 possible combinations or rounds to be certain of finding the correct key (or, on average, 2^127 possible combinations) to convert the ciphertext into plaintext, which is not possible given present and near future computing abilities. However, a cryptanalysis of the cipher reveals a technique that would allow the plaintext to be found in 2^40 rounds. While not completely broken, the cipher is now much weaker and the plaintext can be found with moderate computing resources.

Evolution

Over the years, even though the goal of cryptanalysis has been the same, the methods and techniques have changed drastically. 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. The results of cryptanalysis have also 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 which is known by asymmetric cryptography. Methods for breaking these cryptosystems are typically radically different from before, and usually involve solving carefully-constructed problems in pure mathematics, the best-known being integer factorization.

Classical Cryptanalysis

Although the actual word "cryptanalysis" is relatively recent (it was coined by William Friedman in 1920), the methods for breaking codes and ciphers are much older. The first known recorded explanation of cryptanalysis was given by 9th-century Arabian polymath, Abu Yusuf Yaqub ibn Ishaq al-Sabbah Al-Kindi (also known as "Alkindus" in Europe), in "A Manuscript on Deciphering Cryptographic Messages". This treatise includes a description of the method of frequency analysis. Frequency analysis is known to be a ancient form of classical cryptanalysis. Now let's understand the concept of Frequency analysis in detail.

Frequency Analysis

Frequency analysis is the basic tool for breaking most 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 sample of plaintext. Similarly, the 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".

In practice, frequency analysis relies as much on linguistic knowledge as it does on statistics, but as ciphers became more complex, mathematics became more important in 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 first applied to cryptanalysis in that era with the Polish Bomba device, use of punched card equipment, and in the Colossus which was one of the earliest computers and arguably the first programmable electronic digital computer for code-breaking.

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.". 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, and cryptanalytic methods employed by intelligence agencies remain unpublished. 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. In 2001, Wired Equivalent Privacy (WEP), a protocol used to secure Wi-Fi wireless networks, was shown to be susceptible to a practical related-key attack.

The Techniques

There are numerous techniques for performing cryptanalysis, depending on what access the cryptanalyst has to the plaintext, ciphertext, or other aspects of the cryptosystem. Below are some of the most common types of attacks.

1) Known-plaintext analysis: With this procedure, the cryptanalyst has knowledge of a portion of the plaintext from the ciphertext. Using this information, the cryptanalyst attempts to deduce the key used to produce the ciphertext.

2) Chosen-plaintext analysis (also known as differential cryptanalysis): The cryptanalyst is able to have any plaintext encrypted with a key and obtain the resulting ciphertext, but the key itself cannot be analyzed. The cryptanalyst attempts to deduce the key by comparing the entire ciphertext with the original plaintext. The Rivest-Shamir-Adleman encryption technique has been shown to be somewhat vulnerable to this type of analysis.

3) Ciphertext-only analysis: The cryptanalyst has no knowledge of the plaintext and must work only from the ciphertext. This requires accurate guesswork as to how a message could be worded. It helps to have some knowledge of the literary style of the ciphertext writer and/or the general subject matter.

4) Man-in-the-middle attack: This differs from the above in that it involves tricking individuals into surrendering their keys. The cryptanalyst/attacker places him or herself in the communication channel between two parties who wish to exchange their keys for secure communication (via asymmetric or public key infrastructure cryptography). The cryptanalyst/attacker then performs a key exchange with each party, with the original parties believing they are exchanging keys with each other. The two parties then end up using keys that are known to the cryptanalyst/attacker. This type of attack can be defeated by the use of a hash function.

5) Timing/differential power analysis: This is a new technique made public in June 1998, particularly useful against the smart card that measures differences in electrical consumption over a period of time when a microchip performs a function to secure information. This technique can be used to gain information about key computations used in the encryption algorithm and other functions pertaining to security. The technique can be rendered less effective by introducing random noise into the computations, or altering the sequence of the executables to make it harder to monitor the power fluctuations. This type of analysis was first developed by Paul Kocher of Cryptography Research, though Bull Systems claims it knew about this type of attack over four years before.

In addition to the above, other techniques are available, such as convincing individuals to reveal passwords/keys, developing Trojan horse programs that steal a victim's secret key from their computer and send it back to the cryptanalyst, or tricking a victim into using a weakened cryptosystem. Although all of these are valid techniques to compromise a given code, some technical experts consider these to be unorthodox and non-technical.

A Brief Conclusion

Successful cryptanalysis is a combination of mathematics, inquisitiveness, intuition, persistence, powerful computing resources and more often than many would like to admit—luck. However, successful cryptanalysis has made the enormous resources often devoted to it more than worthwhile. The breaking of the German Enigma code during WWII, for example, was one of the key factors in an early Allied victory.

Today, cryptanalysis is practiced by a broad range of organizations and governments try to break other governments' diplomatic and military transmissions; companies developing security products send them to cryptanalysts to test their security features and to a hacker or cracker to try to break the security of Web sites by finding weaknesses in the securing protocols. It is this constant battle between cryptographers trying to secure information and cryptanalysts trying to break cryptosystems that moves the entire body of cryptology knowledge forward.

—By: R. Manoj. The author is an Assistant Editor at Fanatic Media, Bangalore. He is also an Independent Researcher, specializing in Software Security. He has an active interest in designing security algorithms for securing softwares. He can reached at infosecurity@fanaticmedia.com