Merge branch 'update-post-quantum-experiment-v1'

9 files changed, 253 insertions, 74 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 572e38f197..17e28e5b65 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3232,6 +3232,7 @@ dependencies = [
  "rand 0.8.5",
  "serde",
  "x25519-dalek",
+ "zeroize",
 ]
 
 [[package]]
diff --git a/talpid-tunnel-config-client/Cargo.toml b/talpid-tunnel-config-client/Cargo.toml
index 62d6ab376b..d99e5eb13e 100644
--- a/talpid-tunnel-config-client/Cargo.toml
+++ b/talpid-tunnel-config-client/Cargo.toml
@@ -15,7 +15,7 @@ tonic = "0.8"
 prost = "0.11"
 tower = "0.4"
 tokio = "1"
-classic-mceliece-rust = { version = "2.0.0", features = ["mceliece8192128f"] }
+classic-mceliece-rust = { version = "2.0.0", features = ["mceliece460896f"] }
 
 [dev-dependencies]
 tokio = { version = "1", features = ["rt-multi-thread"] }
diff --git a/talpid-tunnel-config-client/examples/psk-exchange.rs b/talpid-tunnel-config-client/examples/psk-exchange.rs
index b4607be950..4c6a7dfe66 100644
--- a/talpid-tunnel-config-client/examples/psk-exchange.rs
+++ b/talpid-tunnel-config-client/examples/psk-exchange.rs
@@ -1,24 +1,25 @@
-use std::{
-    io,
-    net::{IpAddr, Ipv4Addr},
-};
+//! Example client implementing the quantum resistant tunnel PSK exchange.
+//! Useful to test this crate's implementation.
 
