IACR News item: 04 August 2020
Johannes Mittmann, Werner Schindler
ePrint Report
Montgomerys and Barretts modular multiplication algorithms are widely used in modular exponentiation algorithms, e.g. to compute RSA or ECC operations. While Montgomerys multiplication algorithm has been studied extensively in the literature and many side-channel attacks have been detected, to our best knowledge no thorough analysis exists for Barretts multiplication algorithm. This article closes this gap. For both Montgomerys and Barretts multiplication algorithm, differences of the execution times are caused by conditional integer subtractions, so-called extra reductions. Barretts multiplication algorithm allows even two extra reductions, and this feature increases the mathematical difficulties significantly.
We formulate and analyse a two-dimensional Markov process, from which we deduce relevant stochastic properties of Barretts multiplication algorithm within modular exponentiation algorithms. This allows to transfer the timing attacks and local timing attacks (where a second side-channel attack exhibits the execution times of the particular modular squarings and multiplications) on Montgomerys multiplication algorithm to attacks on Barretts algorithm. However, there are also differences. Barretts multiplication algorithm requires additional attack substeps, and the attack efficiency is much more sensitive to variations of the parameters. We treat timing attacks on RSA with CRT, on RSA without CRT, and on Diffie-Hellman, as well as local timing attacks against these algorithms in the presence of basis blinding. Experiments confirm our theoretical results.
We formulate and analyse a two-dimensional Markov process, from which we deduce relevant stochastic properties of Barretts multiplication algorithm within modular exponentiation algorithms. This allows to transfer the timing attacks and local timing attacks (where a second side-channel attack exhibits the execution times of the particular modular squarings and multiplications) on Montgomerys multiplication algorithm to attacks on Barretts algorithm. However, there are also differences. Barretts multiplication algorithm requires additional attack substeps, and the attack efficiency is much more sensitive to variations of the parameters. We treat timing attacks on RSA with CRT, on RSA without CRT, and on Diffie-Hellman, as well as local timing attacks against these algorithms in the presence of basis blinding. Experiments confirm our theoretical results.
Additional news items may be found on the IACR news page.