Cryptanalysis 2 (by alaric)
In a previous post, I discussed the analysis of an initially robust-looking combination of S-boxes, then suggested two potential extensions of the algorithm to examine.
Well, since then I have had some time to examine the effect of just sticking an extra round onto the previous design, creating the following algorithm:
- EF=S(AB), GH=S(CD)
- IJ=S(EG), KL=S(FH)
- A'B'=S(IK), C'D'=S(JL)
Pleasingly, I've found that the previous attack doesn't work. Keeping CD constant and varying AB means that EF will vary while GH is constant. As before, this means that IJ and KL can each go through only 256 different values out of 65536, with a different 256 values for each constant CD we try, which was the crux of the previous attack. But now IJ and KL are split into two parts and rejoined as IK and JL - each of which could have up to 65536 different values, depending on how the 256 different values of IJ and KL are distributed (eg, all the 256 values of IJ might all have the same I and varying J, while KL's values all have the same J and varying L, meaning that IK is constant while JL has 65536 different values). The output pairs A'B' and C'D' will have the same number of combinations each as IK and JL, respectively, since they just mirror the same through an S-box.
So we can extract some information about the contents of the S-box by seeing how many different values of A'B' and C'D' we get as we hold CD constant and vary AB; but without knowing anything about the values of E and F as we do this, I can't see how this information helps us at all. It just tells us the relative statistical distribution of different halves of the output of the S-box for some range of inputs.
So unless I've missed something, this design might actually be about as secure as a 32-bit keyed block encryption algorithm can be - you could still build up a codebook by choosing all possible 232 plaintexts. But I'll cover widening the algorithm's block later.
Crypto / security | alaric | 
Sun 24th Sep 2006 12:55 am
Subscribe