Visible to the public A Hole in the Ladder : Interleaved Variables in Iterative Conditional Branching

TitleA Hole in the Ladder : Interleaved Variables in Iterative Conditional Branching
Publication TypeConference Paper
Year of Publication2020
AuthorsMarquer, Y., Richmond, T.
Conference Name2020 IEEE 27th Symposium on Computer Arithmetic (ARITH)
KeywordsCountermeasures (computer), cryptographic protocols, cryptography, exponentiation, fault detection, fully-interleaved cases, fully-interleaved ladder properties, fully-interleaved ladders, interleaved codes, interleaved variables, Iterative algorithms, iterative conditional branching, Mathematical model, modular exponentiation, Montgomery ladder, pubcrawl, public key cryptography, public-key cryptography, Registers, Resiliency, RSA cryptographic protocol, Scalability, security, semiinterleaved ladders, side-channel attacks, Space exploration
AbstractThe modular exponentiation is crucial to the RSA cryptographic protocol, and variants inspired by the Montgomery ladder have been studied to provide more secure algorithms. In this paper, we abstract away the iterative conditional branching used in the Montgomery ladder, and formalize systems of equations necessary to obtain what we call the semi-interleaved and fully-interleaved ladder properties. In particular, we design fault-injection attacks able to obtain bits of the secret against semi-interleaved ladders, including the Montgomery ladder, but not against fully-interleaved ladders that are more secure. We also apply 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.
Citation Keymarquer_hole_2020