Path: news.io.com!news.fc.net!news3.net99.net!news.cais.net!news.sprintlink.
+     net!newsfeed.internetmci.com!news.mathworks.com!news.duke.edu!godot.cc.
+     duq.edu!nntp.club.cc.cmu.edu!cantaloupe.srv.cs.cmu.edu!ralf
From: Ralf Brown 
Newsgroups: sci.crypt

Subject: Re: Variable Size Block Ciphers
Date: 27 Aug 1995 10:17:49 GMT
Organization: Just me and my PC....
Lines: 82
Message-ID: <303fc405@ralf>
NNTP-Posting-Host: b.gp.cs.cmu.edu
In-Reply-To: <199508260048.TAA04443@tristero.io.com>
Originator: ralf@B.GP.CS.CMU.EDU

In article <199508260048.TAA04443@tristero.io.com>, ritter@io.com (Terry Ritter)
 wrote:
} In <303bc3ec@ralf> Ralf Brown  wrote:
}>And I proposed another approach to variable-size blocks, namely using a
}>Feistel network and "sliding" it along the input, back in April. If
}>anyone is interested and can't find it in the sci.crypt.research
}>archives, I could dig out a copy of that post.
}
} No need; let me, let me:
}
}>From: ralf+@cs.cmu.edu (Ralf Brown)
}>Subject: Generalized Feistel Networks
}>Date: 2 Apr 1995 23:59:33 GMT
}>
}>As many of you know, Feistel ciphers are based on repeated iterations
[...]
}>This idea can be generalized to the N parts of a block (said block naturally
}>being larger than in the N=2 case normally used).  For instance, if N=4,
}>then the subblocks A,B,C,D of a block would be transformed as follows for
}>encryption:
}>        A' = D
}>        B' = f(A,B)
}>        C' = f(B,C)
}>        D' = f(C,D)
}>
}>For N subblocks in a block, a minimum of N rounds are required to process
} -------------------------------------------------------------------------
} (emphasis added)
}>each subblock uniformly through the network, at which point every subblock
} --------------------------------------------------------------------------
}>of the output depends on every subblock of the input.
} ----------------------------------------------------
}
} In contrast, I have clearly defined "Variable Size Block Ciphers"
} to refer to ciphers which
}             ==>  DO NOT REQUIRE MORE ROUNDS  <==

I wasn't thinking of the above, but an extension thereof which I posted
to sci.crypt.research at the end of April, which takes a generalized
Feistel network and slides it along the input by one subblock for every
K rounds; for a given subblock size (which I would expect to be 16 or 32
bits, depending on machine architecture), "N", and "K", the work is
linear in the total size of the plaintext to be encrypted, generating
encrypted subblocks as output at regular intervals.

} Moreover, a VSBC exhibits
}                 ==>  BIT-LEVEL DIFFUSION  <==
}
} in that every *BIT* in the output block depends on every *BIT* of
} the input block, and this diffusion is also BALANCED.  This is
} *not* just "subblock" diffusion, and it is not just a detail.
} This level and quality of diffusion is important to prevent The
} Opponent from isolating and working on the "subblocks" themselves.

I probably phrased it poorly in my original post, but when I said every
output subblock depends on every input subblock, I meant all the output
bits depend on all the input bits.  In a sliding Feistel network (SFN),
every input bit affects every bit output after the point it was
introduced into the network; due to the delay between inputs and
outputs, each input bit except the very earliest also affects a number
of *preceding* bits (for a network with N subblocks of M bits each, a
bit can affect up to N*M preceding bits).  Not entirely balanced like
your work, but better than simple chaining.

} My VSBC work occurred substantially before April 1995, with the
} announcement naturally being delayed for protection purposes.

Hey, I was just pointing out that there have been other approaches proposed
for handling large, variable-size blocks.  SFNs can even be used in a
stream-cipher mode when the sender has no prior knowledge of the
plaintext's size, though the receiver can't decrypt until the entire
ciphertext has been received, because it has to be decrypted from end to
beginning (which rules it out for general stream-cipher use).  But as I
understand VSBC, it can't be decrypted until the entire encrypted block
is received, either.

Hmm, I hadn't thought of that in April.  A SFN is sorta midway between a
block and a stream cipher....

-- 
My employer will | I'net: ralf@telerama.lm.com   Fido: Ralf Brown 1:129/26.1 
deny knowing of  | "Man is the only kind of varmint sets his own trap, baits
this message...  | it, then steps in it." -- John Steinbeck, _Sweet_Thursday_