Cryptanalysis

Cryptanalysis is the study of analyzing information systems in order to “discover” or “crack” the hidden or secret aspects of those systems. More specifically, cryptanalysis is the study of breaching cryptographic security systems in order to obtain access to the information contained within encrypted messages without necessarily knowing the cryptographic key used to encrypt the information. The field also includes the study of targeting weaknesses in the implementation of cryptographic algorithms which is referred to as a side-channel attack. Throughout the history of the field, the methods of cryptanalysis have evolved over the years to adapt to the increasing complexity of algorithms in use both today and in the future.

What Do Cryptanalysts Do?

At the fundamental level, the primary task or job of a cryptanalyst is to analyze and obtain as much information about plaintext data used to generate ciphertext, or encoded text. Depending on the context of employment and goals of the organization, the work of a cryptanalyst can range from the academic to field work for various government agencies or the military.

How are Cryptanalysis Attacks Categorized?

The primary method used to classify cryptanalysis attacks is based on the type of information available to the analyst from the cipher or crypto system under study (or attack). The basic premise of cryptanalysis is that the general algorithm is known to the person or organization undertaking the attack. This maxim is equivalent to Kerckhoff’s principle that the adversary or enemy will be able to obtain knowledge of the cipher algorithm being employed through betrayal, espionage, reverse engineering, or a combination of all of these factors. At some points in the history of the cryptanalysis field of study, the cipher has been able to be fully reconstructed through pure analysis by the analysts to include the Japanese Purple code, classic encryption schemes, and the German Lorenz cipher.

Ciphertext Only

In the ciphertext only variant, the analyst is assumed to only have access to a given amount of codetext or ciphertext generated by the system of interest.

Known Plaintext

In the known plaintext attack, the analyst has access to a given set of corresponding plaintext and ciphertext.

Chosen Plaintext

In the chosen plaintext attack, the analyst is able to obtain ciphertext on demand for arbitrary sets of plaintexts of his or her choosing.

Adaptive Chosen Plaintext

Similar to a chosen plaintext attack; however, the analyst is able to select subsequent plaintexts based on information learned from previous encryptions. A related attack is the adaptive chosen ciphertext attack.

Related Key Attack

The related key attack is similar to a chosen plaintext attack, except for the analyst being able to obtain ciphertext encrypted by two or more keys. The keys are not known in this attack; however, their relationship is known. A classic example of this attack is when there are two keys that differ by only one or two bits.

Categorizing Attacks by Computer Resources Required

Another common method to categorize cryptanalysis attacks is by the number of computational resource required to conduct the attack. These quantities can be difficult to predict when the attack on the cipher is not practical to implement for testing purposes. In academic circles, analysts typically provide an estimated order of magnitude of the attack’s difficulty. The classic standard that is considered a “Break” in the encryption is any technique that requires less computational resources than a brute force attack against the cipher. This is despite the fact that a “break” may still prove to be impractical in practice. At the time of this writing, the resources most commonly used to describe an attack include:

Computer Memory

The total amount of computer storage required to conduct the attack of the cipher.

Time

Time is typically represented by the total number of computational steps that must be performed to successfully crack the cipher.

Data

The total quantity of corresponding plaintext or ciphertext required to conduct a successful analysis of the cipher.

Advantage of Obtaining Partial Breaks in Ciphers

Over the course of time, analysts have discovered that even obtaining a partial break in a cipher can prove useful depending on the nature of the information being encrypted. Lars Knudsen is credited with classifying the different attacks available to conduct on block ciphers based on the total amount and quality of secret information discovered from attacking ciphers. These include:

Total Break

A total break results when an analyst is able to discover the secret key used in creating ciphertext from plaintext.

Global Deduction

In global deduction, an attacker is able to discover a functional algorithm that is equivalent to that being used for both encryption and decryption without ever discovering the secret key being employed.

Instance Deduction

In instance deduction the analyst is able to discover additional ciphertext or plaintext that was not previously known.

Information Deduction

In information deduction, the analyst is able to obtain Shannon categorized data about either plaintext or ciphertext that was not previously known.

Distinguishing Algorithm

The attacker is able to tell the difference between random permutations and the cipher.

What are Academic Attacks?

In cryptanalysis, academic attacks are typically undertaken against a weakened version of a cryptosystem. These can occur against a hash function with rounds removed or a block cipher. Many of these attacks become more challenging to conduct as additional rounds are added to a cryptosystem making reduced-round variants of the system weak. Over time; however, partial breaks of cryptosystems in academia which come close to breaking a full cryptosystem have indicated that a full break will eventually follow on the system. This was the case with early breaks of SHA-1, MD5, and DES that saw successful attacks on weakened versions of the system before full breaks were achieved.

Another difference in academia is that system breaks or weaknesses may require an impractical amount of resources to conduct the attack. Additionally, the study may only expose a small amount of information to prove the system is not perfect, but not prove useful to a real world attacker.

Cryptanalysis History

Throughout the history of cryptography, cryptanalysis has co-evolved through the contest tug-of-war of creating new ciphers to withstand attacks and the efforts to subvert new encryption methods. Today, modern ciphers are created hand-in-hand with efforts to crack the algorithm, code, or scheme before placing into service. Over the course of modern history, successful cryptanalysis has helped influence history as far back as the 1500s.

In 1587, Mary Queen of Scots was tried and executed for treason against the crown for her involvement in plots to assassinate Elizabeth I or England. Her role in these plans became knowledge of the crown after Thomas Phelippes was able to decode her correspondence with her fellow conspirators.

