High-Order Collision Attack Vulnerabilities in Montgomery Ladder Implementations of RSA

This paper describes a straightforward methodology which allows mounting a specific kind of single-trace attacks called collision attacks. We first introduce the methodology (which operates at the algorithmic level) and then provide empirical evidence of its soundness by locating the points of interest involved in all existing collisions and then attacking an unmasked RSA implementation whose modular exponentiation is based on the Montgomery Ladder. The attacks we performed, albeit slightly worse than the theoretical prediction, are very encouraging nonetheless: the whole secret exponent can be retrieved (i.e., a success rate equal to 100%) using only 10 traces. Lastly, we describe how this could allow for the introduction of high-order attacks, which are known to break some protected implementations of symmetric cryptography, in the context of asymmetric cryptography.