Do you think IIT Guwahati certified course can help you in your career?
Introduction
Cryptography is the practice of hiding and securing information. It is the study of safe communication techniques that allows only the message’s sender and receiver to view its content. This article will teach you about correlation attacks on a combination generator.
Stream Ciphers
Stream Ciphers are an essential part of symmetric (secret key) Cryptography. In this, the plaintext digits are combined with the keystream (pseudorandom cipher digit stream) and are encrypted bit by bit. Examples of stream ciphers are Scream, Grain, PANAMA, etc.
These ciphers use LFSRs (Linear Feedback Shift Register) to generate keystream.
LFSR
An LFSR is a well-chosen feedback function that can produce a sequence of random bits with a very long cycle.
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 adding 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.
Correlation Attacks
Correlation attacks are a type of known plaintext attacks that were first proposed by T. Siegenthaler on Geffe Generator in 1984 for breaking a specific type of stream ciphers known as combination generators.
A combination generator generates the keystream by combining the outputs of several LFSRs using a Boolean function. A correlation attack is an essential cryptanalytic technique discussed against the combination generator.
Combination Generator
LFSRs give a large period and have excellent statistical properties. But they have low linear complexity. Combining several LFSRs with a non-linear Boolean function achieves higher linear complexity. A system where outputs of several individual LFSR units are involved and combined as the inputs to a non-linear Boolean function ‘F’ to ultimately generate the final keystream bit ‘K’ is known as an LFSR-based combination generator.
In a combination generator, we have say, ‘r’ of LFSRs. Suppose that the jth LFSR generates the keystream z1j, z2j,. . . . The basic idea is to use a boolean function f : (Z2)r → Z2 for combining the r keystreams into a new keystream z1z2 . . . , via the rule zi = f(z1i, . . . , zri), i = 1, 2, . . . . where f is the combining function.
Note that it is desirable that the r LFSRs have pairwise relatively prime periods – which provides the longest possible period for the input to the combining function.
Correlation Attack on a Combination Generator
The case where a combination generator uses shift registers with a linear feedback function is very old and is too vulnerable to several attacks like correlation attacks, algebraic attacks, and distinguishing attacks. The combination generators composed of LFSRs are less susceptible to these attacks.
The combination generator with the filter generator is one of stream ciphers’ most straightforward and most analyzed constructions. It uses many linear feedback shift registers (LFSRs) as an internal state. We are taking m as the total size in bits. These LFSRs are filtered using an n-variable balanced Boolean function f(from Fn2 into F2) to produce the keystream (zt) t ≥ 0.
The inputs of this function are taken from some bits in the LFSR’s internal states. We will write xt for the n-bit vector corresponding to the inputs of f at time t. Our goal here is to find the key (that is, the initial state of all the LFSRs), knowing the keystream sequence (zt) t ≥ 0 and all the components of the combination generator.
We are considering that there are r = 3 LFSRs, and the combining function, which is also called the “majority function,” is f(z1, z2, z3) = (z1 ∧ z2) ⊕ (z1 ∧ z3) ⊕ (z2 ∧ z3), where Λ is logical ‘and’ operator, and the symbol ‘⊕’ is the xor operator.
Step 1: Know the number of LFSRs (r) = 3.
z1, z2, and z3 are the input variables. Since r = 3 thus, there will be 8 (23) possible equations for different values of the input variables.
Step 2: Find their binary equivalent from 0 to 2r - 1. These will be your value of input variables. For example, the binary equivalent of 6 is 110, where z1 will be 1, z2 will be 1, and z3 will be 0.
Step 3: Put these 8 different sets of values in the given combining function viz
f(z1, z2, z3) = (z1 ∧ z2) ⊕ (z1 ∧ z3) ⊕ (z2 ∧ z3)
{The xor operator yields true (1) only if the values are different; else results in 0. Whereas the logical and operator yield 1 only if all the values are high (1)}.
We can solve it for different values of input bits, using the majority function as shown -
Step 4: Find all the possible values using the method shown in the image above.
For example, f(1, 1, 0) = (1 ∧ 1) ⊕ (1 ∧ 0) ⊕ (1 ∧ 0)
So, f(1, 1, 0) = 0⊕1⊕1 = 1 as 0⊕1 = 1 and 1⊕1 = 1.
On solving all the eight possible combinations, the outputs of f are:
Step 5: By considering the three inputs are the same, find the probability of getting the matching keystream obtained by solving the above values.
Assuming that every input triple - (z1, z2, z3) is alike, we can associate a random variable zj for each zj - input variable and z a random variable with the output f(z1, z2, z3). From the above image showing the outputs, it can be seen that - Pr[z = zj] = 3/4, which means the probability of the calculated output matching the keystream is 0.75.
On generating a sequence of bits using this LFSR and comparing it to the series of actual keystream bits, if the guessed initial key is correct, we expect 75% of the bits of LFSR to agree with the keystream. If the guessed initial key is incorrect, we expect 50% of the LFSR bits to concur with the keystream.
Ninjas note that probability theory techniques can be used for predicting how many keystream bits are required for the attack to succeed with high probability. Generally, the number of required keystream bits depends on the correlation and the degree of the recurrence relations (the number of stages in the LFSRs). Larger LFSRs usually require more keystream bits. The number of keystream bits, N, must be at least Li for an attack on an LFSR having Li stages to succeed Li/(p − 1/2)2, where p is the predicted correlation.
It is a string of pseudorandom characters combined with the plaintext to produce an encrypted message.
What are the applications of LFSR?
LFSR generates pseudorandom numbers, fast digital counters, pseudo-noise sequences, and whitening sequences.
What is Kerckhoff's principle?
It states that the cryptographic system must be secure even if all its details (except the key) are public.
Why are combination generators used over LFSR?
An LFSR does not give a secure stream cipher. Therefore, combination generators, the combination of LFSRs, are used to get a secure stream cipher.
What is a cipher?
A cipher is an encrypted mode of communication so that if the message is found, the attacker is unable to determine the meaning of that message.
Conclusion
From this article, you might have learned about stream ciphers, Linear Feedback Shift registers (LFSR), correlation attacks, and correlation attacks on a combination generator. Below are some of the articles related to this article, so you must read them:
518+ registered 
