Linear Feedback Shift Registers (LFSRs)

In this post I'll provide a very simple description of linear feedback shift registers (LFSR for short). Further, we'll see how they are used to create stream ciphers. And all these things without going into mathematical details, for which I refer the interested reader to documents such as the Handbook of Applied Cryptography or this LFSR Reference.

Shift Registers

A shift register is basically a construction with interconnected several memory cells, where every cell stores one bit. So, the value of these cells conforms the so-called state of the register. When the register steps from one state to the next one (usually at each clock tick), the new state is created by simply shifting the bit in a cell to the cell next to it. Thus, the right-most bit goes out of the register, and a new bit goes into the left-most cell.

In this picture we can see an implementation of a 4 bit shift register:

Shift register

We can see an input line (Data in), 4 points where one can read the current state (Q1-Q4) and a clock input, which governs the register telling it in which moment it should step into the next state.

Linear Feedback Shift Registers (LFSRs)

Well, once you know what a shift register is, it is fairly straightforward to understand how a LFSR works. We just take the previous register and set the input as a linear combination of the different cells. Since there is a loop which feeds the register based on its previous state, we have feedback. Further, since this feedback is based on a linear function, then we have linear feedback, hence the name .

LFSR

LFSRs' use in cryptography

So far, you probably have guessed that the main use of an LFSR in encryption systems is generating a series of pseudo-random bits to be used as a key stream in a stream cipher.

The idea is to generate a stream of bits with the minimum repetition possible, i.e. with maximal period. For its study, the connections in an LFSR are usually represented as a polynomial and the properties such a polynomial needs to meet to achieve maximal period are analyzed.

Basically, we need to get the LFSR to run through all its possible states before going back into the first one. So, if we have 16 bit registers, we'd want to have the LFSR pass through the 2^16-1 states before cycling back to the first one. And yes, I said 2^16-1 instead of 2^16 because the zero state should never appear. Otherwise the LFSR will never leave this state, since the feedback function is linear. For the curious readers, an LFSR will have maximal period if its generating polynomial is a so-called primitive polynomial (I'm pretty sure this name will ring a bell for some of you guys, although maybe not as a happy memory ).

Setting aside the study of these polynomials, which involves somewhat comlex maths (to my non-mathematician opinion ), an LFSR by itself should not be used as a key stream generator because its properties make it fairly predictable. In fact, given an n bit LFSR, obtaining 2n bits of its output it is possible to recover the generating polynomial and be able to decrypt any subsequent text.

Therefore, LFSRs are not directly used in crypto, but they are generally used in one of these modes:

• Nonlinear combination of LFSRs: the output from several LFSRs is combined in a non-linear fashion to obtain a key stream.
• Nonlinear filter generator: the output is generated from a non-linear combination of the state.
• Clock-controlled generators: In this mode, several LFSRs step based on some rules, instead of stepping for every clock cycle.

With this kind of constructions it is possible to improve LFSR's properties for the creation of secure stream ciphers. And that's it for LFSRs from my side, for more information refer to these references:

Handbook of Applied Cryptography

LFSR Reference

LFSR @ Wikipedia

Crypto Series: Introduction to stream ciphers

Today we're gonna step a little further in our Crypto series. We'll see the main properties of the so-called Stream Ciphers, how they work and some things that should be taken into account when they are used.

Later in this series, we'll see how Linear Feedback Shift Registes (LFSR) work and we'll see one of the most used stream ciphers, together with an example of wrong usage.

Keep on reading to learn more about this class of ciphers.

Crypto Series: Block ciphers

In this entry we introduce block ciphers in a general way, as well as its modes of operation. Further, we'll see how to generate message authentication codes (MAC) using block ciphers.

Block ciphers

