The Monodromy Leak for a Generalized Montgomery Ladder

Abstract

The Diffie-Hellman key exchange protocol using elliptic curves is the most wide-spread approach to the establishment of a secure internet connection. As an important subroutine, Alice and Bob need to perform multiplications of elliptic curve points by large scalars. The textbook method for scalar multiplication is the double-and-add algorithm. For the sake of efficiency, one usually performs x-coordinate only arithmetic using projective coordinates, and doubling-and-adding is done using the Montgomery ladder. The advantage of using projective coordinates is that this avoids costly field inversions at each iteration. However, when Alice (say) uses the double-and-add algorithm for computing her public key Q = [a]P, it is a bad idea for her to publish the resulting projective coordinates of Q. Indeed, it was shown in 2003 by Naccache, Smart and Stern that these coordinates leak a few bits of the secret scalar a. Therefore, Alice must perform a final division deprojectivizing the coordinates of Q, and this division must be done in constant time so that side-channel analysis does not allow for a reconstruction of these projective coordinates. In 2019 Aldaya, Garcia and Brumley discovered that many real-life implementations violate this requirement. New work by Robert from 2024 shows that the leak is much more devastating than assumed by Naccache et al.: one can easily recover the entire secret. Thus, bad implementations of elliptic curve scalar multiplication using the Montgomery ladder are a recipe for disaster. The goal of this thesis is to study the new method by Robert, which he calls “the monodromy leak”. It stems from the deep fact that the set of all possible projective coordinates for points on an elliptic curve E (called “cubical points”) still comes equipped with a natural scalar- multiplication map, despite this set not being a group. Robert shows that the cubical discrete logarithm problem reduces to a discrete logarithm problem in the underlying finite field, which is known to be easier (index-calculus). He then also shows that the Montgomery ladder essentially implements cubical scalar multiplication: whence the devastating conclusion. Besides understanding how the attack works, the goal is also to study the relation between cubical arithmetic and other projective double-and-add algorithms (such as the standard double-and-add algorithm for Weierstrass curves, or Edwards curves). Our current conclusion is that the Monodromy Leak is specific to the Montgomery ladder, but not to Montxi gomery curves : we generalize the attack to Partially-Long Weierstrass curves (PLWC). For the standard double-and-add algorithm on Edwards curves (as used in EdDSA), we report on some first explorations. There are also other applications of cubical arithmetic, namely to the efficient computation of pairings, and to the efficient computation of isogenies. Isogeny-based cryptography is another booming branch in cryptography, which is supposed to remain hard even in the presence of quantum adversaries (unlike “classical” elliptic curve cryptography, which is based on the discrete logarithm problem and therefore broken by Shor’s algorithm). However, these applications are not touched upon in this thesis.