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

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?

-
Why not use directly bcrypt(cost, IV, key), with an initialization vector (which you should have anyways) as salt? –  Paŭlo Ebermann Aug 27 '12 at 18:52
I could, of course, stretch the key into a longer one with bcrypt, however this would violate the condition of the original problem -- using 64-bit encryption key :) I can restate the question: is using the state of bcrypt(cost, salt, password) directly for encryption of data (instead of encrypting "OrpheanBeholderScryDoubt" 64 times and then using the result as the key for new state) acceptable? –  dchest Aug 27 '12 at 19:16
Oh, I think that's what you suggested, actually, right? –  dchest Aug 27 '12 at 19:22
This is known as "EksBlowfish" (mentioned in the bcrypt specification) and I suppose it is at least as secure as normal Blowfish, and as hard to brute-force (in a known-plaintext attack on some part of the message) as a bcrypt output. –  Paŭlo Ebermann Aug 27 '12 at 19:23
Actually I suggested using the output of bcrypt as the new blowfish key, but using EksBlowfish directly makes more sense, I think. –  Paŭlo Ebermann Aug 27 '12 at 19:24

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.

-
Correction: 2^32 * 8-byte blocks would be 32 GB (can't edit your post, because edits under 6 characters are not allowed for some reason.) –  dchest Aug 27 '12 at 23:33
@dchest: You are right - looks like I calculated with bits instead of bytes here. Thanks. –  Paŭlo Ebermann Aug 28 '12 at 11:19