Can iterated key expansion in Blowfish slow down bruteforce attacks on small key sizes?

Question

Suppose I have to use 64-bit keys for encryption (e.g. to comply with export restrictions). For this question, assume this key is truly random, and the encryption algorithm is Blowfish.

Blowfish key schedule expands this 8-byte key into 4168 bytes of state (P-array and S-boxes). Will it slow down bruteforce attacks if I run this expansion a huge number of rounds?

REPEAT rounds
   state := ExpandKey(state, key)
END

(Basically, the scheme is similar to bcrypt if you throw away salt and instead of encrypting a constant to derive a key, use the final state for actual encryption.)

Are there any other practical attacks on such schemes faster than brute force?

Answer 1

Something similar as what you suggest is already known as "Expensive key schedule Blowfish", or "EksBlowfish". It is the encryption algorithm in the core of Bcrypt (a slow hash function designed for password hashing).

It also incorporates a salt, and its setup function is like this (retyped from the paper):

EksBlowfishSetup(cost, salt, key):
   state ← initState()
   state ← ExpandKey(state, salt, key)
   repeat(2^cost):
      state ← ExpandKey(state, 0, salt)  
      state ← ExpandKey(state, 0, key)
   return state

InitState() is the same as in Blowfish: It fills the P- and S-boxes with digits of $\pi$. ExpandKey(state, 0, ...) also works just like the key expansion function of Blowfish - it XORs the P-boxes with (a repeated version of) the key, then encrypts a zero stream in CBC-mode with Blowfish (using the existing state), replacing the boxes with the results after each block is encrypted. The version with a salt parameter simply uses this salt (repeated) as the original value to encrypt.

The actual encryption of EksBlowfish works just like normal Blowfish encryption. In Bcrypt, this is then used to encrypt (64 times in ECB-mode) the 3-block ASCII-string OrpheanBeholderScryDoubt to produce the bcrypt hash, but you can use EksBlowfish also separately.

It can't get worse than "normal" Blowfish, and will get as hard to bruteforce as a bcrypted password with same cost factor. I suppose you could use a constant salt, but using some random (but not secret) salt delivered with the message looks better (and avoids precomputation). If your performance is critical, you should of course not change the salt with every SSL packet.

---

There is another problem with Blowfish: It only has 64-bit blocks, and as such can't get more secure than any 64-bit block cipher. Repeating blocks will occur likely after $2^{32}$ blocks (i.e. 32 GB), which might be enough or not, depending on your application. And repeated blocks give points of attack.

You might consider instead using a 128-bit block cipher like AES, and derive your key with bcrypt from the "short" 64-bit key.