EN 
DE State of the art and outlook
Author: Thomas Pöppelmann, Infineon Technologies AG
Contribution – Embedded Software Engineering Congress 2017
Due to their computing power, quantum computers have the potential to break or weaken various currently used encryption algorithms. This particularly affects asymmetric cryptographic methods such as RSA and Elliptic Curve Cryptography (ECC), which are used by numerous internet standards like Transport Layer Security (TLS), S/MIME, PGP, and GPG. Post-quantum cryptography (PQC) offers a solution, employing methods that can be executed on classical computers but are capable of withstanding the power of quantum computers. Currently, a large number of such PQC methods exist, which differ significantly from RSA and ECC in their implementation characteristics.
Asymmetric cryptographic methods like RSA or ECC form the basis of many cryptographic security protocols today. A prominent example is the Transport Layer Security (TLS) protocol, which secures communication between web browsers and servers and is also increasingly used in the Internet of Things and other embedded systems. Due to its more efficient arithmetic compared to RSA, ECC is particularly attractive for embedded systems. In fact, it is even possible to execute ECC on some microcontrollers without a dedicated hardware accelerator.
RSA and ECC are currently considered very secure because the underlying mathematical problems, such as efficient factorization or calculating the discrete logarithm over elliptic curves, remain difficult even after years of research. However, as early as 1994, Peter Shor presented an algorithm capable of breaking RSA and ECC on a theoretical machine—the quantum computer. Since a powerful quantum computer uses Shor's algorithm to extract the private key from the public key of the RSA or ECC cryptosystem in polynomial time, even massively increased parameters cannot prevent this attack. Besides asymmetric methods like RSA or ECC, symmetric cryptography, such as AES or Triple DES, is also vulnerable to quantum algorithms. However, a practical attack using the so-called Grover algorithm is far less fatal, as it is currently assumed that this can be compensated for by doubling the key length of symmetric methods (e.g., using AES-256 instead of AES-128).
Post-quantum cryptography, the NSA and NIST
For years, researchers have been working on developing a sufficiently powerful quantum computer that could not only advance cryptanalysis but also find applications in materials development and chemical simulation. To counteract the negative consequences for cryptography, researchers have been working for years on so-called post-quantum cryptography (PQC). This involves cryptographic algorithms that run on classical computers but are based on mathematical problems and structures that are considered extremely difficult to solve, even for quantum computers.
Nevertheless, it is a legitimate question why practical users or implementers of cryptography and IT security solutions should now be concerned with a theoretical machine. Furthermore, it is true that PQC led a niche existence outside of academia for a long time and received little attention. However, this situation changed fundamentally in August 2015 with an announcement by the United States National Security Agency (NSA). In a publication on its website, the NSA announced that it would switch to quantum computer-resistant algorithms for its "Commercial National Security Algorithm Suite" (CNSA Suite) "in the not too distant future." At the same time, the requirements regarding key length for new intelligence-processing computer systems were further tightened; for example, AES-256 must now be used. Employees of the German Federal Office for Information Security (BSI) have also come to a similar conclusion that it is time to act [1]. Another initiative comes from the US National Institute for Standards and Technology (NIST), which recently launched a post-quantum cryptography project. The long-term goal is to standardize new key exchange, public-key encryption, and signature methods through a competitive process. Given these initiatives and the resulting disruption, it seems extremely important not to ignore the topic of PQC, but to actively shape it.
Implementation of post-quantum cryptography
Currently, there are five fundamental mathematical problems, or classes of algorithms, with which post-quantum cryptography can be implemented. These include signature schemes based on hash functions or the difficult problem of solving multivariate quadratic polynomial equations. Additionally, there are public-key encryption and key-exchange schemes based on coding-theoretic problems or problems on supersingular elliptic curves. Another promising category is lattice-based cryptography. With this, asymmetric public-key encryption and signature schemes can be implemented, offering a high level of security with moderately large keys and ciphertexts.
The practical implementation of post-quantum key exchange (PQC) methods on embedded systems has been a subject of research for several years. New methods for efficient computation on 8-, 16-, or 32-bit processors must be found, as the existing RSA- or ECC-oriented concepts are no longer applicable. One example of a post-quantum key exchange method is the so-called lattice-based NewHope algorithm [2], developed by Alkim, Ducas, Pöppelmann, and Schwabe. NewHope can replace or complement currently available Diffie-Hellman or Elliptic Curve Diffie-Hellman-based key exchange mechanisms. According to current research, NewHope achieves approximately 256 bits of security against attacks by quantum computers for long-term security. Both sides must transmit approximately 2048 bytes for a key exchange. In 2016, Google integrated the NewHope algorithm into the TLS protocol in a public beta version of the Chrome browser and successfully tested it.
The execution of the NewHope algorithm requires three steps. First, the server generates a public key (key generation) from a secret known only to the server. Second, the client generates a public key from a secret accessible only to the client. The client then combines its secret with the server's public key to create a symmetric session key (keygen + shared key). Third, the server uses its secret and the client's public key to generate the same session key (shared key). The mathematical complexity of the key generation process prevents a passive attacker, who only monitors the data transmission, from deducing the individual secrets or the generated symmetric session key.
On an Intel CPU, several thousand key exchange operations per second can be calculated using the widely available vector registers (Advanced Vector Extensions; AVX). A publicly available implementation of the NewHope algorithm for embedded systems has already been presented by Alkim, Jakubeit, and Schwabe [3]. On a Cortex-M0, the "key generation" step can be executed in 1.2 million cycles, the "keygen + shared key" step in 1.7 million cycles, and the "shared key" step in 0.3 million cycles. The implementation is optimized using assembly instructions and employs a Fast Fourier Transform (FFT)-based algorithm for the necessary polynomial multiplication. Another important step towards sufficiently secure implementations is protection against physical attacks. In [4], Oder, Schneider, and Pöppelmann present an implementation of a public-key encryption algorithm similar to NewHope, which, according to current standards, is intended to offer 233-bit security. Randomizing the internal data achieves a certain level of protection against current profile analysis. On a Cortex-M4F, encrypting a message then requires 4.1 million cycles, while side-channel-protected decryption requires 25.6 million cycles.
Infineon has implemented the NewHope approach for the first time on a commercially available contactless security chip. This demonstrates that PQC can also be implemented on smart card systems with limited memory and contactless power supply, and is therefore practical.
Further research is needed to optimize existing systems with regard to low power consumption, minimal memory requirements, and high security. Infineon, a leading manufacturer of security ICs and chips for the Internet of Things and the automotive industry, is actively involved on several levels to provide future solutions for customers and users. These activities include scientific contributions, participation in PQC standardization, and prototype development and research.
Bibliography and list of sources
[1] Heike Hagemeier, Manfred Lochter: Information security in the quantum age. With certainty – BSI Magazine 2017/01,
[2] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, Peter Schwabe: Post-quantum Key Exchange – A New Hope. USENIX Security Symposium 2016: 327-343,
[3] Erdem Alkim, Philipp Jakubeit, Peter Schwabe: NewHope on ARM Cortex-M. SPACE 2016: 332-349
[4] Tobias Oder, Tobias Schneider, Thomas Pöppelmann, Tim Güneysu: Practical CCA2-Secure and Masked Ring-LWE Implementation. IACR Cryptology ePrint Archive 2016: 1109 (2016)
Our training courses & coaching sessions
Do you want to bring yourself up to date with the latest technology?
Then find out more here Regarding training courses/seminars/workshops and individual coaching sessions offered by MircoConsult on the topic Quality, Safety & Security.
Training & coaching on the other topics in our portfolio can be found here. here.
Quality, Safety & Security – Expertise
Valuable expertise on the topics of quality, safety & security is available. here Available for you to download free of charge.
You can find expertise on other topics in our portfolio here. here.
