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 BrownNewsgroups: 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_