Why you should care about Kyber and the NIST
Something is rotten in the state of Denmark
On October 3rd, 2023, the prolific cryptographer Daniel J Bernstein (djb) posted a 17,000-word rant blog post criticizing what he saw as a blatant inconsistency in the NIST Post-Quantum Cryptography Standardization Project (NISTPQC) assessment of the submissions, namely in its assessment of Kyber-512.
The blog post quickly blew up online, with many folks scratching their heads with the content, wondering what was happening. I deeply respect djb, so I read the entire post from start to finish. While I agree that how it is written is unfortunate (especially for newcomers), the post's content is important and should be explored. So that is my goal here. I aim to provide some context to his post for those who might need help understanding the history of the author or the NIST and why what he is upset about is plausible and has a historical context.
A small note on my background.
I am not a cryptographer, but I have long held a deep interest in cryptography. I’ve dabbled in it in earnest since 2010 while working in the tech industry. In 2018, I began a journey to get a more formal education on the subject. I took the Stanford Online Cryptography I course by Dan Boneh. I wrote a weird little blockchain deadman’s switch experiment that same year. In 2019, I wrote a little experimental chat tool to play around with trust models. In 2022, I took Applied Cryptography, taught by Alexandra (Sasha) Boldyreva, in graduate school while working on my MS in CS at Georgia Tech in my spare time. So, while I do not have a Ph.D. in cryptography, I am also not completely ignorant. The more I learn about the subject, the more in awe I am of the discipline.
Who is djb to me?
DJB has been working in computers, security, mathematics, and cryptography for a long time. If you’ve generated an SSH key recently, you’ve probably used ed25519, a modern cryptographic algorithm he worked on with Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yanga. His work on NaCl includes the beautifully designed authenticated encryption of ChaCha20-Poly1305.
Daniel J Bernstein is part of a long tradition of adversarial hackers in cryptography. These folks understand how vital cryptography is for every human on earth and take a human-first approach to security and cryptography instead of a government-first approach. There is a rich history here that I can’t even begin to cover, but I’d recommend reading Steven Levy’s Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age.
I don’t think most folks realize how lucky we are that a few radical thinkers who rejected coercion from the NSA and other government agencies changed the course of history for everyone. Prolific contrarians like Whitfield Diffie and groups like the EFF, chaos communication club, the cypherpunks, and many others, shared ideas on mathematics, security thinking, hacking, and idealism that could bring to the world outside of coercion for concentrations of power (i.e., large corporations and governments). That last bit wasn’t just some crypto-anarchist rhetoric but a fundamental building block of strong cryptography. Any backdoor to a cryptographic system fundamentally breaks that system. Yet, centralized power, particularly government power, has sought to undermine this guarantee to serve its purposes since the beginning.
In 1995, the government tried to forbid djb from talking about and publishing the source code to an encryption algorithm he’d written. This led to him winning a case against the US government (represented by the EFF), which protected computer code and encryption algorithms from censorship by the government for all of us.
NIST and NSA’s rotten history together.
In the 1990s, NIST proposed DSA as an encryption standard without disclosing that the NSA had designed it. It was a fundamentally flawed algorithm that contained a backdoor.
In the early 2000s, a new type of encryption algorithm was being standardized by the NIST known as Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG). It was broken from day one, and the NSA knew it. The NSA reportedly secretly paid RSA Security 10 million dollars to make this new algorithm the default option in one of their libraries, and they worked closely with the NIST to rubber stamp the standard.
We learned much about their behaviors from the Snowden leaks. Amongst these leaks, we learned that the NSA had become the sole author of the Dual_EC_DRBG standard while working with the NIST. NIST responded by saying:
NIST would not deliberately weaken a cryptographic standard. We will continue in our mission to work with the cryptographic community to create the strongest possible encryption standards for the U.S. government and industry at large.
But it was clear that the NIST was lying, looked the other way, or was incompetent in their dealings with the NSA. At the very least, the NIST was not transparent in their dealings with the NSA, keeping much of their communication outside public scrutiny.
This gets us into a fundamentally flawed philosophy of NOBUS or “Nobody But Us.” It’s the operating belief of the NSA that they are not obligated to notify others of a vulnerability because no one but the NSA could exploit the issue. This sinister line of reasoning undermines our democracy and gives the unelected powers of the NSA a carte blanche excuse to misbehave. Of course, NOBUS falls apart quickly if the NSA gets hacked by China and they steal their tools.
The Kyber Rant
This gets us back to djb’s 17,000-word Kyber rant and the fear that we are experiencing deja vu when it comes to the behavior of the NIST.
The significant points in his post are:
NIST’s Misrepresented Memory Access Costs and Security Margin Calculations: djb challenges NIST's claim that Kyber-512 has a significant security margin over AES-128, arguing that this conclusion is based on flawed assumptions and overestimations. He gives the example that NIST argued that 240 plus 240 equals 280 when it actually equals 241.
NIST’s Lack of Transparency and Evasion of Clarification: This post highlights NIST's lack of transparency in their evaluation process and reluctance to clarify or correct errors, which impedes proper security review. For instance, in 2022, djb filed a FOIA request to discover if the NIST communicated with the NSA directly during the NISTPQC process, and the NIST stonewalled these efforts.
NIST’s Inconsistent and Questionable Methodology in Security Evaluation: The methodology and calculations used by NIST in evaluating the security level of cryptographic systems are questioned, with the author pointing out fundamental flaws and errors and using one standard for one submission and another for others.
When the main points outlined in the blog post are shown in the light of the historical behavior of both the NIST and NSA, djb’s observations seem damning and oddly familiar.
One of my favorite books, The Jakarta Method, explores the dark history of the CIA (I recommend everyone read it). The author, Vincent Bevins, did a series of interviews after the book came out and talked of CIA apologists who said, “Well, sure, the CIA did these rotten things in the past, but they don’t do that sort of thing anymore.” Bevins makes a striking point (I’m paraphrasing): Point to a moment in history where the CIA apologized for its actions and public reforms were taken. There aren’t any. If we have no evidence to demonstrate that a rotten institution was reformed, the only logical conclusion to reach is that the institution is as bad or worse today.
When did we ever hear an apology from the NIST in their interactions with the NSA? Why should we think that now is any different?
Notable Links
djb’s 2022 lawsuit against the NIST (and a fantastic history of the NSA and NIST)
djb and Tanja Lange speaking at CCC Dec 2022 on PQC
a breakdown of how to optimize go, containers, and the Linux scheduler
A pragmatic guide to dealing with generated files in version control (timely, because I’m currently doing this exact thing in a project)
I recently Subscribed to Wes Kao’s newsletter, and this post on rigorous thinking is excellent.
A fascinating look at “What If Gravity is NOT Quantum?”