The most powerful SCA attack from an information theoretic point of view is considered to be a template attack (TA). Template attacks, as introduced in the original paper by Chari et al. in [52], are a combination of statistical modeling and power analysis attacks consisting of two phases, as follows:

• The first phase is the profiling or template-building phase, where the adversary builds templates to characterize the device by executing a sequence of instructions on fixed data. Focusing on an “interesting pattern” or finding the points of interest is very common in this phase.

• The second phase is the template-matching phase, in which the adversary matches or correlates the templates to actual traces of the device. By applying some signal processing and classification algorithms to the templates, it is possible to find the best matching for the traces.

In this type of attacks, the adversary is assumed to have in his possession a device which behaves similar to the device under attack (target device), in order to build template traces. In his device he can simulate the same algorithms and implementations that run in the target device. For the template-matching phase several distinguishers and classification algorithms are proposed; in the next section the most common classifiers are presented.

The practical application of TAs is shown on several cryptographic implementations such as RC4 in [53] and elliptic curves in [54]. Medwed and Oswald demonstrated in [ 42] a practical template attack on ECDSA. However, their attack required an offline DPA attack on the EC scalar multiplication operation during the templatebuilding phase, in order to select the points of interest. They also need 33 template traces per key bit. Furthermore, attacks against ECDSA and other elliptic curve signature algorithms only need to recover a few bits of the ephemeral scalar for multiple scalar multiplications with different ephemeral scalars and can then employ lattice techniques to recover the long-term secret key [35, 36, 43]. It is not possible to obtain several traces in the context of ephemeral Diffie-Hellman: an attacker only gets a single trace and needs to recover sufficiently many bits of this ephemeral scalar from side-channel information to be able to compute the remaining bits through, for example, Kangaroo techniques [55, 56]. With these techniques and by using precomputation tables, it is possible to exploit partial information on the subkeys and recover the last l unknown bits of the key in O(^l) group operations [57].