A new class of weak keys for Blowfish

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 kappa. The attacks work successfully on approximately 2(kappa+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 2(34) 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 center dot 2(16r+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 F in advance. The pre-computation phase costs roughly r center dot 2(kappa-11) steps. Then the unknown key can be recovered in 2((kappa+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.