As we already said in the previous entry, block ciphers are symmetric ciphers which encrypt fixed length blocks. Therefore, a block cipher generally applies a series of operations combining the input block and the secret key (which isn't necessarily the same length) to obtain the output block (ciphertext).

Since they are symmetric, the decryption primitive uses the same key as the encryption primitive, and applies the operations needed to get back the plaintext at its output:

Most block ciphers can be classified as product ciphers or iterative block ciphers, based on a series of basic operations (rounds) which are repeated a number of times. These rounds provide confusion and difusion to the cipher, two concepts identified by Shannon in his famous treaty about communication theory.

Confusion refers to breaking the relationship between ciphertext and key as much as possible, while diffusion refers to destroying the statistical characteristics of the message source. Shannon identified these concepts and established the need for a secure cipher to provide them.

These kind of ciphers are generally Substitution-Permutation Networks (SPN), where several permutations (scrambling) and substitutions (changing values for others) take place one after the other, using a key, trying to achieve the goal: destroy the statistical properties of the source and obtain a secure cipher.

In subsequent entries we'll see how DES and AES, two well-known symmetric encryption standards, work. The remaining of this article treats block cipher modes of operation and how to authenticate messages using these ciphers.

Crypto Series: Introduction to Cryptool

In this post we'll see some of the options provided by Cryptool to analyze classical ciphers, as well as using it for breaking a ciphertext encrypted with Vigenère's cryptosystem.

First step, as usual, consists of installing Cryptool. To that end, I chose using a virtual machine in VMWare with Windows XP. The installation is very simple, typical Windows app installation: Next, Next,... We'll use the English version, which is the one I have installed, but it shouldn't be difficult to follow our steps with a different version.

Once installed, this is how the main window of Cryptool looks like:

Cryptool's main window

Looking at the menus, one can see that Cryptool offers (amongst others) the possibility to encrypt and decrypt texts, cryptanalytic tools and guided tutorials. In this text we'll see how to use Cryptool for analyzing encrypted texts... Let's start with an easy one:

Gznyrém xlmlxrwz xlnl Fmrevihrwzw Klorgéxmrxz wv Ezovmxrz, l vo
Klor kziz olh znrtlh, vh fm lhxfil oftzi oovml wv vhgfwrl b kvievihróm.
Hlyivglwl, klijfv glwl zjféo ol hfurxrvmgvnvmgv olxl xlnl kziz vmgizi
vm vooz, gvmwiá jfv szxvi zotl wv ol zmgvirlinvmgv xrgzwl kziz hzori
zrilhl wv vooz. Vmgiv olh oftzivh náh xlmxfiirwlh, hv vmxfvmgizm oz
Xzhz wvo Zofnml (szyrgfzonvmgv fhzwz kziz wlinri olh qfvevh wv
nzwiftzwz, kvil gznyrém kziz qftzi z yroozi l ufgyloím, zfmjfv mlh
jfrgzm vhgv vm éklxz wv vcánvmvh), oz Yryorlgvxz (wlmwv oz tvmgv hv
wrervigv vhgfwrzmwl), b ozh krhgzh wv gvmrh b káwvo.

The text has been obtained from IEEE's cryptography challenge, by Javi Moreno and Amine Tourisa (sorry, Spanish). Actually, the solution was already published in Javi's blog, but we're gonna see how to obtain it with Cryptool:

• Create a new document ( File | New )
• Copy the text from the challenge
• Go to Analysis | Tools for Analysis | Histogram

Now we get the following frequency diagram from the text:

Frequency analysis of the ciphertext

Next we just compare this diagram with the typical one from Spanish or English, and we can see that it's simply been 'mirrored'... easy, isn't it? So the answer is, as you probably guessed, ATBASH. Decrypting the text with ATBASH (Crypt/Decrypt | Symmetric (Classic) | Substitution/Atbash ... ) , we get this cleartext (again, Spanish):

También conocida como Universidad Politécnica de Valencia, o el Poli para los amigos, es un oscuro lugar lleno de estudio y perversión. Sobretodo, porque todo aquél lo suficientemente loco como para entrar en ella, tendrá que hacer algo de lo anteriormente citado para salir airoso de ella. Entre los lugares más concurridos, se encuentran la Casa del Alumno (habitualmente usada para dormir los jueves de madrugada, pero también para jugar a billar o futbolín, aunque nos quitan este en época de exámenes), la Biblioteca (donde la gente se divierte estudiando), y las pistas de tenis y pádel.

Now we'll see how to solve a Vigenère encrypted text. Let's take as our working example the following text:

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!