Quantum Computing and the Financial System: Spooky Action at a Distance?1
Mr. Michael Gorbanyov Majid Malaika Tahsin Saadi Sedik Michael Gorbanyov
The era of quantum computing is about to begin, with profound implications for the global economy and the financial system. Rapid development of quantum computing brings both benefits and risks. Quantum computers can revolutionize industries and fields that require significant computing power, including modeling financial markets, designing new effective medicines and vaccines, and empowering artificial intelligence, as well as creating a new and secure way of communication (quantum Internet). But they would also crack many of the current encryption algorithms and threaten financial stability by compromising the security of mobile banking, e-commerce, fintech, digital currencies, and Internet information exchange. While the work on quantum-safe encryption is still in progress, financial institutions should take steps now to prepare for the cryptographic transition, by assessing future and retroactive risks from quantum computers, taking an inventory of their cryptographic algorithms (especially public keys), and building cryptographic agility to improve the overall cybersecurity resilience.
/fileasset/fileasset/IMF_Seal_blue.png
IMF eLibrary
Abstract

The era of quantum computing is about to begin, with profound implications for the global economy and the financial system. Rapid development of quantum computing brings both benefits and risks. Quantum computers can revolutionize industries and fields that require significant computing power, including modeling financial markets, designing new effective medicines and vaccines, and empowering artificial intelligence, as well as creating a new and secure way of communication (quantum Internet). But they would also crack many of the current encryption algorithms and threaten financial stability by compromising the security of mobile banking, e-commerce, fintech, digital currencies, and Internet information exchange. While the work on quantum-safe encryption is still in progress, financial institutions should take steps now to prepare for the cryptographic transition, by assessing future and retroactive risks from quantum computers, taking an inventory of their cryptographic algorithms (especially public keys), and building cryptographic agility to improve the overall cybersecurity resilience.

“I cannot seriously believe in it [...] physics should represent a reality in time and space, free from spooky action at a distance.”

Albert Einstein 2

Annex I. Glossary of Technical Terms Used in the Paper

Cryptanalysis studies the encrypted secret message (ciphertext) to gain as much information as possible about the original message.

Cryptography is the science of transmitting secret information using public channels. A cryptologic system performs transformations on a message, the plaintext, and uses a key to render it unintelligible, producing a new version of the message, the ciphertext. To reverse the process, the system performs inverse transformations to recover the plaintext, decrypting the ciphertext (Dooley, 2018).

Cryptographic agility (or crypto agility) is the property that permits changing or upgrading cryptographic algorithms or parameters. While not specific to quantum computing, crypto agility would make defense against quantum computers easier by allowing substitution of today’s quantum-vulnerable public-key algorithms with quantum-resistant algorithms.

HTTPS (Hypertext Transfer Protocol Secure) is a Web communication protocol used between network devices for secure communication. It encrypts both the information a user sends to a website, and the information that the website sends back—for example, credit card information, bank statements, and e-mail.

Quantum annealing is a process for finding the global minimum of a given objective function over a given set of candidate solutions (candidate states), by a process using quantum fluctuations. It finds an absolute minimum size/length/cost/distance from within a possibly very large, but nonetheless finite set of possible solutions using quantum fluctuation-based computation instead of classical computation.

Quantum computing is the use of a non-classical model of computation. Whereas traditional models of computing such as the Turing machine or Lambda calculus rely on classical representations of computational memory, a quantum computation could transform the memory into a quantum superposition of possible classical states. A quantum computer is a device that could perform such computation.

Quantum entanglement is a label for the observed physical phenomenon that occurs when a pair or group of particles is generated, interact, or share spatial proximity in a way such that the quantum state of each particle of the pair or group cannot be described independently of the state of the others, even when the particles are separated by a large distance.

Quantum gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.

Quantum key distribution (QKD) is a secure communication method that implements a cryptographic protocol involving components of quantum mechanics. It enables two parties to produce a shared random secret key known only to them, which can then be used to encrypt and decrypt messages.

Quantum mechanics (also known as quantum physics, quantum theory, the wave mechanical model, or matrix mechanics) is a fundamental theory in physics which describes nature at the smallest scales, including atomic and subatomic.

Quantum superposition is a fundamental principle of quantum mechanics, where a system is in more than one state at a time. It states that, much like waves in classical physics, any two (or more) quantum states can be added together (“superposed”) and the result will be another valid quantum state; and conversely, that every quantum state can be represented as a sum of two or more other distinct states.

Quantum “supremacy” is demonstrating that a programmable quantum device can solve a problem that classical computers practically cannot (irrespective of the usefulness of the problem). By comparison, the weaker quantum advantage is demonstrating that a quantum device can solve a problem faster than classical computers. Using the term “supremacy” has been controversial, and quantum advantage is now often used for both descriptions.16

Qubit or quantum bit is the basic unit of quantum information. It is the quantum version of the classical binary bit. A qubit is a two-state (or two-level) quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics. It allows the qubit to be in a coherent superposition of both states/levels simultaneously, a property which is fundamental to quantum mechanics and quantum computing.

Symmetric key is an approach in cryptography when the same key must be used to either decrypt or encrypt a message. Asymmetric cryptography uses a pair of related keys, when one is used to encrypt a payload and the other to decrypt it. In public-key cryptography, users publish one of the keys, the public key, and keep the other secret, the private key. Then public key is used to encrypt the message and the private key is needed to decrypt it.

Annex II. A Brief History of Encryption, Cryptoanalysis and Digital Computers

Encryption and Cryptoanalysis

Since ancient times, cryptography has been a race between those trying to keep secrets and adversaries trying to uncover them. The earliest examples of transposition ciphers go back to at least 485 B.C., when the Greek soldiers would wrap a strip of papyrus around a staff, a scytale, write a message down its length, and send off the papyrus. The receivers could unscramble messages by wrapping them around another scytale of the same thickness. In this case, the staff’s shape represented the encryption key. The first known historical record of substitution cipher is from Roman Empire: Emperor Julius Caesar is believed to send encrypted messages to the orator Cicero replacing each letter by its third next down the alphabet. The Caesar cipher was broken as early as the 7th century by Arab cryptographers, who documented the techniques of cryptoanalysis, the science of undoing ciphers (Singh, 1999). In “A Manuscript on Deciphering Cryptographic Messages”, the philosopher al-Kindl observed that every language has a characteristic frequency of letters and sequences and that by capturing them using sample texts of that language, the cryptanalyst might decipher any message.

Simple substitutions became obsolete in the 1700s because of the proliferation of Black Chambers—offices kept by European nations for breaking ciphers and gathering intelligence. As Black Chambers industrialized cryptoanalysis, cryptographers were forced to adopt more elaborated substitutions by turning to polyalphabetic methods. Instead of referring to a single alphabet for encryption, cryptographers would switch between two alphabets for choosing replacement symbols. The Vigenère cipher, believed to be the first polyalphabetic method and also called Le Chiffre Indéchiffrable, was first described in 1553 and remained popular until it was broken in the 19th century.

World War I intensified the need for secrecy. The radio had brought new capabilities to the field, such as the coordination of troops at a long distance. However, open waves also allowed enemies to listen to communications. Each nation used its own encryption methods. Some, like the Playfair cipher used by the British, remained unbroken during the war; others, like the German ADFGVX, were broken. In the period following the World War I, machines became the logical solution for the increase in the volume of material to decrypt. Several mechanical cryptographic devices were invented in the period preceding World War II, such as the M-94 cipher device used by the US military; the C-36 by the French Army; and the Enigma by the German Army (Dooley, 2018). Also, several devices were invented to break their encryption. To break Enigma, Alan Turing—one of the inventors of the digital computer—created Bombes for the British secret operation center. Colossus, the first programmable computer based on Turing’s design, enabled the British to break the Lorenz cipher, which protected communications from the German high command. The US navy built fully automatic analog machines to break the cipher from Japan’s Purple device.

