In cryptography, an interpolation attack is a type of cryptanalytic attack against block ciphers.
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.
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.
Famous quotes containing the word attack:
“... possibly there is no needful occupation which is wholly unbeautiful. The beauty of work depends upon the way we meet it—whether we arm ourselves each morning to attack it as an enemy that must be vanquished before night comes, or whether we open our eyes with the sunrise to welcome it as an approaching friend who will keep us delightful company all day, and who will make us feel, at evening, that the day was well worth its fatigues.”
—Lucy Larcom (1824–1893)