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.
Read more about this topic: Correlation Attack
Famous quotes containing the word explanation:
“The explanation of the propensity of the English people to portrait painting is to be found in their relish for a Fact. Let a man do the grandest things, fight the greatest battles, or be distinguished by the most brilliant personal heroism, yet the English people would prefer his portrait to a painting of the great deed. The likeness they can judge of; his existence is a Fact. But the truth of the picture of his deeds they cannot judge of, for they have no imagination.”
—Benjamin Haydon (1786–1846)
“Natural selection, the blind, unconscious, automatic process which Darwin discovered, and which we now know is the explanation for the existence and apparently purposeful form of all life, has no purpose in mind. It has no mind and no mind’s eye. It does not plan for the future. It has no vision, no foresight, no sight at all. If it can be said to play the role of the watchmaker in nature, it is the blind watchmaker.”
—Richard Dawkins (b. 1941)
“Auden, MacNeice, Day Lewis, I have read them all,
Hoping against hope to hear the authentic call . . .
And know the explanation I must pass is this
MYou cannot light a match on a crumbling wall.”
—Hugh MacDiarmid (1892–1978)