https://www.schneier.com/blog/archives/2022/02/breaking-245-bit-elliptic-curve-encryption-with-a-quantum-computer.html Schneier on Security Menu * Blog * Newsletter * Books * Essays * News * Talks * Academic * About Me Search Powered by DuckDuckGo [ ] [Go] ( ) Blog ( ) Essays (*) Whole site Subscribe Atom FeedFacebookTwitterKindleE-Mail Newsletter (Crypto-Gram) HomeBlog Breaking 256-bit Elliptic Curve Encryption with a Quantum Computer Researchers have calculated the quantum computer size necessary to break 256-bit elliptic curve public-key cryptography: Finally, we calculate the number of physical qubits required to break the 256-bit elliptic curve encryption of keys in the Bitcoin network within the small available time frame in which it would actually pose a threat to do so. It would require 317 x 10^ 6 physical qubits to break the encryption within one hour using the surface code, a code cycle time of 1 ms, a reaction time of 10 ms, and a physical gate error of 10^-3. To instead break the encryption within one day, it would require 13 x 10^6 physical qubits. In other words: no time soon. Not even remotely soon. IBM's largest ever superconducting quantum computer is 127 physical qubits. Tags: academic papers, cryptography, IBM, quantum computing Posted on February 9, 2022 at 6:25 AM * 18 Comments Comments JL Sardinas * February 9, 2022 6:30 AM They may want to use hybrids in the meantime... and algorithms may continue evolving, so the time frame is still uncertain. Maybe not too close, but uncertain definitely Alan * February 9, 2022 7:00 AM So breaking ECC key in five years would only require 7000 qubits? There are currently ECC keys in use that are intended to be used for that length of time... I think the limiting issue tho might be the number of quantum logic gates required, not the number of qubits... NoSpamPlease * February 9, 2022 7:18 AM So why is there so much buzz around Post-Quantum Crypto? Can it really be that cryptographers ran out of things to do? null clam * February 9, 2022 7:38 AM This is all very well, but I'm waiting for the black hole computer. Recipe: 1. Warm up a left-over black hole (must not be more that 13.787+-0.020 billion years old) in the cosmic microwave. 2. Uh ... need some help here xyzzy://arxiv.org/pdf/quant-ph/9908043 Ted * February 9, 2022 9:13 AM 127 qubits is a ways off from 13,000,000 physical qubits, but IBM is on a roll. "IBM has said that it hopes to demonstrate a 400-qubit processor next year and to break the 1000-qubit barrier the following year with a chip called Condor." It looks like the US government is putting more money into QIS R&D. Its budget authority has almost doubled in the last 4 years. For FY 2022, it's estimated to be $877 million. What does the NSA think about this? "A: NSA does not know when or even if a quantum computer of sufficient size and power to exploit public key cryptography (a CRQC) will exist." That is from the NSA's 2021 FAQ on Quantum Computing and Post-Quantum Cryptography. At least we know it's on their radar. https://media.defense.gov/2021/Aug/04/2002821837/-1/-1/1/ Quantum_FAQs_20210804.PDF https://www.quantum.gov/wp-content/uploads/2021/12/ NQI-Annual-Report-FY2022.pdf Clive Robinson * February 9, 2022 9:43 AM @ Bruce, ALL, In other words: no time soon. Not even remotely soon. One of the major failings in security is under estimating the human ingenuity and the ability to repurpose ideas or technology. Whilst I agree it is unlikely for QC to become of practical use in security for breaking crypto within the next five generations, and with rapidly increasing uncertainty there after... It could actually be in as little as a year if some one found a way to repurpos an existing technology. And that is the real problem, not if and when QC ever happens, but how fast it can be implemented when it does. Because as humans we tend to put off doing what we should do today unless we see some emergancy in doing so. In the past I've provided reasonable estimates for the effective lifetime of devices that use crypto algorithms such as "smart-meters". Due to "resource issues" these have tended to use "Work-Lite Crypto". The problem is that once a system is inplace the cost of upgrading usually deters any systematic upgrading, only repair for random hardware failures gets done. I know that software I wrote fourty years ago is still in use in a production environment. But what about Crypto life times? Well DES is scarily still used in SIMs for mobile phones. DES was available in 1975 and in products in 1977. So fourt five years and counting... Chips in smart cards and car door locks are still using even weaker crypto some of which originated in the early 1980's. From a practical view point though, consider tge question "Why attack strong crypto such as ECC when you could get to a user interface with much less effort" Will QC enable such attacks, now that is an interesting question Z.Lozinski * February 9, 2022 9:45 AM @NoSpamPlease: So why is there so much buzz around Post-Quantum Crypto? We know that a quantum computer can efficiently factor integers (this is Shor's Algorithm), which means that most current public key systems deployed today (e.g. RSA) are vulnerable once you have quantum computer with enough qubits. IBM's quantum computer roadmap is public and a little thought tells you that scaling quantum computers (at least ones using superconducting transmon qubits) is now about microelectronics. See Moore's Law and Dennard scaling for how that works out over say 50+ years. The NSA is quite proud of the fact it spent 40 years on VENONA - the breaking of WW2 Soviet one-time pads. This was worth it because it enabled them to understand much of Soviet penetration of the Manhattan Project and other agents still in place in the US. Kim Philby recalls how he would regularly visit Meredith Gardner (the ASA /NSA cryptologist) to check on progress, knowing full well that the signals about HOMER referred to him. So, if you have information today that needs to be secure for 30+ years, you need to be thinking about cryptographic agility now. The ability to replace your current cyrptosystems with new cryptosystems and to securely re-encrypt the data. Post-Quantum cryotography is about both cryptosystem agility and new cryptographic algorithms that cannot be broken by a quantum computer. The US NIST is running a competition for these with the results due in 2022/23. So, we're thinking about post-quantum crypto now, because if we wait until quantum computers with 1 million qubits are in production, it will be too late. Z.Lozinski * February 9, 2022 10:10 AM @Clive, Consider that in 1965 we had three active elements (transistors or diodes) on an SLT module. And that in In 2022 we have 57 billion transistors in an Apple M1 Max. That's 20 billion-fold improvement in 57 years. And for extra fun we then put 100,000 of them in a data center and call it a cloud. So now we have 1E15 transistors in a single unit. From a security view-point, you cannot afford to bet against even a fraction of the same level of improvement in quantum computing technology. I have no idea if this will happen, but I can understand why it is a risk that must be managed. But as ever your final conclusion is right. Never mind the technology, what about the person using it? tim * February 9, 2022 11:24 AM From a security view-point, you cannot afford to bet against even a fraction of the same level of improvement in quantum computing technology. I have no idea if this will happen, but I can understand why it is a risk that must be managed. In other words we will cross that bridge when we come to it so lets stop the "panic" post that fills these forums. Most organizations can't even get asset inventories right. Seriously - this is a non issue for everyone for the foreseeable future. V * February 9, 2022 11:26 AM Does anyone have a handle on how many watts/qbit IBM is getting? Morgan Burnham * February 9, 2022 11:34 AM so still safe to say that Bitcoin is thermodynamically secured Clive Robinson * February 9, 2022 12:55 PM @ tim, Z.Lozinski, ALL, In other words we will cross that bridge when we come to it so lets stop the "panic"... ...Seriously - this is a non issue for everyone for the foreseeable future. The only proven way to reliably stop pabic is by solving a problem you are aware of in a sensibly timely manner. But as I said above, "Because as humans we tend to put off doing what we should do today unless we see some emergancy in doing so." So I guess you are just amplifing the point. Z.Lozinski * February 9, 2022 1:33 PM @V Does anyone have a handle on how many watts/qbit IBM is getting? All the information on the IBM Quantum systems that has been published is here: https://quantum-computing.ibm.com/lab/docs/iql/manage/systems/ configuration I have checked and watts/Qubit is not included. To be fair this is dominated by the characteristics of the dilution refrigerator, not the implementation of the qubits. Jp * February 9, 2022 1:44 PM And then even if ECC is cracked you would need first to crack sha256 for not reused Bitcoin address (Bitcoin address is a hash of the ECC public key. You first need to know the public key to be able to crack it) pup vas * February 9, 2022 2:13 PM Record-high seizure of $5bn in stolen Bitcoin https://www.bbc.com/news/world-us-canada-60310783 =Stolen Bitcoin worth more than $5bn (PS3.7bn) has been seized by the US Department of Justice - the largest ever confiscation of its kind. Officials also arrested and charged two people on Tuesday with attempting to launder the money, which amounts to nearly 120,000 Bitcoin. The funds, stolen by a hacker who breached a cryptocurrency exchange in 2016, were valued at about $71m. But, with the rise in Bitcoin's value, it is now valued at more than $5bn. A criminal complaint alleges Lichtenstein and his wife, Heather Morgan, 31, laundered about 25,000 of the stolen Bitcoin through various accounts over the past five years and used various methods to cover their tracks, from fake identities to converting their Bitcoin into other digital currencies. The asset seizure comes four months after the launch of a National Cryptocurrency Enforcement Team at the Justice Department.= Z.Lozinski * February 9, 2022 3:45 PM Further to the question "why now" about the interest in quantum safe cryptography. Have a look at the recent National Security Memorandum (NSM-8, Jan 19, 2022) "Memorandum on Improving the Cybersecurity of National Security, Department of Defense, and Intelligence Community Systems" issued by the White House. NSM-8 mandates US Government agencies develop plans to migrate to quantum secure encryption and submit them for approval. https://www.whitehouse.gov/briefing-room/presidential-actions/2022/01 /19/ memorandum-on-improving-the-cybersecurity-of-national-security-department-of-defense-and-intelligence-community-systems / Firms outside the US Government who are interested in the long term security of data-at-rest are looking seriously at what they need to do after the publication of NSM-8. SpaceLifeForm * February 9, 2022 3:58 PM @ Jp Wouldn't it be easier to exfiltrate the private key? Paper please. https://www.investopedia.com/news/bitcoin-safe-storage-cold-wallet/ Jp * February 9, 2022 4:43 PM @spaceLifeForm my point was that this is not enough because public key of bitcoin address are not public if no spend on it. This was to reply of people speaking about crypto/Bitcoin. And for what I know, sha256 is not easier to crack with quantum computing... Atom Feed Subscribe to comments on this entry Leave a comment Cancel reply Login Name [ ] Email [ ] URL: [ ] [ ] Remember personal info? Fill in the blank: the name of this blog is Schneier on ___________ (required): [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] Comments: [ ] [loader] Allowed HTML * * * *
    1. * 
       Markdown Extra syntax via
