Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Stream Ciphers
3.
Algebraic Attack
3.1.
Algebraic Attack on Stream Ciphers
4.
Linear Feedback Shift Register
5.
Non Linear Filter Generator
6.
Method of Generating System of Equations
7.
Frequently Asked Questions
7.1.
What is the difference between block and stream cipher?
7.2.
What is LFSR?
7.3.
What is the benefit of stream cipher?
7.4.
What is the drawback of LFSR?
7.5.
What is the purpose of the Boolean function in key-stream generators?
8.
Conclusion
Last Updated: Mar 27, 2024

Algebraic Attack on a Filter Generator in Cryptography

Author Vanshika
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

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.

Algebraic attack on a filter generator in cryptography

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 sj which is calculated by a feedback function f(s0, s1, . . . , sn-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 si ∈ {0, 1} for each 0 ≤ i ≤ L − 1, then S = (s0, s1, . . . , sL-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 = (s0, . . . ,sn-1) ∈ F2n and, at each clock t ≥ 0, produces a keystream bit zt = F (Lt(S)), where 

  • L: F2n → F2n is the linear update function; 
  • F ∈ Bn 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 (z0, z1, z2, z3) = (1, 0, 0, 0), which satisfies the recurrence relation zn+4 = zn+1 + zn for n ≥ 0 and the filtering function f(z0, z1, z2, z3) = z0z1+z2z3 for generating the output bit from each state.

Using the output bit, you can derive the equations having initial states - z0, z1, z2, and z3 as variables. Look at the image below, which shows how to calculate the polynomial equations.

Other variables in term of initial variables.

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

  f(z0, z1, z2, z3) = z0z1+z2z3

zn+4 = zn+1 + zn for n ≥ 0

where zi , i ≥ 4 is an intermediate variable with z0, z1, z2 and z3 as initial variables.
 

Step 2: Using the recurrence relation, find the intermediate variables in terms of the initial variables. For example:

z2+4 = z2+1 + z2

z6 = z3 + z2

Now using the filtering relation, we can get the equations in terms of the initial states as shown.

Equations using the filtering function

Step 3: After getting all the variables in terms of initial variables, put them in the filtering function.

The filter function, in general can be written as:

f(zi, zi+1, zi+2, zi+3) = zizi+1+zi+2zi+3

 

Step 4: Use this generalized form of filtering function to get the equations and their values. 

f(z4, z5, z6, z7) = z4z5+z6z7

f(z4, z5, z6, z7) = z4z5+z6z7

Now, 

z4 = z1 + z0

z5 = z2 + z1

z6 = z3 + z2

z7 = z4 + z3 = (z1 + z0) + z3

So,

f(z4, z5, z6, z7) = (z1 + z0)(z2 + z1)+(z3 + z2)(z1 + z0+ z3)

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

Calculations of filter function

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 z0, z1, z2 and z3, 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 -

Representation of the function in terms of matrix multiplication

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.

Read out our other related articles:

You may refer to our Guided Path on Code Studios to enhance your skill set on DSACompetitive ProgrammingSystem Design, and many more. Check out essential interview questions, practice our available mock tests, look at the interview bundle for interview preparations, and much more.

Happy Learning :)

Previous article
Correlation Attack on a Combination Generator in Cryptography
Next article
Stream Ciphers: Trivium in Cryptography
Live masterclass