Known-key distinguishers on type-1 Feistel scheme and near-collision attacks on its hashing modes

Abstract

We present some known-key distinguishers for a type-1 Feistel scheme with a permutation as the round function. To be more specific, the 29-round known-key truncated differential distinguishers are given for the 256-bit type-1 Feistel scheme with an SP (substitution-permutation) round function by using the rebound attack, where the S–boxes have perfect differential and linear properties and the linear diffusion layer has a maximum branch number. For two 128-bit versions, the distinguishers can be applied on 25-round structures. Based on these distinguishers, we construct near-collision attacks on these schemes with MMO (Matyas-Meyer-Oseas) and MP (Miyaguchi-Preneel) hashing modes, and propose the 26-round and 22-round near-collision attacks for two 256-bit schemes and two 128-bit schemes, respectively. We apply the near-collision attack on MAME and obtain a 26-round near-collision attack. Using the algebraic degree and some integral properties, we prove the correctness of the 31-round known-key integral distinguisher proposed by Sasaki et al. We show that if the round function is a permutation, the integral distinguisher is suitable for a type-1 Feistel scheme of any size.

Keywords

known-key / block cipher / generalized Feistel scheme / type-1 / rebound attack / integral distinguisher / algebraic degree

References

[1] KnudsenL R, RijmenV. Known-key distinguishers for some blockciphers. In: Proceedings of the 13th International Conference on the Theory and Application of Cryptology and Information Security. 2007, 315-324

[2] SmidM E, BranstadD K. Data encryption standard: past and future. Proceedings of the IEEE, 1988, 76(5): 550-559

[3] SchneierB. Description of a new variable-length key, 64-bit block cipher (blowfish). Lecture Notes in Computer Science, 1994, 809: 191-204

[4] KazumaroA, TetsuyaI, MasayukiK, MitsuruM, ShihoM, JunkoN, ToshioT. Camellia: a 128-bit block cipher suitable for multiple platforms design and analysis. In: Proceedings of the 7th Annual International Workshop Selected Areas in Cryptography. 2001, 39-56

[5] WallenJ. Design principles of the kasumi block cipher. Proceedings of the Helsinki University of Technology Seminar on Network Security, 2000

[6] RivestR L. The RC5 encryption algorithm. In: Proceedings of the 2nd International Workshop on Fast Software Encryption. 1995, 86-96

[7] WuW, ZhangL. Lblock: a lightweight block cipher. In: Proceedings of the 9th International Conference on Applied Cryptography and Network Security. 2011, 327-344

[8] MendelF, RechbergerC, SchläfferM, ThomsenS S. The rebound attack: Cryptanalysis of reduced Whirlpool and Grøstl. In: Proceedings of the 16th International Workshop on Fast Software Encryption. 2009, 260-276

[9] SasakiY, YasudaK. Known-key distinguishers on 11-round feistel and collision attacks on its hashing modes. In: Proceedings of the 18th International Workshop on Fast Software Encryption. 2011, 397-415

[10] SasakiY, EmamiS, HongD, KumarA. Improved known-key distinguishers on Feistel-SP ciphers and application to camellia. In: Proceedings of the 17th Australasian Conference Conference on Information Security and Privacy. 2012, 87-100

[11] MinierM, PhanR C W, PousseB. Distinguishers for ciphers and known key attack against rijndael with large blocks. Lecture Notes in Computer Science, 2009, 5580: 60-76

[12] LambergerM, MendelF, RechbergerC, RijmenV, SchläfferM. Rebound distinguishers: Results on the full Whirlpool compression function. In: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security. 2009, 126-143

[13] WuS, FengD, WuW. Cryptanalysis of the LANE hash function. In: Proceedings of the 16th Annual International Workshop on Selected Areas in Cryptography. 2009, 126-140

[14] GilbertH, PeyrinT. Super-sbox cryptanalysis: Improved attacks for AES-like permutations. In: Proceedings of the 17th International Workshop on Fast Soft Encryption. 2010, 365-383

[15] DongL, WuW, WuS, ZouJ. Known-key distinguisher on round reduced 3D block cipher. In: Proceedings of the 12th International Workshop on Information Security Applications. 2011, 55-69

