Blowfish breaks between versions 2.0.1 and 2.3

[Eric Chamberlain]

With version 2.0.1 our code works fine, but after upgrading to 2.3,

   blowfish = Blowfish.new(SECRET_KEY)

generates the following error:

   ValueError: Maximum key size is 448 bits

Our SECRET_KEYs are 74 ASCII characters long and we can't easily change them, given the amount of data encrypted with the keys.

Is it possible to bring back the 2.0.1 behavior to support backwards compatability with keys of arbitrary length?

[Thorsten Behrens (sbehrens-gmx)]

That was changed in March 2009, when Dwayne replaced the Blowfish implementation to overcome licensing limitations of the old code. See https://github.com/dlitz/pycrypto/commit/7f3ee6d8eb7225a53a1e63207833e2627ca8e350

Ever since then, this is brand-new code. It wouldn't really be "bringing back", rather it'd be "adding".

I think this speaks to the reason Dwayne didn't want any more C implementations of ciphers in pycrypto. You never know what odd behavior you may inflict.

[Darsey Litzenberger (dlitz)]

I don't think this is a bug in PyCrypto. Blowfish specifies a maximum key size of 448 bits, so if your code is using longer keys, then you're not really using Blowfish anymore, you're using PyCryptoBugFish.

What are you doing that you need a key longer than 448 bits?

"Eric Chamberlain" <email address hidden> wrote:

>Public bug reported:
>
>With version 2.0.1 our code works fine, but after upgrading to 2.3,
>
>   blowfish = Blowfish.new(SECRET_KEY)
>
>generates the following error:
>
>   ValueError: Maximum key size is 448 bits
>
>Our SECRET_KEYs are 74 ASCII characters long and we can't easily change
>them, given the amount of data encrypted with the keys.
>
>Is it possible to bring back the 2.0.1 behavior to support backwards
>compatability with keys of arbitrary length?
>
>** Affects: pycrypto
> Importance: Undecided
> Status: New
>
>--
>You received this bug notification because you are subscribed to
>Python-
>Crypto.
>https://bugs.launchpad.net/bugs/695417
>
>Title:
> Blowfish breaks between versions 2.0.1 and 2.3

--
Sent from my Android phone with K-9 Mail. Please excuse my brevity.

[Eric Chamberlain (eric-rf)]

We don't really need a longer key, it's the key size we used and now have tens of thousands of database columns encrypted a key of that length.

I haven't looked at the old code, is there something we could do to modify the key to get it to work with the new code?

I was hoping for an easier solution than decrypting and re-encrypting the data.

On Dec 29, 2010, at 4:23 PM, Dwayne Litzenberger wrote:

> I don't think this is a bug in PyCrypto. Blowfish specifies a maximum
> key size of 448 bits, so if your code is using longer keys, then you're
> not really using Blowfish anymore, you're using PyCryptoBugFish.
>
> What are you doing that you need a key longer than 448 bits?
>
>
> "Eric Chamberlain" <email address hidden> wrote:
>
>> Public bug reported:
>>
>> With version 2.0.1 our code works fine, but after upgrading to 2.3,
>>
>> blowfish = Blowfish.new(SECRET_KEY)
>>
>> generates the following error:
>>
>> ValueError: Maximum key size is 448 bits
>>
>> Our SECRET_KEYs are 74 ASCII characters long and we can't easily change
>> them, given the amount of data encrypted with the keys.
>>
>> Is it possible to bring back the 2.0.1 behavior to support backwards
>> compatability with keys of arbitrary length?
>>
>> ** Affects: pycrypto
>> Importance: Undecided
>> Status: New
>>
>> --
>> You received this bug notification because you are subscribed to
>> Python-
>> Crypto.
>> https://bugs.launchpad.net/bugs/695417
>>
>> Title:
>> Blowfish breaks between versions 2.0.1 and 2.3
>
> --
> Sent from my Android phone with K-9 Mail. Please excuse my brevity.
>
> --
> You received this bug notification because you are a direct subscriber
> of the bug.
> https://bugs.launchpad.net/bugs/695417
>
> Title:
> Blowfish breaks between versions 2.0.1 and 2.3
>
> Status in Python Cryptography Toolkit:
> New
>
> Bug description:
> With version 2.0.1 our code works fine, but after upgrading to 2.3,
>
> blowfish = Blowfish.new(SECRET_KEY)
>
> generates the following error:
>
> ValueError: Maximum key size is 448 bits
>
> Our SECRET_KEYs are 74 ASCII characters long and we can't easily change them, given the amount of data encrypted with the keys.
>
> Is it possible to bring back the 2.0.1 behavior to support backwards compatability with keys of arbitrary length?
>
> To unsubscribe from this bug, go to:
> https://bugs.launchpad.net/pycrypto/+bug/695417/+subscribe

