Optimization for the Algebraic Method and Its Application to an Attack of MISTY1

Yasuo HATANO  Hidema TANAKA  Toshinobu KANEKO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.1   pp.18-27
Publication Date: 2004/01/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Symmetric Cipher
MISTY1,  higher order differential attack,  algebraic method,  linear dependency,  probabilistic attack equation,  

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

In this paper, we describe a technique for optimizing the algebraic method that is applied to higher order differential attack. The higher order differential attack is a well-known attack on block ciphers, in which we derive an attack equation to determine a round key from a property of a higher order differential of a target block cipher. The algebraic method is a linearization of the attack equation and determines the true key by a method such as Gaussian elimination. Our technique is based on linear dependency and can reduce the complexity of that method. We also describe a technique that allows the algebraic method to be used as an attack equation that holds probabilistically. We demonstrate this method by attacking a five-round MISTY1 and show that it needs 221.6 chosen plaintexts and 228.0 encryption times. The computer simulation took about two minutes to complete.