Interpolation attack

From Wikipedia, the free encyclopedia

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.

[edit] References

• Thomas Jakobsen, Lars Knudsen (January 1997). "The Interpolation Attack on Block Ciphers" (PDF/PostScript). 4th International Workshop on Fast Software Encryption (FSE '97), LNCS 1267: pp.28–40, Haifa: Springer-Verlag. Retrieved on 2007-07-03. 
• Thomas Jakobsen (August 25, 1998). "Cryptanalysis of Block Ciphers with Probabilistic Non-linear Relations of Low Degree" (PDF/PostScript). Advances in Cryptology — CRYPTO '98: pp.212–222, Santa Barbara, California: Springer-Verlag. Retrieved on 2007-07-06.  (Video of presentation at Google Video—uses Flash)
• Shiho Moriai, Takeshi Shimoyama, Toshinobu Kaneko (March 1999). "Interpolation Attacks of the Block Cipher: SNAKE" (PDF). FSE '99: pp.275–289, Rome: Springer-Verlag. Retrieved on 2007-09-16. 
• Amr M. Youssef, Guang Gong (April 2000). "On the Interpolation Attacks on Block Ciphers" (PDF). FSE 2000: pp.109–120, New York City: Springer-Verlag. Retrieved on 2007-07-06. 
• Kaoru Kurosawa, Tetsu Iwata, Viet Duong Quang (August 2000). "Root Finding Interpolation Attack" (PDF/PostScript). Proceedings of the 7th Annual International Workshop on Selected Areas in Cryptography (SAC 2000): pp.303–314, Waterloo, Ontario: Springer-Verlag. Retrieved on 2007-07-06.