[Eric Chamberlain (eric-rf)]

I had a chance to look through the blowfish.c code, it looks like there isn't a way to make the old key work with the new code, unless the key length checking is removed.

Looking through our implementation notes, a 72-character key was chosen because that was the number of iterations through the key string. The blowfish reference C implementation (http://www.schneier.com/blowfish-download.html) release notes mentions a 72-byte key, the C implementations by Bruce and others don't check the key length and will take any size key and use the first 72 bytes. I'm not sure if a key size greater than 448-bits is cryptographically significant.

Would it be possible to again support key sizes larger than 56-characters for backwards compatibility and compatibility with other C implementations? Or note in the documentation that key sizes greater than 448-bits are no longer supported?

On Dec 29, 2010, at 4:38 PM, Eric Chamberlain wrote:

> We don't really need a longer key, it's the key size we used and now have tens of thousands of database columns encrypted a key of that length.
>
> I haven't looked at the old code, is there something we could do to modify the key to get it to work with the new code?
>
> I was hoping for an easier solution than decrypting and re-encrypting the data.
>
>
> On Dec 29, 2010, at 4:23 PM, Dwayne Litzenberger wrote:
>
>> I don't think this is a bug in PyCrypto. Blowfish specifies a maximum
>> key size of 448 bits, so if your code is using longer keys, then you're
>> not really using Blowfish anymore, you're using PyCryptoBugFish.
>>
>> What are you doing that you need a key longer than 448 bits?
>>
>>
>> "Eric Chamberlain" <email address hidden> wrote:
>>
>>> Public bug reported:
>>>
>>> With version 2.0.1 our code works fine, but after upgrading to 2.3,
>>>
>>> blowfish = Blowfish.new(SECRET_KEY)
>>>
>>> generates the following error:
>>>
>>> ValueError: Maximum key size is 448 bits
>>>
>>> Our SECRET_KEYs are 74 ASCII characters long and we can't easily change
>>> them, given the amount of data encrypted with the keys.
>>>
>>> Is it possible to bring back the 2.0.1 behavior to support backwards
>>> compatability with keys of arbitrary length?
>>>
>>> ** Affects: pycrypto
>>> Importance: Undecided
>>> Status: New
>>>
>>> --
>>> You received this bug notification because you are subscribed to
>>> Python-
>>> Crypto.
>>> https://bugs.launchpad.net/bugs/695417
>>>
>>> Title:
>>> Blowfish breaks between versions 2.0.1 and 2.3
>>
>> --
>> Sent from my Android phone with K-9 Mail. Please excuse my brevity.
>>
>> --
>> You received this bug notification because you are a direct subscriber
>> of the bug.
>> https://bugs.launchpad.net/bugs/695417
>>
>> Title:
>> Blowfish breaks between versions 2.0.1 and 2.3
>>
>> Status in Python Cryptography Toolkit:
>> New
>>
>> Bug description:
>> With version 2.0.1 our code works fine, but after upgrading to 2.3,
>>
>> blowfish = Blowfish.new(SECRET_KEY)
>>
>> generates the following error:
>>
>> ValueError: Maximum key size is 448 bits
>>
>> Our SECRET_KEYs are 74 ASCII characters long and we can't easily change them, given the amount of...

[Thorsten Behrens (sbehrens-gmx)]

Have you tested to see what happens when key length checking is removed and everything else remains the same? I'm not saying that'll make it into pycrypto proper, but if you can make your stuff work with a one-line manual change, then I'd say go for it.

Looking through the reference implementation: You are right. It does say 72 bytes. The description of Blowfish states 56 bytes, and implementations vary. I guess it depends on whether an implementation was written from the spec or the reference code.

Bruce Schneier's applied cryptography 2nd ed states that the maximum key length is 448 bits, and then goes on to include code with the book that allows up to 72 bytes.

Hell even the IEEE references 72 bytes as the maximum key length. Where'd that come from?

http://ieeexplore.ieee.org/iel5/10014/32158/01505661.pdf

<whatamess>

I know not where the notion of a 72-byte key length limit originally came from. Dwayne, how well do you know Mr. Schneier? :D

Given the prevalence of 72-byte keys, it may make sense to have a way to request a blowfish object that allows up to 72-byte keys. What's your take, Dwayne?

[Thorsten Behrens (sbehrens-gmx)]

I blush to admit that it is wikipedia that shed light on why we see 72-byte implementations. Oh, the shame.

>>
Because the P-array is 576 bits long, and the key bytes are XORed through all these 576 bits during the initialization, many implementations support key sizes up to 576 bits. While this is certainly possible, the 448 bits limit is here to ensure that every bit of every subkey depends on every bit of the key[2], as the last four values of the P-array don't affect every bit of the ciphertext. This point should be taken in consideration for implementations with a different number of rounds, as even though it increases security against an exhaustive attack, it weakens the security guaranteed by the algorithm. And given the slow initialization of the cipher with each change of key, it is granted a natural protection against brute-force attacks, which doesn't really justify key sizes longer than 448 bits.
>>

And Mr. Schneier has this to say:

>>
Function F, the non-reversible function, gives Blowfish the best possible avalanche effect for a Feistel network: every text bit on the left half of the round affects every text bit on the right half. Additionally, since every subkey bit is affected by every key bit, the function also has a perfect avalanche effect between the key and the right half of the text after every round. Hence, the algorithm exhibits a perfect avalanche effect after three rounds and again every two rounds after that.
>>

and

>>
The number of rounds is set at 16 primarily out of desire to be conservative. However, this number affects the size of the P- array and therefore the subkey-generation process; 16 iterations permits key lengths up to 448 bits.
>>

and

>>
The subkey generation process is designed to preserve the entire entropy of the key and to distribute that entropy uniformly throughout the subkeys.
>>

and

>>
The 448 limit on the key size ensures that the every bit of every subkey depends on every bit of the key. (Note that every bit of P15, P16, P17, and P18 does not affect every bit of the ciphertext, and that any S-box entry only has a .06 probability of affecting any single ciphertext block.)
>>

Which means 72-byte keys had been rejected by the author of the algorithm. They also aren't "the end of the world, this will be cracked" - it makes the algorithm a little less secure, but it's still not something you could break. Brute-force is silly at 56 or 72 bytes, anyway, which means only algorithmic attacks would be possible. No true weaknesses have been found. Yet, maybe.

I'd say default to 56 bytes and allow 57-72 byte keys by a parameter to be passed - sorry, Eric, that means you'd have to change your backend code or keep changing pycrypto when you use it.
When the parameter to allow longer keys is passed, throw a RuntimeWarning. Would have to see whether that is suppressed by default - if not, maybe a FutureDeprecationWarning instead. We could discuss whether the warning should be something a developer would see when using -Wdefault, and suppressed otherwise; or whether we prefer to do a RuntimeWarning and let the chips fall where they may.

[Darsey Litzenberger (dlitz)]

Here's my take on it: Blowfish, as published by Schneier and as analysed by
academic cryptologists, supports keys up to 448 bits. Schneier has given a
specific reason for that. If you somehow manage to exploit a bug in the
reference implementation to use 72-byte keys, then you're not actually using
Blowfish; you're using something else---let's call it "576fish".

The job of Crypto.Cipher.Blowfish is to implement Blowfish, so adding support
for 576fish is beyond the scope of that module. (The AES module works the
same way---it only supports the 128-bit block size specified in the AES
standard, even though Rijndael supports larger block sizes.) I might be
persuaded to add a 576fish module, but of course I would use the same criteria
that I use for other requests to add additional ciphers to PyCrypto, such as:

    - significant use in widely-deployed protocols and/or FOSS; and
    - withstanding analysis by academic cryptanalysts.

At this time, I'm not aware of any widespread use of 576fish, nor any academic
cryptanalysis effort against 576fish.

Sorry, Eric, but my advice is that you re-key your database. You should have
a process to do that anyway, in case your keys are compromised without your
knowledge, or in case the algorithm is broken. I would suggest phasing out
576fish and replacing it with something like AES-256, while you are at it.

Regards,
- Dwayne

[Eric Chamberlain (eric-rf)]

No problem, we re-keyed 10 months ago.