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