I recently did some work as a side project for company called Patero that involved creating quantum hardened prototype of one of their products. This post discusses how to secure state-of-the-art cryptographic protocols against attacks from (future) quantum computers. It starts off with an introduction to how crypto protocols in general are constructed, to serve as an introduction for those of us who haven't done much crypto work in the past.

Video auf Deutsch

In addition to my role at Adobe, I also do occasional freelance work as an software engineer focusing on rust/c++/embedded and cryptographic work. One of the clients I usually do work for is Patero, who are working on integrating quantum hardened secure communication modules in mobile devices, IoT and critical infrastructure. One of their projects is an end-to-end encrypted, hardware-based cryptography module for securing mobile calls and communications in general even in the face of a compromised operating system. To further this project I was asked to create a quantum hardened version of this chip for evaluation purposes; first identifying those parts of their cryptographic protocol¹ that would break when quantum computer based attacks become feasible and finding solutions to harden the protocol against such attacks. This blog post discusses the general approach usually taken when hardening modern crypto protocols.

To be clear here, this post is about Quantum Hardening also known as Post Quantum Cryptography; that is the study of how to secure the sort of crypto protocols used in normal machines against cryptanalysis (attacks) using quantum computers. This post is not about Quantum Computing (the study of how to use quantum computers to solve problems) and it is not about Quantum Cryptography (the study of using quantum effects to do cryptography).

The first part of this post is dedicated to revisiting some cryptography fundamentals the basic make up of modern day crypto protocols so even readers less familiar with the subject can take away something from this post. Jump down to Quantum Attacks: Grover's algorithm if you are already familiar with the inner workings of modern cryptographic transport protocols.

Summary: How to quantum harden in a hurry

The availability of practical quantum computers would render all commonly used asymmetric cryptography used today insecure. Since pretty much all modern day cryptographic protocols (like HTTPS, TLS⁵, or SSH⁶) rely on asymmetric crypto as a vital component, these protocols will also become insecure. Symmetric cryptography is also affected but doubling key sizes provides an easy fix. Updating asymmetric crypto to be secure again will require the introduction of entirely new cryptographic primitives.

This is not a large problem now, because quantum computers are currently impractical, but their technology may advance in the coming years or decades enough to make quantum computer based attacks feasible; we should prepare for this point in time soon and some data needs to remain securely encrypted over the next decades, which is why quantum hardened cryptography is starting to become an important subject.

The process to develop post quantum cryptography is currently ongoing. For key exchanges, Classic McElice is a robust choice, but its memory requirements are prohibitive for many platforms. Failing that FrodoKEM is not a terrible choice. Post quantum signature schemes are not as relevant because they are only relevant to thwart online attacks (and for those you need a quantum computer now). Still Sphincs+ is probably not a particularly bad choice, but again the memory requirements are pretty tough to meet.

Any post quantum crypto primitive is currently suspect and should not be used on it's own; there is significant risk the key exchange or signature scheme could be insecure against classical computers, meaning that you would be worse off than with state of the art protocols using such a primitive. Quantum hardened algorithms should only be used together with classical, well analyzed primitives. Employ robust combiners for this purpose. Open Quantum Safe is probably not a bad source of implementations for post quantum primitives.

Post Quantum Crypto should be limited to research and evaluation use cases at the moment except in very special circumstances. Even though redundant constructions using robust combiners are probably safe, the act of updating protocols, changing implementations may introduce implementation errors, side channels, or operational problems which can easily render your crypto system as a whole insecure. Even if extremely stringent measures are taken to publicly vet the resulting protocol and implementation, this risk persists.

What is crypto

On a basic level, the goal of cryptography is the protection of private messages sent over public channels from interception by a third party. In the slide shown above, Alice would like to send a message ("I like your cat ears!") to Berta; since this message is confidential, she would like to cryptographically protect the message.

Other use cases have even more stringent requirements: imagine sending a message requesting a wire transfer via online banking; you would not want an adversary to be able to send a transfer in your name or modify the message in somehow. This is why all crypto protocols should fulfill all three properties: Confidentiality (only recipient can read it), Authentication (only you can send), as well as Data Integrity (message cannot be changed).

Archaic Ciphers: Rotation Cipher

