Staying Ahead of the Race – Quantum Computing and Cybersecurity

Cryptography is an integral part of a cybersecurity professional’s toolkit.

It is used for Confidentiality, Integrity, Non-repudiation and more. Cryptosystems are the cornerstone for securing communication, data and information systems globally and are deeply embedded in most technologies. Cryptography is integral to hordes of applications where people use it unknowingly, barely giving thought to underlying cryptography at work. The imminent arrival of quantum computers is poised to shake up the current state of cryptography.

Every emerging technology has two faces, one that revs up the potential for technical evolution propelling humanity into the future, the other a harbinger of novel security vulnerabilities and attacks inconceivable before. Quantum computing is no different in this regard and has breathed life into theoretical mathematics from the late nineties, making them potentially the most powerful codebreaking tools ever developed. In Quantum computing, a quantum bit (qubit) can hold multiple values simultaneously whereas a classic bit holds a single binary value of 0 or 1, theoretically enabling a single qubit to take part in multiple computations simultaneously. This makes quantum computers extremely adept at solving certain types of problems, that classical computers cannot. Quantum computers with the power to solve mathematics underlying classical cryptosystems are on their way.

A race for quantum supremacy between various players, industry, government and academia, to build the most capable quantum computer is underway. Physicists, computer scientists, engineers, mathematicians and geeks have a head start, working on quantum computing for well over two decades. In recent years it has become increasingly clear that cybersecurity professionals have an important role to play in addressing potential vulnerabilities in the development and implementation of this incredible technology.

The principle underpinning the effectiveness of cryptography is that the work effort, resources and time needed for cryptoanalysis is either infeasible with the technology available at the present time, or the time taken to defeat the applied cryptography is significantly larger than the meaningful useful lifespan of the encrypted information. This principle has been defeated before. The Turing Bombe in World War II defeated the German Enigma machines’ encryption scheme. 40-bit encryption was common in software released before 1999, especially those based on RC2 and RC4 algorithms. The 40-bit key cipher system approved for use in the 1990s was defeated by the end of the 20th century, when a single PC could search a 240 key space in a matter of hours, ushering in 128-bit encryption [1]. And thus, through the numerous ciphers and algorithms that have been deprecated and retired, over the years, new ones instated with larger key sizes and progressively harder mathematical problems underlying them. Today, we stand yet again, at a similar threshold of cryptographic evolution for popularly used crypto-schemes with the anticipated prowess of quantum computing capable of rendering them no longer secure.

Quantum computers are astonishing contraptions that stabilize sub-atomic particles called qubits that are fragile and can lose their data if disturbed. In quantum computing a qubit is the basic unit of quantum information and operations are conducted by manipulating its quantum mechanical properties. Quantum computers are maintained at zero degrees kelvin and isolated from disturbances through noise, temperature change, electrical fluctuations or vibrations. Therefore, they are neither small nor portable at this time.

In 1996 Grover’s algorithm, proved that quantum computers could implement search functions in OvN time, where N is the size of the function’s domain [2]. This essentially means that a symmetric key can be brute forced in square-root of the time it previously could. It is estimated that a quantum computer with 2953 qubits is able to brute force AES128 [3]. The proposed quick fix to build resistance against quantum attacks targeting symmetric cryptography is to double the key length. This mitigates speed up by square-root time from quantum attacks. This means that to have the same level of protection as AES256, a standard commonly used today, AES512 would need to be deployed. Keep in mind that where secret keys are not pre-shared securely, key exchange of symmetric key cryptography often leverages asymmetric public key cryptography.

In 1997 Peter Shor published a quantum algorithm that performs prime factorization of integers and solves discrete logarithm problems in polynomial time. Cryptographic algorithms such as RSA, ECC and Diffie-Hellman that depend on the inability of classical computers to complete such calculations are now broken by quantum computers. In fact, in 2001, a group in IBM demonstrated Shor’s algorithm on a 7-qubit factorizing the prime number 15 using nuclear magnetic resonance techniques to manipulate the qubits [4]. It is estimated that 2048-bit RSA requires 4096 qubits and 224 ECC requires 1300 to 1600 qubit quantum computers to break respectively [5]. Essentially both the technology and mathematics to break cryptography as we know it has been proven. The only missing element is the number of qubits in universal quantum computers available for operations today.

