@article{Ueno_Homma_2023, title={How Secure is Exponent-blinded RSA–CRT with Sliding Window Exponentiation?}, volume={2023}, url={https://tches.iacr.org/index.php/TCHES/article/view/10283}, DOI={10.46586/tches.v2023.i2.241-269}, abstractNote={<p>This paper presents the first security evaluation of exponent-blinded RSA–CRT implementation with sliding window exponentiation against cache attacks. Our main contributions are threefold. (1) We demonstrate an improved cache attack using Flush+Reload on RSA–CRT to estimate the squaring–multiplication operational sequence. The proposed method can estimate a correct squaring–multiplication sequence from one Flush+Reload trace, while the existing Flush+Reload attacks always contain errors in the sequence estimation. This is mandatory for the subsequent steps in the proposed attack. (2) We present a new and first partial key exposure attack on exponent-blinded RSA–CRT with a random-bit leak. The proposed attack first estimates a random mask for blinding exponent using a modification of the Schindler–Wiemers continued fraction attack, and then recovers the secret key using an extension of the Heninger–Shacham branch-and-prune attack. We experimentally show that the proposed attack on RSA–CRT using a practical window size of 5 with 16-, 32-, and 64-bit masks is carried out with complexity of 2<sup>25.6</sup>, 2<sup>67.7</sup>, and 2<sup>161</sup>, respectively. (3) We then investigate the tradeoffs between mask bit length and implementation performance. The computational cost of exponent-blinded RSA–CRT using a sliding window with a 32- and 64-bit mask are 15% and 10% faster than that with a 128-bit mask, respectively, as we confirmed that 32- and 64-bit masks are sufficient to defeat the proposed attack. Our source code used in the experiment is publicly available.</p>}, number={2}, journal={IACR Transactions on Cryptographic Hardware and Embedded Systems}, author={Ueno, Rei and Homma, Naofumi}, year={2023}, month={Mar.}, pages={241–269} }