Cipher Structure which is Key Dependent

From: Jim Steuert (pjsteuert@rcn.com)
Date: 04/12/03 

From: Jim Steuert <pjsteuert@rcn.com>
Date: Sat, 12 Apr 2003 09:45:35 -0400

Here is a cipher idea which is not given much publicity.
Bruce Schneier in AC2 recommended key-dependent s-boxes.

I know some will consider this amateurish generalization,
but if done "correctly", what are the risks? And I believe
there are an infinite number of "correct" generalizations
in this area. The question is, what is a "correct" class
of parameterized cipher structures?

The idea is to start with a reliable or proven cipher or hash design
such as SHA-1 or SHA-256 and then add a key-dependent number
and form of additional stages.

Can we prove that it "adds". and does not decrease security,
without looking at each instance of a cipher structure?

Key-dependent structure means that if keys are changed often
enough (via DH or some other method) then the amount of
plaintext/ciphertext pairs for any given structure is limited.

I know of no form of cryptanalysis which can attack these
general "classes" of ciphers.

Consider, for example, a 256-bit block cipher with 8 32-bit rails
or state variables R(0)-R(7), which is a Substitution-Permutation
Network (SPN) wherein the permutation parts consist of feistel rounds.

Let each stage s be either a feistel mixer round or an
MDS mixer. Assume that the hash functions h1, h2, h3
are SHA-1 or something as effective.

h1 = sha-1( s, key, constant1 )
h2 = sha-1( s, key, constant2 )
h3 ...
...

Let the range of each hash be a subset of bits
dependent on its context:

For selecting a rail, h has range 0-7.
For selecting a rotate amount it has range 0-31.
For selecting an balanced-correlation-immune 5-bit f-function, h has range
0-7.
For selecting a 32-bit mixer, h has range 0-1023.
  (I've coded this: see my "Wide Random Mixer" code of April 21 2002)
For selecting a specific MDS mixer, let h range from 0 to, say, 31.

Then define a cipher based on n>100 stages, each
stage s of which has the following form:

"stage type" type = h( stage s, key )

type 1: Feistel Mix: R(h1) = MIX(h2) ( R(h1), R(h3) );
type 2: MDS: R(h1) = MDS( R(h2) );
type 3: Rotate: R(h1) = R(h1) rotate (h2 mod 32)
type 4: SumMod232: R(h1) = R(h1) + R(h2) + R(h3) + R(h4)
type 5: Ffunction: R(h1) = R(h1) + f(h2)( R(h3),R(h4),R(h5),R(h6)
,R(h7) )

Note that all operations are either multipermutations between
two or more rails, or else are permutations of a rail.

The inverse of this cipher is simple, given the key.