Practicaltime attacks against reduced variants of

Authors: Orr Dunkelman Nathan Keller

Publish Date: 2014/05/29

Volume: 76, Issue: 3, Pages: 601-627

PDF Link

Abstract

MISTY1 is a block cipher designed by Matsui in 1997 It is widely deployed in Japan where it is an egovernment candidate recommended cipher and is recognized internationally as a NESSIErecommended cipher as well as an ISO/IEC standard and an RFC Moreover MISTY1 was selected to be the blueprint on top of which KASUMI the GSM/3G block cipher was based Since its introduction and especially in recent years MISTY1 was subjected to extensive cryptanalytic efforts which resulted in numerous attacks on its reduced variants Most of these attacks aimed at maximizing the number of attacked rounds and as a result their complexities are highly impractical In this paper we pursue another direction by focusing on attacks of practical time complexity We present the first practicaltime attack on 5round MISTY1 which exploits only the linear FL functions and thus remains valid even if the nonlinear FO functions are replaced On the other extreme we show the importance of the FL layers by presenting a devastating and experimentally verified relatedkey attack that can break MISTY1 with no FL layers requiring only 218 data and time While our attacks clearly do not compromise the security of the full MISTY1 they expose several weaknesses in the components used in MISTY1 and improve our understanding of its security These insights are also applicable to future designs which rely on MISTY1 as their base and should be taken into close consideration by designersThe authors thank the anonymous reviewers for their useful and insightful comments The first author was supported in part by the GermanIsraeli Foundation for Scientific Research and Development through Grant No 228222226/2011 The second author was supported by the Alon Fellowship

Keywords: