About the Complexity of Post Quantum Cryptography

In her recent article Roberta Faux wrote about "Navigating the Post-Quantum Cryptography Minefield" which is as usual very insightful.

In light of her article, I was asking myself: how complex are cryptographic implementations and how does the code base evolve over time?

To develop a quantitative feeling, let's count Source Lines Of Code (SLOC) as a measure of complexity. The subject of my interest is an Open Source implementation under active development and with a long history. That brought me to look at WolfSSL, a well-known SSL implementation with good reputation in the industry. To obtain the number of SLOC, I used a tool called SLOCCount and put everything in Excel. Below a graph, starting from the earliest available WolfSSL version v1.8.8.8 in February 2011 and taking a snapshot of the source code around February for every year up until 2024:

WolfSSL started with ~29.000 SLOC in 2011 and it took until 2018 to get close to 300.000 SLOC. After that, the SLOCcount continued to increase until 2020 just short of 800.000 SLOC - why? The WolfSSL Annual Report 2019 gives us a clue:

We delivered TLS 1.3 ahead of the market, MISRA-C cryptography for the automotive market, FIPS for our government consumers and DO-178 for avionics.

Looks like TLS 1.3 produces a much larger footprint in terms of SLOC than its predecessors. But let's not stop here. Starting from 2021, another 1 Million SLOC are added, reaching almost 1.8M SLOC today - why? The WolfSSL blog of June 2024 provides us with another clue:

We’ve done a lot to enable post quantum cryptography in our products over the last 3 years.

So what we observe is:

• 2017-2021 multiplied the SLOCCount by a factor of 5 which is correlated with the introduction of TLS 1.3
• 2021-2024 increased SLOCCount by ~1 Million SLOC which is correlated with the introduction PQC

For comparison, I was told that implementing [RFC8784] takes ~20.000 SLOC or a bit more than 1% of WolfSSL's total. Naturally, we need to take these observations with a pinch of salt: correlation is not causation and WolfSSL needs to consider lots of different hardware. However, the numbers rhyme well with Roberta Faux's finding:

Crystals-Kyber’s implementation is inherently more complex due to its reliance of advanced algebraic structures, its multidimensional polynomial arithmetic, and the need for structured noise in generating secure keys. The setup for secure, noise-based key exchanges in lattice cryptography adds layers of complexity in both conceptual understanding and implementation. All of this increases the code complexity for the post-quantum key exchange Crystals-Kyber / ML-KEM.

My2c:

• It took 10 years from 2011 to 2021 to mature TLS from TLS 1.1 to TLS 1.2 and now to TLS 1.3. This evolution came with an astonishing 26x increase in SLOCCount. It is scary to think that PQC could eventually follow the same trajectory (cross fingers it doesn't).
• If Evil-Eve is really keen to attack data protected with PQC, she probably can get by for many years with a digital computer exploiting implementation vulnerabilities in SSL's millions of lines of code.
• If 1 Million SLOC is the complexity-price to pay for PQC today, we should not trust in PQC alone. It's more than reasonable to develop a backstop using hybrid schemes. Leveraging [RFC8784] is one element in that strategy.