GENERALIZED BLOWFISH
--------------------

A look at the potential flexibility of the Blowfish cipher.

The Blowfish cipher, designed by Bruce Schneier [1] [2] [3], is designed to
use a 64-bit block size, with 16 rounds.  This results in a key space of up 
to 448 bits, utilizing s-boxes that take up 4168 bytes, and utilizes 521 
encryptions to initilize the s-boxes.

The s-boxes are initialized with the digits of pi, although any other
constant with suitable randomness could be used.  If we forgo the 
computationally expensive s-box initilization, it is important to not have
duplicate s-box entries. [4]  We may also make ourselves more vulnerable to
cryptoanalysis not yet published.

Blowfish can be generalized as follows:

* The block size is n-bits long

* We use r rounds

* The key size, where each bit of the key affects all bits of the ciphertext,
  is up to (r - 2) * (n / 2) bits long.  We use r-2 rounds because it takes 
  three rounds to get a full avalanche effect.

* The s-boxes and p-boxes take up this abount of space, in bytes:

  /    n             \	
  |    - + 2         |  n 
  |    8     + r + 2 | -- 
  |   2              | 16 
  \                  / 

* We perform this many encryptions to initialize the s-boxes:

     n
     - + 1   r
     8     + - + 1
    2        2 

A look at this table, calculated for 16-round encryption, shows that
we get dimishing returns as we make the block size larger, where the
s-box size and the initial setup doubles for every eight bits added to
the block size:

blocksize  max key size memory needed (bytes) Key setup encryptions
---------  ------------ --------------------   --------------------
        8            56                   13                     13
       16           112                   34                     17
       24           168                   75                     25
       32           224                  164                     41
       40           280                  365                     73
       48           336                  822                    137
       56           392                1,855                    265
       64           448                4,168                    521
       72           504                9,297                  1,033
       80           560               20,570                  2,057
       88           616               45,155                  4,105
       96           672               98,412                  8,201
      104           728              213,109                 16,393
      112           784              458,878                 32,777
      120           840              983,175                 65,545
      128           896            2,097,296                131,081
      136           952            4,456,601                262,153
      144         1,008            9,437,346                524,297
      152         1,064           19,923,115              1,048,585
      160         1,120           41,943,220              2,097,161

[1] http://www.counterpane.com/blowfish.html

[2] http://www.counterpane.com/bfsverlag.html

[3] http://www.counterpane.com/bfdobsoyl.html

[4] http://www.dmi.ens.fr/~vaudenay/pub.html#Vau96a