+use std::net::IpAddr;
 use talpid_types::net::wireguard::PublicKey;
 
 #[tokio::main]
 async fn main() {
-    println!("Make sure you're connected to a WireGuard peer and enter your public key: ");
+    let mut args = std::env::args().skip(1);
+    let tuncfg_server_ip: IpAddr = args
+        .next()
+        .expect("Give tuncfg server IP as first argument")
+        .parse()
+        .expect("tuncfg ip argument not a valid IP");
+    let pubkey_string = args
+        .next()
+        .expect("Give WireGuard public key as second argument");
+    let pubkey = PublicKey::from_base64(pubkey_string.trim()).expect("Invalid public key");
 
-    let mut pubkey_s = String::new();
-    io::stdin()
-        .read_line(&mut pubkey_s)
-        .expect("Failed to read from stdin");
-    let pubkey = PublicKey::from_base64(pubkey_s.trim()).expect("Invalid public key");
-
-    let (private_key, psk) =
-        talpid_tunnel_config_client::push_pq_key(IpAddr::V4(Ipv4Addr::new(10, 64, 0, 1)), pubkey)
-            .await
-            .unwrap();
+    let (private_key, psk) = talpid_tunnel_config_client::push_pq_key(tuncfg_server_ip, pubkey)
+        .await
+        .unwrap();
 
     println!("private key: {:?}", private_key);
     println!("psk: {:?}", psk);
diff --git a/talpid-tunnel-config-client/examples/tuncfg-server.rs b/talpid-tunnel-config-client/examples/tuncfg-server.rs
new file mode 100644
index 0000000000..e2f1a84045
--- /dev/null
+++ b/talpid-tunnel-config-client/examples/tuncfg-server.rs
@@ -0,0 +1,84 @@
+//! A server implementation of the tuncfg PskExchangeExperimentalV1 RPC to test
+//! the client side implementation.
+
+#[allow(clippy::derive_partial_eq_without_eq)]
+mod proto {
+    tonic::include_proto!("tunnel_config");
+}
+use classic_mceliece_rust::{PublicKey, CRYPTO_PUBLICKEYBYTES};
+use proto::{
+    post_quantum_secure_server::{PostQuantumSecure, PostQuantumSecureServer},
+    PskRequestExperimentalV0, PskRequestExperimentalV1, PskResponseExperimentalV0,
+    PskResponseExperimentalV1,
+};
+use talpid_types::net::wireguard::PresharedKey;
+
+use tonic::{transport::Server, Request, Response, Status};
+
+#[derive(Debug, Default)]
+pub struct PostQuantumSecureImpl {}
+
+#[tonic::async_trait]
+impl PostQuantumSecure for PostQuantumSecureImpl {
+    async fn psk_exchange_experimental_v0(
+        &self,
+        _request: Request<PskRequestExperimentalV0>,
+    ) -> Result<Response<PskResponseExperimentalV0>, Status> {
+        unimplemented!("Use V1 instead");
+    }
+
+    async fn psk_exchange_experimental_v1(
+        &self,
+        request: Request<PskRequestExperimentalV1>,
+    ) -> Result<Response<PskResponseExperimentalV1>, Status> {
+        let mut rng = rand::thread_rng();
+        let request = request.into_inner();
+
+        println!("wg_pubkey: {:?}", request.wg_pubkey);
+        println!("wg_psk_pubkey: {:?}", request.wg_psk_pubkey);
+
+        // The ciphertexts that will be returned to the client
+        let mut ciphertexts = Vec::new();
+        // The final PSK that is computed by XORing together all the KEM outputs.
+        let mut psk_data = Box::new([0u8; 32]);
+
+        for kem_pubkey in request.kem_pubkeys {
+            println!("\tKEM algorithm: {}", kem_pubkey.algorithm_name);
+            let (ciphertext, shared_secret) = match kem_pubkey.algorithm_name.as_str() {
+                "Classic-McEliece-460896f" => {
+                    let key_data: [u8; CRYPTO_PUBLICKEYBYTES] =
+                        kem_pubkey.key_data.as_slice().try_into().unwrap();
+                    let public_key = PublicKey::from(&key_data);
+                    let (ciphertext, shared_secret) =
+                        classic_mceliece_rust::encapsulate_boxed(&public_key, &mut rng);
+                    (ciphertext.as_array().to_vec(), *shared_secret.as_array())
+                }
+                name => panic!("Unsupported KEM algorithm: {name}"),
+            };
+
+            ciphertexts.push(ciphertext);
+            println!("\tshared secret: {:?}", shared_secret);
+            for (psk_byte, shared_secret_byte) in psk_data.iter_mut().zip(shared_secret.iter()) {
+                *psk_byte ^= shared_secret_byte;
+            }
+        }
+
+        let psk = PresharedKey::from(psk_data);
+        println!("psk: {:?}", psk);
+        println!("==============================================");
+        Ok(Response::new(PskResponseExperimentalV1 { ciphertexts }))
+    }
+}
+
+#[tokio::main]
+async fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let addr = "127.0.0.1:1337".parse()?;
+    let server = PostQuantumSecureImpl::default();
+
+    Server::builder()
+        .add_service(PostQuantumSecureServer::new(server))
+        .serve(addr)
+        .await?;
+
+    Ok(())
+}
diff --git a/talpid-tunnel-config-client/proto/tunnel_config.proto b/talpid-tunnel-config-client/proto/tunnel_config.proto
index 9ce4232d0d..215aa941c8 100644
--- a/talpid-tunnel-config-client/proto/tunnel_config.proto
+++ b/talpid-tunnel-config-client/proto/tunnel_config.proto
@@ -1,15 +1,3 @@
-//
-// If you need to (re)generate the gRPC code, see prerequisites
-//
-// 	https://grpc.io/docs/languages/go/quickstart/
-//
-// and then run
-//
-// 	protoc --go_out=. --go_opt=paths=source_relative --go-grpc_out=. --go-grpc_opt=paths=source_relative tunnel_config.proto
-//
-// from this directory.
-//
-
 syntax = "proto3";
 
 option go_package = "github.com/mullvad/wg-manager/server/tuncfg";
