↑ arvau

Wikipedia / 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

by some key schedule is the ciphertext.

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

's are key dependent constants.

, then we can construct the polynomial. This can for example be done by Lagrange Interpolation (see Lagrange polynomial.

Existence

.

Time complexity

pairs.

Interpolation attack by Meet-In-The-Middle

Often this method is more efficient. Here is how it is done.

.

So it should hold that

are polynomials with a low number of coefficients, then we can solve the equation for the unknown coefficients.

Time complexity

pairs.

pairs are required.

Key-recovery

.

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.

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.

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

guesses before finding the correct key.

pairs.

Real world application

.

The block cipher SHARK 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.

References