https://michelf.ca/projects/php-markdown/extra/

[Preview] [Edit]

[Submit] 

 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
D[                                             ] 

- Amy Zegart on Spycraft in the Internet Age

Sidebar photo of Bruce Schneier by Joe MacInnis.

About Bruce Schneier

[Bruce-Schn]

I am a public-interest technologist, working at the intersection of
security, technology, and people. I've been writing about security
issues on my blog since 2004, and in my monthly newsletter since
1998. I'm a fellow and lecturer at Harvard's Kennedy School, a board
member of EFF, and the Chief of Security Architecture at Inrupt, Inc.
This personal website expresses the opinions of none of those
organizations.

Related Entries

  * The EARN IT Act Is Back
  * Interview with the Head of the NSA's Research Directorate
  * Me on App Store Monopolies and Security
  * Tracking Secret German Organizations with Apple AirTags
  * China's Olympics App Is Horribly Insecure
  * San Francisco Police Illegally Spying on Protesters

Featured Essays

  * The Value of Encryption
  * Data Is a Toxic Asset, So Why Not Throw It Out?
  * How the NSA Threatens National Security
  * Terrorists May Use Google Earth, But Fear Is No Reason to Ban It
  * In Praise of Security Theater
  * Refuse to be Terrorized
  * The Eternal Value of Privacy
  * Terrorists Don't Do Movie Plots

More Essays

Blog Archives

  * Archive by Month
  * 100 Latest Comments

Blog Tags

  * 3d printers
  * 9/11
  * Aaron Swartz
  * academic
  * academic papers
  * accountability
  * ACLU
  * activism
  * Adobe
  * advanced persistent threats
  * adware
  * AES
  * Afghanistan
  * air marshals
  * air travel
  * airgaps
  * al Qaeda
  * alarms
  * algorithms
  * alibis
  * Amazon
  * Android
  * anonymity
  * Anonymous
  * antivirus
  * Apache
  * Apple
  * Applied Cryptography
  * artificial intelligence
  * assassinations

More Tags

Latest Book

We Have Root

More Books

Support Bloggers' Rights! Defend Privacy--Support Epic

  * Blog
  * Newsletter
  * Books
  * Essays
  * News
  * Talks
  * Academic
  * About Me