Taking the (quantum) leap with go

Heard about the quantum threat glooming on the horizon? Today, we dive into post-quantum, or quantum-resistant crypto, which is not to be mixed with quantum cryptography (see our previous blog entry on that), and unbox our post-quantum Go library.

Post-Quantum Cryptography

The arrival of quantum computers threaten the security of traditional cryptographic algorithms. Shor’s, Grover’s and Brassard’s algorithms are few examples of tools that enable powerful quantum attacks on the public key cryptography as we know and use it. The hardness of some schemes such as RSA or Diffie-Hellman is not granted anymore, prompting us to find replacements that rely on alternative assumptions, namely post-quantum cryptography.

Lattice-based cryptography

Lattice-based constructions make for the majority of post-quantum schemes. A lattice is a set with an order relation, meaning that every two elements have unique supremum and infimum. The most important lattice-based computational problem is the Shortest Vector Problem (SVP), which entails finding the shortest vector in a given lattice. The security of most of the lattice-based constructions can be reduced to the security of the SVP problem, which appears to be resistant to attacks by both classical and quantum computers.

The CRYSTALS Suite

The CRYSTALS algorithms are promising candidates for the post-quantum area, and are finalists of the NIST post-quantum cryptography standardization process. They stand out because of their great performance, the main drawback being their relatively large outputs size.

The first protocol of the CRYSTALS suite is Kyber, a Key Encapsulation Mechanism (KEM), that secures the exchange of key material over an insecure channel. It uses asymmetric encryption to transmit a short symmetric key. This symmetric key is then used to encrypt the longer messages. Briefly, Kyber is built using a security transformation that turns Regev’s weakly secure encryption scheme into a strongly secure one.

The second protocol is Dilithium, a Digital Signature Algorithm (DSA), that produces a signature on a message that is verifiable by anyone holding the public verification key associated to the secret signing key. Dilithium follows a Fiat-Shamir construction, sampling a mask and rejecting until the signature is binding yet hides the signing key.

The security of those protocols is parametrized by various factors such as the size of the lattice. Kyber and Dilithium can be instantiated to offer a light, recommended, or very high security level, and are respectively designated as Kyber512, Kyber768, and Kyber1024, or Dilithium2, Dilithium3, and Dilithium5.

Side-Channel Attacks

A thorough cryptanalysis is necessary but not sufficient to guarantee the security of a library. The last decade has seen the number of publications about a new class of attacks arise (Meltdown, SPECTRE, Zombiland…). Side-channels attacks target the implementation of algorithmically secure crypto systems and can exploit information gained from the implementation itself.

Often overlooked, side-channel attacks can be used to weaken or break entirely the security of an infrastructure. Not paying enough attention to side-channel vulnerabilities can lead to devastating breaches, as we have seen with NSA’s TEMPEST system that could reconstruct the entirety of a computer’s screen by listening to its electromagnetic emissions, or more recently with the SPECTRE attacks, that can manipulate a process into revealing sensitive data, such as passwords, after monitoring the cache hits and misses timing. This is why we make it a priority to offer as much protection against said side-channel attacks as possible with our implementation.

Our library

The Go language has gained popularity amongst cryptographers because of its simplicity and security properties. Writing and maintaining Go code is easy and a great fit for projects of all scale, from proof-of-concepts to complete infrastructures.

In our library, we offer an implementation in Go of the CRYSTALS protocols. The open-source code is available in the crystals-go repository. While there are existing implementations that consist of a straightforward translation from the official implementations available in C to Go, we made the choice to deviate from the reference to provide additional security and performance properties. Correct behavior of our code is ensured and tested via known-answer tests provided by the CRYSTALS’s authors.

API

In this section, we provide hands-on examples on how to use our library. First, the crystal-go module can be installed via:

go get -u github.com/kudelskisecurity/crystals-go

In order to have a clear separation between the parameters and the algorithms, we define generic methods that work with all possible sets of parameters, and invoke them on an instance of Kyber or Dilithium that completely defines the parameters to be used. Hence, a user first has to define which level of security they want to work with by creating an instance of Kyber or Dilithium among Kyber512, Kyber768, Kyber1024 and Dilithium2, Dilithium3, Dilithium5:

k := NewKyber512() //Creates a Kyber instance with light security level 
d := Dilithium3() //Creates a Dilithium instance with recommended security level

The user can now generate a public and private key pair by calling:

pk, sk := k.KeyGen(seed)

or

pk, sk := d.KeyGen(seed)

Once the parameters are defined and the keys are generated, the core functionalities of Kyber and Dilithium can be called.

Kyber’s main functions are Encaps and Decaps. A typical flow of Kyber is:

//Select the parameters
k := NewKyber512()
//Generate the keys and openly disclose the public key.
pk, sk := k.KeyGen(seed)
//Generate a shared secret and a ciphertext. Similarly to the seed, the random
//coins used during the encapsulation can be given or deleguated to the method.
c, ss := k.Encaps(coins, pk)
//Send the ciphertext to the private key holder, which decapsulate it to recover 
//the shared secret (ss = ss').
ss' := k.Decaps(c, sk)

Similarly for Dilithium, the main methods Sign and Verify are typically used as follows:

d3 := Dilithium3() //Creates a Dilithium instance with recommended security level
pk, sk := d3.KeyGen()
msg := []byte("This is a message.")
sig := d3.Sign(sk, msg)
verified := d3.Verify(pk, sig, msg) //The boolean verified is true for honest runs

A seed and coins of 32 bytes can be given as argument and allows for reproducibility for example, or is useful if the user does not trust the environment to generate good randomness and wants to use randomness from their own source.
They can be nil in which case the randomness will be generated during the key generation process using Go’s official crypto/rand library.

This section is not exhaustive of the features offered by our library and we refer to our README for a more complete description.

Security

Our library stands out because of its security properties. Among the vulnerabilities reported on the original implementation, we integrate countermeasures for most of them, providing a library that is both theoretically and practically secure. We predict that new attacks will be published as the candidates are refined, and expect changes in the code to occur as the security of our library is treated as a continuous process.

We recall that side-channel attacks are high-risk threats and encourage users to prefer libraries with strong implementation security, such as our library, over implementations that lack these guarantees.

Performance

In order to provide an insight on the computation and communication costs of our library, we report in the following table the runtime in milliseconds and the outputs size in bytes of our implementation for a recommended security level.

The relatively large outputs size can impact some applications but is never considered a bottleneck. Furthermore, we show in the following graphs that the performance of current classical security public-key and signature schemes (ECDSA and RSA-OAEP) can be excelled by our implementation. This difference can be explained by the very simple arithmetic the CRYSTALS suite relies on.

Takeaway

Our post-quantum library is easy to use, fast and secure. The practicality of our library should be used as motivation to integrate post-quantum alternatives in your infrastructures, to protect your data well into the foreseeable future without compromising on the performance.