After World War II, digital computers dominated cryptography. Whereas mechanical devices are subject to physical limitations, computers operate at a much higher speed and scramble numbers, not letters, giving access to a large set of new operations. At the beginning of the 1960s, the transistor replaced the vacuum tube in digital circuits for computers and, at the end of that decade, the Internet was invented, kick-starting the current digital age. By the early 1970s, computers became available for business customers, which demanded secrecy capabilities from vendors. As regular citizens became computer users, cryptography became necessary, for instance, to enable credit card transactions or transmission of personal information through public networks. A plethora of new cryptographic schemes appeared, leading the American National Bureau of Standards to intervene in 1973 and open a public competition to choose a cryptographic standard for the United States. IBM’s Lucifer cipher, renamed Data Encryption Standard (DES), was elected as America’s official standard in 1977. After DES was broken in a public competition in 1997, it was replaced as standard by Triple-DES in 1999, and retired when NIST adopted Advanced Encryption Standard (AES) in the early 2000s.

Until mid-1970s, all cryptographic methods used symmetric keys: the same key must be used to either decrypt or encrypt a message. Thus, to use cryptography, senders and receivers had to share keys in advance, a complicated matter of logistics. Whitfield Diffie, Martin Hellman, and Ralph Merkle solved the problem in 1976. The Diffie-Hellman key exchange allowed two parties to agree on a secret key using a public channel. The trio effectively created asymmetric cryptography, whereby operations are associated with a pair of related keys: when one is used to encrypt a payload, the other decrypts it and vice versa. Two years later, Rivest, Shamir and Adleman extended the concept with public-key cryptograp hy, whereby users publish one of the keys, the public key, and keep the other secret, the private key. Asymmetric methods enabled new applications. For instance, people may claim their identity by showing a plaintext message and the cipher produced by their private key, which could be verified by decrypting the cipher using their public key. Asymmetric cryptography (including RSA), also known as public-key cryptography, is widely used over the Internet, including by the financial system, for key exchanges, digital signatures, non-repudiation and authentication. Public and private keys also underpin digital currencies and blockchain technologies.

Asymmetric or public-key cryptography is the most vulnerable to quantum computing. Potential advantages of quantum computers became apparent in the early 1980s, when Richard Feynman pointed out essential difficulties in simulating quantum mechanical systems on classical computers, and suggested that building computers based on the principles of quantum mechanics would allow us to avoid those difficulties (Nielsen, 2010). The idea was refined throughout the 1980s. In 1994, Peter Shor published an algorithm that would allow one to perform prime factorization much faster when using quantum properties. As prime numbers are used at the core of most asymmetrical cryptography methods, Shor’s algorithm used on quantum computers might render most Internet security invalid.

While quantum computing poses a threat to Internet security, quantum mechanics can also provide unbreakable cryptography. In the 1980s, researchers from IBM proposed a novel way to leverage photon polarization to perform key distribution. By using the laws of physics, Quantum Key Distribution (QKD) can become impenetrable because eavesdroppers cannot intercept communications without interfering with them. Such experimental systems have been implemented since the 1990s, but they are very far from commercial use.

Digital Computers

The origin of classical computers may be traced to 17th century France. In the small town of Clermont-Ferrand, Blaise Pascal built the first machine that enabled humanity to manipulate numbers by mechanically performing the four basic arithmetic operations. Human ability to do math was enhanced again in 1822 by the English polymath Charles Babbage’s Difference Engine. It could tabulate polynomial functions, which enabled the mechanical approximation of complex calculations such as logarithmic or trigonometric functions. Babbage also designed a general-purpose computer, the Analytical Engine. However, the project was terminated due to engineering and funding issues, and a working engine was never built in Babbage’s lifetime. The next notable machines in history were differential analyzers, analog computers that use wheel-and -disc mechanisms to perform integration of differential equations. The first differential analyzer built at MIT by Vannevar Bush in 1931 played a particularly important role in history for inspiring one of Bush’s graduate students, Claude Shannon. In 1938, he invented digital circuits for his master thesis (Shannon, 1938), proving that complex mathematical operations may be performed by running electricity through specific configurations of electronic components.

Shannon’s work was complemented by Alan Turing’s doctoral thesis. It came as an answer to the challenge produced by David Hilbert and Sir Bertrand Russel in the previous decade, the Entscheidungsproblem, or the halting problem: mathematicians should search for an algorithm to prove whether any statement is true in a system. The Turing Machine was an imaginary device composed of a mechanism that moves an infinite tape back and forth, writes symbols to it, and reads recorded symbols. The Church-Turing thesis then states that this device can compute any function on natural numbers as long as there is an effective method of obtaining its value. And, conversely, that such a method exists only if the device can compute that function.

