Editing Elliptic-curve cryptography (section)

== Security ==

=== Side-channel attacks ===
Unlike most other [[Discrete Logarithm|DLP]] systems (where it is possible to use the same procedure for squaring and multiplication), the EC addition is significantly different for doubling (''P'' = ''Q'') and general addition (''P'' ≠ ''Q'') depending on the coordinate system used. Consequently, it is important to counteract [[side-channel attack]]s (e.g., timing or [[Power analysis|simple/differential power analysis attacks]]) using, for example, fixed pattern window (a.k.a. comb) methods{{clarify|date=December 2011}}<ref>{{cite report |first1=M. |last1=Hedabou |first2=P. |last2=Pinel |first3=L. |last3=Beneteau |url=http://eprint.iacr.org/2004/342.pdf |title=A comb method to render ECC resistant against Side Channel Attacks |year=2004 |publisher=IACR Cryptology ePrint Archive}}</ref> (note that this does not increase computation time). Alternatively one can use an [[Edwards curve]]; this is a special family of elliptic curves for which doubling and addition can be done with the same operation.<ref>{{cite web | url=http://blog.cr.yp.to/20140323-ecdsa.html | title=Cr.yp.to: 2014.03.23: How to design an elliptic-curve signature system}}</ref> Another concern for ECC-systems is the danger of [[Differential fault analysis|fault attacks]], especially when running on [[smart card]]s.<ref>See, for example, {{Cite book |first1=Ingrid |last1=Biehl |first2=Bernd |last2=Meyer |first3=Volker |last3=Müller |title=Advances in Cryptology — CRYPTO 2000 |chapter=Differential Fault Attacks on Elliptic Curve Cryptosystems |series=[[Lecture Notes in Computer Science]] |volume=1880 |year=2000 |pages=131–146 |doi=10.1007/3-540-44598-6_8 |isbn=978-3-540-67907-3 |url=http://www.iacr.org/archive/crypto2000/18800131/18800131.pdf }}</ref>

=== Backdoors ===
Cryptographic experts have expressed concerns that the [[National Security Agency]] has inserted a [[kleptographic]] backdoor into at least one elliptic curve-based pseudo random generator.<ref>[https://www.schneier.com/essay-198.html "Did NSA Put a Secret Backdoor in New Encryption Standard?"]. ''www.schneier.com''.</ref> Internal memos leaked by former NSA contractor [[Edward Snowden]] suggest that the NSA put a backdoor in the [[Dual EC DRBG]] standard.<ref>{{Cite web|title = Government Announces Steps to Restore Confidence on Encryption Standards|url = http://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards/|website = NY Times – Bits Blog|access-date = 2015-11-06|date = 2013-09-10}}</ref> One analysis of the possible backdoor concluded that an adversary in possession of the algorithm's secret key could obtain encryption keys given only 32 bytes of PRNG output.<ref>{{Cite web |last1=Shumow |first1=Dan |last2=Ferguson |first2=Niels |title=On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng |url=http://rump2007.cr.yp.to/15-shumow.pdf |website=Microsoft}}</ref>

The SafeCurves project has been launched in order to catalog curves that are easy to implement securely and are designed in a fully publicly verifiable way to minimize the chance of a backdoor.<ref>{{Cite web | url = http://safecurves.cr.yp.to/ | title = SafeCurves: choosing safe curves for elliptic-curve cryptography | first1 = Daniel J. | last1 = Bernstein | first2 = Tanja | last2 = Lange | access-date = October 1, 2016}}</ref>

=== Quantum computing attack ===
[[Shor's algorithm]] can be used to break elliptic curve cryptography by computing discrete logarithms on a hypothetical [[Quantum computing|quantum computer]]. The latest quantum resource estimates for breaking a curve with a 256-bit modulus (128-bit security level) are 2330 [[qubits]] and 126 billion [[Toffoli gate]]s.<ref>{{Cite arXiv |eprint=1706.06752 |last1=Roetteler |first1=Martin |title=Quantum resource estimates for computing elliptic curve discrete logarithms |last2=Naehrig |first2=Michael |last3=Svore |first3=Krysta M.|author3-link= Krysta Svore |last4=Lauter |first4=Kristin |class=quant-ph |year=2017 }}</ref> For the binary elliptic curve case, 906 qubits are necessary (to break 128 bits of security).<ref>{{cite journal
 | last1 = Banegas | first1 = Gustavo
 | last2 = Bernstein | first2 = Daniel J.
 | last3 = van Hoof | first3 = Iggy
 | last4 = Lange | first4 = Tanja
 | doi = 10.46586/TCHES.V2021.I1.451-472
 | issue = 1
 | journal = IACR Transactions on Cryptographic Hardware and Embedded Systems
 | pages = 451–472
 | title = Concrete quantum cryptanalysis of binary elliptic curves
 | volume = 2021
 | year = 2021| doi-access = free
 }}</ref> In comparison, using Shor's algorithm to break the [[RSA (cryptosystem)|RSA]] algorithm requires 4098 qubits and 5.2 trillion Toffoli gates for a 2048-bit RSA key, suggesting that ECC is an easier target for quantum computers than RSA. All of these figures vastly exceed any quantum computer that has ever been built, and estimates place the creation of such computers at a decade or more away.{{when|date=May 2025}}{{citation needed|date=September 2020}}<ref>{{Cite web|last=Holmes|first=David|date=September 7, 2021|title=RSA in a "Pre-Post-Quantum" Computing World|url=https://www.f5.com/labs/articles/threat-intelligence/rsa-in-a-pre-post-quantum-computing-world|url-status=live|access-date=March 16, 2021|website=f5|archive-url=https://web.archive.org/web/20200808204717/https://www.f5.com/labs/articles/threat-intelligence/rsa-in-a-pre-post-quantum-computing-world |archive-date=2020-08-08 }}</ref>

[[Supersingular isogeny key exchange|Supersingular Isogeny Diffie–Hellman Key Exchange]] claimed to provide a [[Post-quantum cryptography|post-quantum]] secure form of elliptic curve cryptography by using [[isogenies]] to implement [[Diffie–Hellman]] key exchanges.  This key exchange uses much of the same field arithmetic as existing elliptic curve cryptography and requires computational and transmission overhead similar to many currently used public key systems.<ref>{{cite web|last=De Feo|first=Luca|title=Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies|url=https://eprint.iacr.org/2011/506|work=Cryptology ePrint Archive, Report 2011/506|publisher=IACR|access-date=3 May 2014|author2=Jao, Plut|archive-url=https://web.archive.org/web/20140503190338/http://eprint.iacr.org/2011/506|archive-date=2014-05-03|url-status=dead|year=2011}}</ref> However, new classical attacks undermined the security of this protocol.<ref>{{Cite journal |last=Robert |first=Damien |date=2022 |title=Breaking SIDH in polynomial time |url=https://eprint.iacr.org/2022/1038 |journal=Cryptology ePrint Archive |language=en}}</ref>

In August 2015, the NSA announced that it planned to transition "in the not distant future" to a new cipher suite that is resistant to [[quantum computing|quantum]] attacks. "Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, necessitating a re-evaluation of our cryptographic strategy."<ref name="nsaquantum">{{cite web|url=https://apps.nsa.gov/iaarchive/programs/iad-initiatives/cnsa-suite.cfm|title=Commercial National Security Algorithm Suite|date=19 August 2015|website=www.nsa.gov|url-status=live|archive-url=https://web.archive.org/web/20190604080321/https://apps.nsa.gov/iaarchive/programs/iad-initiatives/cnsa-suite.cfm|archive-date=2019-06-04|access-date=2020-01-08}}</ref>

=== Invalid curve attack ===

When ECC is used in [[virtual machine]]s, an attacker may use an invalid curve to get a complete PDH private key.<ref name = "Cohen, Seclist, 2019" >{{ cite web | url = https://seclists.org/fulldisclosure/2019/Jun/46 | title = AMD-SEV: Platform DH key recovery via invalid curve attack (CVE-2019-9836) | access-date = 4 July 2019 | first = Cfir | last = Cohen | date = 25 June 2019 | website = Seclist Org | quote = The SEV elliptic-curve (ECC) implementation was found to be vulnerable to an invalid curve attack. At launch-start command, an attacker can send small order ECC points not on the official NIST curves, and force the SEV firmware to multiply a small order point by the firmware’s private DH scalar. | archive-url = https://web.archive.org/web/20190702011957/https://seclists.org/fulldisclosure/2019/Jun/46 | archive-date = 2 July 2019 | df = dmy-all }}</ref>