Correlation Attack - Explanation

Explanation

Correlation attacks are possible when there is a significant correlation between the output state of one individual LFSR in the keystream generator and the output of the Boolean function that combines the output state of all of the LFSRs. Combined with partial knowledge of the keystream (which is easily derived from partial knowledge of the plaintext, as the two are simply XORed together), this allows an attacker to brute-force the key for that individual LFSR and the rest of the system separately. For instance, if, in a keystream generator in which four 8-bit LFSRs are combined to produce the keystream, and one of the registers is correlated to the Boolean function output, we may brute force it first and then the remaining three, for a total attack complexity of 28 + 224. Compared to the cost of launching a brute force attack on the entire system, with complexity 232, this represents an attack effort saving factor of 255, which is substantial. If a second register is correlated with the function, we may repeat this process and drop the attack complexity to 28 + 28 + 216 for an effort saving factor of 65027. In this sense, correlation attacks can be considered divide and conquer algorithms.