Modern cryptographic ciphers can be quite hard to understand, so in order to illustrate how basic encryption works, we will take a look at some historical ciphers. The first cipher I would like to introduce is the Caesar Cipher; called that because Julius Caesar was one of the users of this cipher. Before we can encrypt some text using this cipher, we first have to assign a number to each letter of our alphabet and choose a key. Then we simply add the key to each character or subtract it to decrypt our cipher text.

Using 4 as our key we get the following conversion table:

space/0 → d/4
a/1 → e/5
b/2 → f/6
...
x/24 → a/1
y/25 → b/2
z/26 → c/2

Our text "i like your cat ears" turns into "mdpmoidbsyvdgexdievw", which cannot be red without decryption.

So how hard is breaking this cipher? Not very hard as it turns out: There is one kind of attack that can always be performed; just try every one of our 27 possible keys until you find one that works. This is called a brute force attack and works well for any cipher whose key space (that is the number of possible keys) is very small; other, more advanced ciphers with a very large key space require more sophisticated sorts of attack.

Archaic Ciphers: Substitution Cipher

Substitution ciphers fit that bill; similar to how a rotation cipher works, one character maps to another random character from our alphabet. Basically instead of rotating our alphabet by a fixed offset, we shuffle it. This makes rotation ciphers a specific case of substitution ciphers.

alphabet: " abcdefghijklmnopqrstuvwxyz"
key:      "jxngzdtlciu wemkavbfsoqprhy"

plaintext:  "i like your cat ears"
ciphertext: "ijwi djhkobjgxsjdxbf"

Shuffling our alphabet yields a much larger key space; $27!$ (that is 27 factorial, $2726...21$) to be precise or roughly $10^28$ (a 10 with 28 zeroes) keys, which is far too many keys for us to try each one. Even one or many computers can not try this many keys, so attacking this cipher will require a more advanced attack: Notice how our cipher text contains the letter J a lot? We can use that and infer that J must map to a particularly common character -- space in our case. By using statistical analysis – that measuring the frequency of each character in our cipher text – we can simply look up which character is this frequent in the English language and break the cipher this way. This works because vowels for instance appear much more frequently than consonants.

Archaic Ciphers: Transposition Cipher

Finally, let's look at a slightly different sort of cipher; while substitution ciphers shuffle our alphabet, a transposition cipher shuffles the actual text turning the cipher text into an anagram of the plain text.

key:        31542
plaintext:  HELLO
ciphertext: EOHLL

Unlike with our previous cipher the problem with this cipher is immediately visible: "eohll" being an anagram of "hello" is pretty obvious. This problem gets worse when the key is used multiple times.

Modern Cipher: AES

Having looked at some archaic examples of ciphers, let's now jump into the 21st century and take a look at an example of a modern cipher. The Advanced Encryption Standard is widely used today (although there are alternatives). there is a good chance this website was transferred to you via an AES encrypted channel. It is a block cipher; meaning the data is chopped into fixed size segments which are separately encrypted. All operations used by the cipher are reversible, so to decrypt the data, all operations are applied in reverse.

Internally, AES uses a Substitution-Permutation-Network. The big round plus with a circle you can see is an XOR operation; this is similar to the rotation cipher (rotation or modular addition in binary is just xor), except that every bit of data is rotated with a single bit from the key. The boxes labeled S represent substitution steps; here four bit long words of data are replaced according to a built in lookup table. Finally the step labeled P is a transposition step; here the results of the substitution are shuffled according to a predefined pattern.

Only the xor step actually combines the data with the key; the substitution and permuatation steps are not really encryption steps per say since their "keys" are known to any attackers. Instead they basically scramble the data, ensuring that each bit in the cipher text is influenced by every bit of plain text and key. Applying these three steps multiple times effectively obscures the relationship between ciphertex, key and plaintext, to the point that statistical methods cannot be used to uncover their relationship. Every bit of the output depends on every bit of the input and every bit of the key; changing just one bit in the input or key should change roughly 50% of the output bits.

Note that we left out a lot of the steps required to really make a secure block cipher; e.g. one problem with the above description is that the same input block and key will produce the same output. This is unacceptable since this would allow attackers to detect when two blocks are the same, there are solutions to this problem but we won't go into detail here.