This brings us back to the racetracks where the community is watching with bated breath, the exciting race for the proclaimed arrival of the “Supreme” universal quantum computer. There are numerous companies such as IBM, Intel and Google [6], building and stabilizing the quirky qubits at zero degrees kelvin and error correction algorithms for consistent performance quantum computer. Rigetti has publicly announced a 128 Qubit Universal quantum computer for deployment in 2019 [7]. In a mere two years, the technology has developed from 3 qubit computers to 72 qubit computers (figure -1). D-wave and Fujitsu have 2048-qubit and 1024-qubit annealing quantum computers respectively [8], however they are special purpose computers intended to solve specialized problems [9]. Notably, quantum computers are not to be mistaken for faster computers, in fact, they are good at solving a completely different set of problems that classical computers are not good at, such as, optimization (e.g the travelling salesman problem), machine learning, biomedical simulations and financial services among others [10].

In response, the NIST 2016 report on post-quantum cryptography published the following (Table-1), impact of quantum computing on common cryptographic algorithms [11].

Table 1 [11]

Cryptographic Algorithm	Type	Purpose	Impact from large scale quantum computer
AES	Symmetric Key	Encryption	Larger key sizes needed
SHA-2, SHA-3	————–	Hash Functions	Larger output needed
RSA	Public Key	Signatures, Key establishment	No longer secure
ECDSA, ECDH (Elliptical Curve Cryptography)	Public Key	Signatures, Key Exchange	No longer secure
DSA (Finite Field Cryptography)	Public Key	Signatures, Key Exchange	No longer secure

The cryptosystems listed in Table-1 are pervasive in our environment today: and the post quantum crypto-stack includes: web browsers, certificates, Tor, Signal, imessaging, software updates, mobile phones connecting to cell towers, credit cards transactions, secure boot, code signing, secure password hashing, checksums, encrypted disks, file systems, databases, digital signatures, key exchange, protocols as TLS, IPSec, SSH S/MIME, DNSSec, and lower level modules as gnu multi-precision libraries (GMP), Number theory libraries (NTL), AES block ciphers, hash functions, random number generators, HSMS, TPMs and much more [12] [13].

NIST is currently working on analyzing, rigorously testing various candidates for post-quantum algorithms and expects to release draft standards between 2022 and 2024. NIST is concerned with the long-term viability and robustness of an algorithm, therefore its diligence is very thorough, and will among other parameters, evaluate an algorithms’ efficiency, confidence against cryptoanalysis, usability and interoperability before releasing standards [14].

As of 2016 the National Security Agency (NSA), in anticipation of the transition to quantum resistant algorithm has retired for use by organizations that run classified and unclassified national security systems (NSS) and vendors that build products used in the NSS the following: ECDH and ECDSA with NIST P-256, SHA-256, AES-128, RSA with 2048-bit keys, Diffie-Hellman with 2048-bit keys [15]. The NSA announcement of the adoption of the commercial national security algorithm suite (CNSA) has been issued with the intent to enable NSS developers and operators to plan, budget, design and build new cryptography into their systems [15]. The NSS has further advised that the following set of public cryptographic standards (Table-2) be used to protect the NSS until acceptable standards for quantum resistant cryptography become available and are approved for use:

                                                             Table 2 [15]

Algorithm	Usage
RSA 3072-bit or larger	Key Establishment, Digital Signature
Diffie-Hellman (DH) 3072-bit or larger	Key Establishment
ECDH with NIST P-384	Key Establishment
ECDSA with NIST P-384	Digital Signature
SHA-384	Integrity
AES-256	Confidentiality

This is an interim measure and in the longer term the NSA expects all its systems and suppliers to use standardized quantum resistant algorithms [15].

In the meantime, as of 2016, NIST has proposed a “hybrid mode” [12] and stated that “a focus on maintaining crypto-agility is imperative” [16]. A hybrid mode is a transition or migration step to post-quantum cryptography where such a mode combines a classical algorithm with a post-quantum one. Cryptographic agility or crypto-agility is the ability to easily make changes to cryptographic algorithms and protocols used in a system without having to rebuild the system [17].

Based on this information, there are several steps the community should take to further secure itself. In the past 10 years, our industry has been through several significant cryptographic updates: SHA-1, MD-5, RSA-1024 [18]. Some of these updates took as many as 10 years, and several retired protocols continue to lurk around in disparate software, systems and infrastructure. If history is any indicator of how effectively (or ineffectively) we handle change of cryptographic protocols, we can anticipate a challenge in updating fast enough to meet the quantum era.

Some experts speculate that there is close race between NIST’s post-quantum cryptographic standards expected in 2022 – 2024 and the development of a universal quantum computer that can break classical cryptography forecasted to arrive between 2023 – 2033. In fact, considering change management windows for cryptography and deeply embedded cryptosystems in our technical ecosystems, some analysts suggest that the race to secure our data and infrastructure is a challenging one. It has been reported, that hackers and intelligence agencies are actively harvesting encrypted data today, with the intent to decrypt in the future once a capable quantum computer arrives [19]. Information assets (such as customer contracts, intellectual property etc.), whose lifespan exceeds 5 to 10 years as of today, are at potential risk of exposure by advances in quantum computing, if not adequately protected.

Regardless of the exact time of arrival of the crypto-defeating quantum computer, our entire cryptographic algorithm ecosystem is inevitably coming up for one or several cryptographic updates imminently, only with shorter time windows in which to execute these changes than ever before in the past. In the time preceding standards announcement by the NIST on quantum-resistant cryptography, we have opportunities to proactively prepare ourselves in numerous ways.

Risk Assessment: Security is essentially about managing risks aligned with the business objectives of an organization through various security controls, where cryptography is one control, albeit a critical one. Risk assessment is the first step to understanding risks to the business. There are numerous risk assessment frameworks available. Select one that is suitable for your organization and industry for quantum risk assessment. The Global Risk Institute describes a six-phase quantum risk framework to assess, evaluate, implement and integrate with the organizations’ cyber risk assessment and management framework. [20]

Phase 1 – Identify and document information assets, and their current cryptographic protection
Phase 2 – Research the state of emerging quantum computers and quantum-safe cryptography.
Phase 3 – Identify threat actors, and estimate their time to access technology.
Phase 4 – Identify the lifetime of your assets, and the time required to transform the organization’s technical infrastructure to a quantum-safe state
Phase 5 – Determine quantum risk by calculating whether business assets will become vulnerable before the organization can move to protect them
Phase 6 – Identify and prioritize the activities required to maintain awareness and to migrate the organization’s technology to a quantum-safe state.

Hybrid schemes/Crypto-experimentation: There are numerous quantum safe algorithms available today that have never been broken, such as NTRU [21], NewHope, McEliece [22]among many others. Google has an experimental web browser Canary that uses the NewHope algorithm [22]. Cryptographers caution that post-quantum algorithms are under study. Cryptographers and cryptanalysts are learning about them, and they should not be positioned as post-quantum secure as yet [23]. However, experimenting with PQC, alongside classical cryptography, offers invaluable insight into the effort, implementation, interoperability and operational aspects of the new mathematics underlying the impending post-quantum cryptographic (PQC) suites.

Crypto-Agility: Crypto-agility or cryptographic agility, is the capacity for an information security system to adopt an alternative to the original encryption method or cryptographic primitive without significant change to system infrastructure [24]. Besides the looming quantum threat there are myriad of drivers for crypto-agility such as emergence of new cryptographic standards, new legislation such as GDPR, discovery of a new vulnerability in a cryptographic function that requires an update fix. Business needs where old legacy devices with weak cryptography needs to be managed through a prolonged retirement lifecycle. Exposure is significantly reduced if crypto-agility design principles are in place. Integrate crypto-agility as a core premise of the cryptography lifecycle management.

