Two-dimensional S-Box

Question

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?

Answer 1

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}$.

So the answers to your questions are

1. No advantages.

2. Breakable in seconds.

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

Answer 2

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.