Two-dimensional S-Box

Consider the following simple cipher: $$c_1 = S(m_1 \oplus k_1) \oplus k_2$$ Where $S$ is S-box, $m_1$ - 16-bit plain text, $k_1$ and $k_2$ is two parts of 16-bit key.

If S-box is standard then this cipher is quite easy to hack by differential analysis. But consider $m_1$ as two-dimensional array 4x4 bits and S-box as combination of two same 4-bit S-boxes. In the first S-box input is 4 rows of plain-text, in the second S-box input is 4 columns of output of first S-box: $$c_1 = S''(S'(m_1 \oplus k_1)) \oplus k_2$$

Can you help me analyze this algorithm against the following problems:

1. Are there any advantages and disadvantages of this algorithm to the following: $$c_1 = S(m_1 \oplus k_1) \oplus k_2$$ where $S$ is a 16-bit S-box.
2. How resistant is this algorithm to differential analysis.
3. Is this "two-dimensional s-box" is used somewhere?
-
I'm not sure I understand what you're asking. If $S_1$ and $S_2$ are $n$-bit-to-$n$-bit S-boxes, then the function $S_{12}$ defined as $S_{12}(x) = S_2(S_1(x))$ can also be represented as an $n$-bit-to-$n$-bit S-box, so combining S-boxes like that generally doesn't gain you anything. –  Ilmari Karonen Dec 22 '13 at 19:36
$S'$ and $S''$ is same 4-input-bits S-box. Where $S_1$ and $S_2$ is 16-input-bits S-boxes. $S'$ change plain-text by rows, i.e. convert all rows. $S''$ change only columns of output of $S'$. While $S_1$ change all plain-text and $S_2$ change all 16-bit of output of $S_1$ –  vakoroteev Dec 22 '13 at 19:47
If $S'$ and $S''$ are the same S-box, why do you use two different symbols to represent them? –  Ilmari Karonen Dec 22 '13 at 20:00
I use two different symbols because I want represent that this S-boxes change input message by different way. $S'$ change every row of input message (message is 2-dimensional array 4x4). Output of $S'$ is 2-dimensional array 4x4 too. $S''$ substitute every column of output of $S'$. –  vakoroteev Dec 22 '13 at 20:05

I understand the question as you have a single 4-bit S-box, which you first apply rowwise, and then columnwise.

As already mentioned, this is equivalent to a large S-box $\mathcal{S}$ $$c = \mathcal{S}(m\oplus k_1)\oplus k_2.$$

This is a well-known Even-Mansour cipher, and it can be broken with complexity $2^{n/2}$, which is $2^8$ for your $n=16$. The idea by Daemen is to try $2^{n/2}$ plaintext pairs with the same difference $\Delta$ both for the entire cipher $E$ and the S-box $\mathcal{S}$.

2. Breakable in seconds.

3. Maybe in some marginal ciphers or hash functions. Note that it is quite inefficient in software.

-
My cipher is only example. Consider, that I need several different S-boxes. So I need to construct several good S-boxes. My 4-bit S-box with two level of substitution is equivalent to 16-bit S-box with one level of substitution. So if I right, constructing of 4-bit S-box is simpler, than constructing 16-bit S-box. This simplifies the development of encryption algorithm, in that case when it is necessary with several blocks. If I'm wrong, I'll be glad to hear criticism. –  vakoroteev Dec 22 '13 at 20:39
Well, it is easier to make an 16-bit S-box with good differential and linear properties than to make a good 4-bit one. You just have more choice in the former case. Designers choose 4-bit S-boxes for one particular reason: they are easy to implement on resource-constrained devices with small memory, where you can not place a large lookup table or implement a complicated finite field arithmetic. –  Dmitry Khovratovich Dec 23 '13 at 11:25
Thank you. Your explanation of the development of S-Box really helped my understanding of the issue. –  vakoroteev Dec 23 '13 at 18:28

As with Dmitry, I assume you are applying a 4-bit s-box to a 4-by-4 array of 16 bits, first to the rows (after xoring 16 bits of key material to the plaintext), then to the columns (and lastly xoring 16 more bits of key material to produce the ciphertext). Strictly speaking, you need to specify the 4-bit s-box in order to fully evaluate it against differential cryptanalysis, though I can tell you right now the construction will be extremely weak no matter which such s-box you choose. In fact, you can choose 8 distinct s-boxes (instead of using the same one 8 times) and that won't make any difference to the strength of the construction.

First, if only one of the 'row-wise' s-boxes is differentially 'active' then the attacker can immediately and directly read the output difference of that active row-wise s-box merely by looking at which column-wise s-boxes are differentially active (which you can tell just by looking at the resulting ciphertext pairs). In the same way, if only one row-wise s-box is active at a time you also immediately know the input and output differences for any active column-wise s-box (they'll each have only one active input bit -- the one coming from the active row-wise s-box).

Now, if you know the input and output differences for a given s-box for sufficiently many pairs of texts (which for 4-bit s-boxes may only be two or three pairs) then it is trivial to deduce the key bits standing between the attacker and the active s-box in question. My guess is that it would take no more than 16 chosen plaintexts to recover the entire key -- four per row-wise s-box. Each such quartet of plaintexts would vary in only one row, giving the attacker six differential pairs to play with (four distinct texts can be paired in six ways). I won't bother to speculate how long it would take to deduce the full 32 key bits, but I suspect one could do it by hand with pen and paper in less time than it took me to write this answer.

-