Crypto Series: WWII – Enigma

With this post we're leaving classical pencil and paper ciphers and getting into the mechanic ciphers used during the World War II era. We're gonna see the most famous of the cipher machins, the Enigma machine used by the Germans. Our analysis will be based on the book Applied Cryptanalysis from Mark Stamp and Richard M. Low. A very recommendable book if you are interested on cryptanalysis, really.

The Enigma Machine

The Enigma machine was developoed and patented by Arthur Scherbius in 1918, and was adopted by the nazi Germany for military and diplomacy use. Polish cryptanalysts broke the Enigma cipher in the late 1930s, and Allieds exploited this knowledge during WWII.

Máquina Enigma

It is said that thanks to Enigma being broken without the Germans noticing it (thanks to the more or less careful use of the obtained intelligence) the WWII was shortend one year or even more. There has been a lot of writing around Enigma, and I'm not an expert in the field, so I refer you to Google if you want more historical information 🙂

Encrypting and decrypting with Enigma

To encrypt with Enigma, after initializing the machine with the key as we'll see later, one simply had to press the plaintext letter to encrypt in the keyboard, and then the corresponding ciphertext letter would be enlightened in the upper (back-lighted) keyboard.

To decrypt, one had to set the machine into the corresponding state and press the received ciphertext letter. Then, in the upper keyboard the plaintext letter would get enlightened.

Enigma's features

Enigma was an electro-mechanical machine, based on the use of rotors. In the previous figure, one can easily see the mechanical keyboard and the back-lighted keyboard, which worked as input and output of the device.

Further, there is what seems to be a switchboard (stekker in German) with cables connecting one of the ends with another, and three rotors in the upper side of the machine. The configuration of these rotors and the cables of the stekker are the initial key of the machine.

Once the machine was initialized, it was possible to press in the keyboard the plaintext or ciphertext letters and obtain the ciphertext or the plaintext respectively. The workings of the machine were essantially as follows:

After pressing a key in the keyboard, a signal was sent through the corresponding stekker pin. Thanks to the cable configuration, this signal was transmitted to a different letter. Thus, the stekker worked as a mapping in the alphabet, where each letter was substituted by another one: a simple substitution.

Rotores de la máquina Enigma

After it, the signal went through the three rotors, reflected in the reflector and went back through the rotors (see figure). Finally, from the rotors it went again through the stekker, which performed a new substitution, and turned on the backlight of the corresponding letter. The net effect of the rotors and the reflector was again a permutation: each letter was converted into a different one.

However, if this were it, we would have no more than a simple substitution, with the only complexity of the use of an electromechanical machine. What Enigma added was a variation of the disposition of these rotors.

Each time a key was pressed, the rightmost rotor stepped one position. The middle rotor stepped in an odometer-like fashion, each time the rightmost rotor went through all of its steps. The leftmost rotor stepped in the same way, but depending on the middle rotor.

Further, it was possible to select the point where each rotor would step. This means that it could be when the previous rotor reached the initial position, but it could be in a different position. We could set it, for instance, to step when the previous rotor had stepped 5 times. From there on, it would step every time the initial rotor was in that position.

Therefore, Enigma was a cipher where each letter was encrypted with a different simple permutation of the alphabet... but with an enormous number of possible permutations.

For a more detailed analysis of the Enigma machine, please refer to the aforementioned book, where the way the machin works is analysed, the key space size (i.e. number of possible keys) is computed and an attack is presented.

Crypto Series: Vigenère’s Cipher (2)

As I promished, we're gonna see a different method to obtain the key length used to encrypt a text using Vigenère's algorithm. This is a method somewhat more difficult to understand than Kasiski's method, since it requires some mathematical analysis to obtain the recipe.

Friedman's test or the incidence of coincidences

This method, discovered by William F. Friedman in the 1920s, is based on computing the index of coincidences of the cryptogram's letters. The idea is that for two random letters from the cryptogram to be the same, there is a possibility that they were also the same in the original plaintext if the number of letters they have in between is a multiple of the key length.

