Multi-bit blinding: A countermeasure for RSA against side channel attacks

Asymmetric algorithms such as RSA are considered secure from an algorithmic point of view, yet their implementations are typically vulnerable as they are used by attackers to comprise the secret key. Many countermeasures have been proposed to thwart these attacks. However, they are typically broken as the key can be easily compromised when attackers succeed figuring out which part of the traces belong to the square and multiply operations. In this paper, a new countermeasure is proposed against side channel attacks, referred to as multi-bit blinding. The proposed method provides a constant execution behavior regardless of the key value without additional cost (i.e., dummy/extra operations). It realizes this by considering multiple bits of the key (i.e., two in this paper) simultaneously and always perform the same operations on them independent of the two-bit value. This makes attacks much harder as the attacker cannot retrieve the key simply by identifying the operations. Instead, the attackers need to guess the correct values of the operations as well. As a case study, the security of an RSA algorithm implementation based on the proposed method is evaluated. Our experimental results show that the new method is secure against profiled and non-profiled side channel attacks with less overhead than currently published countermeasures.