Re: Schneier's "Helix" cipher is remarkably similar to the "generic feistel cipher"

From: Jim Steuert (pjsteuert_at_rcn.com)
Date: 11/08/03 

Date: Sat, 08 Nov 2003 13:59:26 -0500

Gregory Rose wrote:
> Jim Steuert wrote:
> ...
>> a) Purely theoretical: Using ideal assumptions about the properties of
>> the
>> black-box invertible hash mixers.
>
> Good luck. If you achieve this, you will be justly
> famous and have many good citations. (sounds like
> a fortune cookie)

I really don't see why an "ideal" construction is difficult.
Consider this:

Let each black-box "invertible hash mixer" H, J, K, and L,
is an independent and randomly generated but publicly known permutation.
(see picture at bottom)

Let H,J,K,L each have input and output of 5 32-bit digest
variables: a, b, c, d, and e.

Ideally, each of H, j, K, L is 2^160-entry "virtual" random permutation
table.

It can be queried only by direct look-up in unit time. There is no
structural simplification of this "virtual table". The reverse
permutation's virtual table also exists and can also be queried in
unit time, like an oracle.

One side-effect result of this random generation is that all
combinations of subsets of input and output bits of the
permutation, with other values set constant, will be
statistically independent.

Let H_k1(a,b,c,d,e) be the permutation which consists of
xoring key part k1 with only digest variable a, a' = a xor k1,
then applying permutation H to (a',b,c,d,e).

Note that any selected composition J_k2( H_k1( x ) ),
where x = (a1,b1,c1,d1,e1), is itself a random permutation.

There are (2^160 factorial) possible permutations.
The keys k1,k2,k3,k4,k5 generates a **much** smaller subset: (2^160) at
most.

An omniscient being could take a single given
(plaintext,ciphertext) pair (p,c) and determine the only
combination of k1,k2,k3,k4,k5 which could produce it, as it is
very probable that only one key combination (composition) could
produce that single pair (p,c).
(that also makes this a one-way function useful for authentication)

Black-Box Invertible Mixer (H,J,K,L) Requirements:

1) Iteration Property:

   All of H_k1, J_k2, K_k3, L_k4, (and their keyed inverses
   L^-1_k5, K^-1_k4, J^-1_k3, H^-1_k2.) must have this
   property.

   Queries in either direction are in unit time.
   And any wild-card variable bit queries must be iterated
   and take 2^t time, where t is the number of variable bits.

2) Composed Iteration Property:

   All adjacent compositions of these permutations (with fixed keys)
   have the Iteration Property, i.e., can only be queried
   in unit time, or iterated. This must also be true in
   reverse direction, for L^-1_k5, K^-1_k4, J^-1_k3, H^-1_k2.

   This means that the composition of adjacent permutations must
   not be trivial in any sense. They must all be unique, and unique when
   composed with adjacent keyed permutations. In other words, the
   2^32 versions of H_k1, when composed with the 2^32 versions
   of J_k2, must generate 2^64 different permutations H_k1(J_k2(x)),
   each of which has similar properties, as it must be
   them composed with K_k3 (and then L_k4)
  The group of this random permutations must be very large, with
   single or few cycles and covering the entire space, and spanning all
bits.
   Since large cycle length predominate in large random permutations,
   this should not be a problem. Imprimitive blocks (cycles) must
   be very large.

3) Middle Key Iteration Requirement:

   Consider two unkeyed permutations
   H and J, with the single key k2 operating on
   the middle digest variable a, J_k2(H(x)).

   Single query in either direction now requires
   supplying input x and also k2.
   Iteration now requires iteration over both
   the middle key k2 and the initial table lookup.

   The middle key k2 could easily be determined
   by a single plain/cipher pair (p,c) being
   k2 = digest value a of H(p) xor J^-1(c)
   Likewise for meet-in-the-middle attacks where
   input p' = p xor k1, and output c' = c xor k3,
   requiring iteration over k1 to load a table,
   and later (not nested) iteration over k3. (2*(2^32) work)
   This mitm attack ***REQUIRES*** iteration over
   all values of k1 (and k3); i.e., there is no simplified search.

   That is the Middle Iteration Requirement. Composing layers
   requires iteration.

   (Of course we thwart the mitm attack with more stages and products of
iteration).

   This must also be true in reverse direction, for
   L^-1_k5, K^-1_k4, J^-1_k3, H^-1_k2.

