CRYPTANALYSIS

It is beyond the scope of this essay to deal with all types of cryptanalysis so I will give a brief overview and an example of where cryptanalysis has been successful. Unlike cryptography which is a clearly defined science, cryptanalysis is as much an art as it is a science. Success in cryptanalysising a cipher is a flash of inspiration almost as often as it the result of using crytanalysis techniques alone.

Types of Cryptanalysis

There are several distinct types of cryptanalytic attack. The type used depends on the type of cipher and how much information the cryptanalyst has.

Types Of Cryptanalytic Attacks

A standard cryptanalytic attack is to determine the key which maps a known plaintext to a known ciphertext. This plaintext can be known because it is standard or because it is guessed. If the plaintext segment is guessed it is unlikely that its exact position is known however a message is generally short enough for a cryptanalyst to try all possible positions in parallel. In some systems a known ciphertext-plaintext pair will compromise the entire system however a strong encryption algorithm will be unbreakable under this type of attack.

A brute force attack requires a large amount of computing power and a large amount of time to run. It consists of trying all possibilities in a logical manner until the correct one is found. For the majority of encryption algorithms a brute force attack is impractical due to the large number of possibilities.

Another type of brute force attack is a dictionary attack. This essentially involves running through a dictionary of words in the hope that the key (or the plaintext) is one of them. This type of attack is often used to determine passwords since people usually use easy to remember words.

In a ciphertext only attack the cryptanalyst has only the encoded message from which to determine the plaintext, with no knowledge whatsoever of the actual message. A ciphertext only attack is presumed to be possible, if not easy. In fact, an encryption techniques resistance to a ciphertext only attack is considered the basis for its cryptographic security.

In a chosen plaintext attack the cryptanalyst has the capability to find the ciphertext corresponding to an arbitrary plaintext message of his or her own choosing. The likelihood of this type of attack being possible is not much. Codes which can survive this attack are considered to be very secure.

In a chosen ciphertext attack the cryptanalyst can choose an arbitrary ciphertext and find the corresponding decrypted plaintext. This attack can be used in public key systems, where it may reveal the private key.

In an adaptive chosen plaintext attack the cryptanalyst can determine the ciphertext of chosen plaintexts in an iterative process based on previous results. This is the general name for a method of attacking product ciphers called "differential cryptanalysis".

Frequency Tables

The cryptanalysis of single-key cryptosystems depends on one simple fact - that some traces of the original structure of the plaintext may be visible in the ciphertext. For example, in a monoalphabetic substitution cipher where each letter in the plaintext is replaced by a letter in the ciphertext which is the same each time, a simple analysis of a sizeable portion of ciphertext can be used to retrieve most of the plaintext.

Here is a monoalphabetic substitution cipher of a random paragraph of English:

UFMDHQAQTMGRG BX GRAZTW PWM

UFMDHBGMGHWOG VWDWAVG BA BAW

GRODTW XQUH AQOWTM HCQH HFQUWG

BX GHFIUHIFW BF DQHHWFA RA HCW

DTQRAHWLH OQM GIFJRJW WAUFMDHRBA

QAV SW VRGUWFARSTW RA HCW

URDCWFHWLH.

W occurs 20 times in the cipher, H occurs 16 times. From this information and using the frequency table to the left it would be possible for a cryptanalyst to recover the majority of the plaintext. The usefulness of analysing the structure of the ciphertext can be reduced by any encryption procedure that attempts to disguise the structure. However, eliminating the underlying structure is harder than it would first seem. Digraphs, for example, show a strong frequency distribution - TH occurs very often, about 20 times more often than HT and so on. With tables of digraph frequencies it is possible to recover the underlying plaintext, however, the amount of ciphertext required would be much greater. In the heyday of manual cryptanalysis huge volumes of word patterns were compiled. Although these only contained the most obvious and easily recognised word patterns they were still of importance if they could provide that vital clue which could break the entire cipher.

Cryptanalysis Of Public Key Ciphers

Public key cryptography requires a fundamentally different type of cryptanalysis than is used for single key cryptanalysis. Because public key cryptography relies on "hard" mathematical problems, their cryptanalysis is essentially research into solving the underlying mathematical problems. Cryptanalysis of public key ciphers is therefore virtually indistinguishable from research into any other area of mathematics.

For example, to "crack" the RSA algorithm and obtain the private key from the public key would essentially involve research into factoring algorithms. Factoring is a very active field of research among mathematicians and computer scientists. The best general-purpose factoring algorithm today is the Number Field Sieve but even so, the running time to search through all the possibilities is very long.

In 1980 it was possible to factor a 50-digit number with 1,000,000,000,000 computer operations. By 1984 factoring algorithms had advanced to the stage where a 75-digit number could be factored in the same number of operations. If a mathematical advance was made which enabled a 150 (or more) digit number to be factored in the same number of operations it would allow cryptanalysts to break many RSA implementations.