Basically, we'll take the X first letters of the cryptogram and the X last letters, and count the number of coinciding letters in the same position. Finally, we'll divide this number by the number of letters taken and then we will have the index of coincidence.

Considering a source providing independent characters with the frequency distribution of English, and uniformly distributed characters for the key (i.e. all letters with the same frequency, 1/26 for the English alphabet), we have that:

• The probability that any two letters are the same is approximately 0.0385 when X is not a multiple of the key length
• The probability that any two letters are the same is approximately 0.0688 when X is a multiple of the key length.

So, with this process wi can determine that high values for the index of coincidence will mean that the shifted distance X is a multiple of the key length, and this way we will determine the most likely key length.

Let's see how we get these probabilities, so that we are able to obtain them in case of having a language different than English. We simply have to consider that for any two ciphertext characters and to coincide, the following relation must hold:

Then, we consider two different cases: if L divides i-j, then , since in that case we have that  . So, the probability for this case is:

However, when i-j is not a multiple of L, then for the two ciphertext characters to be equal the following equation needs to hold

But as we said before, the distribution of key characters is uniform, and therefore this probability is:

That's it for today. This time there is no example, but stay tuned cause we'll see an exercise soon 🙂

And I hope next week I'm able to post some practical exercise using Cryptool to analyze a Vigenère cipher or something alike.

Crypto Series: Classical ciphers

During some posts we're gonna get introduced into classical ciphers. From Wikipedia, "a classical cipher is a type of cipher used historically but which now have fallen, for the most part, into disuse".

This post will study one of the most known classical ciphers, the Caesar cipher, and other similar ciphers.

Caesar Cipher

Caesar's cipher, named after Julius Caesar, is a substitution cipher that simply substitutes each letter by the letter K positions to the right in the alphabet. So, for a K value of 3, A would be encrypted as D, B as E, C as F and so on.

In mathematical terms, considering an alphabet with 26 letters, where A would be letter 0 and Z letter 25, we can define these encryption and decryption operations as:

Where means reducing the result modulo 26, or in simpler terms, if the result is above or below the 0-25 range, we would add/subtract 26 as many times as needed to make it fall into this range.

As you can see, very simple. For instance, if we encrypt the sentence CRIPTOGRAFIA PARA TODOS under key 5, we get the following ciphertext: HWNUYTLWFKNF UFWF YTITX.

Here we can already see one of the weaknesses of this cipher: the structure of the plaintext remains. As you can see, last word in the message starts with a Y, then it has two T's, one I and one X. Therefore, we know that this word has the second and fourth letter identical. Also second and fourth letters are identical in the second word, but different to the ones in the last word.

This, in a large text and within a context, could lead us to decipher great part of the text. For instance, knowing that it's a text about information security, we can try to find words with the same structure as security or information and map these letters for all the text. With this, we would have parts of other words, and with some luck we would be able to obtain more letters by guessing those words. Continuing like this, at the end we would have the complete text.

Another tool that allows us to easily analyse this kind of ciphers is frequency analysis, which we mentioned previously. If we take a text encrypted using this system and count the number of appearances of each letter, and then obtain (or generate) a table of relative frequencies for the target language, we can match the most frequent letter in the ciphertext and the most frequent letter in the target language.

Then, since the same shift is applied to all the letters, we would have the key and would be able to obtain the complete message. In case of getting a non-sense message, we could try with the second most frequent letter instead of the first one. Since it's a statistical analysis, it's possible that the character distribution in our text doesn't completely match the original distribution, but will certainly be similar.

Simple substitution ciphers

Caesar's cipher we just analysed is one of the so-called simple substitution ciphers, which always substitute each symbol of the input alphabet by a given symbol of the output alphabet.Besides Caesar's cipher, Atbash cipher is another quite famous substitution cipher, where each the alphabet is inverted: A->Z, B->Y, ... Y->B, Z->A.