Now since we have a cipher that is actually secure, we can start to encrypt something, we just need a key! So, Alice does create a key and transmits it to Berta over a secure channel. Our key exchange here is really the most important part; if the key is intercepted all our efforts will be wasted. The adversary will be able to decrypt all past, present, and future messages transmitted using this key. Once the key has been exchanged however, we can start sending data, securely, over untrusted channels.

Message Authentication Codes

There is one – actually there are many problems with the protocol above, however one particularly bad one is that the protocol is not authenticated; meaning, that while an attacker could never correctly encrypt data (they would need the key), they could flip bits in the ciphertext or even send entirely random data and Berta would not automatically notice.

To remedy this problem, a message authentication code is used; the authentication tag generated by this function is a bit of redundant data, added to the message to prevent tampering. This tag can only be generated by someone who knows the symmetric key, so an attacker could only guess at the correct code.

Our protocol is still almost the same as it was before: having exchanged a shared key, Alice can now start encrypting data. She uses the shared key to encrypt our message. Before sending it, she also uses the message authentication code to generate a short authentication tag over the cipher text using the key. Both the cipher text as well as the message authentication code are sent to Berta who checks the auth tag by generating an auth tag of her own and comparing the one sent along with the message. Having successfully established that the message is authentic, she continues to decrypt the data as before.

Key derivation Functions

We now have achieved authenticated encryption; our crypto system is secure as long as the shared key is exchanged securely.

That is all well and good, however secure key transmission is actually not that easy to achieve. Sounds easy enough, but in practice it usually the key consists of around one hundred completely random characters; ciphers need high quality keys to function properly. A short key, or a key that has obvious patterns in it will not do. Hardly any messenger would be able to remember such a random figure; you could write it down, but then you may loose the piece of paper so this is not a good solution either.

Luckily, key derivation functions can at least help us lessen that problem; basically a key derivation function can take a string of random data and bring it into the format of a high quality key, provided of course that the input actually contains enough random information. The output will have the needed length, it will look random² and when used with a password, it should be slow to compute, just to thwart attacks testing lot's of commonly used passwords.

Key derivation functions really provide flexibility; you could choose a long sentence as your key (easier for your messenger to remember) or you could sent multiple keys and combine them using the KDF; as long as one key was not intercepted, the generated key will still be secure.

To integrate this key derivation function in our protocol, Alice chooses a password instead of the key itself and transmits it to Berta. Both parties run the key derivation function to generate the actual key and can now transmit data as they did in the previous two protocols.

Asymmetric Cryptography

Using a key derivation function drastically simplifies key transmission, without actually solving our core problem: We still need to transmit our keys via a secure channel. Creating a secure channel is really hard; the entire point of this exercise is to create a secure channel, so wouldn't it be nice to be able to sidestep this problem? Luckily, there is a solution and that solution is called asymmetric cryptography.

While in symmetric crypto there is just one key that is shared between both our parties, in asymmetric crypto there is two keys; one that can be absolutely public³ and one that is to be kept absolutely private; not even shared with your communication partner. The public key can be used by anyone to encrypt data they would like to transmit to you, while only you could decrypt the data again. There also is a corresponding signature scheme that can be used to proof that you are really the sender of some data; only you can sign a message using the private signature key, but anyone can validate the signature against your public key (notice to how this is somewhat similar in purpose to an authentication tag).

In practice, when sending a message, you would encrypt using the recipients public key and sign using your own secret key and since public key crypto is actually a bit inefficient, you would generate a random shared key, encrypt and authenticate the data using that and finally encrypt and sign the symmetric key using asymmetric cryptography.

Combining asymmetric and symmetric crypto in such a way to gain both – the performance of symmetric cryptography and the flexibility of public key cryptography – is called Hybrid Cryptography. When asymmetric encryption is used to encrypt a shared key for further encryption, this is called a Key Encapsulation Method.

Diffie Hellmann Key Exchange

