From: Ralf Brown 
Newsgroups: sci.crypt.research

Subject: Sliding Feistel Networks
Followup-To: sci.crypt.research
Date: 1 May 1995 10:10:18 +1000
Organization: Sterling Software (Aust). Pty. Ltd.
Lines: 69
Approved: PGP Moose V0.9 19950501 sci.crypt.research
+         iQBVAgUBL6Qm6WzWcw3p062JAQFBQwIAsQ7d9r0TqrNWDuTYrLwlyff+dV3Ap18s
+         0wqul0vhHihh1h4cG2RyVB7Sl0qgAfSaJhCVg8xrJch9NM27geyMWA==
+         =1Lkr
Distribution: world
Message-ID: <3o18ta$>

In my previous article, I described a generalization of the standard
Feistel network to use N subblocks instead of two.  This article
describes a further modification which allows the network to be "slid"
along the input, effectively producing an unlimited block size.
Consider the following BUAG of a generalized Feistel network with N=3 and
one additional minor change:
             A   B   C   D   E
              \  |\ /|   |   |
               \ | \ |   |   |
              / \+  \+   |   |
             C   |   |   |   |
             |   |   #   |   |
              \  |\  |   |   |
               \ | \ |  /    |
                \+  \+       |
             D   |   |       |
              \  |\  |       |
               \ | \ |       |
                \+  \+       /
                     |      /
                   : #     /
                   :      /
              \  |\  |
               \ | \ |
                \+  \+

At the points marked by #, instead of feeding a copy of the mixing
function output back to the left edge of the network, we output a copy
of that value and instead feed the next subblock of the plaintext into
the left edge of the network.  Thus, every K rounds (K >= N, as
explained below), we effectively slide the network one position further
down the plaintext, outputting a chunk of ciphertext.  Decryption naturally
runs this process in reverse.
K, the number of rounds between shifts, needs to be at least as great as
the number of subblocks processed at once, to ensure that every subblock
of input is processed uniformly throughout the network.
   1. effectively unlimited block size; chaining is automatic
   2. message need only be a multiple of the subblock size greater than N;
      no additional padding to a multiple of N*subblock is required
   3. except for the very beginning and end of the messsage, all subblocks
      are processed through K*N rounds
   4. except for the subblocks at the very end of the message, all subblocks
      of the input are diffused over K*N subblocks of the ciphertext
   1. the text at the very beginning and very end is processed through fewer
      rounds, which may provide a point of attack
   2. the message must be decrypted from end to beginning, which limits
      usefulness for very large messages (the ideal application is probably
      smallish [up to 8K or so] fixed-size 'messages' such as disk sectors).
   3. slightly greater computational overhead than the simple generalized
      Feistel network of my previous article using K*N rounds
Internet: -=- FIDO: Ralf Brown 1:129/26.1
Disclaimer?    |   Gilb's First Law of Computer Unreliability: Computers
What's that?   |   are unreliable, but humans are even more unreliable.