Combined small subgroups and side-channel attack on elliptic curves with cofactor divisible by $2^m$
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
Issue
Section
License
Copyright (c) 2019 International Journal of Electronics and Telecommunications
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
1. License
The non-commercial use of the article will be governed by the Creative Commons Attribution license as currently displayed on https://creativecommons.org/licenses/by/4.0/.
2. Author’s Warranties
The author warrants that the article is original, written by stated author/s, has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author/s. The undersigned also warrants that the manuscript (or its essential substance) has not been published other than as an abstract or doctorate thesis and has not been submitted for consideration elsewhere, for print, electronic or digital publication.
3. User Rights
Under the Creative Commons Attribution license, the author(s) and users are free to share (copy, distribute and transmit the contribution) under the following conditions: 1. they must attribute the contribution in the manner specified by the author or licensor, 2. they may alter, transform, or build upon this work, 3. they may use this contribution for commercial purposes.
4. Rights of Authors
Authors retain the following rights:
- copyright, and other proprietary rights relating to the article, such as patent rights,
- the right to use the substance of the article in own future works, including lectures and books,
- the right to reproduce the article for own purposes, provided the copies are not offered for sale,
- the right to self-archive the article
- the right to supervision over the integrity of the content of the work and its fair use.
5. Co-Authorship
If the article was prepared jointly with other authors, the signatory of this form warrants that he/she has been authorized by all co-authors to sign this agreement on their behalf, and agrees to inform his/her co-authors of the terms of this agreement.
6. Termination
This agreement can be terminated by the author or the Journal Owner upon two months’ notice where the other party has materially breached this agreement and failed to remedy such breach within a month of being given the terminating party’s notice requesting such breach to be remedied. No breach or violation of this agreement will cause this agreement or any license granted in it to terminate automatically or affect the definition of the Journal Owner. The author and the Journal Owner may agree to terminate this agreement at any time. This agreement or any license granted in it cannot be terminated otherwise than in accordance with this section 6. This License shall remain in effect throughout the term of copyright in the Work and may not be revoked without the express written consent of both parties.
7. Royalties
This agreement entitles the author to no royalties or other fees. To such extent as legally permissible, the author waives his or her right to collect royalties relative to the article in respect of any use of the article by the Journal Owner or its sublicensee.
8. Miscellaneous
The Journal Owner will publish the article (or have it published) in the Journal if the article’s editorial process is successfully completed and the Journal Owner or its sublicensee has become obligated to have the article published. Where such obligation depends on the payment of a fee, it shall not be deemed to exist until such time as that fee is paid. The Journal Owner may conform the article to a style of punctuation, spelling, capitalization and usage that it deems appropriate. The Journal Owner will be allowed to sublicense the rights that are licensed to it under this agreement. This agreement will be governed by the laws of Poland.
By signing this License, Author(s) warrant(s) that they have the full power to enter into this agreement. This License shall remain in effect throughout the term of copyright in the Work and may not be revoked without the express written consent of both parties.
