An online template attack (OTA) is a powerful technique previously used to
attack elliptic curve scalar multiplication algorithms. This attack has only
been analyzed in the realm of power consumption and EM side channels, where the
signals leak related to the value being processed. However, microarchitecture
signals have no such feature, invalidating some assumptions from previous OTA
In this paper, we revisit previous OTA descriptions, proposing a generic
framework and evaluation metrics for any side-channel signal. Our analysis
reveals OTA features not previously considered, increasing its application
scenarios and requiring a fresh countermeasure analysis to prevent it.
In this regard, we demonstrate that OTAs can work in the backward direction,
allowing to mount an augmented projective coordinates attack with respect to
the proposal by Naccache, Smart and Stern (Eurocrypt 2004). This demonstrates
that randomizing the initial targeted algorithm state does not prevent the
attack as believed in previous works.
We analyze three libraries libgcrypt, mbedTLS, and wolfSSL using two
microarchitecture side channels. For the libgcrypt case, we target its EdDSA
implementation using Curve25519 twist curve. We obtain similar results for
mbedTLS and wolfSSL with curve secp256r1. For each library, we execute
extensive attack instances that are able to recover the complete scalar in all
cases using a single trace.
This work demonstrates that microarchitecture online template attacks are
also very powerful in this scenario, recovering secret information without
knowing a leakage model. This highlights the importance of developing
secure-by-default implementations, instead of fix-on-demand ones.