Correlation attack

In cryptography, correlation attacks are a class of known plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear feedback shift registers (called LFSRs for the rest of this article) using a Boolean function. Correlation attacks exploit a statistical weakness that arises from a poor choice of the Boolean function – it is possible to select a function which avoids correlation attacks, so this type of cipher is not inherently insecure. It is simply essential to consider susceptibility to correlation attacks when designing stream ciphers of this type. In cryptography, correlation attacks are a class of known plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear feedback shift registers (called LFSRs for the rest of this article) using a Boolean function. Correlation attacks exploit a statistical weakness that arises from a poor choice of the Boolean function – it is possible to select a function which avoids correlation attacks, so this type of cipher is not inherently insecure. It is simply essential to consider susceptibility to correlation attacks when designing stream ciphers of this type. 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 just under 256, 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 just under 65028. In this sense, correlation attacks can be considered divide and conquer algorithms. Correlation attacks are perhaps best explained via example. We will consider the case of the Geffe keystream generator. The Geffe generator consists of three LFSRs: LFSR-1, LFSR-2 and LFSR-3. If we denote the outputs of these registers by x 1 {displaystyle x_{1}} , x 2 {displaystyle x_{2}} and x 3 {displaystyle x_{3}} , respectively, then the Boolean function that combines the three registers to provide the generator output is given by F ( x 1 , x 2 , x 3 ) = ( x 1 ∧ x 2 ) ⊕ ( ¬ x 1 ∧ x 3 ) {displaystyle F(x_{1},x_{2},x_{3})=(x_{1}wedge x_{2})oplus ( eg x_{1}wedge x_{3})} (i.e. ( x 1 {displaystyle x_{1}} AND x 2 {displaystyle x_{2}} ) XOR (NOT x 1 {displaystyle x_{1}} AND x 3 {displaystyle x_{3}} )). There are 23 = 8 possible values for the outputs of the three registers, and the value of this combining function for each of them is shown in the table below: Consider the output of the third register, x 3 {displaystyle x_{3}} . The table above makes it clear that of the 8 possible outputs of x 3 {displaystyle x_{3}} . 6 of them are equal to the corresponding value of the generator output, F ( x 1 , x 2 , x 3 ) {displaystyle F(x_{1},x_{2},x_{3})} , i.e. x 3 = F ( x 1 , x 2 , x 3 ) {displaystyle x_{3}=F(x_{1},x_{2},x_{3})} in 75% of all possible cases. Thus we say that LFSR-3 is correlated with the generator. This is a weakness we may exploit as follows: Suppose we intercept the ciphertext c 1 , c 2 , c 3 , … , c n {displaystyle c_{1},c_{2},c_{3},ldots ,c_{n}} of a plaintext p 1 , p 2 , p 3 , … {displaystyle p_{1},p_{2},p_{3},ldots } which has been encrypted by a stream cipher using a Geffe generator as its keystream generator, i.e. c i = p i ⊕ F ( x 1 i , x 2 i , x 3 i ) {displaystyle c_{i}=p_{i}oplus F(x_{1i},x_{2i},x_{3i})} for i = 1 , 2 , 3 , … , n {displaystyle i=1,2,3,ldots ,n} , where x 1 i {displaystyle x_{1i}} is the output of LFSR-1 at time i {displaystyle i} , etc. Suppose further that we know some part of the plaintext, e.g. we know p 1 , p 2 , p 3 , … , p 32 {displaystyle p_{1},p_{2},p_{3},ldots ,p_{32}} , the first 32 bits of the plaintext (corresponding to 4 ASCII characters of text). This is not as improbable as it may seem: if we know the plaintext is a valid XML file, for instance, we know that the first 4 ASCII characters must be '<xml'. Similar to this, many file formats or network protocols have standard headers or footers which can be guessed easily. Given the intercepted c 1 , c 2 , c 3 , … , c 32 {displaystyle c_{1},c_{2},c_{3},ldots ,c_{32}} and our known/guessed p 1 , p 2 , p 3 , … , p 32 {displaystyle p_{1},p_{2},p_{3},ldots ,p_{32}} , we may easily find F ( x 1 i , x 2 i , x 3 i ) {displaystyle F(x_{1i},x_{2i},x_{3i})} for i = 1 , 2 , 3 , … , 32 {displaystyle i=1,2,3,ldots ,32} by XORing the two together. We now know 32 consecutive bits of the generator output. Now we may begin a brute force search of the space of possible keys (initial values) for LFSR-3 (assuming we know the tapped bits of LFSR-3, an assumption which is in line with Kerckhoffs' principle). For any given key in the keyspace, we may quickly generate the first 32 bits of LFSR-3's output and compare these to our recovered 32 bits of the entire generator's output. Because we have established earlier that there is a 75% correlation between the output of LFSR-3 and the generator, we know that if we have correctly guessed the key for LFSR-3, approximately 24 of the first 32 bits of LFSR-3 output will match up with the corresponding bits of generator output. If we have guessed incorrectly, we should expect roughly half, or 16, of the first 32 bits of these two sequences to match. Thus we may recover the key for LFSR-3 independently of the keys of LFSR-1 and LFSR-2. At this stage we have reduced the problem of brute forcing a system of 3 LFSRs to the problem of brute forcing a single LFSR and then a system of 2 LFSRs. The amount of effort saved here depends on the length of the LFSRs. For realistic values, it is a very substantial saving and can make brute force attacks very practical. We do not need to stop here. Observe in the table above that x 2 {displaystyle x_{2}} also agrees with the generator output 6 times out of 8, again a correlation of 75% correlation between x 2 {displaystyle x_{2}} and the generator output. We may begin a brute force attack against LFSR-2 independently of the keys of LFSR-1 and LFSR-3, leaving only LFSR-1 unbroken. Thus, we are able to break the Geffe generator with as much effort as required to brute force 3 entirely independent LFSRs, meaning that the Geffe generator is a very weak generator and should never be used to generate stream cipher keystreams. Note from the table above that x 1 {displaystyle x_{1}} agrees with the generator output 4 times out of 8 - a 50% correlation. We cannot use this to brute force LFSR-1 independently of the others: the correct key will yield output which agrees with the generator output 50% of the time, but on average so will an incorrect key. This represents the ideal situation from a security perspective - the combining function F ( x 1 , x 2 , x 3 ) {displaystyle F(x_{1},x_{2},x_{3})} should be chosen so that the correlation between each variable and the combining function's output is as close as possible to 50%. In practice it may be difficult to find a function which achieves this without sacrificing other design criteria, e.g. period length, so a compromise may be necessary. While the above example illustrates well the relatively simple concepts behind correlation attacks, it perhaps simplifies the explanation of precisely how the brute forcing of individual LFSRs proceeds. We make the statement that incorrectly guessed keys will generate LFSR output which agrees with the generator output roughly 50% of the time, because given two random bit sequences of a given length, the probability of agreement between the sequences at any particular bit is 0.5. However, specific individual incorrect keys may well generate LFSR output which agrees with the generator output more or less often than exactly 50% of the time. This is particularly salient in the case of LFSRs whose correlation with the generator is not especially strong; for small enough correlations it is certainly not outside the realm of possibility that an incorrectly guessed key will also lead to LFSR output that agrees with the desired number of bits of the generator output. Thus we may not be able to find the key for that LFSR uniquely and with certainty. We may instead find a number of possible keys, although this is still a significant breach of the cipher's security. If we had, say, a megabyte of known plaintext, the situation would be substantially different. An incorrect key may generate LFSR output that agrees with more than 512 kilobytes of the generator output, but not likely to generate output that agrees with as much as 768 kilobytes of the generator output like a correctly guessed key would. As a rule, the weaker the correlation between an individual register and the generator output, the more known plaintext is required to find that register's key with a high degree of confidence. Readers with a background in probability theory should be able to see easily how to formalise this argument and obtain estimates of the length of known plaintext required for a given correlation using the binomial distribution.