Abstract
The reflection attack is a recently discovered self similarity analysis which is usually mounted on ciphers with many fixed points. In this paper, we describe two reflection attacks on r-round Blowfish which is a fast, software oriented encryption algorithm with a variable key length k. The attacks work successfully on approximately 2k + 32 − 16r number of keys which we call reflectively weak keys. We give an almost precise characterization of these keys. One interesting result is that 234 known plaintexts are enough to determine if the unknown key is a reflectively weak key, for any key length and any number of rounds. Once a reflectively weak key is identified, a large amount of subkey information is revealed with no cost. Then, we recover the key in roughly r·216r + 22 steps. Furthermore, it is possible to improve the attack for some key lengths by using memory to store all reflectively weak keys in a table in advance. The pre-computation phase costs roughly r·2k − 11 steps. Then the unknown key can be recovered in 2(k + 32 − 16r)/64 steps. As an independent result, we improve Vaudenay’s analysis on Blowfish for reflectively weak keys. Moreover, we propose a new success criterion for an attack working on some subset of the key space when the key generator is random.
Chapter PDF
Similar content being viewed by others
Keywords
References
Babbage, S.: Improved Exhaustive Search Attacks on Stream Ciphers. In: European Convention on Security and Detection, IEE Conference publication No. 408, pp. 161-166, IEE (1995)
Biham, E.: New Types of Cryptanalytic Attacks Using Related Keys. J. of Cryptology 7, 229–246 (1994)
Biham, E., Shamir, A.: Differential Cryptanalysis of Data Encryption Standard. Springer, Heidelberg (1993)
Biryukov, A., Wagner, D.: Slide Attacks. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 245–259. Springer, Heidelberg (1999)
Biryukov, A., Wagner, D.: Advanced Slide Attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 589–606. Springer, Heidelberg (2000)
Coppersmith, D.: The Real Reason for Rivest’s Phenomenon. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, p. 535. Springer, Heidelberg (1986)
Golić, J.: Cryptanalysis of Alleged A5 Stream Cipher, In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 239–255. Springer, Heidelberg (1997)
Hong, J., Sarkar, P.: Rediscovery of the Time Memory Tradeoff, Cryptology ePrint Archive, Report 2005/090 (2005)
Kaliski, B.S., Rivest, R.L., Sherman, A.T.: Is DES a pure Cipher(Results of More Cycling Experiments on DES). In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, p. 212. Springer, Heidelberg (1986)
Kara, O.: Reflection Attacks on Product Ciphers, Cryptology ePrint Archive, Report 2007/043 (2007)
Matsui, M.: Linear Cryptanalysis Method of DES Cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Moore, J.H., Simmons, G.J.: Cycle Structures of the DES with Weak and Semi-Weak Keys, In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 9–32. Springer, Heidelberg (1987)
Moore, J.H., Simmons, G.J.: Cycle Structure of the DES for Keys Having Palindromic (or Antipalindromic) Sequences of Round Keys. In: IEEE Transactions on Software Engineering, vol. SE-13, pp. 262–273. IEEE Computer Society Press, Los Alamitos (1987)
Rijmen, V.: Cryptanalysis and Design of Iterated Block Ciphers, Doctoral Dissertation, K.U. Leuven (1997)
Riordan, J.: An Introduction to Combinatorial Analysis. Wiley, New York (1958)
Schneier, B.: Description of a New Variable - Length Key, 64 Bit Block Cipher (Blowfish). In: Anderson, R. (ed.) Fast Software Encryption. LNCS, vol. 809, pp. 191–204. Springer, Heidelberg (1994)
Vaudenay, S.: On the Weak Keys of Blowfish. In: Gollmann, D. (ed.) Fast Software Encryption. LNCS, vol. 1039, pp. 27–32. Springer, Heidelberg (1996)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kara, O., Manap, C. (2007). A New Class of Weak Keys for Blowfish. In: Biryukov, A. (eds) Fast Software Encryption. FSE 2007. Lecture Notes in Computer Science, vol 4593. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74619-5_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-74619-5_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74617-1
Online ISBN: 978-3-540-74619-5
eBook Packages: Computer ScienceComputer Science (R0)