But not only these two simple substitution ciphers exist. We can create any modification of the input alphabet as output alphabet. Even then, all these ciphers suffer from the same problem: the structure is maintained and they are quite easy to break using frequency analysis and word matching.

Example: Breaking a simple substitution cipher

This time I encrypted an English text. This is how the ciphertext looks like:

ZL VAGRERFGF NOBHG FRPHEVGL ERYNGRQ GBCVPF UNIR QEVSGRQ N YVGGYR OVG, ZBIVAT SEBZ CHER FBSGJNER NAQ ARGJBEXVAT FRPHEVGL GB PELCGBTENCUL NAQ CENPGVPNY NGGNPXF BA PELCGBTENCUVP VZCYRZRAGNGVBAF, YVXR FVQR PUNAARY NANYLFVF NGGNPXF.

VA GUVF EROBEA OYBT V JVYY GEL GB VAGEBQHPR GUR ERNQREF VAGB GURFR GBCVPF JVGUBHG TRGGVAT VAGB GBB PBZCYRK ZNGUF. GUR NVZ VF GB CEBIVQR NA HAQREFGNAQVAT BS PELCGBTENCUL JVGUBHG UNIVAT ERNQREF YBFG BA ZNGURZNGVPNY PBAPRCGF. LBH JVYY GRYY JURGURE V NPUVRIR GUVF TBNY BE ABG.

Looks pretty complicated, doesn't it? Let's see how to approach this example, assuming this is a simple substitution cipher. First of all, we're gonna count how many times appears each letter, and then divide it by the total number of letters. I've done it with this simple program I quickly coded, although it's possible to do it with Cryptool but I don't have it available right now.

Once it's done, we sort it by frequency. For instance, copy-pasting the output of the program into a spreadsheet in Google Docs and pressing order by the corresponding column. The top 3 letters are:

G     52    0.124402

R     38    0.090909

V     37    0.088517

So, we go to a frequency table for English (here) and see that E is the most frequent letter in this language. Now we subtract 'G'-'E'=7. If we apply this key using a Caesar's cipher, we just get garbage. However, if we take 'R' as 'E, then 'R'-'E'=13. Deciphering using Caesar's cipher, we get:

MY INTERESTS ABOUT SECURITY RELATED TOPICS HAVE DRIFTED A LITTLE BIT, MOVING FROM PURE SOFTWARE AND NETWORKING SECURITY TO CRYPTOGRAPHY AND PRACTICAL ATTACKS ON CRYPTOGRAPHIC IMPLEMENTATIONS, LIKE SIDE CHANNEL ANALYSIS ATTACKS.

IN THIS REBORN BLOG I WILL TRY TO INTRODUCE THE READERS INTO THESE TOPICS WITHOUT GETTING INTO TOO COMPLEX MATHS. THE AIM IS TO PROVIDE AN UNDERSTANDING OF CRYPTOGRAPHY WITHOUT HAVING READERS LOST ON MATHEMATICAL CONCEPTS. YOU WILL TELL WHETHER I ACHIEVE THIS GOAL OR NOT.

Much more readable 🙂 Don't you recognize it? Look at http://www.limited-entropy.com/en/about 🙂

We've decrypted the text, although not at our first try, but at our second. Another option would have been using 'G' as 'T', since T is the second most frequent letter in English. The result is exactly the same.

However, facing an unknown transformation, we would have been to play with other hints besides frequency analysis. For instance, we could use the fact that we expected to see CRYPTOGRAPHY in the text, and assign this word to the only word in the ciphertext that has the same letter in the third and the last position. Then, we would substitute all its letters in the ciphertext and would see if it makes any sense.

From there, we just need to continue on guessing letters... kind of a puzzle 🙂

That's it for today, I hope you're liking it :). Questions and comments are more than welcome!

Crypto Series: Classification of Attacks

As a quick note on the cryptographic systems description on the previous post, I'd like to mention that atacks to cryptosystems are usually classified based on the information known to the cryptanalyst. The basic types of attacks are:ásicos son:

