Newsgroups: sci.crypt Path: cactus.org!cs.utexas.edu!uunet!mnemosyne.cs.du.edu!nyx10!colin From: colin@nyx10.cs.du.edu (Colin Plumb) Subject: Re: Block Mixing Transformations Message-ID: <1994Mar16.010710.4943@mnemosyne.cs.du.edu> X-Disclaimer: Nyx is a public access Unix system run by the University + of Denver for the Denver community. The University has neither + control over nor responsibility for the opinions of users. Keywords: DES replacement, Large blocks Sender: usenet@mnemosyne.cs.du.edu (netnews admin account) Organization: Nyx, Public Access Unix at U. of Denver Math/CS dept. References: <1994Mar13.051515.27175@cactus.org> <1994Mar15.124011. + 19463@mnemosyne.cs.du.edu> <1994Mar15.194249.28915@cactus.org> Date: Wed, 16 Mar 94 01:07:10 GMT Lines: 140 In article <1994Mar15.194249.28915@cactus.org>, Terry Ritterwrote: > > In <1994Mar15.124011.19463@mnemosyne.cs.du.edu> colin@nyx10.cs.du.edu > (Colin Plumb) writes: > > >>T is A^B, which is the same as X^Y. The high bit is >>highly visible. > > Yup. I had not seen it. Okay, time to comme clean: I get a bit annoyed when I see a fancily-formatted "report" that might fool some people when such glaring points as this are wide open. It seems enormously pretensious and makes me think poorly about the author. Sorry if it's unkind, but it's true that a part of my mind is saying "I wish Terry would quit posting his `clever' ideas until he learns thing one about cryptanalysis." >>My observation about the extremely high degree of linearity in the >>operation was that anything made up only of these mixing operations >>is weak. I'm not sure the above is more trustworthy than the >>substitutions. > > Fine by me. 96 8-bit substitutions means 256!^96 keys. Yes, it's called polyalphabetic substitution and ciphertext-only attacks are trivial. (Remember that the 26! = 403291461126605635594000000 possible keys to a basic momoalphabetic substitution is more than 88 bits; larger than the Skipjack key size. And yet newspapers routinely print short stretches of ciphertext for people to solve for amusement.) Now, the mixing probably makes it harder, but I'm not convinced it's that much harder. > (Obviously we initialize this state by shuffling with a > cryptographic RNG, but we can make that RNG just as large as we > want and seed it with all the key material we want.) > > Just the 32 substitutions in the middle would be more than secure, > *provided* all the stuff around them spread their effects and > prevented them from being attacked separately. > > All we need the mixings to do is to mix. Essentially, we want to > end up with the effect of a bit change in any particular position > being spread among the entire output (statistically), after a set > of mixings. If this can be accomplished, we can use small, > practical substitutions to make a large-block cipher. There are two desirable properties in a mixing: non-linearity (see all the papers on bent functions, which are functions a maximum Hamming distance from any affine function) and the Strict Avalanche Criterion. Which means that, over all possible values of the other n-1 bits, changing one inut bit has a 50% probability of changing each output bit. (Higher-order SAC constraints require this to hold for subsets of the set of excluded input bits. E.g. 2nd order requires that if any one of the n-1 other inputs is fixed, the probability is still 50% over all combinations of the remaining n-2 bits.) Now, let's see what your proposed mixing function does. Changing bit k of A will change bit k of Y and bit k+1 of both X and Y. Unless k=n-1, in which case it will change the bits corresponding to the bits set in the polynomial p. But in most cases, toggling one input bit toggles three output bits. In all cases, there is no dependency on any other input bits; the function is completely linear. You might want to look at the following papers from Eurocrypt '93. The proceedings have now been published by Springer-Verlag, in their Lecture Notes on Computer Science series. Tor Helleseth (Ed.). The full title is "Advanced in Cryptology - Eurocrypt '93" and the ISBN number is 3-540-57600-2 and 0-387-57600-2. Anyway, the papers: Differentially uniform mappings for cryptography, K. Nyberg On almost perfect nonlinear permutations, T. Beth, C. Ding Two new classes of bent functions, C. Carlet Boolean functions satisfying a higher order strict avalanche criterion T.W. Cusick On constructions and nonlinearity of correlation immune functions J. Seberry, X.-M. Zhang, Y. Zheng These talk about useful properties for mixing functions. Another thing about your proposed mixing function is that the bits that get modified are close to each other. Modifying a bit and the bit next to it produces the following pattern of differentials: 1 11 101 1111 10001 110011 1010101 11111111 100000001 This is immediately recognizable as Pascal's triangle, but serves to illustrate the fact that a 1-bit change in the input is slow to propagate. Because you only hav three levels of S-boxes, I suspect the whole thing can be reduced to a system of simultaneous equations of reasonable size and solved with a bunch of known plaintext that is basically the size of the unicity distance. Cryptanalysis is difficult. I am not any good at it, to speak of. (My general rule is that anything I can find a chink in, someone good can probably find a hole in you could drive a Mack truck through.) If you look at papers proposing ciphers, you'll see that the onus is on the proposer to show that a number of known methods of cryptanalysis are ineffective. "Show" does not mean "I couldn't do it", but "Here is a proof that nobody can do it." The requirement for proof can be weakened to an argument, but Xuejia Lai's PhD Thesis gives a good example to try to emulate. More work on the subject can be seen in the Eurocrypt '93 paper Markov ciphers and alternating groups, G. Hornauer, W. Stephan, R. Wernsdorf. Cryptography is harder than cryptanalysis. Cryptanalysis (of modern ciphers) is extremely difficult. I'm not qualified to do either, although I'm slowly working my way through the cryptanalytic literature in an attempt to develop a modicum of skill. One cipher that might be worth exploring is one based on an FFT-like mixing pattern (all butterflies the same size), with S-boxes after each round of the FFT. But if you were to stick to 8-bit mixing, you could merge the mixing function with the previous S-box by having each of the two input S-boxes to the mixer emit 16 bits, which are XORed and the two halves used as outputs. And that would permit much more complex mixing functions with no increase in cost. Even then, I'm not sure if one pass through the FFT network would be enough. Each input byte has only one chance to affect each output byte; that could make solutions comparatively simple. I'd prefer at least two rounds. But remember, these are all off-the-cuff ideas; if I were to start work now and not find any holes after 6 months of effort, it might be worth considering using them to protect data. -- -Colin