Dealing with the Y2Q problem
1. Executive summary
Rapidly advancing quantum technology poses what cryptography expert Bruce Schneier[1] calls a class break threat to today’s cryptography — breaking the confidentiality, integrity, and availability of systems across a connected world. Y2Q[2] is the date when advanced quantum computers are forecast to break the widely used public-key cryptography securing the web, mobile apps, and banking. The Y2Q name is drawn in reference to the Y2K[3] issue of the late 1990s, when the transition of dates to the year 2000 was expected to break critical infrastructure across the world.
Today’s public key cryptography is forecast to be broken by nation state actors by 2035[4]. Advances in quantum computing hardware and software algorithms such a Shor[5], Grover[6], and Artificial Intelligence (AI)[7] are coming together to threaten current cryptography. The time for the industry to act is now, given how long it can take to upgrade millions of systems. Some vendors such as Apple[8] (messaging) and Google[9] (browsing) have already rolled out communications upgrades — the area Booz Allen[10] sees as the earliest to be affected. Recommendations to deal with the Y2Q issue include inventorying systems to determine their cryptographic usage, a triage to the most important business areas to protect first and implementing a phased roadmap of hardening to quantum resistant tools under US Government guidelines [11] [12].
2. Why should we be worried
a. Exponential rate of improvement in quantum computing power
Moore’s law[13] predicted in 1965 that the computing power of classical computers would double approximately every two years. It has held true ever since. When the RSA (Rivest–Shamir–Adleman) public key cryptography standards that secure our websites, mobile apps, and financial tools were created a half century ago, it was believed that they would be unbreakable for the foreseeable future.
Today’s quantum computers are still in their infancy but once perfected, will be many orders of magnitude more powerful than any classical computer … and able to break RSA[14]. As a class, they are described as being “Noisy Intermediate-Scale Quantum (NISQ)” today. The “noisy” part of that name refers to their poor fault tolerance compared to reliable classical computers with designs perfected over decades. Quantum computers do not have the power to break any type of cryptography just yet. However, the rate of improvement in compute power from companies like Quantinuum has been 100 times every two years[15], an exponential rather than linear rate of improvement that is 50 times faster than Moore’s Law.
Microsoft in partnership with Quantinuum announced in April 2024 that they had improved their joint fault tolerance by 800x times[16]. That improvement signals the beginning of the end of the NISQ period and opens the door to even higher rates of improvement. All such improvements bring the Y2Q date closer. These predictions are based on publicly available and verifiable information. It is also possible that secret nation state programs may be further ahead. In WWII, Polish and English codebreakers working against Enigma military communications[17] had made huge advances in classical computing but did not reveal them until long after the war.
The analyst firm McKinsey[18] recorded over $2 billion of investments in quantum technology startups in 2022. In 2024, Global Data[19] recorded $4 billion in US government investments while China is investing $15 billion over 5-years. Quantum hardware is on a new “S-curve” of innovation that will outstrip classical computers in specific use cases like breaking cryptography. The question is not if this will happen rather when (see the timeline chapter).
b. Shor’s algorithm and threat to public or asymmetric keys
Peter Shor’s 1994 algorithm runs on quantum computers. Its ability to speed up certain mathematical operations threatens today’s widely used RSA (previously discussed) and EC (Elliptic Curve) Digital Signature Algorithm (DSA) public or asymmetrical key cryptography. Historically, it was easy for classical computers to multiply two numbers A and B to make C. It was much harder for them to factorize C back into it factors of A and B. Shor’s algorithm allows much faster factorization, which undermines the strength of both RSA and ECDSA cryptography. Both rely on the difficulty of factorization to maintain their security.
Public Key algorithms are popular since they are strong and easy to use. Their main feature is that keys that are split into public and private pairs that rely on that A and B makes C math. The private key locks data (and is kept secret) and its corresponding public key opens it (and can be publicly shared). The public keys are distributed at scale globally.
c. Grover’s algorithm and threat to symmetric keys
Lov Grover’s 1996 algorithm threatens today’s AES (Advanced Encryption Standard) symmetric keys and the SHA (Secure Hash Algorithm) 2 and 3 hashing functions. AES keys and SHA 2 and 3 hashing are not vulnerable to Shor’s algorithm, but their symmetrical nature, where the same key is used to lock and unlock data, makes them harder to use at scale than asymmetric or public keys. The difficulty of use comes from having to securely distribute the same key for each party.
Grover’s algorithm runs on quantum computers and allows symmetric keys and hashing algorithms to be cracked much more quickly than on classical computers. The speed increase is not as much as for Shor’s but again the question is not whether they will work but rather when compared to Grover’s.
d. AI and other innovation add to threat
The rate of improvement of quantum computing, Shor, and Grover are well known threats. Public key cryptography pioneer Whit Diffie in a 2024 paper[20] points out that nothing prevents other elements in computing innovation such as High-Performance Computing (HPC) and AI being combined with quantum techniques to further speed up cracking.
3. Who and what is at risk
a. Symmetric and asymmetric key lengths
Shor’s algorithm can crack symmetric keys exponentially faster than classical approaches. Grover’s algorithm can crack asymmetric keys only quadratically faster (squared power). So, symmetric keys are safer for longer than asymmetric keys but are not invulnerable.
Today, web sites are secured with RSA keys that are 2048 bits in length. That is the technology behind the “lock” symbol next to the web address. Seemingly simple solutions like using bigger key lengths with existing algorithms are not a panacea since a) mathematically that may still not add sufficient protection against a mature or more technically a Cryptologically Relevant Quantum Computer (CRQC), b) their use would break compatibility with existing systems, and c) the extra processing power might exceed the processing capability that is available on current platforms and negatively impact the user experience. In summary, both asymmetric and symmetric keys are vulnerable. Together they represent all classical algorithms, covering cryptography in everything from the web (RSA) to military communications (AES).
b. Public Key Infrastructure (PKI) and Pre-Shared Keys (PSK)
There two main schemes for distributing keys are the widely used PKI e.g. the web and less widely used PSK e.g. in military communications. Since PKI is built on asymmetric keys, it is the most vulnerable to Y2Q. PSK is built on symmetric keys, so is less vulnerable and further out than Y2Q for PKI. However, the world cannot wholly shift to PSK since distribution of keys becomes increasingly challenging at scale and might replace the issue of security of keys with that of the security of the distribution of keys.
4. What is the Y2Q timeline and when should we begin
a. Mosca’s theorem
According to Professor Mosca’s Theorem[21], organizations will experience Y2Q challenges if the formula X + Y > Z is satisfied. X is the amount of time that sensitive data must remain secure at a particular organization. Y is the time it takes for that organization to upgrade their cryptographic systems. Z is the time when quantum computers come online with enough power to break current cryptography (CRQC) and deliver Y2Q.
If Y2Q is expected to be 2035 per the US Government, that sets Z to 11 years from today. If sensitive data has a secure lifetime of say 10 years for X, that means implementation time Y is only 1 year! When the SHA-1 algorithm was found to be flawed and deprecated by NIST in 2011 to be replaced by SHA-2 or 3[22], larger organizations and vendors moved quickly but in 2024 there are still laggards using it. Every organization has a hierarchy of data types from no confidentiality to increasing levels of sensitive data lifetimes. In the US government, the hierarchy ranges from public and unclassified to classified and top secret. The default classified timeline is 25 years[23].
b. Store Now, Decrypt Later (SNDL) attacks
Nation State adversaries are not waiting until Y2Q to begin harvesting wireless and wired data. They are storing data now for later decryption. At any future Y2Q date, they will not only have access to that and future data but a decade or more of stored data.
c. What are crown jewels use cases
In 2022 the US Government in National Security Memos (NSM) 8[24] and 10[25] together with the Quantum Cybersecurity Bill[26] set the date for Y2Q in 2035. They specified a first step towards remediation of inventory and triage. Inventorying was to understand the scope of the problem for a particular organization and triage was to establish which were the “crown jewels” or most important use cases that had to be addressed first around SNDL concerns.
For Top Secret US Government systems, the concerns around digital signatures and Software Bills of Materials (SBOM) for secure supply chain are so acute that the deadline to move to quantum safe models was set at 2025– see Figure 1. The world’s first cyber weapon[27] that became publicly known in 2010 had relied on faked signatures as part of its attack chain, which explains the concern.
More generally, agencies and commercial organizations in critical infrastructure are working on pilots and prototypes to test upgrades ahead of formal standardization (see the certified PQC chapter) and scaling. The sixteen critical infrastructure sectors[28] are shown in Figure 2. Problems in any one of these areas illustrate the consequences of Y2Q. Just in the month of April 2024 nation state adversaries have been seen testing capabilities against water utilities in Texas[29].
· Chemical sector
· Commercial facilities sector
· Communications sector
· Critical manufacturing sector
· Dams sector
· Defense industrial base sector
· Emergency services sector
· Energy sector
· Financial services sector
· Food and agriculture sector
· Government facilities sector
· Healthcare and public health sector
· Information technology sector
· Nuclear reactors, materials, and waste sector
· Transportation systems sector
· Water and wastewater sector
Figure 2 — Cybersecurity and Infrastructure Agency Critical Sectors (CISA) in 2024
5. What preventative steps can be taken and when
a. Certified Post-Quantum Cryptography (PQC)
The National Institute of Standards (NIST) has developed so called post quantum cryptography (PQC) algorithms in a global competition[30] over the past several years that are not vulnerable to Shor’s or Grover’s algorithms. The intent is to replace or use them alongside classical cryptographic keys in a hybrid approach. The period of notice and comment is wrapping with three of the four candidate algorithms (Kyber, Dilithium, and Spincs+) slated to become Federal Information Processing Standards (FIPS) in Summer 2024 — see Figure 3. This is very similar process to the upgrade of SHA-1 mentioned in the timeline chapter. With standardization, organizations can begin to switch from PQC algorithms in testing to production usage following their prioritized roadmaps.
b. Key management
National Security Memo 10[31] (from the timeline chapter) recommends that the “testing of pre-standardized PQC in agency environments will help to ensure that PQC will work in practice before NIST completes PQC standards and commercial implementations.”
Many organizations are carrying out PQC testing in conjunction with their existing Hardware Security Module (HSM). HSM are specialized and hardened physical devices on which all major cryptographic operations such as encryption, decryption, authentication, and key management are centralized. Integrations made with an HSM flow throughout an organization. The use of an HSM is mandatory in banking. A typical military usage would be around a drone fleet’s command and control security given their criticality in modern warfare involving a nation state.
c. Quantum Random Number Generation (QRNG)
Both classical and post quantum cryptographic algorithms rely on strong entropy or randomness in the creation of keys. Where local sources of entropy are low or more commonly where misconfigured, key security can be compromised. This happened with the Cisco ASA network appliances[32] in 2023 whose keys became predictable. Attacks are technically not against the algorithm but against the key itself`
Historically, entropy was derived from weak sources such as software (pseudo randomness) or classical hardware like RNG (Random Number Generation) chips. Quantum effects began to be used in hardware Quantum RNG (QRNG) chips a decade ago[33]. Today actual quantum computers can both generate and more importantly prove[34] the quality of their entropy, allowing their results to be leveraged in software QRNG. QRNG are typically combined with HSM as part of hardening more generally focused on PQC algorithms.
d. Key distribution
There is considerable R&D going on in the area of Quantum Key Distribution (QKD) to resolve the issues of both PKI and PSK key distribution. However, the National Security Agency (NSA) has identified a laundry list of vulnerabilities[35] that limit its wider use.
6. Conclusion and recommendations
The risk especially to public key cryptography from Y2Q is clear and present. Mosca’s theorem and SNDL attacks mean that organizations must act now rather than take a wait and see approach. The bad news is that the cost and disruption of upgrading systems is likely to be higher than Gartner’s Y2K estimates[36] of $600 billion, especially for laggards. The good news is that not all cryptography will be equally affected immediately, organizations can inventory and triage systems and adopt a phased approach that upgrades the most critical systems first. New federally approved algorithms will be available this Summer and many technology vendors have been building in support for them to facilitate a switchover.
7. About the author
Simon is an alum of successful startups and Fortune 100 companies, an expert in the business of quantum, cybersecurity, and hardening critical infrastructure. He joined Quantinuum to help organizations drive mission and maintain personnel safety — mitigating the “threat” of quantum computers and realizing their “promise.” He is also a startup advisor, published author, and public speaker.
Previously, he successfully introduced a mobile security platform with startup CIS Mobile after working with Apple and Samsung to harden their platforms for US government needs. Prior to that, Simon was a co-founder of IoT cybersecurity startup RunSafe Security, VP Sales & Marketing at cybersecurity startup Kaprica Security, and re-started Thursby Software in mobile security.
Simon began his career in nuclear software engineering in Europe before taking executive roles at HP, Red Hat, and Capgemini. Past end customers include large government and commercial organizations. He is a CISSP security professional, with a BSc in Physics from the University of Manchester, MS in Law & Cybersecurity and MBA from the University of Maryland. He is continuing education in Purdue’s Doctor of Technology Program.
8. References
[1] Schneier, B. (2019). Click here to kill everybody: Security and survival in a hyper-connected world. W.W. Norton & Company.
[2] This is the large-scale threat known as Y2Q. World Economic Forum. (2023, October 19). https://www.weforum.org/agenda/2023/10/y2q-cybersecurity-cyberattack-quantum-computing/
[3] Halton, C. (n.d.). The truth about Y2K: What did and didn’t happen in the year 2000. Investopedia. https://www.investopedia.com/terms/y/y2k.asp
[4] Leibson, S. (2023, March 13). Tick tock: The Quantum Boogeyman is coming for your most sensitive data. EEJournal. https://www.eejournal.com/article/tick-tock-the-quantum-boogeyman-is-coming-for-your-most-sensitive-data/
[5] Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science.
https://doi.org/10.1109/sfcs.1994.365700
[6] Grover, L. K. (1996, November 19). A fast quantum mechanical algorithm for database search. arXiv.org. https://arxiv.org/abs/quant-ph/9605043
[7] Campbell, Dr. R., Diffie, Dr. W., & Robinson, C. (n.d.). Advancements in quantum computing and ai may impact PQC migration timelines. [v1] | Preprints.org.
https://www.preprints.org/manuscript/202402.1299/v1
[8] IMessage with PQ3: The New State of the art in quantum-secure messaging at scale. Blog — iMessage with PQ3: The new state of the art in quantum-secure messaging at scale — Apple Security Research. (n.d.). https://security.apple.com/blog/imessage-pq3/
[9] Crane, C. (2023, August 28). Google chrome adds support for a hybrid post-quantum cryptographic algorithm. Hashed Out by The SSL StoreTM. https://www.thesslstore.com/blog/google-chrome-adds-support-for-a-hybrid-post-quantum-cryptographic-algorithm/
[10] Townsend, B. (2022, January 3). Quantum computing is for tomorrow, but quantum-related risk is here today. SecurityWeek. https://www.securityweek.com/quantum-computing-tomorrow-quantum-related-risk-here-today/
[11] Computer Security Division, I. T. L. (n.d.). Post-quantum cryptography: CSRC. CSRC. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
[12] Sanzeri, S. (2023, January 27). Council post: What the quantum computing cybersecurity preparedness act means for national security. Forbes.
https://www.forbes.com/sites/forbestechcouncil/2023/01/25/what-the-quantum-computing-cybersecurity-preparedness-act-means-for-national-security/?sh=4be07a6a368a
[13] By. (n.d.). Moore’s law. Intel. https://www.intel.com/content/www/us/en/newsroom/resources/moores-law.html
[14] Leibson, S. (2023, March 13). Tick tock: The Quantum Boogeyman is coming for your most sensitive data. EEJournal. https://www.eejournal.com/article/tick-tock-the-quantum-boogeyman-is-coming-for-your-most-sensitive-data/
[15] Quantum Volume: The Power of Quantum Computers. Honeywell. (n.d.). https://www.honeywell.com/us/en/news/2020/03/quantum-volume-the-power-of-quantum-computers
[16] Microsoft, Quantinuum claim breakthrough in Quantum Computing | Reuters. (n.d.). https://www.reuters.com/technology/microsoft-quantinuum-claim-breakthrough-quantum-computing-2024-04-03/
[17] Baker, J. (2018, September 3). Forgotten heroes of the enigma story. Nature News. https://www.nature.com/articles/d41586-018-06149-y
[18] Bogobowicz, M., Gao, S., Masiowski, M., Mohr, N., Soller, H., Zemmel, R., & Zesko, M. (2023, April 24). Quantum Technology sees record investments, progress on talent gap. McKinsey & Company. https://www.mckinsey.com/capabilities/mckinsey-digital/our-insights/quantum-technology-sees-record-investments-progress-on-talent-gap
[19] China invests billions in quantum computing, race with us … (n.d.-a). https://www.sdxcentral.com/articles/analysis/china-invests-billions-in-quantum-computing-race-with-us-now-neck-and-neck/2024/02
[20] Campbell, Dr. R., Diffie, Dr. W., & Robinson, C. (n.d.). Advancements in quantum computing and ai may impact PQC migration timelines. [v1] | Preprints.org.
https://www.preprints.org/manuscript/202402.1299/v1
[21] What is the mosca-theorem?. Utimaco. (n.d.). https://utimaco.com/service/knowledge-base/post-quantum-cryptography/what-mosca-theorem
[22] Staff, D. R. (2023, October 17). NIST finally retires SHA-1, kind of. https://www.darkreading.com/cyber-risk/nist-finally-retires-sha-1
[23] National Archives and Records Administration. (n.d.). Executive order 13526- classified National Security Information. National Archives and Records Administration. https://obamawhitehouse.archives.gov/the-press-office/executive-order-classified-national-security-information
[24] The United States Government. (2022, January 19). Memorandum on improving the Cybersecurity of National Security, Department of Defense, and Intelligence Community Systems. The White House. 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/
[25] The United States Government. (2024, February 9). National security memorandum on Safeguards and accountability with respect to transferred defense articles and Defense Services. The White House. https://www.whitehouse.gov/briefing-room/presidential-actions/2024/02/08/national-security-memorandum-on-safeguards-and-accountability-with-respect-to-transferred-defense-articles-and-defense-services/
[26] H.R.7535–117th Congress (2021–2022): Quantum Computing Cybersecurity Preparedness Act | Congress.gov | Library of Congress. (n.d.-b). https://www.congress.gov/bill/117th-congress/house-bill/7535
[27] Countdown to Zero Day: Stuxnet and the launch of the world’s first Digital Weapon: Zetter, Kim: 9780770436193: Amazon.com: Books. (n.d.). https://www.amazon.com/Countdown-Zero-Day-Stuxnet-Digital/dp/0770436196
[28] Critical Infrastructure Sectors: CISA. Cybersecurity and Infrastructure Security Agency CISA. (n.d.). https://www.cisa.gov/topics/critical-infrastructure-security-and-resilience/critical-infrastructure-sectors
[29] Lyngaas, S. (2024a, April 17). Russia-linked hacking group suspected of carrying out cyberattack on Texas Water Facility, cybersecurity firm says | CNN politics. CNN. https://www.cnn.com/2024/04/17/politics/russia-hacking-group-suspected-texas-water-cyberattack/index.html
[30] Computer Security Division, I. T. L. (n.d.). Post-quantum cryptography: CSRC. CSRC. https://csrc.nist.gov/projects/post-quantum-cryptography
[31] The United States Government. (2024, February 9). National security memorandum on Safeguards and accountability with respect to transferred defense articles and Defense Services. The White House. https://www.whitehouse.gov/briefing-room/presidential-actions/2024/02/08/national-security-memorandum-on-safeguards-and-accountability-with-respect-to-transferred-defense-articles-and-defense-services/
[32] CVE-2023–20107. CVE. (n.d.). https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2023-20107
[33] BioSpace. (2015, August 3). Whitewood encryption systems introduces the entropy engine, the world’s most cost-effective, quantum-powered random number generator. https://www.biospace.com/article/releases/-b-whitewood-encryption-systems-b-introduces-the-entropy-engine-the-world-s-most-cost-effective-quantum-powered-random-number-generator-/
[34] Foreman, C., Wright, S., Edgington, A., Berta, M., & Curchod, F. J. (2023, March 30). Practical randomness amplification and privatization with implementations on Quantum Computers. Quantum. https://quantum-journal.org/papers/q-2023-03-30-969/
[35] Home. National Security Agency/Central Security Service > Cybersecurity > Quantum Key Distribution (QKD) and Quantum Cryptography QC. (n.d.). https://www.nsa.gov/Cybersecurity/Quantum-Key-Distribution-QKD-and-Quantum-Cryptography-QC/
[36] Union calendar no. 469 — congress.gov. (n.d.). https://www.congress.gov/105/crpt/hrpt827/CRPT-105hrpt827.pdf
