Why are side channel attacks such as SPA/DPA/ CPA based on the AES SubBytes routine? I have three questions about AES related to side channel attacks:


Why are side channel attacks  such as CPA  related to the non-linearity of the SubBytes routine within AES?
What is the difference between using the substitution BOX (SBOX) in a non-linear way and the combinational SBOX proposed in articles such as "Design of AES S-box using combinational logic optimization"?
Does the use of a combinational SBOX avoid side channel attacks?
The values targeted by CPA are of the type $S(p\oplus k)$ where $p$ is a plaintext and $k$ a key byte, and $S$ maps bytes bijectively to bytes. One finds the correct key $k_0$ by correlating the Hamming weight of $S(p\oplus k)$ with the power consumption, as the absolute value of the correlation is expected to be the highest for the correct key $k_0$ at the time $t_0$ when the $S$-box output is processed in the CPU.

Now assume that for a second key $k_1\ne k_0$ the values of $S(p\oplus k_0)$ and $S(p\oplus k_1)$ differ only by a single bit for all plaintext bytes $p$. Then also their Hamming weights differ only by 1, and therefore the Hamming weights of $S(p\oplus k_0)$ and $S(p\oplus k_1)$ are strongly correlated. So whenever $k_0$ gives a high correlation between current consumption and predicted Hamming weight, so does $k_1$, which makes both keys difficult to distinguish, if one wants to know, which one is the correct one.

If $S$ happens to be linear, then $S(p\oplus k_0)\oplus S(p\oplus k_1) = S(k_0\oplus k_1)$ is independent of $p$. So if $S(k_0\oplus k_1)$ has Hamming weight 1, one is exactly in the bad situation (for the attacker) of the last paragraph. For $S$ bijective linear, this occurs for $8$ different key bytes $k_1$'s.

As the $S$-boxes have to protect the crypto-algorithm against linear and differential attacks, they are chosen such that $S(x)$ and $S(x\oplus\Delta)$ are "linearly as independent as possible". In particular, also their Hamming weights have as little correlation as possible. So if you have a high correlation with $S(x)$ (think $x=p\oplus k_0$), you will not have much correlation with $S(x\oplus\Delta)$ (think $\Delta=k_0\oplus k_1$), making different key bytes easily distinguishable.

Differently phrased, real $S$-boxes fulfill the basic assumption of DPA that wrong keys give random predictions for the current consumption, whereas linear $S$-boxes violate it.

In conclusion, any $S$-box good for "classical" cryptography is bad (=good target) for side-channel attacks like CPA, and vice versa. (There are some papers published about finding $S$-boxes good for both purposes, but to my knowledge none were found yet, and I'd be surprised if there will be.)

I do not know the article you ask about, but judging from the abstract the authors are only interested in an efficient (time+space) HW-implementation of the AES S-box, and not at all in security against side-channel attacks (they would mention it).

For the security against CPA it doesn't matter how an intermediate value you try to attack was created in the HW, only if it (or something else correlated to it) shows up leaking side-channel information (like power consumption).

Trying to fight side-channel attacks without using dynamic random (dynamic = freshly generated each time the algorithm is run) I wouldn't bet on. Just take a look at how easily all white-box implementations got broken using DPA-like techniques.