For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Efficient Interpolation Attack
Shiho MORIAI Takeshi SHIMOYAMA Toshinobu KANEKO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/01/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
cryptanalysis, block cipher, interpolation attack, computer algebra system, SNAKE,
Full Text: PDF>>
We introduce an efficient interpolation attack which gives the tighter upper bound of the complexity and the number of pairs of plaintexts and ciphertexts required for the attack. In the previously known interpolation attack there is a problem in that the required complexity for the attack can be overestimated. We solve this problem by first, finding the actual number of coefficients in the polynomial used in the attack by using a computer algebra system, and second, by finding the polynomial with fewer coefficients by choosing the plaintexts. We apply this interpolation attack to the block cipher SNAKE and succeeded in attacking many ciphers in the SNAKE family. When we evaluate the resistance of a block cipher to interpolation attack, it is necessary to apply the interpolation attack described in this paper.