Abstract
The MISTY1 is a 64-bit block cipher designed by Matsui in 1997. It is listed on the Japanese CRYPTREC Candidate Recommended Ciphers List. Cryptanalysis against the full MISTY1 has already been known, which is the analysis of weak keys in a related-key setting and the integral attack using the division property in a single-key setting. However, these attacks require large amounts of data and time complexity that are practically infeasible. In this paper, we show the existence of new weak keys for the full MISTY1. The MISTY1 can be distinguished from a random permutation and the keys are recovered with a realistically feasible computational complexity, in a related-key setting. It means that a pair of weak keys, one key of which has a specific differential relationship with the other, is used. The computational complexity of the attacks is \(2^5\) chosen plaintexts for distinguishing the MISTY1 from a random permutation, and \(2^8\) chosen plaintexts, \(2^{25}\) bytes of memory and a few seconds computed by a desktop PC for key recovery.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Matsui, M.: New block encryption algorithm MISTY. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 54–68. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052334
CRYPTREC Homepage. http://www.cryptrec.go.jp/en/method.html
Specifications in 2001 MISTY1. http://www.cryptrec.go.jp/en/cryptrec_03_spec_ cypherlist_files/ PDF/05_02espec.pdf
NESSIE Homepage. https://www.cosic.esat.kuleuven.be/nessie/
ISO/IEC Homepage. JTC1: ISO/IEC 18033: Security techniques - encryption algorithms - part 3: Block ciphers (2005)
Ohta, H., Matsui, M.: A description of the MISTY1 encryption algorithm (2000). https://tools.ietf.org/html/rfc2994
Lu, J., Yap, W.-S., Wei, Y.: Weak keys of the full MISTY1 block cipher for related-key differential cryptanalysis. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 389–404. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36095-4_25
Lu, J., Yap, W.S., Wei, Y.: Weak keys of the full MISTY1 block cipher for related-key amplified boomerang cryptanalysis. IET J. 12(5), 389–397 (2018)
Todo, Y.: Integral cryptanalysis on full MISTY1. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 413–432. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_20
Todo, Y.: Integral cryptanalysis on full MISTY1. J. Cryptology. 30, 920–959 (2017)
Bar-On, A., Keller, N.: A \(2^{70}\) attack on the full MISTY1. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 435–456. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_16
NIST FIPS PUB 46-3.: Data Encryption Standard (DES). http://csrc.nist.gov/ csrs/media/publications/fips/46/3/archive/1990-10-25/documents/fips46-3.pdf
NIST FIPS PUB 197.: Advanced Encryption Standard (2001). http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
Biham, E.: New types of cryptanalytic attacks using related keys. J. Cryptology 7(4), 229–246 (1994)
Knudsen, L.R.: Cryptanalysis of LOKI 91. In: Seberry, J., Zheng, Y. (eds.) AUSCRYPT 1992. LNCS, vol. 718, pp. 196–208. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57220-1_62
Biryukov, A., Khovratovich, D.: Related-key cryptanalysis of the full AES-192 and AES-256. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 1–18. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_1
Biryukov, A., Khovratovich, D., Nikolić, I.: Distinguisher and related-key attack on the full AES-256. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 231–249. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_14
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Taga, B., Ito, N., Okano, T. (2024). Weak Keys of the Full MISTY1 Recovered in Practical Time. In: Minematsu, K., Mimura, M. (eds) Advances in Information and Computer Security. IWSEC 2024. Lecture Notes in Computer Science, vol 14977. Springer, Singapore. https://doi.org/10.1007/978-981-97-7737-2_4
Download citation
DOI: https://doi.org/10.1007/978-981-97-7737-2_4
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-7736-5
Online ISBN: 978-981-97-7737-2
eBook Packages: Computer ScienceComputer Science (R0)