@@ -19,7 +7,71 @@ package tunnel_config;
 service PostQuantumSecure {
   // PskExchangeExperimentalV0 uses the common API defined by LibOQS.  See:
   // https://github.com/open-quantum-safe/liboqs
+  // This endpoint is deprecated in favor for `PskExchangeExperimentalV1`. Please use that instead.
   rpc PskExchangeExperimentalV0(PskRequestExperimentalV0) returns (PskResponseExperimentalV0) {}
+
+  // Allows deriving a preshared key (PSK) using one or multiple PQ-secure key-encapsulation
+  // mechanisms (KEM). The preshared key is added to WireGuard's preshared-key field in a new
+  // ephemeral peer (PQ-peer). This makes the tunnel resistant towards attacks using
+  // quantum computers.
+  //
+  // The VPN server associates the PQ-peer with the peer who performed the exchange. Any
+  // already existing PQ-peer for the normal peer is replaced. Each normal peer can have
+  // at most one PQ-peer.
+  //
+  // The PQ-peer is mutually exclusive to the normal peer. The server keeps both peers in memory,
+  // but only one of them is loaded into WireGuard at any point in time. A handshake from the
+  // normal peer unloads the corresponding PQ-peer from WireGuard and vice versa.
+  //
+  // A new peer is negotiated for PQ to avoid a premature break of the tunnel used for negotiation.
+  // A tunnel would break prematurely if the preshared key is applied before the normal peer
+  // received the server's contribution to the KEM exchange. This cannot occur now because
+  // the client decides when to switch to the PQ-secure tunnel. This design also allows
+  // the client to switch back to using a non-PQ-secure tunnel at any point.
+  //
+  // The negotiated PQ-peer is ephemeral. The server gives no guarantees how long it will be
+  // valid and working. The client should negotiate a new PQ-peer every time it establishes a new
+  // tunnel to the server.
+  //
+  // The full exchange requires just a single request-response round trip between the VPN client
+  // and the VPN server.
+  //
+  // # Request-response format
+  //
+  // The request from the VPN client contains:
+  //   * `wg_pubkey` - The public key used by the current tunnel (that the request travels inside).
+  //   * `wg_psk_pubkey` - A newly generated ephemeral WireGuard public key for the PQ-peer.
+  //     The server will associate the derived PSK with this public key.
+  //   * `kem_pubkeys` - A list describing the KEM algorithms. Must have at least one entry.
+  //                     The same KEM must not be listed more than once. Each list item contains:
+  //     * `algorithm_name` - The name of the KEM, including which variant. Should be the same
+  //       name/format that `liboqs` uses.
+  //     * `key_data` - The client's public key for this KEM. Will be used by the server to
+  //       encapsulate the shared secret for this KEM.
+  //
+  // The response from the VPN server contains:
+  //   * `ciphertexts` - A list of the ciphertexts (the encapsulated shared secrets) for all
+  //     public keys in `kem_pubkeys` in the request, in the same order as in the request.
+  //
+  // # Deriving the WireGuard PSK
+  //
+  // The PSK to be used in WireGuard's preshared-key field is computed by XORing the resulting
+  // shared secrets of all the KEM algorithms. All currently supported and planned to be
+  // supported algorithms output 32 bytes, so this is trivial.
+  //
+  // Since the PSK provided to WireGuard is directly fed into a HKDF, it is not important that
+  // the entropy in the PSK is uniformly distributed. The actual keys used for encrypting the
+  // data channel will have uniformly distributed entropy anyway, thanks to the HKDF.
+  // But even if that was not true, since both CME and Kyber run SHAKE256 as the last step
+  // of their internal key derivation, the output they produce are uniformly distributed.
+  //
+  // If we later want to support another type of KEM that produce longer or shorter output,
+  // we can hash that secret into a 32 byte hash before proceeding to the XOR step.
+  //
+  // Mixing with XOR (A = B ^ C) is fine since nothing about A is revealed even if one of B or C
+  // is known. Both B *and* C must be known to compute any bit in A. This means all involved
+  // KEM algorithms must be broken before the PSK can be computed by an attacker.
+  rpc PskExchangeExperimentalV1(PskRequestExperimentalV1) returns (PskResponseExperimentalV1) {}
 }
 
 message PskRequestExperimentalV0 {
@@ -36,3 +88,18 @@ message KemPubkeyExperimentalV0 {
 message PskResponseExperimentalV0 {
   bytes ciphertext = 1;
 }
+
+message PskRequestExperimentalV1 {
+  bytes wg_pubkey = 1;
+  bytes wg_psk_pubkey = 2;
+  repeated KemPubkeyExperimentalV1 kem_pubkeys = 3;
+}
+
+message KemPubkeyExperimentalV1 {
+  string algorithm_name = 1;
+  bytes key_data = 2;
+}
+
+message PskResponseExperimentalV1 {
+  repeated bytes ciphertexts = 1;
+}
diff --git a/talpid-tunnel-config-client/src/kem.rs b/talpid-tunnel-config-client/src/classic_mceliece.rs
index 778c66a0aa..dbba95f067 100644
--- a/talpid-tunnel-config-client/src/kem.rs
+++ b/talpid-tunnel-config-client/src/classic_mceliece.rs
@@ -1,6 +1,9 @@
-use classic_mceliece_rust::keypair_boxed;
-use talpid_types::net::wireguard::PresharedKey;
+use classic_mceliece_rust::{keypair_boxed, SharedSecret};
 
+/// The `keypair_boxed` function needs just under 1 MiB of stack in debug
+/// builds. Even though it probably works to run it directly on the main
+/// thread on all OSes, we take this precaution and always generate the huge
+/// keys on a separate thread with a large enough stack.
 const STACK_SIZE: usize = 2 * 1024 * 1024;
 
 pub use classic_mceliece_rust::{Ciphertext, PublicKey, SecretKey, CRYPTO_CIPHERTEXTBYTES};
@@ -19,7 +22,6 @@ pub async fn generate_keys() -> (PublicKey<'static>, SecretKey<'static>) {
     rx.await.unwrap()
 }
 
-pub fn decapsulate(secret: &SecretKey, ciphertext: &Ciphertext) -> PresharedKey {
-    let shared_secret = classic_mceliece_rust::decapsulate_boxed(ciphertext, secret);
-    PresharedKey::from(*shared_secret.as_array())
+pub fn decapsulate(secret: &SecretKey, ciphertext: &Ciphertext) -> SharedSecret<'static> {
+    classic_mceliece_rust::decapsulate_boxed(ciphertext, secret)
 }
diff --git a/talpid-tunnel-config-client/src/lib.rs b/talpid-tunnel-config-client/src/lib.rs
index 4dce3edf67..de7db33c26 100644
--- a/talpid-tunnel-config-client/src/lib.rs
+++ b/talpid-tunnel-config-client/src/lib.rs
@@ -2,7 +2,7 @@ use std::{fmt, net::IpAddr};
 use talpid_types::net::wireguard::{PresharedKey, PrivateKey, PublicKey};
 use tonic::transport::Channel;
 
-mod kem;
+mod classic_mceliece;
 
 #[allow(clippy::derive_partial_eq_without_eq)]
 mod proto {
@@ -13,7 +13,8 @@ mod proto {
 pub enum Error {
     GrpcConnectError(tonic::transport::Error),
     GrpcError(tonic::Status),
-    InvalidCiphertext,
+    InvalidCiphertextLength { actual: usize, expected: usize },
+    InvalidCiphertextCount { actual: usize },
 }
 
 impl std::fmt::Display for Error {
@@ -22,7 +23,13 @@ impl std::fmt::Display for Error {
         match self {
             GrpcConnectError(_) => "Failed to connect to config service".fmt(f),
             GrpcError(status) => write!(f, "RPC failed: {}", status),
-            InvalidCiphertext => "The service returned an invalid ciphertext".fmt(f),
+            InvalidCiphertextLength { actual, expected } => write!(
+                f,
+                "Expected a ciphertext of length {expected}, got {actual} bytes"
+            ),
+            InvalidCiphertextCount { actual } => {
+                write!(f, "Expected 1 ciphertext in the response, got {actual}")
+            }
         }
     }
 }
@@ -41,7 +48,9 @@ type RelayConfigService = proto::post_quantum_secure_client::PostQuantumSecureCl
 /// Port used by the tunnel config service.
 pub const CONFIG_SERVICE_PORT: u16 = 1337;
 
-const ALGORITHM_NAME: &str = "Classic-McEliece-8192128f";
+/// Use the smallest CME variant with NIST security level 3. This variant has significantly smaller
+/// keys than the larger variants, and is considered safe.
+const CLASSIC_MCELIECE_VARIANT: &str = "Classic-McEliece-460896f";
 
 /// Generates a new WireGuard key pair and negotiates a PSK with the relay in a PQ-safe
 /// manner. This creates a peer on the relay with the new WireGuard pubkey and PSK,
@@ -52,28 +61,53 @@ pub async fn push_pq_key(
     wg_pubkey: PublicKey,
 ) -> Result<(PrivateKey, PresharedKey), Error> {
     let wg_psk_privkey = PrivateKey::new_from_random();
-    let (kem_pubkey, kem_secret) = kem::generate_keys().await;
+    let (cme_kem_pubkey, cme_kem_secret) = classic_mceliece::generate_keys().await;
 
     let mut client = new_client(service_address).await?;
     let response = client
-        .psk_exchange_experimental_v0(proto::PskRequestExperimentalV0 {
+        .psk_exchange_experimental_v1(proto::PskRequestExperimentalV1 {
             wg_pubkey: wg_pubkey.as_bytes().to_vec(),
             wg_psk_pubkey: wg_psk_privkey.public_key().as_bytes().to_vec(),
-            kem_pubkey: Some(proto::KemPubkeyExperimentalV0 {
-                algorithm_name: ALGORITHM_NAME.to_string(),
-                key_data: kem_pubkey.as_array().to_vec(),
-            }),
+            kem_pubkeys: vec![proto::KemPubkeyExperimentalV1 {
+                algorithm_name: CLASSIC_MCELIECE_VARIANT.to_owned(),
+                key_data: cme_kem_pubkey.as_array().to_vec(),
+            }],
         })
         .await
         .map_err(Error::GrpcError)?;
 
-    let ciphertext_array: [u8; kem::CRYPTO_CIPHERTEXTBYTES] = response
-        .into_inner()
-        .ciphertext
-        .try_into()
-        .map_err(|_| Error::InvalidCiphertext)?;
-    let ciphertext = kem::Ciphertext::from(ciphertext_array);
-    Ok((wg_psk_privkey, kem::decapsulate(&kem_secret, &ciphertext)))
+    let ciphertexts = response.into_inner().ciphertexts;
+    // Unpack the ciphertexts into one per KEM without needing to access them by index.
+    let [cme_ciphertext] = <&[Vec<u8>; 1]>::try_from(ciphertexts.as_slice()).map_err(|_| {
+        Error::InvalidCiphertextCount {
+            actual: ciphertexts.len(),
+        }
+    })?;
+
+    // Store the PSK data on the heap. So it can be passed around and then zeroized on drop without
+    // being stored in a bunch of places on the stack.
+    let mut psk_data = Box::new([0u8; 32]);
+    // Decapsulate Classic McEliece and mix into PSK
+    {
+        let ciphertext_array =
+            <[u8; classic_mceliece::CRYPTO_CIPHERTEXTBYTES]>::try_from(cme_ciphertext.as_slice())
+                .map_err(|_| Error::InvalidCiphertextLength {
+                actual: cme_ciphertext.len(),
+                expected: classic_mceliece::CRYPTO_CIPHERTEXTBYTES,
+            })?;
+        let ciphertext = classic_mceliece::Ciphertext::from(ciphertext_array);
+        let shared_secret = classic_mceliece::decapsulate(&cme_kem_secret, &ciphertext);
+        xor_assign(&mut psk_data, shared_secret.as_array());
+    }
+
+    Ok((wg_psk_privkey, PresharedKey::from(psk_data)))
+}
+
+/// Performs `dst = dst ^ src`.
+fn xor_assign(dst: &mut [u8; 32], src: &[u8; 32]) {
+    for (dst_byte, src_byte) in dst.iter_mut().zip(src.iter()) {
+        *dst_byte ^= src_byte;
+    }
 }
 
 async fn new_client(addr: IpAddr) -> Result<RelayConfigService, Error> {
diff --git a/talpid-types/Cargo.toml b/talpid-types/Cargo.toml
index ff007b74ab..4db8315c99 100644
--- a/talpid-types/Cargo.toml
+++ b/talpid-types/Cargo.toml
@@ -14,6 +14,7 @@ base64 = "0.13"
 x25519-dalek = { version = "2.0.0-pre.1" }
 rand = "0.8.5"
 err-derive = "0.3.1"
+zeroize = "1.5.7"
 
 [target.'cfg(target_os = "android")'.dependencies]
 jnix = { version = "0.5", features = ["derive"] }
diff --git a/talpid-types/src/net/wireguard.rs b/talpid-types/src/net/wireguard.rs
index 8306c773a1..b5c3268af5 100644
--- a/talpid-types/src/net/wireguard.rs
+++ b/talpid-types/src/net/wireguard.rs
@@ -9,6 +9,7 @@ use std::{
     hash::{Hash, Hasher},
     net::{IpAddr, Ipv4Addr, Ipv6Addr, SocketAddr},
 };
+use zeroize::{Zeroize, ZeroizeOnDrop};
 
 /// Tunnel parameters required to start a `WireguardMonitor`.
 /// See [`crate::net::TunnelParameters`].
@@ -55,7 +56,10 @@ pub struct PeerConfig {
     pub allowed_ips: Vec<IpNetwork>,
     /// IP address of the WireGuard server.
     pub endpoint: SocketAddr,
-    /// Preshared key.
+    /// Preshared key (PSK). The PSK should never be persisted, so it does not serialize
+    /// or deserialize. A PSK is only used with quantum-resistant tunnels and are then
+    /// ephemeral and living in memory only.
+    #[serde(skip)]
     pub psk: Option<PresharedKey>,
 }
 
@@ -260,40 +264,25 @@ impl fmt::Display for PublicKey {
     }
 }
 
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub struct PresharedKey([u8; 32]);
+/// A WireGuard preshared key (PSK). Used to make the tunnel quantum-resistant.
+#[derive(Debug, Clone, PartialEq, Eq, Hash, Zeroize, ZeroizeOnDrop)]
+pub struct PresharedKey(Box<[u8; 32]>);
 
 impl PresharedKey {
-    /// Get the PSK as bytes
+    /// Get the PSK as bytes. Try to move or dereference this data as little as possible,
+    /// since copying it to more memory locations potentially leaves the secret in more memory
+    /// locations.
     pub fn as_bytes(&self) -> &[u8; 32] {
         &self.0
     }
 }
 
-impl From<[u8; 32]> for PresharedKey {
-    fn from(key: [u8; 32]) -> PresharedKey {
+impl From<Box<[u8; 32]>> for PresharedKey {
+    fn from(key: Box<[u8; 32]>) -> PresharedKey {
         PresharedKey(key)
     }
 }
 
-impl Serialize for PresharedKey {
-    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
-    where
-        S: Serializer,
-    {
-        serialize_key(&self.0, serializer)
-    }
-}
-
-impl<'de> Deserialize<'de> for PresharedKey {
-    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
-    where
-        D: Deserializer<'de>,
-    {
-        deserialize_key(deserializer)
-    }
-}
-
 fn serialize_key<S>(key: &[u8; 32], serializer: S) -> Result<S::Ok, S::Error>
 where
     S: Serializer,