Thus, engineering met mathematics: by the time Claude Shannon invented digital circuits, Turing had just designed the mathematical blueprint of a general-purpose computer. The resulting circuitry, Turing-complete digital computers, were capable of computing every function the imaginary machine can compute. While the Colossus, a war secret built by British intelligence to break Hitler’s communications, was the first in history, modern computers are based on the architecture designed within a team lead by John Von Neumann, first used in 1949’s EDVAC (Electronic Discrete Variable Automatic Computer). Contemporary digital devices are Turing-complete devices generally composed of processing units (e.g., CPU), storage devices (e.g., RAM/ROM and disk drives), and input and output mechanisms (e.g., keyboard and video). Desktop computers and smartphones follow this same design.

Once the design was invented, engineering advanced enormously in speeding up each of its components. For instance, vacuum tubes were prominent components of CPUs in early machines, needed for their singular capacity to control the direction of the flow of electrons through its terminals. However, tubes presented several challenges related to durability and reliability. They were replaced by transistors invented in the 1940s, which in turn were replaced by integrated circuits throughout the 1960s. Since then, performance and size of digital computers have been dictated by the technology of fabrication of integrated circuits. Since the 1960s such technologies have allowed us to double the number of components in each single integrated circuit every 18 months, as foreseen by Intel’s Gordon Moore in 1965—the so-called Moore’s law. Such advance, for instance, is the reason we were able to cram all computing power used in the Apollo 11 lunar landing capsule in 1969 into a single device by early 2010s. Similar leaps occurred for other components, spawning things like paper-thin foldable displays, or pinhead-sized devices that can store entire encyclopedias.

However, since such machines are Turing machines at its core, they are also bound by Turing machine’s limitations. One of such is their inability to tackle certain mathematical problems, the so-called NP-Hard problems. The most infamous of them is the Traveling Sales agent problem—calculating the shortest route through a series of cities and visiting each exactly once. Digital computers can calculate solutions for small setups, roughly by comparing all possible paths to each other. As problem size grows, mathematicians invented heuristic algorithms for finding reasonable solutions without going through all possibilities, but there is no certainty that the optimal path will be found.

As every NP-Hard problem is equivalent to the traveling sales agent, unlocking its solution would set in motion a whole new universe of possibilities, for many optimizations. This is the key held by quantum computers.

Annex III. Modern Cryptographic Algorithms and Their Vulnerabilities to Current Technologies

Today’s cryptography is based on three main types of algorithms: symmetric keys, asymmetric (public) keys and algorithmic hash functions, or hashing. Appendix IV lists the current and past main algorithms.

AES algorithm is currently the accepted standard for symmetric-key encryption. NIST selected it in 2001 to replace the former standard (Triple-DES). Although multiple publications introduced new cryptanalysis schemes attempting to undermine AES, the cryptographic community proved them ineffective. For example, Biryukov and others (2010) outlined an effective attack against specific variations of AES, which reduces the encryption strength. However, such attacks were deemed impractical and dismissed as a non-threat to AES encryption algorithms.

The RSA algorithm, a popular standard for asymmetric (public-key) encryption, is widely used to protect confidentiality and digital signature. The RSA algorithm has been resilient to cryptanalysis techniques since its publication in 1977, despite several attempts to challenge its strength. Earlier it was suggested that some knowledge of the plaintext message, under specific conditions, could weaken the encryption (Durfee, 2002). However, RSA algorithms continue to be resilient. Although some schemes may be used to reduce time and memory required to break public-key encryption, so far it has been proven that adequate key sizes and best practices make public-key cryptography resilient to classical computer attacks. It would take billions of years for a digital computer to break the current standard RSA 2,048-bit key (CISA, 2019).