• Ciphertext-only: The cryptanalyst knows only the ciphertext, and often also some information about the context of the message.
• Known-Plaintext: The cryptanalyst knows pairs of plaintexts and corresponding ciphertexts.
• Chosen-Plaintext: The cryptanalyst is able to choose plain texts and obtain their corresponding ciphertexts.
• Chosen-Ciphertext: The cryptanalyst can choose any ciphertext and obtain its corresponding plaintext.

Although the final two kinds could seem to be identical, there is a big difference mainly when applied to public key algorithms. In these algorithms, it is usually very easy to encrypt any plaintext. Thus, these algorithms need to withstand chosen-plaintext attacks. However, a chosen-ciphertext attack would require a decryption oracle, which would return any ciphertext decrypted without exposing the decryption key.

Crypto Series: Introduction – Basic Concepts

Before getting into matter, we're gonna see the basic concepts on which great part of the text is going to relay on. Don't be scared, they are very basic :-). These are the definitions:

Cryptography is the science studying information protection, both unauthorized accesses/uses and modification of the information. Cryptography is only about using algorithms to protect this information, while Cryptanalysis is about studying techniques to break this protection, those algorithms designed by cryptographers. It's clear that both sides are intimately related, and both of them are grouped in what is known as Cryptology.

A Cryptosystem is made of the following components:

• Messages: The group of all the messages that one can encrypt. Also known as plaintext.
• Ciphertexts: The group of all encrypted messages.
• Keys: The group of all the secrets that can be used to obtain a ciphertext from a plaintext.
• Encryption and Decryption algorithms: The algorithms or transformations that need to be applied to a plaintext in order to convert it into a ciphertext or back, using a secret key.

Un Criptosistema o Sistema Criptográfico consta de los siguientes componentes:

• Mensajes: Es el conjunto de todos los mensajes que se pueden cifrar. El llamado texto en claro o plaintext.
• Criptogramas: El conjunto de todos los mensajes cifrados. En inglés llamado ciphertext.
• Claves: El conjunto de secretos que se pueden utilizar para obtener un criptograma en base a un mensaje.
• Algoritmos de cifrado y descifrado: Los algoritmos o transformaciones necesarias para convertir un mensaje en su correspondiente criptograma y viceversa, haciendo uso de una clave secreta.

So, given a cryptosystem with its encryption algorithm, which we denote as , and its corresponding decryption algorithm ( ), the following equation must hold:

Where k y k' are the corresponding encryption and decryption keys. These keys might be identical (symmetric crypto) or different (asymmetric crypto), as we'll see later.

This means that when you decrypt a message encrypted under key K using its corresponding decryption key K', you obtain the original message. Obvious, isn't it?

The figure below shows the conventional cryptosystem as depicted by C.E. Shannon in its book Communication Theory and Secrecy Systems.

Cryptosystem scheme

Finally, to finish this post about basic concepts, we'll see how to statistically characterize a message source. Statistical characterization of a language is a quite powerful tool on its own when it's about analyzing a cipher, specially in case of basic ciphers as we'll see in the next post.

Let's imagine a message source that produces messages in a given language, for instance Spanish. We can try to characterize the source by  means of the probability that a certain character appears in the text, independent of the rest of the text.

Thus, a character c would appear with a probability . With this characterization, the word hola would appear with a probability of:

A slightly more powerful option would be characterizing the language as a series of bi-grams (i.e. groups of two characters) with a given probability. In this case, the word hello would have the following probability:

However, this option besides being an identical concept to the former one, requires of much bigger frequency tables and more effort to characterize the message source.

A question that might arise now is how would we manage to  obtain a table of relative frequencies for each one of the letters. Basically, we would take a sufficiently large text in the given language and count the number of times each letter appears. Then we divide this number by the total of letters in the text, and get its relative frequency. Frequency tables can be seen in Frequency Analysis [Wikipedia].

Next time we'll see how this frequency characterization with independent charactes can be useful to break basic ciphers.