Fast forwarding to WW I, the breaking of the Zimmermann Telegram was key in bringing the Americans into the War. During World War 2, the Allied powers were able to obtain significant advantages over the Axis Powers through the successful cryptanalysis of German ciphers (Lorenz cipher and the Enigma machine) and the JN-25 and Purple ciphers of the Japanese. During the War, Ultra intelligence efforts in Europe have been given credit for ending the war up to two years early while “Magic” intel in the Pacific Theater had a similar result.

To this day, governments continue to recognize the benefits of leveraging cryptanalysis for both diplomatic, military, and commercial purposes. The U.S. NSA and the GCHQ remain very active in these fields today.

What are the Classical Ciphers?

Even though the term cryptanalysis was not “coined” until 1920 by William Friedman, the act of breaking codes and ciphers has been around since at least the 9^th century. In this timeframe, Al-Kindi, an Arabian polymath, wrote about the topic in A Manuscript on Deciphering Cryptographic Messages. His work included a method for conducting frequency analysis. Similarly, Italian scholar, Giambattista della Porta created a book on cryptanalysis, “De Furtivis Literarum Notis”.

Since this time, frequency analysis has become the core method for breaking the majority of classical ciphers. In most natural languages, there are letters that appear more frequently than others which allow analysis to be conducted on any code. For example, the most two common letters in combination in the English language are “TH” with “E” being the most common letter in any plaintext message. When conducted frequency analysis, the attack relies on the system or person conducting the encoding to not being able to hide these facts.

In the 15^th and 16^th centuries, a polyalphabetic substitution cipher was created by Frenchman, Blaise de Vigenère. For almost three hundred years, the Vigenère cipher that used a repeating key to choose different encryption alphabets was believed to be secure. In the 1800s; however, Charles Babbage and later Friedrich Kasiski were able to crack the cipher. Realizing the weaknesses in the repetition of characters in the Vigenère system, Arthur Scherbius crated the Enigma system based on a rotor cipher machine.

World War I and World War II Ciphers

Cryptanalysis played a significant role in the Allied victory in World War 2. The intelligence provided from Ultra provided significant advantages to the United States and United Kingdom commanders during the European Theater of war. Sir Harry Hinsley, official U.K. historian of British intelligence in WW2 went on the record stating that the access to information derived from Ultra sources helped to shorten the war “by not less than two years and probably by four years.”

On the scientific side of things, frequency analysis conducted during the war evolved from requiring an in-depth knowledge of linguistic knowledge to relying on advanced mathematics by the end of the war. The level of effort to crack Axis ciphers required new discoveries in mathematical techniques and automation. These efforts resulted in the development of the Colossus computers which were the first electronic digital computers to be controlled by a computer program and the Birtish Bombe device that used punch cards.

How Did Modern Cryptography Develop?

The U.K. Bombe device was able to replicate the output of several German Enigma machines that were wired together. Now residing in a Bletchley Park museum, the device was able to simulate the actions of an Enigma machine. Although this computation effort was used very successfully in cryptoanalyzing the Lorenz cipher and Enigma machines, the advances also permitted new methods of encoding information at complexity levels not seen before the war. Over the course of the computer age, the growth of cryptology-based systems has grown to the point, that many systems are almost impervious to traditional modes of attack.

Although developers of new systems prefer to tout the “death” of cryptanalysis, there continues to be successful advances in both academic and practical cryptoanalysis circles against modern ciphers. Of course, many break-throughs against today’s ciphers may not be read about for several decades until they are almost obsolete against the next generation of encryption.

Cryptanalysis Attacks against Symmetric Ciphers

A symmetric key algorithm is a class of cryptographic algorithm that uses the same key for encryption and decryption of plaintext and ciphertext respectfully. The keys can be the same or use a transformation to toggle between the two modes. The key represents a shared secret key between two or more organizations or individuals to help keep information secret. The primary drawback for symmetric ciphers is the reliance of a shared key. The following are many of the known attacks against symmetric ciphers:
Boomerang attack
Brute force attack
Davies’ attack
Differential cryptanalysis
Impossible differential cryptanalysis
Improbable differential cryptanalysis
Integral cryptanalysis
Linear cryptanalysis
Meet-in-the-middle attack
Mod-n cryptanalysis
Related-key attack
Sandwich attack
Slide attack
XSL attack

Cryptanalysis Attacks against Asymmetric Ciphers

Public key cryptography, or asymmetric cryptography, is one of the most used cryptographic systems in use today. The system relies on two keys, one that is private and one that is shared, or public. These ciphers rely on a difficult mathematical problem as the basis for the security of the cipher. The study in how to break an asymmetric cipher in cryptanalysis relies on significantly difficult mathematical research.

When a cryptologist looks to crack an asymmetric cipher, he or she will try to create an improved algorithm to solve the math problem posed by the cipher. In 1983, Don Coppersmith was able to discover a faster way to calculate discrete algorithms in certain groups which required cryptographers to use different types of groups or larger sizes. By 1980, an analyst could factor a 50 digit number at the cost of only 1012 computer operations. Computer technology allowed this same work to factor a 75 digit number. As technology continued to improve at the start of the 21^st century, 150 digit numbers were not considered a sufficient key size for asymmetric cryptography schemes. Unlike attempts to crack symmetric cryptosystems, cryptanalysis provides opportunities to use knowledge provided by public keys to obtain an advantage when attempting to crack asymmetric-based systems.