[16] ZhengY, MatsumotoT, ImaiH. On the construction of block ciphers provably secure and not relying on any unproved hypotheses. Lecture Notes in Computer Science, 1989, 435: 461-480

[17] AdamsC, TavaresS, HeysH, WienerM. The CAST-256 encryption algorithm. Submission to AES competition, 1998

[18] YoshidaH, WatanabeD, OkeyaK, KitaharaJ, WuH, KüçükÖ, PreneelB. Mame: A compression function with reduced hardware requirements. In: Proceedings of the 9th International Workshop Workshop on Cryptographic Hardware and Embedded Systems. 2007, 148-165

[19] HiroseS, KuwakadoH, YoshidaH. SHA-3 proposal: Lesamnta. Submission to NIST, 2008

[20] BouillaguetC, DunkelmanO, LeurentG, FouqueP A. Lecture Notes in Computer Science, 2010, 6544: 18-35

[21] SasakiY, AokiK. Improved integral analysis on tweaked lesamnta. In: Proceedings of the 14th International Conference on Information Security and Cryptology. 2011, 1-17

[22] PeyrinT. Improved differential attacks for ECHO and Grøstl. In: Proceedings of the 30th Annual Cryptology Conference. 2010, 370-392

[23] MendelF, PeyrinT, RechbergerC, SchläfferM. Improved cryptanalysis of the reduced Grøstl compression function, ECHO permutation and aes block cipher. Lecture Notes in Computer Science, 2009, 5867: 16-35

[24] MatusiewiczK, Naya-PlasenciaM, NikolicI, SasakiY, SchläfferM. Rebound attack on the full LANE compression function. In: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security. 2009, 106-125

[25] MendelF, RechbergerC, SchläfferM. Cryptanalysis of twister. In: Proceedings of the 7th International Conference on Applied Cryptography and Network Security. 2009, 342-353

[26] RijmenV, TozD, VariciK. Rebound attack on reduced-round versions of JH. In: Proceedings of the 17th International Workshop on Fast Soft Encryption. 2010, 286-303

[27] Naya-PlasenciaM, TozD, VariciK. Rebound attack on JH42. In: Proceedings of the 17th International Conference on the Theory and Application of Cryptology and Information Security. 2011, 252-269

[28] WuS, FengD, WuW. Practical rebound attack on 12-round Cheetah-256. In: Proceedings of the 12th International Conference Annual International Conference on Information Security and Cryptology. 2009, 300-314

[29] KhovratovichD, Naya-PlasenciaM, RöckA, SchläfferM. Cryptanalysis of Luffa v2 components. In: Proceedings of the 17th International Workshop on Selected Areas in Cryptography. 2010, 388-409

[30] DaemenJ, KnudsenL R, RijmenV. The block cipher square. In: Proceedings of the 4th International Workshop on Fast Soft Encryption. 1997, 149-165

[31] FergusonN, KelseyJ, LucksS, SchneierB, StayM, WagnerD, WhitingD. Improved cryptanalysis of Rijndael. In: Proceedings of the 7th International Workshop on Fast Soft Encryption. 2000, 213-230

[32] GaliceS, MinierM. Improving integral attacks against Rijndael-256 up to 9 rounds. Lecture Notes in Computer Science, 2008, 5023: 1-15

[33] KnudsenL R, WagnerD. Integral cryptanalysis. In: Proceedings of the 9th International Workshop on Fast Soft Encryption. 2002, 112-127

[34] PreneelB, GovaertsR, VandewalleJ. Hash functions based on block ciphers: A synthetic approach. Lecture Notes in Computer Science, 1993, 773: 368-378

[35] BlackJ, RogawayP, ShrimptonT. Black-box analysis of the blockcipher-based hash-function constructions from PGV. Lecture Notes in Computer Science, 2002, 2442: 320-335

[36] YuX, WenlingW. Cryptanalysis of MAME compression function. In: Proceedings of the 2010 International Conference on Computer Design and Applications. 2010, 5: 602-605

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg