A Hole in the Ladder: Interleaved Variables in Iterative Conditional Branching (Extended Version)

Yoann Marquer (1) , Tania Richmond (2, 1) , Pascal Véron (3)

1 IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires
2 DGA.MI - DGA Maîtrise de l'information
3 IMATH - Institut de Mathématiques de Toulon - EA 2134

The iterative conditional branchings appear in various sensitive algorithms, like the modular exponentiation in the RSA cryptosystem or the scalar multiplication in ellipticcurve cryptography. In this paper, we abstract away the desirable security properties achieved by the Montgomery ladder, and formalize systems of equations necessary to obtain what we call the semi-interleaved and fully-interleaved ladder properties. This fruitful approach allows us to design novel fault-injection attacks, able to obtain some/all bits of the secret against different ladders, including the common Montgomery ladder. We also demonstrate the generality of our approach by applying the ladder equations to the modular exponentiation and the scalar multiplication, both in the semi-and fully-interleaved cases, thus proposing novel and more secure algorithms.

Mots clés: Security and Privacy Protection; Public key cryptosystems; Computer arithmetic; Fault injection; Security and Privacy Protection; Security and Privacy Protection

Domaines: Cryptographie et sécurité [cs.CR]

Yoann Marquer, Tania Richmond, Pascal Véron. A Hole in the Ladder: Interleaved Variables in Iterative Conditional Branching (Extended Version). 2021. ⟨hal-03157804v1⟩