Article 29595 of sci.crypt:
Path: jac.zko.dec.com!crl.dec.com!pa.dec.com!decwrl!enews.sgi.com!lll-winken.llnl.gov!uwm.edu!spool.mu.edu!mnemosyne.cs.du.edu!nyx10.cs.du.edu!not-for-mail
From: colin@nyx10.cs.du.edu (Colin Plumb)
Newsgroups: sci.crypt
Subject: Blowfish key schedule problem
Date: 1 Jun 1995 03:31:08 -0600
Organization: University of Denver, Dept. of Math & Comp. Sci.
Lines: 87
Message-ID: <3qk1cs$qr5@nyx10.cs.du.edu>
NNTP-Posting-Host: nyx10.cs.du.edu

I was playing with Blowfish a bit and thinking about its (IMHO,
overly complex) key scheduling algorithm, when I came across something
that's quite suspiscious.  I don't think it can be turned into an
attack, but it's worth fixing nonetheless.

Blowfish is a Feistel cipher with the keys inserted in the Feistel
ladder like so:

      K2      K4       K16 K18
      |       |        |   |
      v       v        v   v
----*-*-+---*-*-+....*-*-+-*--\    /->
    ^   |   ^   |    ^   |     \  /
    |   F   |   F    |   F      \/
    F   |   F   |    F   |      /\
    |   v   |   v    |   v     /  \
--*-+---*-*-+---*....+---*-*--/    \->
  ^       ^                ^
  |       |                |
  K1      K3               K17

The way the key schedule is built, the user KEY is circularly XORed into
the K1..K18 array, then a block of zero is encrypted and the output block
is used to replace K1 and K2, then the output block is re-encrypted and
that output block replaces K3 and K4, and so on until after 9 rounds,
K17 and K18 are set.  (Then Blowfish goes on to the S-boxes, but  I'll skip
that.)

This is a bootstrapping sort of key schedule.  The subkeys K1..K18 and the
S-boxes are initialized with the digits of pi and then all this munging
takes place.

The concern is the second encryption, when K1 and K2 are set, and then
K1 and K2 are fed into the cipher.  On the lower leg, K1 * K1 (* is XOR)
is zero.  Then on the upper leg, fed into the second F box, is K2 * K2 * F(0).
Since the F boxes have not been modified by anything yet (they're set to the
digits of pi default), this is also a fixed value.  (I haven't computed
it, admittedly.)

Thus, what actually gets encrypted is a fixed value, and it gets
encrypted with 14 rounds rather than 16.  The block chaining comes to
naught in this case.

Swapping the inputs is a minor help, but it's still a reduced
cipher.  It's equivalent to setting K1 and K2 to 0 and feeding K1 * K2
into both inputs.  Not quite the 64 bits of randomness that's expected.

The simplest fix is to populate the S-boxes backwards, starting with
K17 and K18.  That way, K1 and K2 are never fed into the
cipher.  (Of course, fitting in the S boxes somewhere is more involved.)

But I'd really rather have a simpler key scheduling algorithm.
How about a couple of passes over the key data with a scrambler polynomial
of sufficient length, a la SHA?  That provides good uniformity properties
and a much simpler analysis.

(Note to amateur cryptgraphers: simple analysis is a *good* thing, if
it doesn't weaken the cipher.  You've probably heard of the software
aphorism that it can either be so simple there are obviously no flaws,
or so complex there are no obvious flaws?  And you know that the latter
kind of software always has lots of flaws, right?  The same principle
applies here.  It's better to be able to prove that an attack won't
work than to have to guess that it won't because it's too much work.)

I like Blowfish's round structure, although I'd like to understand the
effects of DES's E expansion and similar operations better before I
totally commit to a cipher without such an operation.  But the key schedule
has be worried, as I can't really classify it's behaviour other than
as a Monster Mash.  ("Ooo!  Mash Good!")
-- 
	-Colin

P.S. It's interesting that IDEA's round structure:

-->I--+--->*-->
      |    ^
      v    |
      *->F-+
      ^    |
      |    v
-->I--+----*-->

Where I is an invertible mapping and F is a one-way function, hasn't
attracted any more attention.  I wonder why?  Is it the dager of symmetric
transition matrices like in the original PES?
-- 
	-Colin


