Re: Help with understanding sub-key generation in Blowfish

From: Ian Piper (ianpiper@mac.com)
Date: 03/17/03


From: ianpiper@mac.com (Ian Piper)
Date: 17 Mar 2003 01:11:10 -0800


"Tom St Denis" <tomstdenis@yahoo.com> wrote in message news:<2MZca.260578$UXa.191868@news02.bloor.is.net.cable.rogers.com>...
> "Ian Piper" <ianpiper@mac.com> wrote in message
> news:BA99F1FE.7CB0%ianpiper@mac.com...
> > Any thoughts on this, anyone?
>
> I have blowfish code in my LibTomCrypt library. Why not just check that
> out?
>
> http://libtomcrypt.org
>
> Tom

Thanks, I downloaded your source and it seems little different in
essentials from the source I had looked at already, so the question
remains (I've copied it here again). To clarify, I don't have a
problem understanding how (or why) the XOR function takes place. I am
confused about the size of the keyspace - 448 bits would require 14
loops, whereas all of the code I have seen does 18 loops (which would
lead to 576 bits, wouldn't it?).

==== quote ====
In particular there is one part that I am finding it hard to figure
out:
sub-key generation. As I understand it, in the initialisation process
we
start with a P-box array with 18 members, each a 32-bit number
representing
the hex values of the decimal portion of pi. Each member of the P-box
array
is then XORed with a 32-bit portion of the key to produce the
sub-keys.

I suppose that is one of the first confusions. For this to work don't
we
need to allow for 576 bits in the key (18 x 32)? But the maximum key
size in
Blowfish is 448 (14 x 32). In the original Schneier paper, it says
"XOR P1
with the first 32 bits of the key, XOR P2 with the second 32-bits of
the
key, and so on for all bits of the key (possibly up to P14)." I can
understand that. But when I look at the source, it has this in the
initialisation function:

#define bf_N 16
...
  j = 0;
  for (i = 0; i < bf_N + 2; ++i) {
    temp.word = 0;
    temp.w.byte0 = key[j];
    temp.w.byte1 = key[(j+1)%keybytes];
    temp.w.byte2 = key[(j+2)%keybytes];
    temp.w.byte3 = key[(j+3)%keybytes];
    data = temp.word;
    bf_P[i] = bf_P[i] ^ data;
    j = (j + 4) % keybytes;
  }

Which seems to be running the loop 18 times. It obviously works, so
what am
I missing here?

Second, and also related, is the next statement in the original paper.
I
quote: "(For every short key, there is at least one equivalent longer
key;
for example, if A is a 64-bit key, then AA, AAA, etc, are equivalent
keys)."
I can't understand why a repeated key is the same as the individual
key:
doesn't this suggest that any key consisting of repeated characters is
weak?
Again I know that Blowfish is not noted for weak keys, so there is
obviously
something I don't understand.
==== quote ====



Relevant Pages