Quantum-safe Secure Key Exchange White Paper

The BlazeQ Key Agreement Protocol

Introduction

This document outlines the BlazeQ Key Agreement Protocol. BlazeQ enables two parties to establish a shared secret key while mutually authenticating each other through public keys. BlazeQ offers post-quantum forward secrecy.

BlazeQ is designed for asynchronous environments, where one party (“Bob”) is offline but has made certain information available on a server. Another party (“Alice”) can use this published data to securely send encrypted information to Bob and establish a shared secret key for future communications.

Preliminaries

This document will use the following notation:

X || Y is the concatenation of byte sequences X and Y.

DH(SK, PK) denotes the byte sequence representing the shared secret generated by an Elliptic Curve Diffie-Hellman (ECDH) operation, where SK is the private key from one key pair and PK is the public key from a different key pair. The shared secret is derived by combining these two keys.

SIG(SK, M) represents a signature on the message M generated using either the Ed25519 or Ed448 signing algorithm, where SK is the private key. The signature can be verified using the corresponding public key derived from SK.

ML-DSA-SIG(SK, M) represents a signature on the message M generated using one of the ML-DSA signing algorithms (ML-DSA-44, ML-DSA-65, or ML-DSA-87), where SK is the private key. The signature can be verified using the corresponding public key derived from SK.

(CT, SS) = ML-KEM-ENC(PK) represents a tuple consisting of the KEM ciphertext CT, generated by the ML-KEM algorithm (with variants ML-KEM-512, ML-KEM-768, or ML-KEM-1024 depending on the key sizes), and the shared secret SS, encapsulated by the ciphertext using the public key PK.

ML-KEM-DEC(SK, CT) represents the shared secret SS decapsulated from the pqkem ciphertext CT using the private key SK, which is the counterpart to the public key PK used for encapsulating the ciphertext.

Roles

The BlazeQ protocol involves three key participants: Alice, Bob, and a server.

Alice seeks to send encrypted data to Bob while also establishing a shared secret key for secure, bidirectional communication.
Bob aims to facilitate secure communication with parties like Alice, allowing them to establish a shared key and send encrypted data. However, Bob may not always be online when Alice tries to initiate this process. To address this, Bob has a relationship with a server.
The server serves two main functions: it stores messages from Alice to Bob, which Bob can retrieve later when online, and it enables Bob to publish data that Alice can access when attempting to establish the shared key. The level of trust required in the server is an important consideration.

In our implementation, the server’s role is distributed across multiple entities, but for simplicity, this protocol assumes a single server that performs all these functions for Alice and Bob.

Curve Keys

BlazeQ uses the following elliptic curve keys:

IKa Alice’s elliptic curve identity key.
IKb Bob’s elliptic curve identity key.
EKa Alice’s elliptic curve ephemeral key.
LKb Bob’s elliptic curve long-lived key.
SPKb Bob’s elliptic curve short-lived pre-generated key.
(OPKb1, OPKb2, OPKb3, …) Bob’s set of elliptic curve one-time pre-generated keys.

Post-Quantum Key Encapsulation Keys

BlazeQ uses the following post-quantum keys:

PQIKa Alice’s post-quantum identity key.
PQIKb Bob’s post-quantum identity key.
PQLKb Bob’s post-quantum long-lived key.
PQSPKb Bob’s post-quantum short-lived pre-generated key.
(PQOPKb1, PQOPKb2, PQOPKb3, …) Bob’s set of post-quantum one-time pre-generated keys.

Overview

BlazeQ has three phases:

Bob publishes his elliptic curve identity key, post quantum identity key, elliptic curve pre-generated keys, post quantum pre-generated keys to a server.
Alice retrieves identity keys and a “pre-generated key bundle” from the server and uses it to send an initial message to Bob.
Bob receives and processes Alice’s initial message.

Publishing keys

Bob publishes a set of curve keys to the server containing:

Bob’s elliptic curve identity key IKb.
Bob’s signed elliptic curve long-lived key and its identifier (LKb, Id(LKb)).
Bob’s signature on the elliptic curve long-lived curve key SIG(IKb, LKb).
Bob’s signed elliptic curve short-lived pre-generated key and its identifier (SPKb, Id(SPKb)).
Bob’s signature on the elliptic curve short-lived pre-generated key SIG(IKb, SPKb).
A set of Bob’s elliptic curve one-time pre-generated keys (OPKb1, OPKb2, OPKb3, …) along with their identifiers (Id(OPKb1), Id(OPKb2), Id(OPKb3), …).
The set of Bob’s signatures on the elliptic curve signed one-time pre-generated keys (SIG(IKb, OPKb1), SIG(IKb, OPKb2), SIG(IKb, OPKb3), …).

