The Delicate Issues of Addition with Respect to XOR Differences
In this paper we analyze the previous attacks on the block cipher SHACAL-1 and show that all the differential-based attacks fail due to mistreatment of XOR differences through addition. We show that the previously published differential and rectangle atta
- PDF / 316,822 Bytes
- 20 Pages / 430 x 660 pts Page_size
- 110 Downloads / 268 Views
School of Mathematics and System Sciences, Shandong University Jinan 250100, China [email protected] 2 Einstein Institute of Mathematics, Hebrew University Jerusalem 91904, Israel [email protected] 3 Katholieke Universiteit Leuven Dept. of Electrical Engineering ESAT/SCD-COSIC Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium [email protected]
Abstract. In this paper we analyze the previous attacks on the block cipher SHACAL-1 and show that all the differential-based attacks fail due to mistreatment of XOR differences through addition. We show that the previously published differential and rectangle attacks on SHACAL-1 fail as some of the underlying differentials are impossible. The relatedkey rectangle attacks on the cipher generally fail, but if some conditions are imposed on the key (i.e., for a weak key class) they work. After identifying the flaws in previous attacks, we present possible fixes to these attacks. We then present some modified differentials which lead to a related-key rectangle attack which can be applied to 2504 weak keys. Our observations are then used to improve a related-key rectangle attack on IDEA by a factor of 2. Keywords: Related-Key Rectangle attack, Block cipher, SHACAL-1, IDEA.
1
Introduction
Differential cryptanalysis [5] was introduced by Biham and Shamir in 1990, and it is one of the most powerful known attacks on block ciphers. The related-key attack [1] was introduced by Biham in 1993. The attack considers the encryption under two unknown but related keys. The attack’s applicability depends on the
Supported by National Natural Science Foundation of China Key Project No.90604036 and 973 Program No.2007CB807902. The research presented in this paper was supported by the Adams fellowship. This work was supported in part by the Concerted Research Action (GOA) Ambiorics 2005/11 of the Flemish Government and by the IAP Programme P6/26 BCRYPT of the Belgian State (Belgian Science Policy).
C. Adams, A. Miri, and M. Wiener (Eds.): SAC 2007, LNCS 4876, pp. 212–231, 2007. c Springer-Verlag Berlin Heidelberg 2007
The Delicate Issues of Addition with Respect to XOR Differences
213
key schedule algorithm and shows that a block cipher with a weak key schedule algorithm may be vulnerable to this kind of attack. Many cryptanalytic results of this attack model were presented in [6, 10, 11, 12, 15]. Illuminated by the complex local collisions of the analysis of SHA-0 which were pointed in the earlier papers in 1997 by X.Y.Wang [25], SHA-0 [24], and SHA-1 [22], we show that in the case of SHACAL-1 [8], all previous differential attacks [2, 7, 10, 13, 14, 17] fail due to this fact. For example, we show that the attack of [10] uses a differential that can never be satisfied. For other attacks, e.g., the related-key rectangle attack on the full SHACAL-1 in [7], we show that the attack is applicable only to a weak key class (of 2496 keys). We show that the combination of XOR differentials (or related-key XOR differentials) when the addition operation is used should b
Data Loading...