Algorithmic hash functions were temporarily impacted by cryptanalysis, but recent progress restored their effectiveness. In 2005, the mathematician Lenstra demonstrated a hash-collision attack 17 against one of the most used hashing functions named MD5 (Lenstra et. al, 2005). Other researchers later demonstrated that a decent desktop computer equipped with a cheap graphics processor (GPU) could find a hash-collision in less than a minute. MD5 algorithm was officially retired by NIST in 2011. However, it is still widely used despite its known weaknesses, demonstrating the long-lasting issue with replacing legacy systems. NIST ran a competition to create the next standard for the algorithmic hash function named SHA-3 to overcome the cryptanalysis advancement undermining MD5 and the earlier versions of the SHA algorithms. While there are some possible weaknesses,18 SHA-3 was selected in 2015 and became the approved standard (Morawiecki et. al, 2014). Furthermore, almost any cryptographic algorithm can be strengthened by increasing its key sizes, but that would require more processing power and thus increase the costs of running the algorithm, often making it prohibitively expensive.

Beyond the encryption algorithm itself, a different class of attacks studies the exogenous systems. Sid e-channel attacks target the software, firmware, and hardware used to implement the encryption algorithm. Software and hardware vulnerabilities are usually easier to find and exploit compared to breaking the underlying mathematical techniques of the encryption algorithm. Vulnerabilities, or bugs, are the result of implementation mistakes during the development phases. However, some vulnerabilities may be the result of misuse or misconfiguration of the cryptographic libraries. The Heartbleed vulnerability (CMU, 2014) was a devastating example of a vulnerability discovered in OpenSSL, a widely used cryptographic library to secure network communication. (Lazar et. al., 2014) reported that 17 percent of the vulnerabilities in cryptographic libraries published by CVE19 between 2011 and 2014 were mistakes made during the development phases while the remaining 83 percent were related to misuse or misconfiguration by the hosting applications.

Annex IV. Main Cryptographic Algorithms

Symmetric Algorithms Description Cryptanalysis State 1 Enigma The Enigma was an encryption machine built by the Nazi Germany to encrypt/decrypt messages during World War II. The Enigma’s encryption was broken in 1932 by the Polish Cipher Bureau with the assistance of the French and British allies. The Enigma had several poorly designed procedures that made reverse-engineering possible. The British used the Bombe machine to assist with breaking the encrypted messages by crunching the permutations (Tang et. al, 2018). 2 DES Data Encryption Standard was develop ed in 1970s by IBM. A version of it was officially published as U.S. federal standard in 1977. DES key size was 56 bits. DES was cracked in 1998 by the Electronic Frontier Foundation by building a machine named the EFF DES cracker and brute-forcing the DES key where it took the machine 3 days to find the encryption key (EFF, 1999). 3 Triple-DES Triple Data Encryption Standard (Triple DES) or TDEA (Triple Data Encryption Algorithm) was introduced in 1995 due to the growing concern of DES’s strength to withstand brute-force attacks. Trip le-DES is still approved by the US government to protect sensitive unclassified data but under certain conditions (using three distinctive keys with certain key length). New cryptanalysis schemes such as meet-in- the-middle attack proved effective in reducing Triple-DES key strength, deeming some variation of the algorithm insecure. NIST is deprecating Triple-DES by the end of 2023 (NIST , 2019). 4 AES Advanced Encryption Standard was selected in the 1997 NIST program to develop a DES replacement. AES was introduced in 2001 by NIST and had key sizes of 128, 192, and 256 bits with 10, 12, and 14 rounds respectively. In the early 2000s, some cryptanalysts proposed ways to break the standard, but the cryptography community proved them ineffective. In 2009 a new side-channel attack was introduced reducing the AES key strength slightly. Biryukov et al. (2010) presented an effective attack to AES 192 and 256 bit keys reducing their strengths to 176 and 22.9 bit keys respectively. 5 Twofish One of the five AES finalists in the 1997 NIST program to develop a replacement to DES. While having a similar structure as DES, Twofish has been demonstrated to be efficient with memory usage and speed of encrypting/decrypting messages compared with other symmetric algorithms. Moriai, et al. (1999) presented a truncated differential cryptanalysis of the block cipher in Twofish reducing the number of rounds to 5 from a random permutation requiring a known plaintext. The same year Ferguson (1999) presented an impossible differentials attack breaking 6 rounds of the 256 bit key version using 2 256 steps which is faster than an exhaustive search.

