Path: news.io.com!uunet!in2.uu.net!news.mathworks.com!gatech!swrinde!cs. + utexas.edu!not-for-mail From: ritter@io.com (Terry Ritter) Newsgroups: sci.crypt Subject: Variable Size Block Ciphers II Date: 26 Aug 1995 02:41:01 -0500 Organization: UTexas Mail-to-News Gateway Lines: 72 Sender: nobody@cs.utexas.edu Message-ID: <199508260740.CAA19029@tristero.io.com> NNTP-Posting-Host: news.cs.utexas.edu There appears to have been some confusion with respect to the short sci.crypt introduction to the Variable Size Block Cipher designs: A casual examination of the fixed-size 80-bit examples in the "full" HTML document should indicate that each substitution is intended to be a separate keyed (shuffled) table. It is also mentioned that a dynamically-variable-size design would dynamically select a table for each operation from an array or heap of separately keyed tables. Saying that the structures are based on similar columns is not intended to mean that all tables at each level are the same! Currently, I am less interested in strength than overall diffusion. My point is that it seems amazing -- wondrous -- that an overall bit-level diffusion effect can be generated for an essentially arbitrary block width by a fixed-depth structure. Now, it is obvious that the diffusion "bandwidth" is limited by the number of diffusion paths, so this may not be "true" diffusion in some sense. (Perhaps a 10-diffusion-layer structure would come closer.) However, to the extent that the diffusion we produce cannot be externally *distinguished* from "true" diffusion, it may be good enough. Certainly single-bit overall diffusion is often considered a worst case, and that is demonstrably present or closely approached in all these examples. To the extent that the diffusion itself is linear (in the first and third examples), the results are rendered nonlinear at each level. In contrast to the comments in Kaliski-Robshaw (which I have recently re-read several times), I would expect that a fencing array of keyed substitutions which protects a true nonlinear overall diffusion *should* be strong. Thus, *if* we can protect the input from attacks intended to separate the individual elements, and then produce a nonlinear overall diffusion, a single subsequent fencing layer should be sufficient for strength. In the first example, I am of course aware that attacks on, say, the first two elements could produce values which "cancel out" and thus not conduct further diffusion. However, a zero exclusive-OR result is just one of the values we should expect to get at *any* particular stage. We would expect that *any* substitution result could zero-out a confusion-chain at *any* level. Indeed, this happens all the time. My feeling is that we should consider zero just another value; it is not a lack of diffusion, it *is* the diffusion. The bit-level diffusion experiments do not show a problem. Perhaps some other experiment would. At this point I am not greatly concerned, but of course a lot of analysis is still needed. If it turns out that there is a problem, I expect that adding one or more sets of confusion / diffusion stages should be a big help. One advantage of this type of architecture is that strength can be added without re-design of the rest of the cipher. Apparently. These Variable Size Block Cipher designs are *new* structures. They have not had 20 years of analysis. They have not had 20 years of understanding about when, and when not, they should be used. It is ridiculous to expect them to conform to the level of analysis that DES has collected. They are not Feistel block ciphers! After more than six years, I feel that we finally have a good handle on the weaknesses of Dynamic Substitution, which was fundamentally-new stream-cipher cryptography in 1990, and still is. It will be some time before the same understanding can occur with respect to Variable Size Block Ciphers. Any and all insights would be appreciated. --- Terry Ritter ritter@io.com http://www.io.com/~ritter