Crypto-agile abstraction essentially decouples the implementation of cryptographic suites from the application, solution or infrastructure itself. The algorithms are not hardcoded and systems are able to change cryptography dynamically or with a simple update. Usage of cryptography suites must be manageable separately from the solution and the cryptography must be portable across multiple devices without having to rebuild new systems [25]. Cryptographic change is constant and the slower an entity is to respond to adopt a cryptography update, the greater the vulnerability to a potential cyberattack.

The new attribute, crypto-agility has been added to the suite of elements under the umbrella of cryptographic life cycle management. All components of a cryptographic system such as keys, certificates, algorithms, ciphers are implemented, optimized and collectively managed to the desired security objective of the asset it is protecting. For all systems, solutions, software, firmware and infrastructure there needs to be an approach that assumes that the cryptographic algorithms will change during the course of its useful lifetime and have an inbuilt capability to seamlessly incorporate this cryptographic change or update. It makes sense to plan for crypto-agility as part of cryptographic life-cycle management and build products and solution with crypto-agile abstraction and architectures in mind to prepare for our collective quantum crypto-futures.

For new products, software, infrastructure and solutions being developed, ensure specifications that respect crypto-agile architectures and design principles. Use the latest cryptographic schemes approved and the most secure postures as publicized by the standards and regulatory bodies based on the industry in question. Consider scenarios that may require the solutions to be capable of doubling the key length, hash strings or similar crypto-applications via a simple configuration change. Architect products and infrastructure such that they are capable of running both classical and quantum secure algorithms in parallel, to support the previously mentioned “hybrid” approach to PQC.

Supply Chain: Integrate quantum safe and hybrid cryptographic criteria into your procurement pipeline. Ensure that the products, equipment and software that is purchased today is capable of supporting cryptographic changes in the near future. Include crypto-agility, crypto-agile abstraction, design principles and architectures as part of your requirement specifications to third party suppliers. Require your suppliers to architect solutions such that when NIST announces PQC standards their solutions can transition and support them without a rebuild or a repurchase. Include crypto-agility and PQC readiness criteria into your contracting language. Discuss the vendors’ consideration of quantum-safe algorithms and evaluate maturity of the vendors’ product roadmaps in this regard.

Data Life Cycle Management: For information assets ensure data classification policies are utilized effectively throughout the organization. If there are data assets that are known to be of critical value such as trade secrets, customer and employee PII, financial information and records, intellectual property and the like, that essentially has a life span into years where a quantum computer may exist, consider tagging them and applying quantum resistant cryptographic (or hybrid) discipline around its storage, transit and management throughout its lifecycle. Know where your crown jewels are, the current state of cryptographic protection applied and pre-emptively plan a strategy to manage the risks of the quantum cryptography era.

Inventory Applications that use Cryptography: Armed with the inventory of information assets that must be protected, knowing what applications, protocols, infrastructure interact with the data along with the cryptography in place will enable prepare for necessary algorithm swaps or changes in parameters that are integral to crypto-agility [26]. There are tools available in the market that enable this, such as Infosec Global’s Agilescan [27].

Industry Standards, Audits and Compliance: Most industries grapple with an alphabet soup of standards such as GDPR, PCI Compliance, HIPAA. Many of these standards require an array of specific security controls requiring auditability. Several standards require assurance that implemented cryptography is current and secure. One can anticipate that as PQC is standardized, industry standards will cascade and fold updated PQC requirements into their own standards. It is advisable to assess the impact of managing cryptographic updates for an ecosystem of technologies, in context to compliance and auditability.

Business Continuity Planning: While PQC readiness is certainly a better antidote in the face of a probabilistic zero-day attack from quantum computing, it is impossible to be a 100% prepared for a new technology with newly emerging quantum attack vectors. As with any novel threat, ensure business continuity plans concern themselves with the impacts from PQC. Business drivers and risk appetites of certain businesses may drive PQC strategy to be skewed more towards mitigation and remediation rather than prevention. Conducting table top exercises on PQC impacts as relates to business continuity planning and recovery would be valuable.

