# A3/Attacks

A3

Communication
Introduction

Lektionen

There are different types of attacks to break an encryption in cryptography. We will explain some of the basic techniques.

Let us first note that for any message of finite length there is always a possibility to correctly guess the message, without breaking the code at all. This is highly impractical, as the success probability is astronomically low, but one should note that no cryptographic system can protect against this. Suppose, a message consists of N letters, each chosen from one of K different symbols, Then the probability to correctly guess the message is K^N. Suppose for example that a message consists of 5 letters from the English alphabet, then the probability of correctly guessing the message would be approximately 1 in 12 million.

Brute force

The simplest attack in to decipher a cryptogram is to try every possible key until one decodes to a valid message, which is referred to as a brute force attack. How successful this strategy is, depends on the code in question and the associated key space. The larger the key space is, the more tries it will take for the attacker to find the right key. There is also the possibility, that two different keys decode the cryptogram to a valid message. If this is the case, then the attacker can even with a brute force attack never be sure, which of the two messages was sent. In cryptography this is called a "collision", and it is highly desirable to use a code that has a high probability to produce collisions. The best example is the one time pad, which is guaranteed to produce the maximal number of collisions, simply as all messages are possible candidates for any cryptogram of the same length. The probability of finding the correct one is thus exactly equal to guessing the message without decoding in the first place.

Example

Let us reconsider the transposition code of the Caesar cipher. Here, each letter is transposed by a fixed number of steps in the alphabet. There size of the key space is 25 (one for every letter in the alphabet minus one, as a transposition by 26 steps would leave the message unchanged), so an attacker would have to try at most 25 different keys. The probability that this cipher produces a collision is effectively zero for any full sentence. On the level of single words, there are only few examples of terms in the English language that could lead to collision. For instance the cryptogram "ALIIP" could translate either to "wheel" or to "dolls".

Frequency analysis

This type of attack uses the fact that not all letters are equally frequent in the English language. This means that some letters will appear more often throughout a text then others. The letter "e" is the most frequent letter in English while the letter "z" is the most infrequent. To break a transposition cipher for example one would usually guess, that the most common letter in the cryptogram is actually the letter "e". This method can even be extended to incorporate combinations of letters or letter positions. For instance, the most frequent first letter is "t", the most frequent combination of two letters is "th".

Plain text attack

In this form of attack, Eve uses some prior information she has about the message. For example she could know that Alice will sign her messages with her name, or use a certain opening phrase. Knowledge of such structures in the cryptogram can severely reduce the key space that is compatible with the cryptogram.

Side channels

A different class of attacks are the so called side channel attacks. This class covers attacks that are not directed at the cryptogram, but towards the system that is implementing the cryptography. For instance an attacker could use prior knowledge about the (pseudo-) random number genitor used by Alice and Bob. Common internet attacks like viruses or Trojan horse attacks are also in this category. And finally, instead of breaking the encryption an attacker could try to threaten or bribe an employee of Bob with access to the information to steal it.