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.
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.
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.
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.
Using as many plaintext/ciphertext pairs as the number of unknown coefficients in the polynomial
pairs as the number of unknown coefficients in the polynomial, then an interpolation attack exist only if
pairs are small, in comparison to the time to encrypt the required plaintexts.
is obtain by computing forward using the iterated formula of the cipher until round
is obtain by computing backwards from the iterated formula of the cipher starting from round
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.
By the Meet-In-The-Middle approach the total number of coefficients is usually smaller than using the normal method.
We can also use the interpolation attack to recover the secret key
The idea is to make a guess on the last round key
To verify the guess of the last round key, then check with one extra
pair if it holds that If yes, then with high probability the guess of the last round key was correct.
To verify the guess of the last round key, then check with one extra
pair if it holds that If yes, then with high probability the guess of the last round key was correct.
Hence, the normal method have average time complexity
pairs, and the Meet-In-The-Middle method have average time complexity
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.
Jakobsen and Knudsen found that there exist an interpolation attack on SHARK
chosen plaintexts, and an interpolation attack on SHARK
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.