Interpolation attack
In cryptography, an interpolation attack is a type of cryptanalytic attack against block ciphers. After the two attacks, differential cryptanalysis and linear cryptanalysis, were presented on block ciphers, some new block ciphers were introduced, which were proven secure against differential and linear attacks. Among these there were some iterated block ciphers such as the KN-Cipher and the SHARK cipher. However, Thomas Jakobsen and Lars Knudsen showed in the late 1990s that these ciphers were easy to break by introducing a new attack called the interpolation attack. In the attack, an algebraic function is used to represent an  S-box. This may be a simple quadratic, or a polynomial or rational function over a Galois field. Its coefficients can be determined by standard Lagrange interpolation techniques, using known plaintexts as data points. Alternatively, chosen plaintexts can be used to simplify the equations and optimize the attack. In its simplest version an interpolation attack expresses the ciphertext as a polynomial of the plaintext. If the polynomial has a relative low number of unknown coefficients, then with a collection of plaintext/ciphertext (p/c) pairs, the polynomial can be reconstructed. With the polynomial reconstructed the attacker then has a representation  of the encryption, without exact knowledge of the secret key. The interpolation attack can also be used to recover the secret key. It is easiest to describe the method with an example. Example. Let an iterated cipher be given by where formula_2 is the plaintext, formula_3 the output of the formula_4 round, formula_5 the secret formula_4 round key (derived from the secret key formula_7 by some key schedule), and for a formula_8-round iterated cipher, formula_9 is the ciphertext. Consider the 2-round cipher. Let formula_10 denote the message, and formula_11 denote the ciphertext. Then the output of round 1  becomes and the output of round 2 becomes Expressing the ciphertext as a polynomial of the plaintext yields where the formula_16's are key dependent constants. Using as many plaintext/ciphertext pairs as the number of unknown coefficients in the polynomial formula_17, then we can construct the polynomial. This can for example be done by Lagrange Interpolation (see Lagrange polynomial). When the unknown coefficients have been determined, then we have a representation formula_17 of the encryption, without knowledge of the secret key formula_7. Existence. Considering an formula_20-bit block cipher, then there are formula_21 possible plaintexts, and therefore formula_21 distinct  formula_23 pairs. Let there be formula_24 unknown coefficients in formula_17. Since we require as many formula_23 pairs as the number of unknown coefficients in the polynomial, then an interpolation attack exist only if formula_27. Time complexity. Assume that the time to construct the polynomial formula_17 using formula_23 pairs are small, in comparison to the time to encrypt the required plaintexts. Let there be formula_24 unknown coefficients in formula_17. Then the time complexity for this attack is formula_24, requiring formula_24 known distinct formula_23 pairs. Interpolation attack by Meet-In-The-Middle. Often this method is more efficient. Here is how it  is done. Given an formula_8 round iterated cipher with block length formula_20, let formula_37 be the output of the cipher after formula_38 rounds with formula_39. We will express the value of formula_37 as a polynomial of the plaintext formula_10, and as a polynomial of the ciphertext formula_11. Let formula_43 be the expression of formula_37 via formula_10, and let formula_46 be the expression of formula_37 via formula_11. The polynomial formula_49 is obtain by computing forward using the iterated formula of the cipher until round formula_38, and the polynomial formula_51 is obtain by computing backwards from the iterated formula of the cipher  starting from round formula_8 until round formula_53. So it should hold that and if both formula_55 and formula_56 are polynomials with a low number of coefficients, then we can solve the equation for the unknown coefficients. Time complexity. Assume that formula_49 can be expressed by formula_58 coefficients, and formula_51 can be expressed by formula_60 coefficients. Then we would need formula_61 known distinct formula_23 pairs to solve the equation by setting it up as a matrix equation. However, this matrix equation is solvable up to a multiplication and an addition. So to make sure that we get a unique and non -zero solution, we set the coefficient corresponding to the highest degree to one, and the constant term to zero. Therefore, formula_63 known distinct formula_23 pairs are required. So the time complexity for this attack is formula_63, requiring formula_63 known distinct formula_23 pairs. By the Meet-In-The-Middle approach the total number of coefficients is usually smaller than using the normal method. This makes the method more efficient, since less formula_23 pairs are required. Key-recovery. We can also use the interpolation attack to recover the secret key formula_7. If we remove the last round of an formula_8-round iterated  cipher with block length formula_20, the output of the cipher becomes formula_72. Call the cipher the reduced cipher. The idea is to make a guess on the last round key formula_73, such that we can decrypt one round to obtain the output formula_74 of the reduced cipher. Then to verify the guess we use the interpolation attack on the reduced cipher either by the normal method or by the Meet-In-The-Middle method. Here is how it is done. By the normal method we express the output formula_74 of the reduced cipher as a polynomial of the plaintext formula_10 . Call the polynomial formula_77. Then if we can express formula_17 with formula_24 coefficients, then using formula_24 known distinct formula_23 pairs, we can construct the polynomial. To verify the guess of the last round key, then check with one extra formula_23 pair if it holds that If yes, then with high probability the guess of the last round key was correct. If no, then make another guess of the key. By the Meet-In-The-Middle method we express the output formula_37 from round formula_39 as a polynomial of the plaintext formula_10 and as a polynomial of the output of the  reduced cipher formula_74. Call the polynomials formula_49 and formula_89, and let them be expressed by formula_58 and formula_60 coefficients, respectively. Then with formula_92 known distinct formula_23 pairs we can find the coefficients. To verify the guess of the last round key, then check with one extra formula_23 pair if it holds that If yes, then with high probability the guess of the last round key was correct. If no, then make another guess of the key. Once we have found the correct last round key, then we can continue in a similar fashion on the remaining round keys. Time complexity . With a secret round key of length formula_20, then there are formula_21 different keys. Each with probability formula_98 to be correct if chosen at random. Therefore, we will on average have to make formula_99 guesses before finding the correct key. Hence, the normal method have average time complexity formula_100, requiring formula_101 known distinct formula_102 pairs, and the Meet-In-The-Middle method have average time complexity formula_103, requiring formula_104 known distinct formula_102 pairs. Real world application. The Meet-in-the-middle attack can be used in a variant to attack S-boxes, which uses the inverse function, because with an  formula_20-bit S-box then formula_107 in formula_108. The block cipher SHARK uses SP-network with S-box formula_109. The cipher is resistant against differential and linear cryptanalysis after a small number of rounds. However it was broken in 1996 by Thomas Jakobsen and Lars Knudsen, using interpolation attack. Denote by SHARKformula_110 a version of SHARK with block size formula_111 bits using formula_24 parallel formula_20-bit S-boxes in formula_8 rounds. Jakobsen and Knudsen found that there exist an interpolation attack on SHARKformula_115 (64-bit block cipher) using about formula_116 chosen plaintexts, and an interpolation attack on SHARKformula_117 (128-bit  block cipher) using about formula_118 chosen plaintexts. Also Thomas Jakobsen introduced a probabilistic version of the interpolation attack using Madhu Sudan's algorithm for improved decoding of Reed-Solomon codes. This attack can work even when an algebraic relationship between plaintexts and ciphertexts holds for only a fraction of values.