Post-Quantum VPN Setup Part One: Scratch-Work


14 min read
Post-Quantum VPN Setup Part One: Scratch-Work

For those that are familiar with the Librehash organization and our objectives, one of the things that we've spent a lot of time over the past few weeks discussing is the deployment of a post-quantum VPN.

As the name implies, a post-quantum VPN is a VPN structure that employs cryptographic primitives that have post-quantum level strength.

What Determines Whether Something Has Post-Quantum Level Strength or Not?

The literal, direct answer to this = mathemtical proofs

However, in lieu of actual quantum machines that exist in the capacity that many anticipate they will be in the future - whitepapers, cryptographic conferences, academic peer review, challenges from colleagues in the cryptographic space, and the NIST post-quantum competition (currently in Round 2) all serve as established barometers for which signatures will likely possess post-quantum strength.

What is Post-Quantum Strength?

'Post-quantum strength' is an abstract term that defines a level of cryptographic resistence in a primitive that would sufficiently resist (not disable) brute force attacks by a quantum computer (in the future at some point), assuming that we establish defined limits on the practical time for the brute forcing of said algorithm. [If it were to take 10,000 years, for example, for a post-quantum computer to 'break' a cryptographic algo or find a collision, we would consider that algorithm to have post-quantum level resistance].

'What is This Piece About'?

We wanted the community to go along on this journey with us as we seek out a suitable post-quantum structure to deploy for users.

This will not only give users the transparency that they need (you should never assume that someone possesses such a capability), but also (hopefully) solicit contributions / feedback / suggestions and perhaps even direct assistance in the development of said post-quantum VPN.

With that being said, everything that is posted below should serve as our first installment of this series.

Please forgive the informal nature of these notes as they were written as notes.

We purpoefully abstained from 'cleaning them up' in order to give readers a more "raw view" of how we're putting these things together.

Without further ado, what is presented below is our piece.


Main Setup

We've decided - Wireguard > OpenVPN.

Way too much hassle in deploying OpenVPN and it doesn't come packaged w the flexibility that Wireguard has from the Noise Protocol (+ noise protocol already supports one pq-crypto alg as it is).

Mullvad Model

MullvadVPN published a public repo for a post-quantum fork of Wireguard back in 2017.

The repo is outdated, but from what we've seen - all we need to do is update the cryptographic primitives from the liboqs library, re-compile it using the build instructions, then select the actual post-quantum KEX algorithms we want to use and we should be good to go.

Hide and Seek: Find the Repos and Dissect Them

Main repo = https://github.com/mullvad/oqs-rs (hasn't been updated since 2017 ; that's where the work in deploying this comes in)

Roadmap of how its setup:

Oqs-sys

This repository doesn't need to be touched because all it does is provide 'FFI' bindings for the 'libqos' library.

Actual rust library for 'oqs-sys' can be found here: https://docs.rs/releases/search?query=liboqs

Main GitHub branch for 'oqs-sys' = https://github.com/mullvad/oqs-rs/tree/master/oqs-sys

'liboqs' Cryptographic Library

This is the library that needs to be re-built.

Fortunately, that's not an issue because all we need to do in order to do that is just build the repo for liboqs sitting at: https://github.com/open-quantum-safe/liboqs

Solid chance that this process can be expedited by using a docker image for their NGINX distro, among other things - depends where they're getting the liboqs sources from on that though.

Important Instructions

At this point, an understanding of the purpose + architecture of the 'oqs-sys' library is established + liboqs should be downloadedin full and placed in a finite directory.

From here, we follow these directions in order to point to the liboqs repo that we just built (for the updated ciphers placed in liboqs since 2017):

'build.rs' file that they're referencing should be created (or modified) underneath the 'oqs-sys' directory in this repo.

Here's the link to it on GitHub: https://github.com/mullvad/oqs-rs/blob/master/oqs-sys/build.rs (clearly has a directive pointing to whatever environment variable that we established as the location for liboqs).

Build-liboqs.sh

Hopefully this file is either modified or re-generated upon running the 'build.rs' script.

Its located under the same directory as the build.rs script at the same level.

Here is the GitHub link = https://github.com/mullvad/oqs-rs/blob/master/oqs-sys/build-liboqs.sh

If it hasn't been modified, then we're going to need to edit the script to include the additional post-quantum safe algorithms that liboqs has been updated with since Mullvad open sourced this repo.

