# Collision-Correlation Attacks

As mentioned above, collision attacks exploit leakages by comparing two portions of the same or different traces exploiting the same power being consumed when values are reused. The Big Mac attack [38] is the first theoretical attack on public-key cryptosystems, in which only a single trace is required to observe key dependencies and collisions during an RSA exponentiation. Witteman et al. performed a similar attack on the RSA modular exponentiation even in the presence of blinded messages [48]. Clavier et al. introduced horizontal correlation analysis, as a type of attack where a single power trace is enough to recover the private key [46]. They also extended the Big Mac attack using different distinguishers, i.e., types of statistical tests.

The *doubling attack,* proposed by Fouque and Vallette [37] and described previously, is a special type of collision attack relevant to ECC. The main assumption of this attack is that an adversary can distinguish collisions of power trace segments (within a single or more power traces) when the device under attack performs twice the same computation, even if the adversary is not able to tell which exact computation is done. Collision of two computations will not reveal the value of the operand. Yen et al. extended this attack to the *Refined Doubling Attack (RDA)* [39], where the adversary is assumed to be able to detect the collision between two modular squarings, i.e., detecting if the squared value is the same or not. Collisions of computations cannot be distinguished; the only knowledge obtained is that k *= k* __{1} if a collision is detected. Based on the derived relationship between every two adjacent private key bits (either *k = k*__{1} or *k =* k_{i}__{1}) and a given bit (e.g., k_{0} or k_{m-1}), all other private key bits can be derived uniquely. RDA is a powerful attack technique that works against some scalar multiplication algorithms, which are resistant against the doubling attack (e.g., the Montgomery power ladder).