Combined small subgroups and side-channel attack on elliptic curves with cofactor divisible by $2^m$

Authors

Abstract

Nowadays, alternative models of elliptic curves like Montgomery, Edwards, twisted Edwards, Hessian, twisted Hessian, Huff's curves and many others are very popular and many people use them in cryptosystems which are based on elliptic curve cryptography. Most of these models allow to use fast and complete arithmetic which is especially convenient in fast implementations that are side-channel attacks resistant. Montgomery, Edwards and twisted Edwards curves have always order of group of rational points divisible by 4. Huff's curves have always order of rational points divisible by 8. Moreover, sometimes to get fast and efficient implementations one can choose elliptic curve with even bigger cofactor, for example 16. Of course the bigger cofactor is, the smaller is the security of cryptosystem which uses such elliptic curve. In this article will be checked what influence on the security has form of cofactor of elliptic curve and will be showed that in some situations elliptic curves with cofactor divisible by $2^m$ are vulnerable for combined small subgroups and side-channel attacks.

References

@InProceedings{Bie00,

author="Biehl, Ingrid

and Meyer, Bernd

and M{"u}ller, Volker",

editor="Bellare, Mihir",

title="Differential Fault Attacks on Elliptic Curve Cryptosystems",

booktitle="Advances in Cryptology --- CRYPTO 2000",

year="2000",

publisher="Springer Berlin Heidelberg",

address="Berlin, Heidelberg",

pages="131--146",

abstract="In this paper we extend the ideas for differential fault attacks on the RSA cryptosystem (see [4]) to schemes using elliptic curves. We present three different types of attacks that can be used to derive information about the secret key if bit errors can be inserted into the elliptic curve computations in a tamper-proof device. The effectiveness of the attacks was proven in a software simulation of the described ideas.",

isbn="978-3-540-44598-2"

}

@Article{Poh76,

author="Pohlig, S. and Hellman, M.",

title="An Improved Algorithm for Computing Logarithms over and Its Cryptographic Significance",

journal="IEEE Trans. Inf. Theor.",

year="1978",

month="September",

day="01",

volume="24",

number="1",

pages="106--110",

abstract="",

issn="0018-9448",

doi="10.1109/TIT.1978.1055817",

url="https://doi.org/10.1109/TIT.1978.1055817"

}

@Article{Cie05,

author="Ciet, Mathieu

and Joye, Marc",

title="Elliptic Curve Cryptosystems in the Presence of Permanent and Transient Faults",

journal="Designs, Codes and Cryptography",

year="2005",

month="Jul",

day="01",

volume="36",

number="1",

pages="33--43",

abstract="Elliptic curve cryptosystems in the presence of faults were studied by Biehl et al., Advances in Cryptology CRYPTO 2000, Springer Verlag (2000) pp. 131--146. The first fault model they consider requires that the input point P in the computation of dP is chosen by the adversary. Their second and third fault models only require the knowledge of P. But these two latter models are less `practical' in the sense that they assume that only a few bits of error are inserted (typically exactly one bit is supposed to be disturbed) either into P just prior to the point multiplication or during the course of the computation in a chosen location.",

issn="1573-7586",

doi="10.1007/s10623-003-1160-8",

url="https://doi.org/10.1007/s10623-003-1160-8"

}

@inproceedings{Bir08,

author = {Bernstein, Daniel J. and Birkner, Peter and Joye, Marc and Lange, Tanja and Peters, Christiane},

title = {Twisted Edwards Curves},

booktitle = {Proceedings of the Cryptology in Africa 1st International Conference on Progress in Cryptology},

series = {AFRICACRYPT'08},

year = {2008},

isbn = {3-540-68159-0, 978-3-540-68159-5},

location = {Casablanca, Morocco},

pages = {389--405},

numpages = {17},

url = {http://dl.acm.org/citation.cfm?id=1788634.1788672},

acmid = {1788672},

publisher = {Springer-Verlag},

address = {Berlin, Heidelberg},

keywords = {edwards curves, elliptic curves, isogenies, montgomery curves, twisted edwards curves},

}

@InProceedings{Ber06,

author="Bernstein, Daniel J.",

editor="Yung, Moti

and Dodis, Yevgeniy

and Kiayias, Aggelos

and Malkin, Tal",

title="Curve25519: New Diffie-Hellman Speed Records",

booktitle="Public Key Cryptography - PKC 2006",

year="2006",

publisher="Springer Berlin Heidelberg",

address="Berlin, Heidelberg",

pages="207--228",

abstract="This paper explains the design and implementation of a high-security elliptic-curve-Diffie-Hellman function achieving record-setting speeds: e.g., 832457 Pentium III cycles (with several side benefits: free key compression, free key validation, and state-of-the-art timing-attack protection), more than twice as fast as other authors' results at the same conjectured security level (with or without the side benefits).",

isbn="978-3-540-33852-9"

}

@Article{Mon87,

author="Peter, Montgomery",

title="Speeding the Pollard and elliptic curve methods of factorization",

journal="Mathematics of Computation",

year="1987",

month="",

day="01",

volume="48",

number="",

pages="243--264",

abstract=""

}

@Article{Nev16,

author = "Samuel Neves and

Mehdi Tibouchi",

title = "Degenerate curve attacks: extending invalid curve attacks to Edwards curves and other models",

journal = "{IET} Information Security",

volume = "12",

number = "3",

pages = "217--225",

year = "2018",

url = "https://doi.org/10.1049/iet-ifs.2017.0075",

doi = "10.1049/iet-ifs.2017.0075",

timestamp = "Fri, 30 Nov 2018 00:00:00 +0100",

biburl = "https://dblp.org/rec/bib/journals/iet-ifs/NevesT18",

bibsource = "dblp computer science bibliography, https://dblp.org"

}

@InProceedings{Lan07,

author="Bernstein, Daniel J.

and Lange, Tanja",

editor="Kurosawa, Kaoru",

title="Faster Addition and Doubling on Elliptic Curves",

booktitle="Advances in Cryptology -- ASIACRYPT 2007",

year="2007",

publisher="Springer Berlin Heidelberg",

address="Berlin, Heidelberg",

pages="29--50",

abstract="Edwards recently introduced a new normal form for elliptic curves. Every elliptic curve over a non-binary field is birationally equivalent to a curve in Edwards form over an extension of the field, and in many cases over the original field.",

isbn="978-3-540-76900-2"

}

@Article{Edw07,

author="Harold, Edwards",

title="A normal form for elliptic curves",

journal="Bulletin

of the American Mathematical Society",

year="2007",

month="April",

day="09",

volume="44",

number="3",

pages="393--422",

doi="https://doi.org/10.1090/S0273-0979-07-01153-6",

abstract=""

}

@INPROCEEDINGS{Lim97,

author = {Chae Hoon Lim and Pil Joong Lee},

title = {A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup},

booktitle = {},

year = {1997},

pages = {249--263},

publisher = {Springer-Verlag}

}

@Article{Zuc00,

author="R., Zuccherato",

title="Methods for Avoiding the small-Subgroup Attacks on the Diffie-Hellman Key Agreement Method for S/MIME",

journal="RFC 2785",

year="2000",

month="March",

day="01",

volume="",

number="",

pages="",

doi="",

abstract=""

}

@InProceedings{Fan11,

author="Fan, Junfeng

and Gierlichs, Benedikt

and Vercauteren, Frederik",

editor="Preneel, Bart

and Takagi, Tsuyoshi",

title="To Infinity and Beyond: Combined Attack on ECC Using Points of Low Order",

booktitle="Cryptographic Hardware and Embedded Systems -- CHES 2011",

year="2011",

publisher="Springer Berlin Heidelberg",

address="Berlin, Heidelberg",

pages="143--159",

abstract="We present a novel combined attack against ECC implementations that exploits specially crafted, but valid input points. The core idea is that after fault injection, these points turn into points of very low order. Using side channel information we deduce when the point at infinity occurs during the scalar multiplication, which leaks information about the secret key. In the best case, our attack breaks a simple and differential side channel analysis resistant implementation with input/output point validity and curve parameter checks using a single query.",

isbn="978-3-642-23951-9"

}

@InProceedings{Joy10,

author="Joye, Marc

and Tibouchi, Mehdi

and Vergnaud, Damien",

editor="Hanrot, Guillaume

and Morain, Fran{c{c}}ois

and Thom{'e}, Emmanuel",

title="Huff's Model for Elliptic Curves",

booktitle="Algorithmic Number Theory",

year="2010",

publisher="Springer Berlin Heidelberg",

address="Berlin, Heidelberg",

pages="234--250",

abstract="This paper revisits a model for elliptic curves over Q introduced by Huff in 1948 to study a diophantine problem. Huff's model readily extends over fields of odd characteristic. Every elliptic curve over such a field and containing a copy of Z/4Z {texttimes}Z/2Z is birationally equivalent to a Huff curve over the original field.",

isbn="978-3-642-14518-6"

}

@inproceedings{Gen17,

author = {Genkin, Daniel and Valenta, Luke and Yarom, Yuval},

title = {May the Fourth Be With You: A Microarchitectural Side Channel Attack on Several Real-World Applications of Curve25519},

booktitle = {Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security},

series = {CCS '17},

year = {2017},

isbn = {978-1-4503-4946-8},

location = {Dallas, Texas, USA},

pages = {845--858},

numpages = {14},

url = {http://doi.acm.org/10.1145/3133956.3134029},

doi = {10.1145/3133956.3134029},

acmid = {3134029},

publisher = {ACM},

address = {New York, NY, USA},

keywords = {cache-attacks, curve25519, flush+reload, order-4 elements, side channel attacks},

}

Downloads

Published

2024-04-19

Issue

Section

Cryptography and Cybersecurity