Bob publishes a set of post-quantum keys to the server containing:

Bob’s post-quantum identity key PQIKb.
Bob’s signed post-quantum long-lived key and its identifier (PQLKb, Id(PQLKb)).
Bob’s signature on the post-quantum long-lived key ML-DSA-SIG(PQIKb, PQLKb).
Bob’s signed post-quantum short-lived pre-generated key and its identifier (PQSPKb, Id(PQSPKb)).
Bob’s signature on the post-quantum short-lived pre-generated key ML-DSA-SIG(PQIKb, PQSPKb).
A set of Bob’s post-quantum one-time pre-generated keys (PQOPKb1, PQOPKb2, PQOPKb3, …) along with their identifiers (Id(PQOPKb1), Id(PQOPKb2), Id(PQOPKb3), …).
The set of Bob’s signatures on the signed post-quantum one-time pre-generated keys (ML-DSA-SIG(PQIKb, PQOPKb1), ML-DSA-SIG(PQIKb, PQOPKb2), ML-DSA-SIG(PQIKb, PQOPKb3), …).

Sending a message

To initiate a BlazeQ key agreement with Bob, Alice contacts the server to retrieve a “pre-generated key bundle”.

The pre-generated key bundle includes the following curve keys:

Bob’s elliptic curve identity key (IKb).
Bob’s signed elliptic curve long-lived key, along with its identifier: (LKb, Id(LKb)).
Bob’s signature on the elliptic curve long-lived key: SIG(IKb, LKb).
Bob’s signed elliptic curve short-lived pre-generated key, along with its identifier: (SPKb, Id(SPKb)).
Bob’s signature on the elliptic curve short-lived pre-generated key: SIG(IKb, SPKb).
Bob’s signed elliptic curve one-time curve pre-generated key, along with its identifier: (OPKb, Id(OPKb)).
Bob’s signature on the elliptic curve one-time pre-generated key: SIG(IKb, OPKb).

The pre-generated key bundle includes the following post-quantum keys:

Bob’s post-quantum identity key (PQIKb).
Bob’s signed post-quantum long-lived key, along with its identifier: (PQLKb, Id(PQLKb)).
Bob’s signature on the post-quantum long-lived key: ML-DSA-SIG(PQIKb, PQLKb).
Bob’s signed post-quantum short-lived pre-generated key, along with its identifier: (SPKb, Id(PQSPKb)).
Bob’s signature on the post-quantum short-lived pre-generated key: ML-DSA-SIG(PQIKb, PQSPKb).
Bob’s signed post-quantum one-time pre-generated key, along with its identifier: (PQOPKb, Id(PQOPKb)).
Bob’s signature on the post-quantum one-time pre-generated key: ML-DSA-SIG(PQIKb, PQOPKb).

The server should provide one of Bob’s available one-time pre-generated keys, if any exist, and then delete the key after use. If all of Bob’s one-time pre-generated keys have been deleted, the bundle will not include a one-time pre-generated element.

Alice should prioritize using one of Bob’s available one-time signed pre-generated keys. If all of Bob’s one-time signed pre-generated keys on the server have been used, Alice should then use Bob’s short-lived signed pre-generated key.

Alice verifies the signatures on the pre-generated keys. If any signature verification fails, Alice aborts the protocol. If all signature checks pass, Alice proceeds to generate an ephemeral curve key, EKa then she calculates:

DH1 = DH(LKa, LKb)
DH2 = DH(EKa, LKb)
DH3 = DH(EKa, OPKb) if exists OPKb else DH3 = DH(EKa, SPKb)
DH4 = DH(LKa, OPKb) if exists OPKb else DH4 = DH(LKa, SPKb)

Alice generates a post-quantum encapsulated shared secret using one of Bob’s available one-time pre-generated keys, if any exist. If no such keys are available, she generates the shared secret using Bob’s short-lived pre-generated key. In parallel, Alice also generates a post-quantum encapsulated shared secret using Bob’s long-lived key.

(CT1, SS1) = ML-KEM-ENC(PQLKb)
(CT2, SS2) = ML-KEM-ENC(PQOPKb) if exists PQOPKb else (CT2, SS2) = ML-KEM-ENC(PQSPKb)

Finally, Alice computes the shared key SK using key derivation function KDF as follows:

