Practical-time attacks against reduced variants of?MISTY1
详细信息 查看全文
- 作者：Orr Dunkelman ; Nathan Keller
- 关键词：MISTY1 ; Cryptanalysis ; Practical ; time ; Slide attacks ; Related ; key attacks ; 94A60 ; 68P25
- 刊名：Designs, Codes and Cryptography
- 出版年：2015
- 出版时间：September 2015
- 年：2015
- 卷：76
- 期：3
- 页码：601-627
- 全文大小：971 KB
- 参考文献：1.3GPP TS 35.201: 3rd Generation Partnership Project: Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 2: KASUMI Specification V3.1.1. (2001).
2.Babbage S., Frisch L.: On MISTY1 higher order differential cryptanalysis. In: Won D. (ed.) ICISC. Lecture Notes in Computer Science, vol. 2015, pp. 22-6. Springer, Heidelberg (2000).
3.Biham E.: New types of cryptanalytic attacks using related keys. J. Cryptol. 7(4), 229-46 (1994).
4.Biham E., Biryukov A., Shamir A.: Miss in the middle attacks on IDEA and Khufu. In: Knudsen L.R. (ed.) FSE. Lecture Notes in Computer Science, vol. 1636, pp. 124-38. Springer, Berlin (1999).
5.Biham E., Dunkelman O., Keller N.: A unified approach to related-key attacks. In: Nyberg K. (ed.) FSE. Lecture Notes in Computer Science, vol. 5086, pp. 73-6. Springer, Berlin (2008).
6.Cryptrec: e-Government Recommended Ciphers List (2012).
7.Daemen J., Knudsen L.R., Rijmen V.: The Block Cipher Square. In: Biham E. (ed.) Fast Software Encryption: Proceedings of 4th International Workshop (FSE -7), Haifa, Israel, 20-2 January 1997. Lecture Notes in Computer Science, vol. 1267, pp. 149-65. Springer, Heidelberg (1997).
8.Dunkelman O., Keller N.: An improved impossible differential attack on MISTY1. In: Pieprzyk J. (ed.) ASIACRYPT. Lecture Notes in Computer Science, vol. 5350, pp. 441-54. Springer, Berlin (2008).
9.Dunkelman O., Keller N., Shamir A.: A practical-time related-key attack on the KASUMI Cryptosystem used in GSM and 3G telephony. In: Rabin T. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 6223, pp. 393-10. Springer, Santa Barbara (2010).
10.Ferguson N., Kelsey J., Lucks S., Schneier B., Stay M., Wagner D., Whiting D.: Improved cryptanalysis of Rijndael. In: Schneier B. (ed.) FSE. Lecture Notes in Computer Science, vol. 1978, pp. 213-30. Springer, Berlin (2000).
11.Furuya S.: Slide attacks with a known-plaintext cryptanalysis. In: Kim K. (ed.) ICISC. Lecture Notes in Computer Science, vol. 2288, pp. 214-25. Springer, Heidelberg (2001).
12.Hatano Y., Tanaka H., Kaneko T.: Optimization for the algebraic method and its application to an attack of MISTY1. IEICE Trans. 87-A(1), 18-7 (2004).
13.ISO/IEC: ISO/IEC 18033-:2010 Information technology—Security techniques—Encryption algorithms—Part 3: Block ciphers. Technical Report (2010).
14.Jia K., Li L.: Improved impossible differential attacks on reduced-round MISTY1. In: Lee D. H., Yung M. (eds.) WISA. Lecture Notes in Computer Science, vol. 7690, pp. 15-7. Springer, Berlin (2012).
15.Knudsen L.R.: The security of Feistel ciphers with six rounds or less. J. Cryptol. 15(3), 207-22 (2002).
16.Knudsen L.R., Wagner D.: Integral cryptanalysis. In: Daemen J., Rijmen V. (eds.) FSE 2002. LNCS, vol 2365, pp. 112-27. Springer, Heidelberg (2002).
17.Kühn U.: Cryptanalysis of reduced-round MISTY. In: Pfitzmann B. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 2045, pp. 325-39. Springer, Berlin (2001).
18.Kühn U.: Improved cryptanalysis of MISTY1. In: Daemen J., Knudsen L.R., Rijmen V.: The block cipher square. In: Biham E. (ed.) FSE 1997. LNCS, pp. 61-5. Springer, Heidelberg (2002).
19.Matsui M.: New block encryption algorithm MISTY. In: Biham E. (ed.) Fast Software Encryption: Proceedings of 4th International Workshop (FSE -7), Haifa, Israel, 20-2 January 1997. Lecture Notes in Computer Science, vol. 1267, pp. 54-8. Springer, Heidelberg (1997).
20.Matsui M.: A Description of the MISTY1 Encryption Algorithm, RFC 2994. Technical Report (2000).
21.NESSIE Consortium: Portfolio of recommended cryptographic primitives (2003, Online). https://?www.?cosic.?esat.?kuleuven.?be/?nessie/?deliverables/?decision-final.?pdf .
22.Sakurai K., Zheng Y.: On Non-Pseudorandomness from block ciphers with provable immunity against linear cryptanalysis. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E80-A(1), 19-4 (1997).
23.Sugio N., Aono H., Hongo S., Kaneko T.: A study on higher order differential attack of KASUMI. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E90-A(1), 14-1 (2007).
24.Sun X., Lai X.: Improved integral attacks on MISTY1. In: Jacobson M.J. Jr., Rijmen V., Safavi-Naini R., eds.: Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 5867, pp. 266-80. Springer, Berlin (2009).
25.Tsunoo Y., Saito T., Shigeri M., Kawabata T.: Higher order differential attacks on reduced-round MISTY1. In: Lee P.J., Cheon J.H. (eds.) ICISC. Lecture Notes in Computer Science, vol. 5461, pp. 415-31. Springer, Heidelberg (2008).
26.Tsunoo Y., Saito T., Kawabata T., Nakagawa H.: Finding higher order differentials of MISTY1. IEICE Trans. 95-A(6), 1049-055 (2012). - 作者单位：Orr Dunkelman (1)
Nathan Keller (2)
1. Computer Science Department, University of Haifa, Haifa, 31905?, Israel
2. Department of Mathematics, Bar-Ilan University, Ramat Gan?, 52900, Israel - 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Combinatorics
Coding and Information Theory
Data Structures, Cryptology and Information Theory
Data Encryption
Discrete Mathematics in Computer Science
Information, Communication and Circuits - 出版者：Springer Netherlands
- ISSN：1573-7586
文摘
MISTY1 is a block cipher designed by Matsui in 1997. It is widely deployed in Japan where it is an e-government candidate recommended cipher, and is recognized internationally as a NESSIE-recommended 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 practical-time attack on 5-round MISTY1 which exploits only the linear \(FL\) functions, and thus, remains valid even if the non-linear \(FO\) functions are replaced. On the other extreme, we show the importance of the \(FL\) layers, by presenting a devastating (and experimentally verified) related-key attack that can break MISTY1 with no \(FL\) layers, requiring only \(2^{18}\) 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 designers.