Incident Response Plan: Throughout history we have seen cryptography succumb to attacks in various ways, brute force, poor implementation, side channel attacks, mathematical developments among others. In the current climate of accelerated crypto-updates, it is recommended that the SOC be up to date on crypto-agile concepts and the vulnerabilities of classic cryptography to quantum attacks. Gartner suggests including cryptographic alternatives and algorithm swap-out procedures in incident response plans [26].

Quantum Products Market Awareness: The quantum computing related products and services marketplace is extremely active. Morgan-Stanley has forecasted a market potential of $5 to $10 billion annually over the next ten years [28], with a CAGR of 24.6% over 2018-2024 projected by Homeland Security Research [29]. There are new and innovative products and services becoming available, such as, cryptographic cipher scanning tools, quantum-proof digital certificates poised to remake the PKI industry, PQC ready hardware security modules to name a few. There may be solutions available that enable the PQC transition for your organization on certain fronts.

As discussed, cybersecurity professionals have a lot of work ahead in preparation for the entrance of quantum computing into the world of cryptography. While not typically quantum scientists, cybersecurity professionals are specialists in their own right and post quantum cybersecurity needs the attention of every cybersecurity professional, not in quantum time, but NOW. At this time preparation is our best defense against the future quantum attack on our information assets and infrastructure.

REFERENCES

