Known-key distinguishers on type-1 Feistel scheme and near-collision attacks on its hashing modes
Le DONG1,2,3,*(),Wenling WU2,Shuang WU2,Jian ZOU2,3
1. College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China 2. Institute of Software, Chinese Academy of Sciences, Beijing 100190, China 3. Graduate University of Chinese Academy of Sciences, Beijing 100149, China
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.
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 doi: 10.1109/5.4441
3
SchneierB. Description of a new variable-length key, 64-bit block cipher (blowfish). Lecture Notes in Computer Science, 1994, 809: 191-204 doi: 10.1007/3-540-58108-1_24
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 doi: 10.1007/3-540-60590-8_7
7
WuW, ZhangL. Lblock: a lightweight block cipher. In: Proceedings of the 9th International Conference on Applied Cryptography and Network Security. 2011, 327-344 doi: 10.1007/978-3-642-21554-4_19
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 doi: 10.1007/978-3-642-03317-9_16
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 doi: 10.1007/978-3-642-21702-9_23
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 doi: 10.1007/978-3-642-02384-2_5
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 doi: 10.1007/978-3-642-05445-7_8
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 doi: 10.1007/978-3-642-13858-4_21
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 doi: 10.1007/0-387-34805-0_42
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 doi: 10.1007/978-3-642-19574-7_2
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 doi: 10.1007/978-3-642-05445-7_2
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 doi: 10.1007/978-3-642-01957-9_21
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 doi: 10.1007/978-3-642-13858-4_16
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 doi: 10.1007/BFb0052343
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 doi: 10.1007/978-3-540-68164-9_1
33
KnudsenL R, WagnerD. Integral cryptanalysis. In: Proceedings of the 9th International Workshop on Fast Soft Encryption. 2002, 112-127 doi: 10.1007/3-540-45661-9_9
34
PreneelB, GovaertsR, VandewalleJ. Hash functions based on block ciphers: A synthetic approach. Lecture Notes in Computer Science, 1993, 773: 368-378 doi: 10.1007/3-540-48329-2_31
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 doi: 10.1007/3-540-45708-9_21
36
YuX, WenlingW. Cryptanalysis of MAME compression function. In: Proceedings of the 2010 International Conference on Computer Design and Applications. 2010, 5: 602-605
