A Hole in the Ladder: Interleaved Variables in Iterative Conditional Branching

January 11, 2021

Yoann Marquer (INRIA Rennes)

Iterative conditional branching are used in sensitive environments, like the modular exponentiation in the RSA cryptographic protocol, but these algorithms are usually vulnerable against side-channel attacks and fault-injection attacks.
The Montgomery ladder algorithm for the modular exponentiation uses interleaved variables to protect the execution from these attacks.
We abstracted away the properties verified by the Montgomery ladder at every step of the computation, and formalized the conditions for more secure algorithms by using systems of equations.
We obtained the conditions for semi-interleaved (like the Montgomery ladder) or even fully-interleaved ladder algorithms, and proposed a fault-injection attack able to obtain bits of the secret against semi-interleaved ladders (including the original Montgomery ladder) but not against fully-interleaved ladders.
We also applied these equations to extend the Montgomery ladder for both the semi- and fully-interleaved cases, thus proposing novel and more secure algorithms to compute the modular exponentiation.
Thus, we captured a classe of secure algorithms, and proposed a general and fruitful methodology to detect or construct these algorithms for the targetted functions.