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

k

. The attacks work successfully on approximately 2

k

 + 32 − 16

r

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

·2

16

r

 + 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

·2

k

 − 11

steps. Then the unknown key can be recovered in 2

(

k

 + 32 − 16

r

)/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.