1. R. Curley, Cryptography Cracking Codes, New York: Britannia Educational Publishing, 2013.
2. L. K. Grover, “A fast quantum mechanical algorithm for database search,” Symposium on the Theory of Computing (STOC), Murray Hill, 1996.
3. B. L. ,. M. R. ,. a. R. S. Markus Grassl, “Applying Grover’s algorithm to AES: quantum resource estimates,” arXiv:1512.04965v1 , 15 December 2015. [Online]. Available: https://arxiv.org/pdf/1512.04965v1.pdf. [Accessed 5 Nov 2018].
4. “IBM’s Test-Tube Quantum Computer Makes History – First Demonstration of Shor’s Historic Factoring Algorithm,” IBM, 19 Dec 2001. [Online]. Available: https://www-03.ibm.com/press/us/en/pressrelease/965.wss. [Accessed 5 Nov 2018].
5. C. Z. John Proos, “Shor’s discrete logarithm quantum algorithm for elliptic curves,” University of Waterloo, 22 Jan 2004. [Online]. Available: https://arxiv.org/pdf/quant-ph/0301141v2.pdf. [Accessed 5 Nov 2018].
6. Quantum Computing Report, “Quantum Computing Report,” 13 Oct 2018. [Online]. Available: https://quantumcomputingreport.com/scorecards/qubit-count/. [Accessed 5 Nov 2018].
7. C. Rigetti, “The Rigetti 128-qubit chip and what it means for quantum,” Rigetti, 8 August 2018. [Online]. Available: https://medium.com/rigetti/the-rigetti-128-qubit-chip-and-what-it-means-for-quantum-df757d1b71ea. [Accessed 5 Nov 2018].
8. P. Teich, “Google Joins the Quantum Race,” EE Times – Tirias Research, 3 Sep 2018. [Online]. Available: https://www.eetimes.com/author.asp?section_id=36&doc_id=1333058. [Accessed 5 Nov 2018].
9. D-wave, “Quantum Computing Applications,” D-wave, [Online]. Available: https://www.dwavesys.com/quantum-computing/applications. [Accessed 5 Nov 2018].
10. Gartner, “The CIO’s Guide to Quantum Computing,” Gartner, 29 Nov 2017. [Online]. Available: https://www.gartner.com/smarterwithgartner/the-cios-guide-to-quantum-computing/. [Accessed 5 Nov 2018].
11. NIST, “Report on Post-Quantum Cryptography,” April 2016. [Online]. Available: https://csrc.nist.gov/csrc/media/publications/nistir/8105/final/documents/nistir_8105_draft.pdf. [Accessed 5 Nov 2018].
12. D. Moody, “The Ship has Sailed, The NIST Post-Quantum Cryto “Competition”,” 2017. [Online]. Available: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/asiacrypt-2017-moody-pqc.pdf. [Accessed 5 Nov 2018].
13. M. W. e. al, “Post-Quantum Crypto for Dummies,” Wiley, Weinheim, 2018.
14. Post Quantum Cryptograhy Team – NIST, “A Quantum World and how NIST is preparing for future crypto,” March 2014. [Online]. Available: https://csrc.nist.gov/CSRC/media/Events/ISPAB-MARCH-2014-MEETING/documents/a_quantum_world_v1_ispab_march_2014.pdf. [Accessed 5 Nov 2018].
15. Information Assurance Directorate, “Cryptome.org,” Jan 2016. [Online]. Available: https://cryptome.org/2016/01/CNSA-Suite-and-Quantum-Computing-FAQ.pdf. [Accessed 5 Nov 2018].
16. NIST, “Report on Post-Quantum Cryptography – NISTIR 8105,” Computer Security Division, Applied and Computational Mathematics Division Information Technology Library, 2016.
17. IETF, “Guidelines for Cryptographic Algorithm Agility and Selecting Mandatory-to-Implement Algorithms,” Nov 2015. [Online]. Available: https://tools.ietf.org/html/rfc7696. [Accessed 5 Nov 2018].
18. K. Martin, “Waiting for quantum computing: Why encryption has nothing to worry about,” TechBeacon, 15 Aug 2018. [Online]. Available: https://techbeacon.com/waiting-quantum-computing-why-encryption-has-nothing-worry-about. [Accessed 5 Nov 2018].
19. M. Schwartz, “Post-Quantum Crypto: Don’t Do Anything,” Bank Info Security, 22 Feb 2017. [Online]. Available: https://www.bankinfosecurity.com/quantum-crypto-dont-do-anything-a-9737. [Accessed 5 Nov 2018].
20. J. M. Dr. Michele Mosca, “A Methodology for Quantum Risk Assessment,” Global Risk Institute, 5 Jan 2017. [Online]. Available: https://globalriskinstitute.org/publications/3423-2/. [Accessed 5 Nov 2018].
21. Onboard Security, “NTRU Post Quantum Cryptography,” Onboard Security, 2018. [Online]. Available: https://www.onboardsecurity.com/products/ntru-crypto. [Accessed 5 Nov 2018].
22. A. W. William Buchanan, “Will quantum computers be the end of public key encryption?,” Journal of Cyber Security Technology, vol. 1, no. 1, pp. 1-22, 2017.
23. B. Schneier, “Google’s Post-Quantum Cryptography,” 12 July 2016. [Online]. Available: https://www.schneier.com/blog/archives/2016/07/googles_post-qu.html. [Accessed 5 Nov 2018].
24. J. Henry, “What is CryptoAgility,” Cryptomathematic, Aug 2018. [Online]. Available: https://www.cryptomathic.com/news-events/blog/what-is-crypto-agility. [Accessed 5 Nov 2018].
25. I. G. Tomislav Nad, “Cryptography Lifecycle,” in PrimeKey Tech Days 2018, 2018.
26. D. M. Mark Horvath, “Better Safe Than Sorry: Preparing for Crypto-Agility,” Gartner, 12 April 2018. [Online]. Available: https://www.gartner.com/doc/3645384/better-safe-sorry-preparing-cryptoagility. [Accessed 10 Nov 2018].
27. Infosec Global, “Agilescan,” Infosec Global, 2018. [Online]. Available: https://www.infosecglobal.com/solutions/threat-detection/agilesca. [Accessed 31 Jan 2019].
28. P. Bajpai, “Quantum Computing: What It Is, And Who The Major Players Are,” www.Nasdaq.com, 26 March 2018. [Online]. Available: https://www.nasdaq.com/article/quantum-computing-what-it-is-and-who-the-major-players-are-cm939998. [Accessed 5 Nov 2018].
29. Homeland Security Research, “Quantum Computing Market & Technologies – 2018-2024,” Jan 2018. [Online]. Available: http://old.homelandsecurityresearch.com/Quantum+Computing+Market+and+Technologies. [Accessed 5 Nov 2018].