Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Invalid Curve Attacks in a GLS Setting
verfasst von : Taechan Kim, Mehdi Tibouchi
Erschienen in: Advances in Information and Computer Security
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In recent years, most speed records for implementations of elliptic curve cryptosystems have been achieved on curves endowed with nontrivial fast endomorphisms, particularly based on the technique introduced by Galbraith, Lin and Scott (GLS). Therefore, studying the security of those curves is of prime importance.
In this paper, we examine the applicability of the class of attacks introduced by Biehl et al., known as invalid curve attacks, to cryptographic implementations based on GLS curves. In invalid curve attacks, a cryptographic device that computes a secret scalar multiplication \(P\mapsto kP\) on a certain elliptic curve \(E/{\mathbb F}_q\) receives as input an arbitrary “invalid” point \(\widetilde{P}\not \in E({\mathbb F}_q)\). Biehl et al. observed that the device then computes the scalar multiplication by k on a different elliptic curve \(\widetilde{E}/{\mathbb F}_q\), and if that curve is weaker than E, the attacker can use the result to recover information about the secret k.
The attack doesn’t readily adapt to the GLS setting, since the device computes the scalar multiplication as \(P\mapsto k_1P + k_2\psi (P)\) where \(\psi \) is the efficient endomorphism of the GLS curve E, and if it receives an arbitrary invalid point \(\widetilde{P}\) on a curve \(\widetilde{E}\ne E\), the computation of the map \(\psi \) yields a point on a completely different curve again, and the scalar multiplication outputs gibberish. We show, however, that a large family of invalid points \(\widetilde{P}\) lie on curve stable under \(\psi \), and using that observation we can modify the attack of Biehl et al. to effectively recover the secrets \(k_1\) and \(k_2\), although the result of the computation on an invalid point doesn’t have the “correct” discrete logarithm.