Correlated extra-reductions defeat blinded regular exponentiation

Walter and Thomson (CT-RSA ’01) and Schindler (PKC ’02)It should be emphasized that that have shown that extra-reductions allow to break RSA-CRT even with message blinding. Indeed, the extrareduction probability depends on the type of operation (square, multiply, or multiply with a constant). Regular exponentiation schemes can be regarded as protections since the operation sequence does not depend on the secret. In this article, we show that there exists a strong negative correlation between extra-reductions of two consecutive operations, provided that the first feeds the second. This allows to mount successful attacks even against blinded asymmetrical computations with a regular exponentiation algorithm, such as Square-and-Multiply Always or Montgomery Ladder. We investigate various attack strategies depending on the context— known or unknown modulus, known or unknown extra-reduction detection probability, etc.—and implement them on two devices: a single core ARM Cortex-M4 and a dual core ARM Cortex M0-M 4.