Transitioning to quantum-safe communication: Adding Q-safe preference to OpenSSL TLSv1.3

Future quantum computers will be able to break the asymmetric cryptographic algorithms widely in use online today. The US National Security Agency has issued a list of approved quantum-safe (or Q-safe) algorithms, as well as a timeline for transition in the CNSA 2.0, Commercial National Security Algorithm Suite. For TLS (Transport Layer Security, RFC 8446), the approved algorithms for key agreements and certificates are ML-KEM (FIPS-203) and ML-DSA (FIPS-204) or SPINCS+ (FIPS-205) respectively. These were all co-developed by researchers at IBM.

CNSA 2.0 Specifically, the NSA states: ''developments will be required to support CNSA 2.0 algorithms once appropriate standards for the given technology are in place. All appropriate system components should be configured to prefer CNSA 2.0 algorithms. As products mature, those components should be configured to accept only CNSA 2.0 algorithms.''allows the transition to happen in two phases, where the algorithms of CNSA 2.0 should be preferred during the first phase (while older algorithms are still allowed) and exclusively be used in the second phase.

While this two-phase transition seems like a natural choice, the “prefer” aspect in the first phase causes a concern: The TLS standard isn’t mandating such preference. The TLS standard allows both the client and the server a high degree of freedom in choosing cryptographic algorithms and their preferences. Consequently, there is an urgent need for a way to configure TLS connections to enable preference for CNSA 2.0 algorithms.

The TLS standard

The TLS standard ensures confidentiality by encrypting all network traffic right after an initial key agreement between the client and the server. For this key agreement, the client initiates the session establishment by sending a list of its supported algorithms for a key agreement in a ClientHello message to the server as well as a few speculative key shares for some of the supported algorithms. The supported algorithms are commonly known as groups or curves.

If the server finds an acceptable key share in the ClientHello message, it can immediately send their own key share for the selected algorithm back to the client in a ServerHello (SH) message. Both parties now have sufficient information to establish a common key and can proceed with the session, exchanging encrypted messages.

However, if the server does not identify a suitable client key share but finds one of the remaining client-supported algorithms acceptable, it will inform the client about the acceptable algorithm and implicitly request a key share for this algorithm in a HelloRetryRequest (HRR) message. This causes an additional communication round-trip over the network. And while the computation of key pairs typically happens within some tens of micro-seconds, the network induced latency for an extra communication round caused by a HRR message can easily reach tens of milli-seconds. The desire to minimize extra network roundtrips is clear.

The challenges

Considering CNSA 2.0, it is instrumental to enable a client to indicate preference for Q-safe algorithms and the server to preferably select such algorithms.

As the TLS standard is not to be changed, it’s necessary to achieve new requirements for algorithm selection purely by enhancing the configuration capabilities. In the past, the list of supported algorithms in OpenSSL was configured as a colon-separated list of algorithm names. This approach is also used by many applications which leverage OpenSSL under the hood, such as example cURL, HAproxy, and Nginx. Any changes to the configuration capabilities must be made in a way that allows applications to seamlessly use the new configuration capabilities — whether in their own configuration files or on the command line — without requiring any code changes for widely used programs and libraries.

The OpenSSL code base also consists of more than 500,000 lines of code, with around 70,000 of them devoted to TLS alone. Any changes must be made without impacting the functionality of other functions, additions or changes to the source code made in only a few pinpointed locations within this large code base. And any changes must maintain full backward compatibility to allow continuation of smooth operation during a transition phase.

The solution: Client-side

We started out by analyzing the configuration method used for the initial key agreement during a TLS session establishment, which so far consisted of the colon-separated list of algorithms used by client and server alike.

For the client, we identified the need to specify a list of supported algorithms and the ability for a client to send key shares for multiple algorithms in a well-controlled manner. Combining this new requirement with the existing specification via the colon-separated list of algorithms, we quickly concluded that adding a prefix character to an algorithm name would be an efficient way to indicate that a key share for this algorithm should be generated and sent in the ClientHello message.

The prefix character had to be chosen such that the most widely command line interfaces (like bash or sh) would not intercept and process it, such as the semicolon character (end of command) or backslash character (escape). The prefix character should also not be an option as a first character in any of the algorithm names.

The ‘*’ star character was identified to serve such a purpose well. As such, we added code to OpenSSL which would identify a ‘*’ prefix character while parsing the colon-separated list of algorithms and consequently add a key share for each occurrence. To avoid network overload on the server side caused by the considerable size of key shares for Q-safe algorithms (measured in KBs vs just a few bytes for legacy key shares), we deliberately limited the number of key shares to be sent by a client to four. This is changeable via a build option within the OpenSSL code base. This number was chosen with the intent to allow key shares to be sent for: One fully Q-safe algorithm, one hybrid algorithm, and one legacy algorithm, with one spare available. For backward compatibility, our code is automatically adding a single key share for the first algorithm in the list if no ‘*’ prefix character is used anywhere in the colon separated list.

