Do you think IIT Guwahati certified course can help you in your career?
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.
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.
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.
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.
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.
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 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 -
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.
85+ registered 