They will probably need to be included here:

We can examine the names given in this repo in order to assess the 'format' of the post-quantum signatures (more than likely mirror whatever names they're given in the 'readme' of the liboqs main repo).

Submodule Found

At the top, the 'liboqs @ 581fbbb' ; obviously points to 'liboqs'

We won't be downloading the git repo recursively to include the submodules, but if there are any issues with pointing to the liboqs directory that we establish, then we could use this as a last resort - which would just involve us git cloning this repo recursively w submodules, grabbing the new liboqs git directory & installing it in its place (this shouldn't be too difficult either way and no issues w building this portion of the project are anticipated - this is just straightforward compilation with header / c files).

Oqs-rs/oqs Directory

This is the directory that iterates over the ffi bindings (what we set up in the previous step) in order to handle the client / server aspects of the key exchange

Kex.rs - May Need Customization

Here is the link: https://github.com/mullvad/oqs-rs/blob/master/oqs/src/kex.rs

As can be seen below - the library does refer to the ffi bindings created by 'oqs-sys' (in accordance with the liboqs library that its built with).

However, there are still references to outdated pq cryptograhic primitives - as can be seen here:

However, this is no issue as it defers to whatever the signatures are that were compiled w liboqs.

That can be seen below:

Further down the file, the actual key exchange process is broken down in the comments before the code is presented:

