Cryptography is made of two words: crypto means “hidden,” and graphy means “writing.” It is hiding and securing the information and data using codes and other means so that only the receiver can understand the message, not the attackers. In this article, you will learn about algebraic attacks and algebraic attacks on a filter generator.

Stream Ciphers

Stream Ciphers are an essential part of symmetric (secret key) Cryptography. In these ciphers, only one bit (each character) is encrypted at a time. Encryption of the character depends on the key, the character, and the current state of stream ciphers, due to which these ciphers are also termed “state ciphers .”With time, the transformations of the cipher vary.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Algebraic Attack

There have been several recent attacks on cryptosystems using algebraic attacks. These attacks can be launched against various types of stream and block ciphers. These attacks are made for deducing the secret key by solving the system on non-linear equations which involve message, information, and the ciphertext.

A new “Relinearization” algorithm was found for solving the system of non-linear equations over finite fields and attacking the public key cryptosystems.

Algebraic Attack on Stream Ciphers

In stream ciphers, an algebraic attack is known as a plaintext attack. In this, the attacker knows some bits of the plaintext beforehand. These bits do not need to be consecutive. Also, corresponding bits of the ciphertext at some positions are known to the attacker.

Linear Feedback Shift Register

There are various constituents in the construction of the stream ciphers. One of the well-known classes of stream ciphers is the one that contains ciphers based on the linear feedback shift registers (LFSR).

A linear feedback shift register (LFSR) with length L consists of L stages numbered 0, 1, . . . , L − 1. Each of these stages can store one bit and has one input and one output. There is a clock that controls the movement of data. With each unit of time, the following operations are performed:

A part of the output sequence is the content of stage 0

For each i, 1 ≤ i ≤ L − 1; and 10, the content of stage i is moved to stage i − 1

The new content of stage L−1 is the feedback bit s_{j} which is calculated by a feedback function f(s_{0}, s_{1}, . . . , s_{n-1}). It is equal to the addition of the previous contents of a fixed subset of stages modulo 2.

If the content of stage i is s_{i} ∈ {0, 1} for each 0 ≤ i ≤ L − 1, then S = (s_{0}, s_{1}, . . . , s_{L-1}) is called the state of the LFSR.

Non Linear Filter Generator

A non-Linear Filter Generator is one of the two large classes of stream ciphers based on LFSRs. It combines a linear feedback shift register (LFSR) and a non-linear Boolean function.

A non-linear filter generator is a stream cipher that starts from an initial state S = (s_{0}, . . . ,s_{n-1}) ∈ F_{2}^{n} and, at each clock t ≥ 0, produces a keystream bit z_{t} = F (Lt(S)), where

L: F_{2}^{n} → F_{2}^{n} is the linear update function;

F ∈ B_{n} is the nonlinear output function.

F is called the filter function.

Method of Generating System of Equations

The LFSR stream cipher can be easily attacked by solving a system of linear equations. Whereas, if a non-linear filter generator is used for generating a keystream, it would be difficult to attack the system because here, you need to solve a system of polynomial equations in several variables.

For solving the set of polynomial equations, let us consider an example -

If the attacker wants to attack, then knowing the initial state of LFSR is the secret key. Let’s suppose that he knows the recurrence relation of the LFSR. Also, he knows the filtering function. For instance, taking the initial state as (z_{0}, z_{1}, z_{2}, z_{3}) = (1, 0, 0, 0), which satisfies the recurrence relation z_{n+4} = z_{n+1} + z_{n} for n ≥ 0 and the filtering function f(z_{0}, z_{1}, z_{2}, z_{3}) = z_{0}z_{1}+z_{2}z_{3} for generating the output bit from each state.

Using the output bit, you can derive the equations having initial states - z_{0}, z_{1}, z_{2,} and z_{3} as variables. Look at the image below, which shows how to calculate the polynomial equations.

Step 1: Take the given filtering function (f) and recurrence relation

Further, one can do all the calculations like this. The results of every calculation are:

Step 5: Put the values of all the variables in the equations obtained as shown in the image above.

Since, there are four initial variables z_{0}, z_{1}, z_{2} and z_{3}, there are 10 possible equations.

Step 6: As the result of the operation carried out by updating every state is linear, so we can represent it using matrix multiplication as -

Step 7: By this method, attackers get to know that the value of initial states are 1,0,0 and 0.

Once these equations are solved (as shown above), it is easy to get attacked because they are converted from polynomial to linear equations, which are easy to attack. The risk of a system being attacked may increase if the Boolean function, the feedback polynomial, or the connection between the function and the LFSR are not chosen rightly.

Frequently Asked Questions

What is the difference between block and stream cipher?

A complex stream cipher takes 1 byte of text per unit of time to convert plaintext into ciphertext. In contrast, block ciphers are less complicated and convert a block of text at a time.

What is LFSR?

A Linear Feedback Shift Register (LFSR) is a device that can generate a seemingly random series of one and zero signals.

What is the benefit of stream cipher?

For making the cryptanalysis more difficult by making the key longer. It helps in achieving more security. The primary benefit is that few lines of code are required.

What is the drawback of LFSR?

Because of linearity, you cannot use a maximum length of LFSR directly as a key stream.

What is the purpose of the Boolean function in key-stream generators?

To hide the linearity introduced by the LFSRs.

Conclusion

In this article, you gained basic knowledge about the stream ciphers and a detailed understanding of Linear Feedback Shift Registers, algebraic attacks, and algebraic attacks on a filter generator. We hope this might seem insightful to you.