TY - JOUR
AU - Ueno, Rei
AU - Homma, Naofumi
PY - 2023/03/06
Y2 - 2023/03/22
TI - How Secure is Exponent-blinded RSA–CRT with Sliding Window Exponentiation?
JF - IACR Transactions on Cryptographic Hardware and Embedded Systems
JA - TCHES
VL - 2023
IS - 2
SE - Articles
DO - 10.46586/tches.v2023.i2.241-269
UR - https://tches.iacr.org/index.php/TCHES/article/view/10283
SP - 241-269
AB - <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>
ER -