As an example, the following list “*ML_KEM-1024:ML-KEM-512:*x25519” would indicate support for the four named algorithms in the list, and would also send a key share for ML-KEM-1024 and x25519.

This was the easy part of enhancing the OpenSSL functionality.

The solution: Server-side

As we mentioned, the TLS standard does not mandate any specific methodology for the server to make its choice which algorithm offered by the client it should select for the key agreement. However, to avoid round trips, it is common that the server first checks the available key shares and selects one of the algorithms to use. The key shares therefore implicitly define a first priority level. A second priority level is defined by the sequence of the supported algorithms announced by the client: The server either selects the first supported algorithm that overlaps with its own list, which is commonly known as the client preference mode of operation, or it selects the first algorithm in its own list which overlaps with the client-supported algorithms, which is commonly known as the server preference mode of operation.

But adding the requirement to not only support, but also prefer, Q-safe algorithms implies the presence of a third priority level, for which – in addition to the key shares and list of supported algorithms – no feature of the TLS standard is readily available to be used for that. Some new way to specify such an additional hierarchy was therefore required.

Again, we looked at the existing specification of algorithms via colon-separated list. We realized that by replacing some of the colons in the list of algorithms with some other character, it is possible to define tuples of algorithms for which the server assumes equivalent security levels. In this case too, such a character had to be chosen such that command line shells would ignore the character. Initially, we played around with curly braces “{}” to define tuples but finally selected the slash “/” character as a single tuple delimiting character.

With that, we had the necessary ingredients at hand to have the server select an algorithm for the session establishment key agreement making use of three priority levels: The highest priority level is implemented by processing one tuple after the other, starting from the left side of the configuration string. The next two levels are defined by checking algorithm overlap within each tuple: The overlap of a specified algorithm in the currently processed tuple with one used to provide a key share is leveraged as second priority level, and the overlap with a client supported algorithm for which no key share is available finally is used as third priority level.

If no selection could be made while processing a tuple, the next tuple is processed, and so on. If no selection is made after all tuples are processed, the server signals an alert back to the client and terminates the session establishment because the establishment of a common shared key is not possible due to lack of algorithmic overlap between the client and the server. As an example, the following list “ML-KEM-768 / X25519MLKEM768: SecP256r1MLKEM768 / x25519” defines three tuples with two algorithms in each tuple.

To illustrate the impact of the prefer mandate from CNSA 2.0, let’s assume that a client has used the above defined string “*ML_KEM-1024:ML-KEM-512:*x25519” when initiating the TLS session establishment via its ClientHello. The server starts processing its own list with its first tuple “ML-KEM-768.” It first checks whether there’s an overlap with ML-KEM-1024 for which the client sent a key share. As there is no such overlap, it then checks whether the supported algorithms overlap. As there is an overlap for the ML-KEM-512 algorithm, the server will initiate a HelloRetryRequest message, which will cause a network roundtrip penalty. The server does that even though a key share for x25519 would be readily available, theoretically allowing a session establishment without round-trip penalty. However, the prefer mandate of CNSA 2.0 enforces higher priority to the use of Q-safe algorithms, even if that comes at the cost of a round-trip penalty — which is completely achieved using the new specification syntax.

Final remarks

There were a couple of additional, minor challenges when implementing the code changes. For example, pseudo algorithm names like “DEFAULT” should be enabled to represent an entire list of — as the name implies — default algorithms. Also, the desired ability to use the same specification string on both the server and the client side required to filter (and ignore) key share defining prefix characters on the server side, as well as tuple limiting characters on the client side. Finally, processing a “?” prefix to allow a client or server to ignore unknown algorithm names had to be included as well.

The discussion thread to find an agreement on all the features described above and their implementation was long. There were 240 discussion posts for the pull request alone, predated by a similar number of posts during the initial discussion in GitHub Issues. The discussion was highly output oriented, and we want to explicitly acknowledge the excellent interactions with Tomáš Mráz and Matt Caswell from the OpenSSL maintainer team, as well as Viktor Dukhovni and Geert Hendrickx.

The OpenSSL version v3.5 includes these features by adding 1,862 lines of code in 16 files (which have a total of more than 30,000 lines), making it, to the best of our knowledge, the first TLS library to fully adhere to the CNSA 2.0 mandate to prefer Q-safe algorithms. Since this OpenSSL version has long-term support (LTS) status, it will be the version that Linux distributors include in their shipments sooner rather than later, making these new features widely accessible.