Symmetric Algorithms Description Cryptanalysis State 1 Enigma The Enigma was an encryption machine built by the Nazi Germany to encrypt/decrypt messages during World War II. The Enigma’s encryption was broken in 1932 by the Polish Cipher Bureau with the assistance of the French and British allies. The Enigma had several poorly designed procedures that made reverse-engineering possible. The British used the Bombe machine to assist with breaking the encrypted messages by crunching the permutations (Tang et. al, 2018). 2 DES Data Encryption Standard was develop ed in 1970s by IBM. A version of it was officially published as U.S. federal standard in 1977. DES key size was 56 bits. DES was cracked in 1998 by the Electronic Frontier Foundation by building a machine named the EFF DES cracker and brute-forcing the DES key where it took the machine 3 days to find the encryption key (EFF, 1999). 3 Triple-DES Triple Data Encryption Standard (Triple DES) or TDEA (Triple Data Encryption Algorithm) was introduced in 1995 due to the growing concern of DES’s strength to withstand brute-force attacks. Trip le-DES is still approved by the US government to protect sensitive unclassified data but under certain conditions (using three distinctive keys with certain key length). New cryptanalysis schemes such as meet-in- the-middle attack proved effective in reducing Triple-DES key strength, deeming some variation of the algorithm insecure. NIST is deprecating Triple-DES by the end of 2023 (NIST , 2019). 4 AES Advanced Encryption Standard was selected in the 1997 NIST program to develop a DES replacement. AES was introduced in 2001 by NIST and had key sizes of 128, 192, and 256 bits with 10, 12, and 14 rounds respectively. In the early 2000s, some cryptanalysts proposed ways to break the standard, but the cryptography community proved them ineffective. In 2009 a new side-channel attack was introduced reducing the AES key strength slightly. Biryukov et al. (2010) presented an effective attack to AES 192 and 256 bit keys reducing their strengths to 176 and 22.9 bit keys respectively. 5 Twofish One of the five AES finalists in the 1997 NIST program to develop a replacement to DES. While having a similar structure as DES, Twofish has been demonstrated to be efficient with memory usage and speed of encrypting/decrypting messages compared with other symmetric algorithms. Moriai, et al. (1999) presented a truncated differential cryptanalysis of the block cipher in Twofish reducing the number of rounds to 5 from a random permutation requiring a known plaintext. The same year Ferguson (1999) presented an impossible differentials attack breaking 6 rounds of the 256 bit key version using 2 256 steps which is faster than an exhaustive search.

Asymmetric Algorithms Description Cryptanalysis State 1 Diffie-Hellman Diffie-Hellman is one of the first public-key exchange methods. Named after Whitfield Diffie and Martin Hellman who published it, this algorithm was considered a breakthrough in cryptography as it enabled parties to exchange secure messages over an untrusted communication channel (Diffie et. al, 1976). Diffie-Hellman key exchange is known to be susceptible to man-in-the-middle attacks. Newer variations of Diffie-Hellman have addressed this issue. However, Heninger (2015) discusses a method to perform precomputations for a prime number that can weaken the standard and make it less secure than widely believed. 2 EIGamal ElGamal is an asymmetric key encryption based on Discrete Logarithm (El Gamal, 1985) an the Diffie- Hellman key exchange. ElGamal is widely used in the Pretty Good Privacy (PGP) email encryption system and GNU Privacy Guard (GPG), among others. Cryptanalysis approaches against ElGamal were introduced in Allen (2008). However, the authors admit that these attacks are effective against the algorithm in certain length and key selection conditions and can be avoided by configuring the cryptosystems. 3 Rivest-Shamir-Adleman (RSA) Developed and published by Rivest–Shamir– Adleman in 1977, this algorithm stems from the difficulty of factoring large integers that are the product of two large prime numbers. RSA is widely used for key establishment as well as generating and verifying digital signatures. Initially, proposed attacks were for scenarios where the same plaintext is used with different public keys (different recipient) with access to the ciphertext. Johan Håstad found an improvement of the attack where the plaintext doesn’t have to be the same, but with linear relationship among the plaintext messages. Don Coppersmith later improved this attack to gain some efficiencies (Durfee, 2002). However, proper length selection and following best practices confirms RSA’s strong security. 4 Elliptic Curve Digital Signature Algorithm (ECDSA) ECDSA requires smaller encryption keys compared to other asymmetric encryption algorithms. In addition, the execution time of ECDSA to encrypt/decrypt messages is faster than other asymmetric keys, and this algorithm requires less storage space and transmission bandwidth. Proposed schemes to reduce the strength of ECDSA include Pohlig-Hellman algorithm, Pollard’s Rho and the most effective Parallelized Pollard’s Rho algorithm. However, best practices in randomization and key selection would deem these algorithms ineffective (Johnson et. al, 2001). 5 Super-singular Isogeny Key Exchange (SIDH) In efforts to develop a quantum-safe asymmetric (public-key) cryptographic algorithm, SIDH was developed based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. It is motivated by the development of a subexponential-time quantum algorithm for constructing isogenies between elliptic curves (De Feo et. al., 2011). Galbraith et al. (2016) state that certain attacks against SIDH—such as side-channel and fault attacks—may reduce the key strength. The authors believe that the industry will see more literature and research in the cryptanalyses of SIDH in the near future as it becomes more popular and widely adopted.

