Cryptanalysis (by alaric)
Now, that's kind of surprising, isn't it? The four-S-box design looked pretty strong, but with a careful bit of probing with chosen plaintexts, we can actually deduce what's in the S-box, without having direct access to it.
Even XORing key data into XYZW gives us nothing, since it just means that the U- and L- values output by the first layer aren't the same as received by the second layer, but unless you go and do the constraint logic to get a single S-box, you're not assuming they're the same anyway. At worst, by XORing different things into W and Y (which are both U-values) you can make it so that we can't just have U- and L-values, and instead must have seperate symbols for W-, X-, Y-, and Z-values, requiring more chosen plaintexts to map them out independently. But in general, XORing stuff into the input of an S-box just makes it behave like a slightly different S-box. Any improvement in security is going to have to involve more criss-crossing of things between layers of S-boxes.
When I get some idle time, I'm going to look at two different arrangements: Just adding an extra layer of byte swaps and S-boxes to the existing design (ABCD -> WXYZ -> EFGH -> A'B'C'D'), thereby having more layers than is required to make sure every output byte is a function of every input byte; and the second arrangement will use an 8-byte block instead of 4 bytes, with a more complex rearrangement of bytes between each layer to make sure all the output bytes are affected by all the input bytes:
* Input ABCDEFGH
* A'B'=S(AB), C'D'=S(CD), E'F'=S(EF), G'H'=S(GH)
* IJ=S(A'C'), KL=S(B'D'), MN=S(E'G'), OP=S(F'H')
* I'J'=S(IM), K'L'=S(JN), M'N'=S(KO), O'P'=S(LP)
* Output I'J'K'L'M'N'O'P'
I'll see if I can see which of the two is stronger, and reason about combining the two; a large block, plus more layers than is necessary to ensure that every output byte is a function of every input byte.
Crypto / security | alaric | 
Fri 22nd Sep 2006 1:46 pm
Subscribe
By Try the Ghost, Wed 20th Feb 2008 @ 8:34 am
This thread has been dead for quite some time, but if you're still interested, here are my thoughts:
In option 1, you're adding one extra round of S-boxes and diffusion. This buys you an extra avalanche, and therefore a lot more complexity for the attacker. Essentially you've got a three round block cipher with two complete avalanches. No matter how strong your S-boxes, the small number of avalanches will leave it vulnerable to differential cryptanalysis (and possibly other exotic attacks, like impossible linear, and meet in the middle). Your best bet is to have many rounds, so as to increase your total number of avalanches. For me, I'm not satisfied with anything less than 6 complete avalanches. I believe DES had about 5.5, and Blowfish has 7.5. In your case, it takes two passes of S-boxes for the first avalanche, and then one avalanche per round thereafter. However, no matter how many avalanches you have, a 32-bit block cipher is susceptible to a complete "codebook" attack where the interceptor just records plaintext/ciphertext combos for all possible 32-bit inputs -- that table would fit on your iPod several times over.
So option 2 is much stronger. You've now got a 64-bit block cipher. After three rounds you have a complete avalanche, and then every two rounds thereafter (I think). With a 16 round cipher you'd have something like 7.5 full avalanches. Have you considered using several 16-bit S-boxes? In this particular design, 4 separate 16-bit S-boxes would fit quite naturally. Lots more key setup time, but then the attacker is faced with a very, very hard task.
p.s. I loved how you deduced that XORing inputs into an S-box doesn't make the S-box any stronger. In fact, if your S-box is 16 bits and based on only on the user key, then your S-box contains billions of times as much information as your subkeys. Mad entropy, like you said. With key dependent S-boxes, you can scrap subkeys -- they don't add any non-linearity or diffusion, as you so cleanly stated. In my own ciphers, which tend to be based on key dependent S-boxes, I often skip subkeys.
By alaric, Thu 21st Feb 2008 @ 6:58 pm
Yes indeed! I wouldn't recommend using the results of either such options as a 'real cipher', since 32 bit blocks are indeed trivially codebooked, and too few layers of avalanche do ease cryptanalysis greatly. I'm studying them more as basic components, so that their weaknesses can be found and mitigated when using them as parts of a larger whole.
What I've since become more interested in is less linear operations between the S-boxes. Analyses of the implications of a small change in the input, as I've done, rely to a certain extent on the simplicity of the diffusion between layers. While the S-boxes provide a high level of good old key-dependent unguessability, I'm interested in finding functions that efficiently diffuse changes across as much width as possible, with things like key dependence being lower priorities.
See: http://www.snell-pym.org.uk/archives/2005/07/04/avalanche-functions/
I posted my own further examinations of the S-box layering later:
http://www.snell-pym.org.uk/archives/2006/09/24/cryptanalysis-2/#more-311