How to Improve Interpolation Attack

Kaoru KUROSAWA  Tetsu IWATA  Quang Viet DUONG  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.1   pp.9-15
Publication Date: 2005/01/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.1.9
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Symmetric Key Cryptography
block cipher,  interpolation attack,  root finding algorithm,  resultant,  

Full Text: PDF(178.6KB)>>
Buy this Article

In the key recovery variant of the interpolation attack, exhaustive search is required to find the last round key Km. Therefore, this attack is almost impractical if the size of Km is too large. In this paper, we show that Km can be very efficiently obtained if F(K,x) can be approximated by a low degree polynomial gx(K) in K for any fixed x, where F is a round function of Feistel type block ciphers.