Discussion:
Blowfish Variant and Possible Ramifications
2006-03-15 13:49:02 UTC
Raw Message
I was consulting for a client who has an application that uses uses the
Blowfish algorithm. They were having trouble getting files saved with
it to interoperate with another program that uses it as well.

What I found was that their Feistel round function is quite...bizarre.

This is the what they had:

unsigned int F(BLOWFISH_CTX *ctx, unsigned int x) {
unsigned short a, b, c, d;
unsigned int y, z;

d = (unsigned short)(x & 0xFF);
x >>= 8;
c = (unsigned short)(x & 0xFF);
x >>= 8;
b = (unsigned short)(x & 0xFF);
x >>= 8;
a = (unsigned short)(x & 0xFF);

z = ctx->S[3][a];
y = ctx->S[1][c];
z &= 1;
y &= 1;
z ^= 32;
y ^= 32;
y += z;

y += ctx->S[2][b];
y += ctx->S[0][d];

return y;
}

The "real" one looks like this:

static unsigned int RealF(BLOWFISH_CTX *ctx, unsigned int x) {
unsigned short a, b, c, d;
unsigned int y;

d = (unsigned short)(x & 0xFF);
x >>= 8;
c = (unsigned short)(x & 0xFF);
x >>= 8;
b = (unsigned short)(x & 0xFF);
x >>= 8;
a = (unsigned short)(x & 0xFF);
y = ctx->S[0][a] + ctx->S[1][b];
y = y ^ ctx->S[2][c];
y = y + ctx->S[3][d];

return y;
}

Noone could remember who did this or why. My best guess is someone
thought that making the algorithm a little more proprietary would make
it secure, but they ended up ruining it. As you can see, once of the
differences is that most of the data of the s-box is thrown out since
they AND it with 1, and then they XOR that with 32 (which obviously
does nothing ever). Everything other than this function is the same as
the Blowfish spec.

Now, I honestly haven't worked out the exact math behind the Feistel
rounds and the permutation/substitution boxes and such. What I was
wondering is, obvious coding flaws aside, does this make the algorithm
less secure? It would seem to be much less secure as this affects both
the initial key generation as well as encryption/decryption. It seems
like this would possibly expose the key a little in the ciphertext. If
anyone has any thoughts, I'm very interested. I'd like to understand
this stuff better.

Peter Gutmann
2006-03-15 15:36:07 UTC
Raw Message
I was consulting for a client who has an application that uses uses the
Blowfish algorithm. They were having trouble getting files saved with it to
interoperate with another program that uses it as well.
What I found was that their Feistel round function is quite...bizarre.
[...]
Noone could remember who did this or why. My best guess is someone thought
that making the algorithm a little more proprietary would make it secure, but
they ended up ruining it.
Some years ago I was contacted by a company who wanted me to design a
proprietary block cipher for them. After fruitlessly trying to convince them
that this was a dumb idea, I eventually suggested that if they really wanted
an incompatible-with-everything-else cipher they could just take Blowfish (as
I said, it was some time ago and their options at the time were either
Blowfish or 3DES) and make a trivial tweak to it, e.g. by changing the
constants used to set up the S-Boxes or by applying a DESX-like whitening
step, some no-op change that wouldn't make it any weaker. I never heard from
them again after that, but if that sort of mentality exists out there then
constructs like the one you describe aren't that unexpected.

Peter.
David Wagner
2006-03-16 01:36:25 UTC
Raw Message
My best guess is someone
thought that making the algorithm a little more proprietary would make
it secure, but they ended up ruining it. As you can see, once of the
differences is that most of the data of the s-box is thrown out since
they AND it with 1, [...]
does this make the algorithm less secure?
Yup. Looks like it has created a 2r-round differential characteristic
of probability 1/2^r, where a difference in one of the input bytes to
the F function leads to no difference at the output, so I'd expect this
ruined version of Blowfish to completely fall apart under differential
cryptanalysis. The attack might require tens of thousand chosen
plaintexts or something like that (wild speculation...). This is
just a wild guess -- if the answer really matters, please confirm it
for yourself.