A Triumph of Cryptanalysis - Enigma

No look at cryptanalysis, however brief, with even the slightest element of historical content, could finish without at least briefly covering the tale of how the Enigma was broken.

What Was Enigma?

The efficiency of the German armed forces during World War 2 would not have been possible without radio communication. Messages sent over the radio had to be encrypted and the encryption system they used was adapted from one which was commercially available before the war. Despite the fact that it was modified so as to make it harder to crack it was broken by a group working at the GCHQ.

The Enigma machine consisted of a 26 letter keyboard for input. The output was read off 26 lamps which each corresponded to a letter. The encipherment was performed by a device called a "scrambler" that was made of three rotating wheels on a common spindle and a plugboard known as a "Steckerboard" that added an additional level of security.

The keyboard and lampboard were both connected to a common cabling bus. When no keys were being held down all the lamps were connected to the bus and the current present on any particular wire would cause its lamp to glow. When a key was pressed a current was placed on its wire but the corresponding lamp was disconnected from the bus.

Since no letter could ever be enciphered to itself this was a good set-up. When a key was pressed one wire on the bus would have current applied to it and the other 25 could respond with the enciphered letter. The one that actually did respond was the result of the other components.

The original, commercial, Enigma did not have the plugboard. The 26 wire bus was connected to a circular set of contacts that sat to the right hand side of the three rotor scrambler. These three rotors were identical except in their internal wiring. The rotors had two sets of 26 connectors, one on the left and one on the right. All three rotors had to be rotated by hand and by doing so the "key" could be changed. Because each rotor could be set independently there were 26 ´ 26 ´ 26 (17576) possible rotor settings. This would not have provided a secure ciphering system so every time a key was pressed one of the rotors (known as the "fast" rotor) was advanced one position so that even if the same key was pressed three times the result would be three different characters. When the fast rotor got to a certain position it would cause the middle rotor to be rotated to one position, which in turn could cause the slow rotor to move one position.

Initial Work On Cryptanalysing Enigma

The initial work on cryptanalysing Enigma was done by the Polish. The earliest Polish work on the intercepting German machine ciphers had begun in 1928, right after the systems introduction by the German Army. However, no progress was made during the first four years. Then the Polish Cipher Bureau decided to recruit three young mathematicians. Among them was Marian Rejewski. On September 1, 1932 Rejewski and his two somewhat younger colleagues began work at the Cipher Bureau in Warsaw. In early October Rejewski began work on the Enigma and was supplied with an obsolete commercial Enigma machine which had been brought in Germany.

The whole, complicated process of mastering the German Enigma was ultimately concluded in the early days of 1933. This included combinations of mathematics, statistics, computational ability and guesswork. The breaking of Enigma involved two distinct processes. The first was the theoretical reconstruction of the Enigma cipher device itself including the internal wiring and the interdependence between different components of the machine. This knowledge of the machine enabled the Poles to build doubles of the Enigma, The second was the creation of methods for recovering the Enigma keys (starting positions) based exclusively on the basis of intercepts.

At the beginning of the second world war, realising that a German invasion was imminent, the Polish handed over all the information including the duplicate Enigma models over to the British.

What Made It Possible?

With the level of sophistication of the Enigma machines it should have been unbreakable. However, the Germans had a number of procedural flaws which allowed the British and Polish to break the cipher.

Some of these were just stupid. For example, the Germans reused the monthly code book settings. Others were less obvious. It was discovered that the German military messages were very similar in nature and, once they were decrypted, very careful records were kept regarding how the messages tended to be formatted. When the British thought they had a likely idea of what the start of the message was, they would use this to reduce the many trillions of possible Enigma settings to a small enough number to be tested individually.

The Turing Bombe

The design of the Turing bombe is normally credited to two British mathematicians - Alan Turing and Gordon Welchman, working in secret at Bletchley Park. The information handed over to the British by the Polish was much more advanced than anything the British (or anyone else) had accomplished . One of the things the Polish had developed was a machine they called a Bomba (the Polish word for bomb - probably named because of the ticking sound it made). The Polish machine and the British one worked on different algorithms but were mechanically very similar. This provided Turing with a starting point.

The Bombe was effectively a collection of Enigma machines that were all working together. According to Welchman there were twelve sets of Enigma rotors in the Bombe, but there is also other evidence that larger Bombes existed. None of the Bombes survived the war so it is difficult to be sure.

The theorem the Bombe was based on the loop that exists between the crib (a guessed sequence of letters) and the equivalent cipher text. The method Turing devised to test this was based upon the mathematical technique reductio ad adsurdum. For every one of the possible rotor settings Turing would start by assuming that this was the correct setting and then try to disprove this. If the procedure did disprove the setting the machine would automatically advance to the next setting to be tested. If it did not the setting was recorded, and then the procedure continued to try and find other possible settings.