-----BEGIN PGP SIGNED MESSAGE----- In article <01I0SDBW5VYY984JFR@delphi.com>, <JMKELSEY@delphi.com> wrote: [ ... 1/4 of a cycle of RC2: ... ]
A = rotl(A + f(B,C,D) + sk[i], 1); [...] Has anyone looked at this cipher with regard to linear attacks?
A little bit.
However, it's not clear to me how to build linear characteristics that will make it through more than a few rounds of alleged-RC2. Linear characteristics that are spread across many subblocks (i.e., partly in A and partly in B) seem to get messed up quickly by the rotations.
Hrmm, I'm not convinced that it's so hard to build a linear characteristic; there are plenty of 1/4-cycle characteristics that don't spread out very much. The problem is that I can't find any approximations with high enough bias to be useful. So here's some information on the (useless) linear characteristics I've been thinking about; maybe this will prompt some clever improvement from someone else. They're all based on two observations: first, the addition operation Y = A + X has linear characteristics of the form Y[i] = A[i] + X[i,i-1] bias 1/2 Y[i] = A[i,i-1] + X[i] bias 1/2 and second, the bit-multiplexing function X = f(B,C,D) has linear characteristics of the form X[i] = B[i] bias 1/2 X[i] = C[i] bias 1/2 X[i] = B[i] + D[i] bias 1/2 X[i] = C[i] + D[i] + 1 bias 1/2 etc. (A note on notation: X[i] denotes the i-th bit of X, and X[i,j,k] = X[i] + X[j] + X[k]. If an approximation holds with probability p, then I say it has bias b = 2 |p - 1/2|; note that adding two approximations multiplies their biases, and that one needs about 1/b^2 known plaintexts to take advantage of a linear characteristic for the whole cipher. Next, let K denote the 1/4-cycle subkey, and let A' denote the new value of A after the 1/4-cycle is applied to it. Also, + denotes xor in approximations. By 1/4-cycle, I mean something of the form A = rotl(A + f(B,C,D) + K, 1); so RC2 has 16 full cycles, and each full cycle has 4 1/4-cycles.) Now given those building blocks for linear characteristics, you can combine them to get various linear characteristics for 1/4 of a cycle, like this: A'[i+1] = A[i,i-1] + B[i] + K[i,i-1] bias 1/8 A'[i+1] = A[i] + B[i,i-1] + K[i,i-1] bias 1/8 A'[i+1,i] = A[i,i-2] + B[i,i-1] + K[i,i-2] bias 1/64 A'[i+1,i] = A[i,i-1] + B[i,i-2] + K[i,i-2] bias 1/64 A'[i+1] = A[i,i-1] + C[i] + K[i,i-1] bias 1/8 A'[i+1] = A[i] + C[i,i-1] + K[i,i-1] bias 1/8 etc. These don't spread out too well; I haven't completely worked out how to do many-cycle linear approximations, but I think they shouldn't be too hard to find. (For instance, keep only A and C active, or somesuch.) The real stumbling block is the lack of high-bias linear approximations for a 1/4-cycle, not the difficulty of combining them, IMHO. For instance, if you supposed that there was just one 1/8-bias linear approximation active in each full cycle, we get a total bias over 16 cycles of 2^{-48}, which would imply something like 2^{96} known plaintexts for a linear attack. This is an overly optimistic estimate, since any full 16-cycle linear characteristic which I can imagine will probably require more than one linear approximation per cycle. (It also ignores the non-iterative rounds; but I think they'll be easy to deal with if you can handle everything else.) What makes the 1/4-cycle linear approximations have such a low bias is RC2's extensive use of addition mod 2^32 instead of bitwise xor. So anyhow, the final word is that I don't see how to do linear cryptanalysis of RC2, but maybe someone else will have some insights. P.S. There is an analogue of differential cryptanalysis where we consider the difference measure as addition mod 2^32 instead of bitwise xor. Is there a similar generalization of linear cryptanalysis? I don't know any, offhand. - --- [This message has been signed by an auto-signing service. A valid signature means only that it has been received at the address corresponding to the signature and forwarded.] -----BEGIN PGP SIGNATURE----- Version: 2.6.2 Comment: Gratis auto-signing service iQBFAwUBMRbB/CoZzwIn1bdtAQEKEAGAujcKp6aM4OV9AoveQaFQdEpQi/hQTSK/ YoMEkSKYtt+aq0Usv5nMHB7ikEflmGak =TYbl -----END PGP SIGNATURE-----