SK = KDF(DH1 || DH2 || DH3 || DH4 || SS1 || SS2)

Alice then sends Bob an initial message containing:

Alice’s elliptic curve identity key IKa.
Alice’s elliptic curve long-lived key LKa.
Alice’s elliptic curve ephemeral key EKa.
The post-quantum ciphertexts CT1 and CT2 encapsulating respectively SS1 and SS2.
Alice’s signatures on the post-quantum ciphertexts CT1 and CT2: ML-DSA-SIG(PQIKa, CT1), ML-DSA-SIG(PQIKa, CT2)
Identifiers stating which of Bob’s pre-generated keys Alice used.
An initial ciphertext encrypted with some AEAD encryption scheme (AES-GCM) using AD as associated data and using an encryption key which is either SK or the output from some cryptographic PRF keyed by SK.

Receiving a message

Bob retrieves the following values from Alice’s initial message:

Alice’s elliptic curve identity key (IKa).
Alice’s elliptic curve long-lived key (LKa).
Alice’s elliptic curve ephemeral key (EKa).
Post-quantum ciphertexts (CT1, CT2).
Identifiers of the pre-generated keys used by Alice.
The AEAD-encrypted initial ciphertext.
Bob verifies that the pre-generated keys Alice used correspond to those he provided to the server. This ensures that Alice is using valid pre-generated keys:
If the identifier corresponds to a one-time key, Bob verifies that the key has not been previously used and deletes it after this session.
If a one-time key is unavailable, Bob verifies that Alice used his short-lived key.

Bob computes the necessary Diffie-Hellman shared secrets:

DH1 = DH(LKb, LKa)
DH2 = DH(LKb, EKa)
DH3 = DH(OPKb, EKa) if OPKb exists, otherwise DH3 = DH(SPKb, EKa)
DH4 = DH(OPKb, LKa) if OPKb exists, otherwise DH4 = DH(SPKb, LKa)

Bob decrypts the post-quantum encapsulated shared secrets:

SS1 = ML-KEM-DEC(PQLKb, CT1)
SS2 = ML-KEM-DEC(PQOPKb, CT2) if PQOPKb exists, else SS2 = ML-KEM-DEC(PQSPKb, CT2)

Bob derives the shared key using the key derivation function KDF:

SK = KDF(DH1 || DH2 || DH3 || DH4 || SS1 || SS2)

Security Considerations

The security of the BlazeQ protocol has been carefully designed to ensure secure key establishment and forward secrecy in the presence of quantum adversaries. While the protocol leverages both classical elliptic curve Diffie-Hellman (ECDH) and post-quantum key encapsulation mechanisms (PQKEM), it is crucial to consider the potential attack vectors and assumptions behind the protocol’s security.

BlazeQ guarantees post-quantum forward secrecy through the use of a hybrid approach, combining elliptic curve-based key exchange (ECDH) with post-quantum KEM. The key establishment process requires solving both the classical Diffie-Hellman problem and the post-quantum security assumption for the KEMs, which offers strong resistance against quantum attacks targeting either component.

In this section, we outline the main security properties of BlazeQ, including authentication, deniability, and resilience against common attacks.

Authentication

BlazeQ guarantees mutual authentication between Alice and Bob by employing a dual-signature approach, combining elliptic curve signatures with post-quantum cryptographic signatures. This hybrid mechanism ensures robust authentication, even against quantum-capable adversaries. However, before or after a key agreement is made, Alice and Bob should independently authenticate each other’s identity through an out-of-band method (e.g., fingerprint comparison or QR code scanning).

If such a method is not employed, the protocol does not offer a guarantee of who the parties are, particularly in the presence of a malicious server or man-in-the-middle attack.

Deniability

BlazeQ supports cryptographic deniability, meaning that it does not offer participants a cryptographic proof of the content of their communication or evidence that they communicated in the first place.

The protocol aims for offline deniability, where if a third party (e.g., a judge) obtains access to one of the participants’ secret keys, they cannot prove the communication took place based solely on the transcript. This property is important when the communication occurs in a situation where one party might need to later deny involvement.

Deniability in the case of a quantum adversary remains a challenge. Future revisions may introduce mechanisms that provide quantum-safe deniability.

Forward Secrecy

Forward secrecy in BlazeQ is guaranteed through the use of ephemeral keys and one-time pre-generated keys. Even if a participant’s long-term private key is compromised in the future, previous session keys (SK) will remain secure. This is ensured by deleting the one-time pre-generated keys after each use and using ephemeral keys to establish the session key.

