Online Template Attacks

An adaptive template attack technique, called online template attacks (OTAs), can recover a complete scalar from only one power trace of a scalar multiplication.


Lejla Batina, Radboud University Nijmegen, Nijmegen, The Netherlands
Łukasz Chmielewski, Riscure, Delft, The Netherlands
Louiza Papachristodoulou, Radboud University Nijmegen, Nijmegen, The Netherlands
Peter Schwabe, Radboud University Nijmegen, Nijmegen, The Netherlands
Michael Tunstall, Rambus Cryptography Research Division, San Francisco, USA.

Template attacks are a special kind of side-channel attacks that work in two stages. In a first stage, the attacker builds up a database of template traces collected from a device which is identical to the attacked device, but under the attacker’s control. In the second stage, traces from the target device are compared to the template traces to recover the secret key. In the context of attacking elliptic curve scalar multiplication with template attacks, one can interleave template generation and template matching and reduce the amount of template traces. This paper enhances the power of this technique by defining and applying the concept of online template attacks, a general attack technique with minimal assumptions for an attacker, who has very very limited control over the template device. We show that online template attacks need only one power consumption trace of a scalar multiplication on the target device; they are thus suitable not only against ECDSA and static elliptic curve Diffie–Hellman (ECDH), but also against elliptic curve scalar multiplication in ephemeral ECDH. In addition, online template attacks need only one template trace per scalar bit and they can be applied to a broad variety of scalar multiplication algorithms. To demonstrate the power of online template attacks, we recover scalar bits of a scalar multiplication using the double-and-add-always algorithm on a twisted Edwards curve running on a smartcard with an ATmega163 CPU.

Click here to continue reading.

Leave a Reply

(Note: This name will be displayed publicly)