Most cryptographic connections today are online – meaning it is possible to quickly send messages back and forth. Key encapsulation can be used to exchange the keys for such a connection, however there is a better way: The Diffie Hellmann Key Exchange; this is a function that produces a shared key directly using my own private key and your public key. To execute the key exchange, both parties generate a random key pair and transmit their public key before executing the Diffie Hellman function. That's it. Just two packets to transmit and the secret never actually has to be transmitted over the wire.

Putting it together: Modern day Crypto protocols

Now, using both symmetric and asymmetric cryptography we can build a cryptographic protocol like this:

1. Alice and Berta generate random Diffie Hellmann key pairs, and exchange their public keys and generate a secret using those keys.
2. They establish each others authenticity; often this involves using a digital signature scheme, although different ways to achieve this exist.
3. They use a key derivation function to generate a good key using the secret they just exchanged.
4. They use the key to encrypt data.
5. And a message authentication code to make sure the data is not tampered with.

That's it. This is pretty much how state-of-the-art cryptographic protocols work; there is a good chance your browser is used something like this to download this blog post.

Quantum Attacks: Grover's algorithm

There are two ways that quantum computers can attack modern cryptography; the first and less important of the two is grovers algorithm. As we discussed before, there is one attack that works on every cryptographic method: A "brute force" attack which is just a fancy word for trying every possible key until you find one that works. In computer science this is known as a "linear search" – the most basic search algorithm. Given a million possible keys it would take five hundred thousand tries on average to find the correct one; the formula is just $^N/_2$ where $N$ is the number of keys.

Grover's algorithm is the generic quantum search; this takes (don't ask me how) just a thousand tries for a million possible keys: While the generic classical search takes $^N/_2$ tries, quantum search just takes $sqrt(N)$ attempts on average, so it is much faster, or one thousand tries given a million possible keys. Luckily, we can just double our key size from six decimal places to twelve (or from 128 bits to 256 bits for actual cryptographic algorithms) to achieve the same security level as before.

So while Grover's algorithm can be used against any cryptographic algorithm, there is a relatively easy fix.

Quantum Attacks: Shor's algorithm

Shor's algorithm presents a bigger problem; pretty much all asymmetric cryptography⁴ used today is either based on the Discrete Logarithm Problem or the difficulty of factorizing integers. Both problems can be solved very efficiently using Shor's algorithm.

This means: Our handshake is broken; it is entirely insecure against attacks from quantum computers. This is why it is commonly said that quantum computers break all modern crypto; the symmetric part is fine, but if the handshake is insecure the symmetric key will be known so the protocol is insecure as a whole

Quantum Attacks: Are they feasible?

Now, this sounds really bad until you remember that practical quantum computers simply do not exist at the moment. They are really expensive, need to be cooled using cryogenics and just have on the order of 50 to 60 quantum bits; you would need thousands of quantum bits to even attempt breaking modern crypto. Attacking modern crypto with ENIAC (a very early computer) seems more feasible than using quantum computer at this time.

However, there is a good chance practical quantum computers will arrive in the next decades, so it is good to be prepared. Besides, in addition to all the cat videos, there is some data stored and transmitted now that we would like to remain secure in thirty to forty years; think financial or medical records. An attacker could simply commit all data they can get their hands on to cold storage and wait until quantum computers are advanced enough to decrypt it; a concept that is called "store now break later". To thwart this, we should really start to use post quantum crypto as soon as possible.

Quantum Hardening: Currently in early alpha

To this end, the National Institute of Standards and Technology – the same organization that standardized SHA, AES, and RSA – has organized a competition to find suitable post quantum crypto algorithms. The competition started 2017 and is expected to take half a decade more. In the beginning around 90 candidates where submitted, but a lot of them where discovered to be insecure in the first couple of hours after submission. Some similar ones have also been merged, but 26 are left and are now candidates in round two of the competition; you can follow the progress here.

The new primitives include signature schemes as well as key encapsulation methods and a single example SIKE of a replacement for Diffie Hellmann style key exchanges. They are based on problems like Learning With Errors, Elliptic Curve Isogeny, or the difficulty of decoding Error Correction Codes (as if I knew what the first two meant).