In the event of key compromise, session keys are protected as long as ephemeral and pre-generated keys are properly managed. The protocol offers forward secrecy even if a party’s private key is later compromised, so long as the relevant one-time or ephemeral keys are not reused or exposed.

Key Compromise

Key compromise scenarios pose significant security risks, but BlazeQ incorporates strategies to mitigate these risks. The compromise of a participant’s private key can lead to impersonation or the leakage of session keys from past communications. However, the protocol ensures that compromised keys do not immediately compromise the security of future communications.

Compromise of Identity Keys: If a participant’s identity key (e.g., IKa or PQIKa) is compromised, their ability to authenticate in future sessions is affected. However, previous sessions’ session keys will remain secure as long as ephemeral or pre-generated keys were not exposed.

Compromise of Pre-Generated Keys: The compromise of pre-generated keys (e.g., SPKb, PQSPKb) could potentially compromise past session keys that used these pre-generated keys. Frequent rotation of pre-generated keys and the use of a ratcheting protocol can mitigate this risk by updating session keys frequently.

Compromise of One-Time Pre-Generated Keys: If an attacker compromises a one-time pre-generated key (e.g., OPKb or PQOPKb) during or after a session, it can only affect that particular session. However, as these keys are deleted after use, the attacker cannot reuse them, and the impact is limited to the single session.

A more comprehensive analysis of key compromise scenarios is outside the scope of this document but is critical for the continued security of the protocol.

Passive Quantum Adversaries

BlazeQ is specifically designed to mitigate the risk of “harvest now, decrypt later” attacks by adversaries who possess a quantum computer capable of computing discrete logarithms on elliptic curves. The security of BlazeQ is primarily rooted in the post-quantum key exchange mechanism (PQKEM), but it also depends on the ability of AEAD (Authenticated Encryption with Associated Data) to provide post-quantum IND-CPA (Indistinguishability under Chosen-Plaintext Attack) and INT-CTXT (Integrity under Chosen-Ciphertext Attack) security.

There is significant uncertainty in assessing the post-quantum security strength of cryptosystems, making it difficult to define this requirement with absolute precision. However, by referring to the NIST evaluation criteria for post-quantum cryptography submissions, one can infer that AES256’s key-search resistance places it at the highest security level. Although this doesn’t directly match our specific security needs, it suggests that using an appropriate AEAD mode based on AES256 will likely be adequate. Below are some key security properties of BlazeQ in this context:

Quantum-resilient Public Key Protection: If an attacker has recorded the public data and the message sent from Alice to Bob, having access to a quantum computer will not allow them to compromise the session’s secret key (SK).

Security of One-Time Pre-generated Keys: If a post-quantum key encapsulation one-time pre-generated key (PQOPKB) is used in a protocol session and properly deleted after use, any future access to a quantum computer will not enable the attacker to recover the SK, even after the pre-generated key’s deletion.

Impact of Missing One-Time Pre-Generated Keys: If a post-quantum one-time pre-generated key was not used during the protocol run, then access to a quantum computer and the compromise of the private key for PQSPKB could potentially reveal the SK calculated during that session. To mitigate this risk, it is recommended to frequently replace signed pre-generated keys and use a ratcheting protocol, which quickly rotates the SK with fresh keys to ensure forward secrecy.

Active Quantum Adversaries

BlazeQ is specifically designed to protect against active quantum adversaries. An active attacker with access to a quantum computer capable of computing discrete logarithms on elliptic curves can compute DH(PK1, PK2) and Sig(PK, M) for all elliptic curve keys (PK1, PK2, and PK). However, BlazeQ incorporates post-quantum cryptographic techniques, including post-quantum signing, which ensures that even with a quantum computer, an attacker cannot impersonate Alice or Bob.

In the event of a malicious server attempting to impersonate Bob, BlazeQ allows Bob to use a post-quantum identity key to sign his post-quantum pre-generated keys, ensuring that Alice can cryptographically verify that she is indeed communicating with Bob. This provides Alice with the confidence that the pre-generated key bundle she receives comes from Bob, preventing man-in-the-middle attacks by an adversary with quantum capabilities.

Moreover, BlazeQ guarantees mutual authentication, which means that both Alice and Bob can be assured of each other’s identities. Alice has a cryptographic guarantee that she is communicating with Bob, and Bob similarly has a cryptographic guarantee that he is communicating with Alice. This mutual authentication is achieved through the use of post-quantum signatures, which protect the integrity of the exchanged keys and prevent attackers from forging or tampering with the communication.