From this paper, there are two conditions for a successful DPA attack:
i) there exists an intermediate variable in the implementation that is correlated with the power consumption and
ii) this variable exclusively depends on the plaintext (or ciphertext) and a small part of the key.
My question is that, on the condition i), does the variable need to appear on the calculation of the algorithm? Can a variable that is not explicitly computed correlate with the power consumption?
Can a variable that is not explicitly computed correlate with the power consumption?
Yes, and this can happen in several ways. When you say "not computed explicitly", I assume you mean that the computation is performed on a masked value or share instead. That is, the secret inputs (referred to as the key by the paper you link to) themselves do not directly appear in any of the computations. Below, I discuss why this condition is not enough. So "correlation" is used in a very broadway. In fact, for higher-order attacks nonlinear dependencies (i.e. not just linear correlation) can also be problematic.
First, let's consider a traditional boolean masking scheme: add a random mask to the secret input of your combinatorial circuit. Let's say that you've implemented a very nice masking scheme: operations are never done directly on the unmasked (secret) values and leakage, in general, is carefully avoided. So you made sure to choose the operations with care so that no intermediate values depend on the unmasked values.
(Un)fortunately, it has been shown that hardware glitches can leak information anyway. This paper concludes that this is a general problem for non-linear masked gates:
It has turned out that masked nonlinear gates, such as AND, NAND, OR and NOR gates are susceptible to DPA-attacks, while masked linear gates, such as XOR and XNOR gates, are resistant to DPA attacks.
The general idea is that the number of gates affected by a glitch depends on the unmasked input, for example this paper has a nice example of a masked AND gate. Methods that solve this problem have been proposed since then, though (see below). This is an area of active research.
Higher-order attacks are another possibility. I won't go into detail here, but if information from several points in the implementation can be combined, this (i.e. higher-order statistical moments) may leak information about the unmasked data.
I think my recent answer about threshold implementations is worth mentioning here. There, mutual information analysis (MIA) can be used to attack the proposed scheme. Hence, it's an example of how, even though each share of the realization is independent of at least one of the input shares, an unshared (secret) value may still be revealed using MIA. Of course, simply observing several shares (also a higher-order attack) would also work. Higher-order threshold implementations attempt to mitigate this problem (but currently don't entirely succeed).
Note: Some comments on the question have also mentioned the influence of memory access. As my knowledge of that subject is relatively limited, I'll leave the discussion to others. So you can take this answer to be mainly about the combinatorial part of an implementation.
The generation of random masks is also an interesting subject by itself, and much could be said about that. Other types of side-channel attacks, such as fault-attacks, will also lead to several other difficulties. For example, a fault-attack model allows active disruption of the implementation (injecting faults) which may lead to other ways of revealing key bits which do not explicitly occur in any computation. Consider what happens if you sabotage the RNG that provides the masks.
v (S-box output) is always computed in the form f(v), but f(v) still correlates with (leaks information about) v. Thus the power consumption still leaks information about v.
$\endgroup$
Most of side channel attacks are depends on algorithm and implementation. In several cases, power consumption is evidently visible in algorithm. For example in the algorithm for elliptic curve points multiplication, for computing $Q=k\cdot P$ we have following algorithm:
Let $k$ be $l$ bit.
Q=P
for i from l-1 to 0 do
Q = 2Q
if k_i == 1 then Q = Q+P
return Q
In this algorithm we find that if $k_i$ be $1$, then we must run $1$ more operation(Q+P).
So with observe to power consumption of device, we can recover key.
However, in another cases, this impact is not evident in algorithm, but we have probabilistic attack to recover key too.
For see an examples and another details you can see here.