4) Middle Key Statistical Independence Requirement:

   Again consider any two permutations H_ and J, with
   the single key k2 operating on the middle digest
   variable a, J_k2(H_(x)).

   The use of the middle key k2, in J_k2( H_ (x) ),
   must not in any way leak it's existence to the
   output of the sandwich. With a single plain/cipher
   pair (p,c) we could in theory determine k2. But
   that would require a table of 2^160*2^160 entries.
   The requirement is that no small table of 2^40 or
   fewer entries will yield k1. Since we clearly
   cannot iterate all (p,c) pairs and determine
   a pattern usable for finding k1, we must not also
   embed a pattern.

   Statistical attacks on the key require knowing biases
   based on smaller subsets of input or output bits.
   The key in the middle (k2) must not affect the biases
   of the "sandwich" by virtue of that key's value. This
   will prevent statistical attacks.

5) Inter-Permutation independence:

   H, J, K, L should be separate random permutations. If they
   were the same, then some cycles might be discovered
   and exploited. In general, cycles will overlap, and
   thus creating ever-more-complex cycles when composed.

I again include the picture below:
 
key parts k1-5 = HASH(user key)
 
                   \/ \/ \/ \/ \/
ind. key part k1===X| || || || ||
                   \/ \/ \/ \/ \/
                ============================
                | INVERTIBLE HASH MIXER H |
                |___________________________|
                   \/ \/ \/ \/ \/
ind. key part k2===X| || || || ||
                   \/ \/ \/ \/ \/
                ============================
                | INVERTIBLE HASH MIXER J |
                |___________________________|
              \/ \/ \/ \/ \/
ind. key part k3===X| || || || ||
                   \/ \/ \/ \/ \/
                ============================
                | INVERTIBLE HASH MIXER K |
                |___________________________|
                   \/ \/ \/ \/ \/
ind. key part k4===X| || || || ||
                   \/ \/ \/ \/ \/
                ============================
                | INVERTIBLE HASH MIXER L |
                |___________________________|
                   \/ \/ \/ \/ \/
ind. key part k5===X| || || || ||
                   \/ \/ \/ \/ \/
 
 

Relevant Pages

  • Re: 1-1/2+1/3-1/4+1/5-1/6+1/7
    ... infinitely many permutations must itself be a permutation. ... is definitely true that the composition of finitely many permutations ... So, after an infinitude of Ullrich's, the _whole_ set of naturals has ...
    (sci.math)
  • Re: balanced REDUCE: a challenge for the brave
    ... Composition of permutations can be used. ... loop -rot 2drop; ... swap over swap hshift swap r> hshift +; ...
    (comp.lang.forth)
  • Re: Tone row permutations
    ... on composition, and it ... 'new' serial works by substituting one tone-row (and its permutations) ... was concentrating more on learning guitar than learning about writing. ... of Schoenberg's original concepts: all melodic and harmonic material should ...
    (rec.music.theory)
  • Re: Generating all combinations
    ... It only does partitions of a sequence. ... I don't expect a listing -- when I need to loop over permutations, ... calculator and to the itertools module for high-speed looping ... iteration, or to find at an arbitrary iteration: ...
    (comp.lang.python)
  • Re: Generating all combinations
    ... It only does partitions of a sequence. ... I don't expect a listing -- when I need to loop over permutations, ... calculator and to the itertools module for high-speed looping ... iteration, or to find at an arbitrary iteration: ...
    (comp.lang.python)