block cipher; key collisions; equivalent keys; CRYPTREC; hash function
Abstract :
[en] In this work we present analysis for the block cipher SC2000, which is in the Japanese CRYPTREC portfolio for standardization. In spite of its very complex and non-linear key-schedule we have found a property of the full SC2000-256 (with 256-bit keys) which allows the attacker to find many pairs of keys which generate identical sets of subkeys. Such colliding keys result in identical encryptions. We designed an algorithm that efficiently produces colliding key pairs in 2^39 time, which takes a few hours on a PC. We show that there are around 2^68 colliding pairs, and the whole set can be enumerated in 2^58 time. This result shows that SC2000-256 cannot model an ideal cipher. Furthermore we explain how practical collisions can be produced for both Davies-Meyer and Hiroses hash function constructions instantiated with SC2000-256 .
Disciplines :
Computer science
Author, co-author :
BIRYUKOV, Alex ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Aumasson, J.-P., Nakahara Jr., J., Sepehrdad, P.: Cryptanalysis of the ISDB scrambling algorithm (MULTI2). In: Dunkelman [6], pp. 296-307
Biham, E., Dunkelman, O., Keller, N.: New results on boomerang and rectangle attacks. In: Daemen and Rijmen [4], pp. 1-16
Biryukov, A., Gauravaram, P., Guo, J., Khovratovich, D., Ling, S., Matusiewicz, K., Nikolić, I., Pieprzyk, J., Wang, H.: Cryptanalysis of the LAKE hash family. In: Dunkelman [6], pp. 156-179
Dunkelman, O., Keller, N.: Boomerang and rectangle attacks on SC2000. In: NESSIE 2nd Workshop (London) (2001)
Hirose, S.: Some plausible constructions of double-block-length hash functions. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 210-225. Springer, Heidelberg (2006)
Kelsey, J., Schneier, B., Wagner, D.: Key-schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 237-251. Springer, Heidelberg (1996)
Lu, J.: Differential attack on five rounds of the SC2000 block cipher. In: Bao, F., Yung, M., Lin, D., Jing, J. (eds.) Inscrypt 2009. LNCS, vol. 6151, pp. 50-59. Springer, Heidelberg (2010)
Matsui, M.: Key collisions of the RC4 stream cipher. In: Dunkelman [6], pp. 38-50
Preneel, B., Govaerts, R., Vandewalle, J.: Hash functions based on block ciphers: A synthetic approach. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 368-378. Springer, Heidelberg (1994)
Raddum, H., Knudsen, L.R.: A differential attack on reduced-round SC2000. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 190-198. Springer, Heidelberg (2001)
Robshaw, M.: A cryptographic review of Cipherunicorn-A. Technical Report, CRYPTRECT Technical report (2001)
Shimoyama, T., Yanami, H., Yokoyama, K., Takenaka, M., Itoh, K., Yajima, J., Torii, N., Tanaka, H.: The block cipher SC2000. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 312-327. Springer, Heidelberg (2002)
Technical Report 1087. Analysis of SC2000 (2000). http://www.ipa.go.jp/security?enc/CRYPTREC/fy15/doc/1087 sc2000.pdf
Yanami, H., Shimoyama, T., Dunkelman, O.: Differential and linear cryptanalysis of a reduced-round SC2000. In: Daemen and Rijmen [4], pp. 34-48