(for reference for all those reading; kex = key exchange ; 'oqskexalg'= post-quantum key exchange cipher ; OqsRand = rng generator , we will have to probe a bit more into this in order to ascertain what's being relied upon for the rng generator)

Nothing much more to see in this repository unless there's more interest about the general key exchange mechanisms that are coded into Wireguard.

^^ This could be tweaked, but its important to first ensure that we're able to build a successful fork of this already existing (yet outdated) code from 2017 to update it w/ new liboqs algos.

back to the main branch (oqs-rs)

Oqs-kex-rpc

This part is a bit more interesting and is one that should be referred to after the necessary configurations are made in the steps above.

URL for this repo on GitHub = https://github.com/mullvad/oqs-rs/tree/master/oqs-kex-rpc

The 'ReadMe' Defines the Repo As:

A client and server able to perform post-quantum safe key exchanges over HTTP based JSON-RPC 2.0. The client and server uses oqs for the cryptography.

Example code below (being pasted directly because its really important to scan through this):

extern crate oqs_kex_rpc;

use oqs_kex_rpc::server::ServerConstraints;
use oqs_kex_rpc::client::OqsKexClient;
use oqs_kex_rpc::{OqsKexAlg, SharedKey};

static ALGORITHMS: &[oqs_kex_rpc::OqsKexAlg] = &[
    OqsKexAlg::RlweNewhope,
];

// This is the callback that will be called on the server after the shared key
// has been computed on the server, but before Bob's messages are returned
// to the client.
let on_kex = move |_metadata: (), keys: Vec<SharedKey>| {
    println!("Done exchanging {} keys", keys.len());
    // If this callback return an `Err`, Bob's messages will not be returned
    // to the client, instead a JSON-RPC error will be returned.
    Ok(()) as Result<(), ::std::io::Error>
};

// See the `start` function's documentation for an explanation of the
// `meta_extractor` and how it can be used. Here it does the least possible to
// keep the example simple.
let meta_extractor = |_: &oqs_kex_rpc::server::Request| ();

// Start the server on localhost. Port zero means that the OS will pick a
// random port that we can later get with `server.address()`.
let server: oqs_kex_rpc::server::Server = oqs_kex_rpc::server::start(
    SocketAddr::from_str("127.0.0.1:0").unwrap(),
    meta_extractor,
    on_kex,
    ServerConstraints::default(),
).expect("Unable to start RPC server");

let http_addr = format!("http://{}", server.address());
println!("kex server listening on {}", http_addr);

// Connect a client to our localhost server and exchange keys with it
let mut client = OqsKexClient::new(&http_addr).unwrap();
let client_keys = client.kex(ALGORITHMS).expect("Error in client during exchange");

// Check that the result is sane (same algorithms as requested)
assert_eq!(client_keys.len(), ALGORITHMS.len());
for (key, algorithm) in client_keys.iter().zip(ALGORITHMS) {
    assert_eq!(key.algorithm(), *algorithm);
}

According to the Repo:

This example code shows how to set up a key exchange server listening on localhost and then perform a key exchange with it from a client instance.

Question that we've been having while going through the repo is this = How does the client gain capabilities to negotiate said post-quantum signatures w/o running all of these same compilations on their end?

perhaps this answered by the code - but we're going to put a flag on this portion of our notes to remind us to include it in the subsequent e-mail that we send to the Mullvad development team

There's a portion of the code that indicates that perhaps the negotiation of the post-quantum occurs server side (see below):

// Connect a client to our localhost server and exchange keys with it
let mut client = OqsKexClient::new(&http_addr).unwrap();
let client_keys = client.kex(ALGORITHMS).expect("Error in client during exchange");

// Check that the result is sane (same algorithms as requested)
assert_eq!(client_keys.len(), ALGORITHMS.len());
for (key, algorithm) in client_keys.iter().zip(ALGORITHMS) {
    assert_eq!(key.algorithm(), *algorithm);
}

The code above was excerpted from the example that we posted prior at the beginning of this section.

This code excerpts the final 9 lines of that example.

The comments that were added here (behind the double slashes) indicate that perhaps the authentication + negotiation occur on the server side, exclusively.

Specifically, line #3 in the excerpt posted above:

let client_keys = client.kex(ALGORITHMS).expect("Error in client during exchange");

This code seems to indicate that the client's environment is not setup to comprehend the cryptographic primitives being used in this exchange (post-quantum kex from our ffi bindings & pre-selected key negotiation choice).

Notably, users when launching Wireguard with a Mullvad configuration file do not necessarily choose the algorithm that they would like to use to connect to their VPN / tunnel-point.

This is a smart configuration for the client side though - you don't want to offer unnecessary avenues for compromise or have people making decisions about things that they perhaps were not previously educated about (i.e., post-quantumc cryptographic primitives).

However, there is a lot of trust in the server at this point (entirely, essentially) if our interpretation of this excerpt is correct.

While this is troubling since that would render the client unable to gauge whether there is an evil replacement (& subequently, undermine the purpose of the entire setup) - this avoids the impossible hurdle of asking the client (end user) to run commands in the terminal, download + install liboqs, etc.

Potential Remedy

Assuming that this is not already in the code (these are notes are being taken in live time), the best solution to the issue above (assuming that it is genuinely an issue) would be to combine the liboqs algorithm with an already understood, non-pq algo.

These are called 'hybrid algorithms', per the liboqs documentation.

The liboqs library already allows for this. Below is an example in documentation (from their openssh-portable post quantum fork repo), that exemplifies this:

(link for reference = https://github.com/open-quantum-safe/openssh-portable)

Our Assumptions RE: Key Exchange Being Handled Server Side May Be Further Confirmed by the Client Configuration Files Underneath 'Src'

This can be seen under the tree /oqs-rs/oqs-kex-rpc/src/client

(github link for quick visual reference = https://github.com/mullvad/oqs-rs/tree/master/oqs-kex-rpc/src/client)

Specifically under the mod.rs crate

More relevantly, this screenshot:

The code comments here shed a lot more light.

It appears that:

The client is not setup to interpret the validity of the quantum key exchange itself - this is left up to the server. We're still antsy about the potential attack vector that this could create, but there are ways to mitigate this when looking at the other means by which this tunnel is established in the code excerpt from above.

When 'alice' (our hypothetical/example end user) initiates her tunnel connection with the pq-enabled Wireguard server, she is using the normal algorithms available with a default Wireguard installation in order to connect to the server.

This is indicated by the line in the code comments that states:

    /// Performs a full key exchange with all the algorithms in `algs` at the same time.
    ///
    /// This will compute Alice's message for each given algorithm, and send them in one RPC
    /// call to the server. The server will then compute the corresponding shared keys and Bob's
    /// messages. Then the server return Bob's messages and this client finally computes
    /// the shared keys and returns them.

From what we can see above, it appears that the steps are as follows:

A. 'Alice' initiates a connection with the server ; we'll assume that 'Bob' in this example is the website she's trying to access (youtube.com ; who knows)

B. The Wireguard client for 'Alice' will select one of its built-in cryptographic primitives for the key exchange (and also for her private key generation)

C. However, there is an extra step that is added on for the pq implementation of Wireguard because normally, Alice would solely be responsible for generating her own private keys. But since we're not going to burden Alice with becoming a professional cryptographer, network expert, and sysadmin - we'll assume that she just wants to press a button & connect. So we need to setup a 'middle man' to perform the pq-key generation for her

D. To facilitate this, Alice's client sends each algorithm that her Wireguard (out of the box) comes with. This allows the server to "then compute the corresponding shared keys and Bob's messages."

E. "Then the server returns Bob's messages and this client finally computes the shared keys and returns them."

The final four commented lines (of importance) reference the kex alg (OqsKexAlg variable) - see below:

    /// The returned vector has the same length as `algs` and the [`SharedKey`] at position `n`
    /// corresponds to the [`OqsKexAlg`] at position `n` in `algs`.
    ///
    /// [`SharedKey`]: struct.SharedKey.html
    /// [`OqsKexAlg`]: struct.OqsKexAlg.html

It appears that the pq-algorithm used for Alice (end user client) is contingent upon the regular elliptic curve signature / KEX that Alice's client decides to use to negotiate a connection with Wireguard.

Peering further down into this code, it appears that Wireguard appends a post-quantum kex / signature to Alice's pre-negotiated handshake in order to facilitate the post-quantum exchange:

This Could Work and Be Safe

This is a setup that gives us a bit more peace because it could work & be safe.

The reason why is because Alice ultimately must validate the message that's being received (as expected). Thus, if there is a non-pq public key that is supposed to be returning said messages & what Alice is sending to the server is already encrypted before the post-quantum KEX is attached to it, then, by default - her message should be verifiable because the key verification process with the server should never change.

The Only Vector That Exists Here (that we can see) = Whether Alice's message was verifiably upgraded with post-quantum strength encryption

There could be an error / failure on behalf of the server to properly negotiate this additional post-quantum handshake properly - resulting in failure.

^^^ Our assertion here relies on the assumption that Alice can receive & send messages to her recipient even in the event that the post quantum exchange that's handled & negotiated by the server that she's connecting to fails.

However, logically we imagine that this isn't the case (another question to lob to the Mullvad team to double check on this & ask for the relevant code references).

If the server does fail in such an event, then Alice can be sure that the post-quantum upgrade did not occur (because she won't be able to receive a connection / data back from recipient in the tunnel).

'Tests (repo)

This is under the same subdirectory that we were in before.

The 'tests' repo (at the same level as the 'src' that we were digging into above), provides a 'demo' that server admins compiling this same setup can use for themselves.

File can be found here (visually on GitHub) = https://github.com/mullvad/oqs-rs/blob/master/oqs-kex-rpc/tests/localhost.rs

Between lines 146-169 in the code for 'localhost.rs', it appears that our interpretation of the code in the previous section is confirmed (see below):

In the above excerpt, it appears the code dictates Alice (client) needs to authenticate with the server as she normally would and that it is the server's responsibility to compute an OQS-KEX to use from there.

However, Alice is also given something additional (beyond the message that she is crafting and sending to the server) that will allow her to verify on the client-side end of things that the oqs-kex negotiation failed (for whatever reason), despite not running her client in an environment built to recognize & process those cryptographic primitives.

Again, we'll refer to the Mullvad VPN team through an e-mail in order to get more answers about whether our presuppositions on the code is correct or not.

Conclusion

These notes only serve as 'part 1' to the series that we're publishing on building our post-quantum VPN.

There is another article that will be published in parallel that outlines all the reasons why we decided to scrap 'OpenVPN' as our VPN software of choice for the post-quantum VPN setup, in favor of Wireguard instead.

We will title that installment, 'Librehash Post-Quantum Setup Notes v1.01: Choosing Wireguard Over OpenVPN' or something to that effect.

Before the Next Installment (v2)

Ideally, we'll have a response in hand from the Mullvad team that either confirms or denies the assumptions that we have made looking at their code here.

We reached out to them several months ago to ask questions and they were extremely responsive and helpful, so we don't anticipate that it will be an issue this time around either.

Chances are, they may be a bit more interested inn assisting us since this would be an inevitable upgrade / update to their own VPN setup (assuming that they really didn't update their Wireguad configuration since publishing the code for their Rust-based post-quantum Wireguard fork in 2017).

If this is not the case, then we'll be sure to ask why the updated repository is not public (especially in light of the fact that this would be news to the general public & all of their customers).

Until next time (and if you have any questions that you would like us to send over to the MullvadVPN team, join our public Telegram channel t.me/librehashdiscussion and let us know what you think).

GO TOP