Asymmetric Algorithms Description Cryptanalysis State 1 Diffie-Hellman Diffie-Hellman is one of the first public-key exchange methods. Named after Whitfield Diffie and Martin Hellman who published it, this algorithm was considered a breakthrough in cryptography as it enabled parties to exchange secure messages over an untrusted communication channel (Diffie et. al, 1976). Diffie-Hellman key exchange is known to be susceptible to man-in-the-middle attacks. Newer variations of Diffie-Hellman have addressed this issue. However, Heninger (2015) discusses a method to perform precomputations for a prime number that can weaken the standard and make it less secure than widely believed. 2 EIGamal ElGamal is an asymmetric key encryption based on Discrete Logarithm (El Gamal, 1985) an the Diffie- Hellman key exchange. ElGamal is widely used in the Pretty Good Privacy (PGP) email encryption system and GNU Privacy Guard (GPG), among others. Cryptanalysis approaches against ElGamal were introduced in Allen (2008). However, the authors admit that these attacks are effective against the algorithm in certain length and key selection conditions and can be avoided by configuring the cryptosystems. 3 Rivest-Shamir-Adleman (RSA) Developed and published by Rivest–Shamir– Adleman in 1977, this algorithm stems from the difficulty of factoring large integers that are the product of two large prime numbers. RSA is widely used for key establishment as well as generating and verifying digital signatures. Initially, proposed attacks were for scenarios where the same plaintext is used with different public keys (different recipient) with access to the ciphertext. Johan Håstad found an improvement of the attack where the plaintext doesn’t have to be the same, but with linear relationship among the plaintext messages. Don Coppersmith later improved this attack to gain some efficiencies (Durfee, 2002). However, proper length selection and following best practices confirms RSA’s strong security. 4 Elliptic Curve Digital Signature Algorithm (ECDSA) ECDSA requires smaller encryption keys compared to other asymmetric encryption algorithms. In addition, the execution time of ECDSA to encrypt/decrypt messages is faster than other asymmetric keys, and this algorithm requires less storage space and transmission bandwidth. Proposed schemes to reduce the strength of ECDSA include Pohlig-Hellman algorithm, Pollard’s Rho and the most effective Parallelized Pollard’s Rho algorithm. However, best practices in randomization and key selection would deem these algorithms ineffective (Johnson et. al, 2001). 5 Super-singular Isogeny Key Exchange (SIDH) In efforts to develop a quantum-safe asymmetric (public-key) cryptographic algorithm, SIDH was developed based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. It is motivated by the development of a subexponential-time quantum algorithm for constructing isogenies between elliptic curves (De Feo et. al., 2011). Galbraith et al. (2016) state that certain attacks against SIDH—such as side-channel and fault attacks—may reduce the key strength. The authors believe that the industry will see more literature and research in the cryptanalyses of SIDH in the near future as it becomes more popular and widely adopted.