Experimental implementations of NewHope, NTRU, and SIKE where created for TLS⁵ and used in the Chrome browser and some servers with good results. BSI (the German equivalent of the American NIST) recommends using FrodoKEM or ClassicMcElice if you so choose to use quantum hardened key exchanges. Post Quantum Signature Schemes haven't received as much attention because they are not quite as relevant for protection from "save now decrypt later" style attacks. They protect from man in the middle attacks which have to be performed live – just at the time the connection is being created.

Robust Combiners

Post quantum crypto primitives are new and shiny; with crypto as with databases this is a bad thing. It means we can not really trust these algorithms' security as there is still a good chance some of these will turn out to be insecure in future cryptanalytic works. If we were to rely on them alone, our cryptographic protocol may not only be susceptible to quantum attacks but to classical attacks as well. This would be a total failure.

Optimally we would find some way to combine state-of-the-art asymmetric cryptographic primitives with post quantum ones, similar to how we combined symmetric and asymmetric cryptography to get the best from both worlds. There is a way and the study of how to do this securely is called "Robust Combiners"; enter the term in the search engine of your choice and you will find that there are a lot of constructions that are unsafe – proven to be bad. One of the few things that has been show to work as a robust combiner is the concatenation combiner: Simply perform both key exchanges; and concatenate the secrets they produce. You will end up with a secret twice the size, which is not really a problem because we just use it as the input for our key derivation function anyways. Combining signature schemes is trivial because we can just use both; test each signature and if one of the tests fails, consider the signature to be invalid.

Putting it together: The make up of a quantum hardened crypto protocol

Now, finally, we can actually come up with a quantum hardened cryptographic protocol: Perform two key exchanges – one post quantum key exchange and one legacy key exchange; concat their secrets. Perform two authentication steps; again, one quantum hardened and one legacy authentication. Use your key derivation function to format the combined secrets and start encrypting data. That's it.

Choosing primitives and implementations

Should you ever be given the challenge to quantum harden a protocol, you will find yourself trying to decide which cipher to use. Unfortunately, there is no straight answer to this question yet; the jury is still out on which post quantum primitives will turn out to be secure and which ones have vital flaws. If you had to choose, Classic McEleice is based on a crypto system invented in 1979 that has been analyzed pretty extensively. It is probably secure, but its key sizes are huge, too huge to fit into the memory of the chip I was programming. If memory is not a giant constraint for your application, use Classic McEleice. FrodoKEM is not as well analyzed, but probably not a terrible choice either and it's keys are still large, but not prohibitively so at least for the chip I was using. Sphincs+ is probably not a terribly choice for a post quantum signature algorithm, but it's signatures are around 40Kb large, so probably too large for a lot of platforms especially when trying to establish a chain of trust.

As for implementations, libsodium is what you should use in most applications for pre quantum algorithms and symmetric crypto. It provides a very small, secure set of cryptographic functions and follows usable security API design practices which make it comparatively hard to create unsafe constructions. There are alternatives implementing a wider array of cryptographic primitives, but often these include unsafe primitives or ones which are only secure when used in very specific ways. A limited set of choices can be a good thing.

Finally, there are a couple of libraries that implement post quantum crypto primitives; these implementations are of course not as tried and true as libsodium, but they do follow similar API design guides. There is Open Quantum Safe which is a good default choice as a source of post quantum crypto algorithms. PQClean provides a lot of the implementations used in OQS; I ended up using this one just because I had an easier time compiling it for my platform. mupq implements variants of post quantum primitives optimized for Arm M4; I could have used this, I ended up not using this simply because speed wasn't an issue at all for my platform, memory was the primary constraint.

[1]: https://en.wikipedia.org/wiki/Cryptographic_protocol; this is the sort of technology used to encrypt live connections; TLS – the protocoll your browser is using to fetch this blog post – is an example of such a protocol.

[2]: On average – there must be a 50% probability for each bit to be one or zero.

[3]: Download my public key from my web server https://cupdev.net/keys/7EA37614E956818EBFEA76526739B1556DBB745A.asc or from the key servers: gpg --search-key 7EA37614E956818EBFEA76526739B1556DBB745A

[4]: This includes RSA, DSA, Diffie-Hellman and all Elliptic Curve Cryptography

[5]: Transport Layer Security, your browser is using this to encrypt the connection with the blog's HTTP server.

[6]: Secure Shell; the most widely used protocol for administrating servers on the internet.