Hash Functions Description Cryptanalysis State 1 MD5 This cryptographic hash function was developed by cryptographer Ronald Rivest from MIT Laboratory for Computer Science. MD5 function produces a 128-bit long hash digest. It became an RFC#1321 standard in 1991 and was widely used for integrity checks as well as password hashing, among other sensitive functions. Lenstra et al. (2005) demonstrated a hash- collision attack by generating two public keys with the same MF5 hash digest. Therefore, MD5 is considered a weak hash function and is no longer used for critical security functions. 2 SHA-1 A cryptographic hash function developed and designed in 1995 by the NSA. SHA-1 function produces a 160 bit hash digest with more rounds than MD5. SHA-1 was widely used among the major web browsers with SSL certificates. In 2017 a group of researchers demonstrated a full collision attack against SHA-1 (Stevens et al., 2017). SHA-1 was deprecated by NIST in 2011. 3 SHA-2 A cryptographic hash function developed and designed in 2001 by the NSA. SHA-2 hash function can produce different digest sizes 224, 256, 384, or 512 bits with 64 or 80 rounds. SHA-2 replaced SHA-1 with SSL certificates among other secure protocols like SSH, PGP and IPSec. Over the years, cryptographers have proposed attacks against SHA-2 reducing specific variations of the algorithm, which weakened SHA-2’s strength. Dobraunig et al. (2016) used differential cryptanalysis, in addition to sophisticated search tools to maximize effectiveness with SHA-512/224 and SHA- 512/256. SHA-2 is still a valid standard and is widely used. 4 SHA-3 (Keccak) The latest member of the Secure Hash Algorithm selected through the NIST 2007 competition that was completed by 2015. SHA-3 (originally named KECCAK) is not a variation of its predecessor (Sha- 2, SHA-1 or MD5). SHA-3’s algorithm is structurally different and is based on a cryptographic sponge function (Bertoni et al., 2007). SHA-3 hash function can produce different digest sizes 224, 256, 384, and 512. Morawiecki et al. (2014) describe a preimage attack based on rotational cryptanalysis to reduce the algorithm rounds against SHA-3 512 bit variation, which can slightly reduce the time and memory needed to break this algorithm.

Hash Functions Description Cryptanalysis State 1 MD5 This cryptographic hash function was developed by cryptographer Ronald Rivest from MIT Laboratory for Computer Science. MD5 function produces a 128-bit long hash digest. It became an RFC#1321 standard in 1991 and was widely used for integrity checks as well as password hashing, among other sensitive functions. Lenstra et al. (2005) demonstrated a hash- collision attack by generating two public keys with the same MF5 hash digest. Therefore, MD5 is considered a weak hash function and is no longer used for critical security functions. 2 SHA-1 A cryptographic hash function developed and designed in 1995 by the NSA. SHA-1 function produces a 160 bit hash digest with more rounds than MD5. SHA-1 was widely used among the major web browsers with SSL certificates. In 2017 a group of researchers demonstrated a full collision attack against SHA-1 (Stevens et al., 2017). SHA-1 was deprecated by NIST in 2011. 3 SHA-2 A cryptographic hash function developed and designed in 2001 by the NSA. SHA-2 hash function can produce different digest sizes 224, 256, 384, or 512 bits with 64 or 80 rounds. SHA-2 replaced SHA-1 with SSL certificates among other secure protocols like SSH, PGP and IPSec. Over the years, cryptographers have proposed attacks against SHA-2 reducing specific variations of the algorithm, which weakened SHA-2’s strength. Dobraunig et al. (2016) used differential cryptanalysis, in addition to sophisticated search tools to maximize effectiveness with SHA-512/224 and SHA- 512/256. SHA-2 is still a valid standard and is widely used. 4 SHA-3 (Keccak) The latest member of the Secure Hash Algorithm selected through the NIST 2007 competition that was completed by 2015. SHA-3 (originally named KECCAK) is not a variation of its predecessor (Sha- 2, SHA-1 or MD5). SHA-3’s algorithm is structurally different and is based on a cryptographic sponge function (Bertoni et al., 2007). SHA-3 hash function can produce different digest sizes 224, 256, 384, and 512. Morawiecki et al. (2014) describe a preimage attack based on rotational cryptanalysis to reduce the algorithm rounds against SHA-3 512 bit variation, which can slightly reduce the time and memory needed to break this algorithm.